list

首先学习list，不妨我们先来看看文档中它是怎么说明的：

中文翻译：

可以看到list是模板，它可以接收任何类型。

list成员函数的使用

list的构造函数

list的构造函数如上：默认构造函数、迭代器构造函数等等，list有多种初始化的方式：

#include<iostream>
#include<list>
using namespace std;
void test_list1()
{
    list<int> lt1;
    list<int> lt2(10,5);
    list<int> lt3(lt2.begin(),lt2.end());
    vector<int> v={1,2,3,4,5};
    list<int> lt4(v.begin(),v.end());
}

list有这样的构造函数：

list<int> lt2(10,5);

list还有这样的构造函数：

它可以用一段迭代器区间来进行构造：

list<int> lt3(lt2.begin(),lt2.end());

可以用其他容器的迭代器区间进行构造：

vector<int> v = { 1,2,3,4,5 };
list<int> lt4(v.begin(), v.end());

list也支持赋值：

lt1 = lt4;

list的遍历方式

1、迭代器遍历

void test_list2()
{
    vector<int> v = { 1,2,3,4,5 };
	list<int> lt4(v.begin(), v.end());
    list<int>::iterator it4 = lt4.begin();
    while(it4!=lt4.end())
    {
        cout<<*it4<<" "<<endl;
        it4++;
    }
    cout<<endl;
}

2、范围for遍历：

void test_list3()
{
	vector<int> v = { 1,2,3,4,5 };
	list<int> lt4(v.begin(), v.end());
	for(auto e:lt4)
    {
        cout<<e<<" ";
    }
	cout << endl;
}

因为list不支持随机访问，所以不存在[]+下标进行遍历

assign

lt3.assign(5,3);//重新给值
for(auto e:lt3)
{
    cout<<e<<" ";
}
cout<<endl;

push_back和push_front

void test_list4()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    
    lt.push_front(10);
    lt.push_front(20);
    lt.push_front(30);
    lt.push_front(40);
    for(auto e:lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
}

pop_back和pop_front

void test_list5()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    
    lt.push_front(10);
    lt.push_front(20);
    lt.push_front(30);
    lt.push_front(40);
    for(auto e:lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
    
    lt.pop_back();//删除需要保证有数据
    lt.pop_back();
    lt.pop_back();
    lt.pop_back();
    lt.pop_front();
    for(auto e:lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
}

可以看到成功的进行了尾删和头删

insert

void test_list6()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    list<int>::iterator pos = find(lt.begin(),lt.end(),2);
    if(pos!=lt.end())
    {
        //找到
        lt.insert(pos,20);
    }
    //这里pos是否会失效呢？不会失效
    //原因是list和vector的结构不同
    //因为底层空间是物理连续数组。可能扩容，导致野指针问题，不扩容，挪动数据，也导致pos意义变了
    //list insert不会失效，因为list是一个个独立节点，2前面插入数据是新增节点，pos还是指向2这个节点的，所以不会失效
}

**有一个问题：这里的pos会不会像vector一样会失效呢？**不知道迭代器失效问题可以看看这篇文章：

erase

void test_list7()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    list<int>::iterator pos = find(lt.begin(),lt.end(),2);
    if(pos!=lt.end())
    {
        //找到
        lt.erase(pos);
    }
    //erase这里会失效，因为pos指向的节点已经被释放了，出现野指针
    cout<<*pos<<endl;
    *pos = 100;
}

当我们用pos来接收时：

clear

void test_list8()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
    lt.clear();
}

那么我们知道list是带头双向循环链表，那么头节点被删除了吗？

答案是没有，我们看下面的测试：

void test_list8()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
    lt.clear();
    //但是头节点没有清，还可以插入
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;   
}

swap

void test_list9()
{
	list<int> lt;
	list<int> lt1;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt1.push_back(10);
	lt1.push_back(20);
	lt1.push_back(30);
	lt1.push_back(40);
	lt.swap(lt1);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
}

还有一个算法中的swap：

