开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 系统运维 -> C++STL之list的使用和模拟实现 -> 正文阅读

[系统运维]C++STL之list的使用和模拟实现

list

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

中文翻译：

list是序列式容器，允许在序列内的任何位置进行插入和删除操作，并且该容器可以前后双向迭代。

list容器在底层被实现为双向链表；双向链表中的每个元素存储在不同且不相关的存储位置。每个节点是通过与指向它前面元素的指针和指向它后面元素的指针进行关联的。

list与 forward_list 非常相似：主要区别在于 forward_list 对象是单链表，因此它们只能向前迭代，以让其更小更高效。

与其他序列式容器（array、vector和deque）相比，list通常在拥有迭代器的容器内任何位置插入、提取和移动元素方面表现更好

与这些其他序列容器相比，list 和 forward_lists 的主要缺点是它们无法直接访问元素的位置；例如，要访问列表中的第六个元素，必须从已知位置（如开头或结尾）迭代到该位置，这在这些位置之间的距离上需要线性时间。它们还消耗一些额外的内存来保存与每个元素相关联的信息

可以看到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有这样的构造函数：

它用来构造n个值为val的节点

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;

可以看到lt4已经赋值给了lt1

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

给list对象分配新的内容代替当前的内容，并且修改它的size

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一样会失效呢？**不知道迭代器失效问题可以看看这篇文章：

答案是不会，原因是list和vector的结构不同，vector因为底层是物理连续数组，插入时可能会扩容，导致野指针问题，不扩容，挪动数据也导致pos的意义遍历，而对于list，list的每一个节点不一定连续，插入时不需要挪动数据，insert后不会失效因为list是一个个独立的节点，这里在2的前面插入数据是插入新增的节点，pos还是指向2这个节点的，所以不会失效

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;
}

可以看到我们erase时不用一个迭代器来接收时报错了，原因是erase时这里pos会失效，因为pos指向的节点已经被释放了，出现野指针

当我们用pos来接收时：

这里说明了erase返回的迭代器是指向删除节点的下一个节点

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

进行list对象的交换

所有的容器进行交换，都尽量用库里面的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

传一个参数值，如果有的话删掉，没有的话不进行处理，从容器中移除所有等于 val 的元素。这会调用这些对象的析构函数，并通过移除的元素数量来减小容器大小。

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不一样，它的迭代器是用一个类去封装了节点的指针

迭代器的实现方式分析：

原生指针(天然的迭代器)，要求：原生指针指向的空间物理上是连续的，能正确的解引用，以及++，–等操作。比如string和vector

它还是原生指针(比如Node)，但是它指向的物理结构不连续(链表)，但是它不能满足解引用以及++，–等操作，所以需要用一个类去封装原生指针，重载相关运算符，让这个类的对象用起来像指针一样。比如list、map等。*

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

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;

是iterator就传T, T&, T*去实例化对象，是const_iterator就传T, const T&, const T*去实例化对象。

那么为什么要有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;
}

it->本质上是这样调用的it.operator->()，它返回一个结构体指针。本来这个调用应该是it->->_val，但是这里这样写，可读性太差了，所以编译器进行了特殊处理，省略了一个->，保持程序的可读性

vector迭代器和list迭代器比较

list迭代器：

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

vector迭代器：

typedef T* iterator;

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

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

list迭代器也是4个字节，因为它是一个自定义类型，他只有一个成员是指针，所以他也是4个字节，C++的类，运算符重载的能力让我们在用的角度我们感觉并没有什么区别

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;
}

注意clear的意思是清除所有有效数据，而头节点不会清除，这里需要注意的是在删除完之后，头节点的next需要更新为head，否则就会野指针

也可以直接复用：

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

erase会帮我们链接好最后删除完后仅剩的头节点

析构函数模拟实现

~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;
}