lt.swap(lt1);
swap(lt,lt1);//尽量不要用这个
//对于C++98版本，交换效果一样，但是效率不一样
//vector/string容器也类似

我们尽量不要用这个算法中的swap函数，对于C++98版本，这两个交换函数交换效果一样，但是效率不一样，vector/string容器也类似，为什么呢？因为它是深拷贝式的交换：

而list类成员函数中的swap，只是交换指针(成员变量)就可以了，故两个容器要交换，尽量使用容器自己的swap，不要使用库函数的swap

sort

void test_list10()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(30);
    lt.push_back(4);
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
    lt.sort();
    for(auto e : lt)
    {
        cout<<e<<" ";
    }//默认排升序
    //排降序
    greater<int> g;
    lt.sort(g);
    cout<<endl;
}

可以看到已经排好序，但是list里的sort效率低，一般很少用

效率测试对比：

void testOP()
{
    srand(time(0));
    const int N = 10000;
    list<int> lt;
    vector<int> v;
    resize(N);
    for (int i = 0; i < N; ++i)
    {
        v[i] = rand();
        lt.push_back(v[i]);
    }
    int begin1 = clock();
    sort(v.begin(), v.end());
    int end1 = clock();
    
    int begin2 = cLock();
    lt.sort();
    //sort(lt.begin(),lt.end())//error
    int end2 = clock();
    cout << "vector sort" << end1 - begin1 << endl;
    cout << "list sort" << end2 - begin2 s<< endl;
}

unique

即**”删除”序列中所有相邻的重复元素(只保留一个)。此处的删除，并不是真的删除，而是指重复元素的位置被不重复的元素给占领了(详细情况，下面会讲)。由于它”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序。**

void test_list11()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(1);
    lt.push_back(4);
    lt.push_back(30);
    lt.push_back(4);
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
    lt.sort();
    lt.unique();//去重
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
}

remove

void test_list12()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.remove(2);
	lt.remove(4);

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

容器的迭代器的分类

**使用功能的角度：**正向、反向、const正向、const反向

容器底层结构的角度：

单链表迭代器/哈希表迭代器是单向，只能用++

双向链表迭代器/map迭代器是双向，它们能++/–

string/vector/deque迭代器/map迭代器是随机，支持随机访问，它们能用++/–/+/-等

struct input iterator taa {};//只写迭代器
struct output iterator taa {};//只读迭代器
struct forward iterator tag : public input iterator tag {};//单向迭代器
struct bidirectional_iterator_tag : public forward iterator tag {};//双向迭代器
struct random access_iterator_tag : public bidirectional iterator_tag {};//随机迭代器

可以看到继承关系，单向迭代器也是只写迭代器，双向迭代器也是单向迭代器，随机迭代器也是双向迭代器

sort要用需要满足随机迭代器才能使用：

reverse要满足是双向链表迭代器才能使用：

容器算法迭代器之间的关系

list的模拟实现

首先我们实现链表节点的结构，链表节点也是一个模板类：

template<class T>
struct __list_node
{
    __list_node<T>* _next;
    __list_node<T>* _prev;
    T _data;
    __list_node(const T& x = T())//默认构造函数，传参也可以调用
        :_next(nullptr)
        ,_prev(nullptr)
        ,_data(x)
    {}
};

list模板类的底层是什么呢？成员变量是什么呢？我们一起来看看：

list的成员变量是头节点，通过节点的结构可以知道我们实现的是带头循环双向链表：

template<class T>
class list
{
    typedef __list_node Node;
public:
    list()
    {
        _head = new Node;
        _head->_next = _head;
        _head->prev = _head;
    }
private:
    Node* _head;
};

list的迭代器怎么实现的呢？list迭代器不仅仅是指针，和vector和string不一样，它的迭代器是用一个类去封装了节点的指针

迭代器的实现方式分析：

迭代器的本质是：不破坏容器封装的情况，屏蔽底层结构差异，提供统一的方式去访问容器

list迭代器的实现

template<class T>
struct __list_iterator
{
	typedef __list_node<T> Node;
    typedef __list_iterator<T> self;//为了方便将类类型typedef成self
    Node* _node;//指向节点的指针
    
    __list_iterator(Node* node)
        :_node(node)
    {}
    //*it ->it.operator*()
    //*it = 10//需要可以写，所以返回引用
    T& operator*()
    {
        return _node->data;
    }
    //++it -> it.operator++()
    self& operator++()
    {
        _node = _node->_next;
        return *this;
    }
    //++it -> it.operator++(0)
    self operator++(int)
    {
        __list_iterator<T> tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    
    self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }
    //--it -> it.operator--(0)
    self operator--(int)
    {
        __list_iterator<T> tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    //!=
    bool operator!=(self& it)
    {
        return _node!=it._node;
    }
    bool operator==(self& it)
    {
        return _node==it._node;
    }   
};

有一个问题？我们要不要写拷贝构造和赋值重载、析构函数

list<int>::iterator it = lt.begin();

const对象一般需要const迭代器，例如下面代码：

void print_list(const list<int>& lt)
{
    list<int>::iterator it = lt.begin();
    while(it != lt.end())
    {
        cout<<*it<<" ";
    }
    cout<<endl;
}

这里就不能用了，因为lt是const对象，const对象需要提供const迭代器:

void print_list(const list<int>& lt)
{
    list<int>::const_iterator it = lt.begin();
    while(it != lt.end())
    {
        cout<<*it<<" ";
    }
    cout<<endl;
}

那么我们就重新再写个const迭代器的类：

template<class T>
struct __list_const_iterator
{
	typedef __list_node<T> Node;
    typedef __list_const_iterator<T> self;
    Node* _node;//指向节点的指针
    
    __list_iterator(Node* node)
        :_node(node)
    {}
    //*it ->it.operator*()
    //*it = 10//需要可以写，所以返回引用
    const T& operator*()
    {
        return _node->data;
    }
    //++it -> it.operator++()
    self& operator++()
    {
        _node = _node->_next;
        return *this;
    }
    //++it -> it.operator++(0)
    self operator++(int)
    {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    
    self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }
    //--it -> it.operator--(0)
    self operator--(int)
    {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    //!=
    bool operator!=(const self& it)const
    {
        return _node!=it._node;
    }
    bool operator==(const self& it)const
    {
        return _node==it._node;
    }   
};

const迭代器只需要将*运算符重载的返回值改为const即可，让他不能写，我们发现普通迭代器和const迭代器代码有好多相同的部分，都是微改，那么我们有没有办法可不可以只写一个类模板呢？

答案是可以的，我们可以增加模板参数，Ref(自引用)，Ptr(结构体指针)，为什么添加Ptr我们下面会说：

list迭代器和const迭代器模拟实现

template<class T,class Ref,class Ptr>
struct __list_iterator
{
	typedef __list_node<T> Node;
    typedef __list_iterator<T,Ref,Ptr> self;
    Node* _node;//指向节点的指针
    
    __list_iterator(Node* node)
        :_node(node)
    {}
    //*it ->it.operator*()
    //*it = 10//需要可以写，所以返回引用
    Ref operator*()
    {
        return _node->data;
    }
    //++it -> it.operator++()
    self& operator++()
    {
        _node = _node->_next;
        return *this;
    }
    //++it -> it.operator++(0)
    self operator++(int)
    {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    
    self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }
    //--it -> it.operator--(0)
    self operator--(int)
    {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    //!=
    bool operator!=(const self& it)const
    {
        return _node!=it._node;
    }
    bool operator==(const self& it)const
    {
        return _node==it._node;
    }   
};
template<class T>
class list
{
	typedef __list_node<T> Node;
public:
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;
    iterator begin()
    {
        return iterator(_head->next);
    }
    iterator e()
    {
        return iterator(_head->prev);
    }
    const_iterator begin()const
    {
        return const_iterator(_head->next);
    }
    const_iterator end()const
    {
        return const_iterator(_head);
    }
    list()
    {
        _head = new Node;
        _head->_next = _head;
        _head->prev = _head;
    }
private:
    Node* _head;
};

可以看到我们进行了显式实例化：

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
iterator it;

那么为什么要有T*呢？

struct TreeNode
{
    struct TreeNode* _left;
    struct TreeNode* _right;
    int _val;
    TreeNode(int val)
        :_left(nullptr)
        ,_right(nullptr)
        ,_val(val)
        {}
};

void test_list2()
{
    list<TreeNode> lt;
    lt.push_back(TreeNode(1));
    lt.push_back(TreeNode(2));
    lt.push_back(TreeNode(3));
    lt.push_back(TreeNode(4));
    list<TreeNode>::iterator it = lt.begin();//it现在指向的是结构体
    while(it != lt.end())
    {
        cout<<*it<<" ";
        ++it;
    }
    cout<<endl;
}

这里编译不过：

为什么会报错呢？我们分析一下，TreeNode是一个自定义类型，相当于这里的T：

typedef __list_iterator<T, T&, T*> iterator;

将TreeNode传过去，T为TreeNode，我们解引用it时，这里返回的是TreeNode，返回的是一个结构体对象，那么我们当然不能对它解引用了打印了，除非我们在TreeNode里面实现<<运算符重载

ostream operator<<(ostream& out,TreeNode n);

不实现这个重载我们只能这样访问：

cout<<(*it)._val<<" ";

那么我们能不能这样访问呢？

cout<<it->_val<<" ";

现在还不可以，it是一个结构体(迭代器)对象，不能够支持这样，对于内置类型的指针：int* p，我们取数据用p，对应自定义类型指针TreeNode p ，我们取数据用p->_val

所以我们需要给迭代器重载->运算符：

Ptr operator->()
{
    return &_node->_data;//这里的_data相当于是TreeNode，
}

下面我们测试一下：

void test_list2()
{
    list<TreeNode> lt;
    lt.push_back(TreeNode(1));
    lt.push_back(TreeNode(2));
    lt.push_back(TreeNode(3));
    lt.push_back(TreeNode(4));
    list<TreeNode>::iterator it = lt.begin();//it现在指向的是结构体
    while(it != lt.end())
    {
        
        //cout<<(*it)._val<<" ";
        //假设打印这三个
        //printf("val:%d,left:%p,right:%p\n",(*it)._val,(*it)._left,(*it)._right);
        printf("val:%d,left:%p,right:%p\n",it->_val,it->_left,it->_right);
       	
        ++it;
    }
    cout<<endl;
}

vector迭代器和list迭代器比较

list迭代器：

typedef __list_iterator<T,T&,T*> iterator;

vector迭代器：

typedef T* iterator;

在逻辑上感觉list比vector更复杂，但在物理上它们并没有什么区别。

vector迭代器是原生指针，它的大小为4个字节，那么list迭代器呢？

push_back模拟实现

void push_back(const T& x)
{
	Node* tail = _head->_prev;
	Node* newnode = new Node(x);

	newnode->_next = _head;
	newnode->_prev = tail;
	tail->_next = newnode;
	_head->_prev = newnode;
}

代码测试：

push_front模拟实现

void push_front(const T& x)
{
    Node* next = _head->_next;
    Node* newnode = new Node(x);
    
    newnode->_next = next;
    newnode->_prev = _head;
    _head->_next = newnode;
    next->_prev = newnode;
}

代码测试：

insert模拟实现

iterator insert(iterator pos, const T& x)
{
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* newnode = new Node(x);
    
    newnode->_next = cur;
    cur->_prev = newnode;
    prev->_next = newnode;
    newnode->_prev = prev;
    
    return iterator(newnode);
}

erase模拟实现

//类模板中的成员函数是按需实例化，调用了哪个成员函数，实例化哪一个
//成员函数是函数模板
iterator erase(iterator pos)
{
    assert(pos != end())
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    
    prev->_next = next;
    next->_prev = prev;
    delete cur;
    return iterator(next);
}

pop_back模拟实现

复用erase：

void pop_back()
{
    erase(--end());       
}

pop_front模拟实现

复用erase：

void pop_front()
{
    erase(begin());
}

push_back和push_front也都可以复用insert：

void push_back(const T& x)
{
    insert(end(),x);
}

void push_front(const T& x)
{
    insert(begin(),x);
}

size模拟实现

size_t size()
{
    size_t n=0;
    iterator it = begin();
    while(it!=end())
    {
        it++;
        n++;
    }
    return n;
}

empty模拟实现

bool empty()
{
    return begin()==end();
    //如果begin等于end就是链表为空的时候
}

clear模拟实现

void clear()
{
    iterator it = begin();
    while(it!=end())
    {
        Node* del = it->_node;
        ++it;
        delete del;
    }
    _head-_next = _head;
}

也可以直接复用：

void clear()
{
    iterator it = begin();
    while(it!=end())
    {
        it = erase(it);
    }
}

析构函数模拟实现

~list()
{
    clear();
    delete _head;
    _head = nullptr;
}

拷贝构造模拟实现

void test_list4()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    list<int> lt1(lt);
}

同样的list也有拷贝构造函数：

拷贝构造传统写法

//lt2(lt1)
list(const list<T>& lt)
{
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    for(const auto& e:lt)
    {
        push_back(e);
    }
}

拷贝构造现代写法

//lt2(lt1)
template<class InputIterator,class InputIterator>
list(InputIterator first,InputIterator last)
{
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    while(first!=last)
    {
        push_back(*first);
        ++first;
    }
}
list(const list<T>& lt)
{
    this->_head = new Node;//这里需要给lt2头节点，不然lt2的_head指向的空间都没有创建，_head是空指针，swap会出问题
    _head->_next = _head;
    _head->_prev = _head;
    
    list<T> tmp(lt.begin(),lt.end());
    std::swap(_head,tmp._head);//tmp函数调用结束会销毁
    //这里不能这样交换：
    //swap(lt,tmp);
    //因为swap的底层实现用到了拷贝构造函数，我们正在写的就是拷贝构造函数，这里就会出问题
}

operator=模拟实现

赋值重载传统写法

//lt1 = lt4 传统写法
list<T>& operator=(const list<T>& lt)
{
    if(this!=&lt)
    {
        clear();
        for(const auto& e:lt)
        {
            push_back(e);
        }
    }
}

赋值重载现代写法

list<T>& operator=(list<T> lt)
{
    swap(_head,lt._head);
    return *this;
}

list模拟实现完整代码：

#include<iostream>
#include<vector>
#include<stdio.h>
#include<assert.h>
using namespace std;
namespace Z
{
	template<class T>
	struct __list_node
	{
		__list_node<T>* _next;
		__list_node<T>* _prev;
		T _data;
		//默认构造函数
		__list_node(const T& x = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}

	};
	//迭代器类
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef __list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;
		__list_iterator(Node* node)
			:_node(node)
		{}
		//*it->it.operator*()
		T& operator*()//这里需要返回引用，*it = 1;当做这样的操作时需要能够写
		{
			return _node->_data;
		}
		Ptr operator->()//这里需要返回引用，*it = 1;当做这样的操作时需要能够写
		{
			return &_node->_data;
		}
		//operator->()
		//{

		//}
		self& operator++()//前置++,返回引用减少拷贝构造
		{
			_node = _node->_next;
			return *this;
		}
		self operator++(int)//后置++，不能返回引用，因为tmp出了作用域就销毁了
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self& operator--()//前置--,返回引用减少拷贝构造
		{
			_node = _node->_prev;
			return *this;
		}
		self operator--(int)//后置--，不能返回引用，因为tmp出了作用域就销毁了
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		bool operator==(const self& it)
		{
			return _node == it._node;
		}
		bool operator!=(const self& it)
		{
			return _node != it._node;
		}
	};
	template<class T>
	class list
	{
		typedef __list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		//默认构造函数
		list()
		{
			//带头双向链表
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		//lt2(lt1)
		//传统拷贝构造
		//list(const list<T>& lt)
		//{
		// _head = new Node;
		// _head->_next = _head;
		// _head->_prev = _head;
		// for (const auto& e : lt)
		// {
		// push_back(e);
		// }
		//}
		//现代拷贝构造
		//迭代器构造函数
		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		//lt2(lt1)
		//拷贝构造现代写法
		list(const list<T>& lt)
		{
			//this->_head = new Node;//这里需要给lt2创建头节点，不然lt2的_head是空指针，swap会出问题
			//_head->_next = _head;
			//_head->_prev = _head;
			list<T> tmp(lt.begin(), lt.end());
			std::swap(_head, tmp._head);
		}
		//赋值重载传统写法
		list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				//不是相同的对象就交换
				clear();
				for (const auto& e : lt)
				{
					push_back(e);
				}
			}
		}
		//赋值重载现代写法
		list<T>& operator=(list<T> lt)
		{
			swap(_head, lt._head);
			return *this;
		}
		迭代器的模拟实现
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end()const
		{
			return const_iterator(_head);
		}
		void push_back(const T& x)
		{
			Node* tail = _head->_prev;
			Node* newnode = new Node(x);

			newnode->_next = _head;
			newnode->_prev = tail;
			tail->_next = newnode;
			_head->_prev = newnode;
		}
		void push_front(const T& x)
		{
			Node* next = _head->_next;
			Node* newnode = new Node(x);

			newnode->_next = next;
			newnode->_prev = _head;
			next->_prev = newnode;
			_head->_next = newnode;
		}
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

			newnode->_next = cur;
			cur->_prev = newnode;
			prev->_next = newnode;
			newnode->_prev = prev;

			return iterator(newnode);
		}
		//类模板中的成员函数是按需实例化，调用了哪个成员函数，实例化哪一个
//成员函数是函数模板
		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;
			delete cur;
			return iterator(next);
		}
		size_t size()
		{
			size_t n = 0;
			iterator it = begin();
			while (it != end())
			{
				it++;
				n++;
			}
			return n;
		}
		bool empty()
		{
			return begin() == end();
			//如果begin等于end就是链表为空的时候
		}
		/*void clear() { iterator it = begin(); while (it != end()) { Node* del = it->_node; ++it; delete del; } _head - _next = _head; }*/
		//可以复用
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

	private:
		Node* _head;
	};
	struct TreeNode
	{
		struct TreeNode* _left;
		struct TreeNode* _right;
		int _val;
		TreeNode(int val = -1)
			:_left(nullptr)
			, _right(nullptr)
			, _val(val)
		{}
	};
	//ostream operator<<(ostream& out,TreeNode n);
	void test_list1()
	{
		Z::list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_front(10);
		lt.push_front(20);
		lt.push_front(30);
		lt.push_front(40);
		list<int> lt1(lt);
		list<int>::iterator it = lt1.begin();
		while (it != lt1.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;
	}
	void test_list2()
	{
		Z::list<TreeNode> lt;
		lt.push_back(TreeNode(1));
		lt.push_back(TreeNode(2));
		lt.push_back(TreeNode(3));
		lt.push_back(TreeNode(4));
		list<TreeNode>::iterator it = lt.begin();//it现在指向的是结构体
		while (it != lt.end())
		{
			//cout<<*it<<" ";
			//cout << (*it)._val << " ";
			//假设打印这三个
			//printf("val:%d,left:%p,right:%p\n", (*it)._val, (*it)._left, (*it)._right);
			printf("val:%d,left:%p,right:%p\n", it->_val, it->_left, it->_right);
			++it;
		}
		cout << endl;
	}
}
int main()
{
	Z::test_list1();
	return 0;
}