C++基础 [八] - list的使用与模拟实现

目录

list的介绍

List的迭代器失效问题

List中sort的效率测试

list 容器的模拟实现思想

模块分析

作用分析

list_node类设计 

list 的迭代器类设计

迭代器类--存在的意义

迭代器类--模拟实现

模板参数 和 成员变量

构造函数 

* 运算符的重载

++运算符的重载  

 -- 运算符的重载

 重载 != 和 ==

 -> 运算符的重载 

list 结构的完善

默认成员函数

构造函数

拷贝构造 

迭代器区间构造  

n个相同元素构造  

赋值重载 

析构函数 

迭代器相关函数

begin 和 end  

访问容器相关函数

fron 和 back 

增删改查相关函数

insert

earse 

push_back 和 pop_back

push_front 和 pop_front

容量相关函数

size

resize 

empty

clear

list 容器的模拟实现整体代码

list.h 

list.cpp

---

list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素

List的迭代器失效问题

我们之前学习vector的时候，知道了insert和erase都有可能存在迭代器失效的问题，那list会出现这种情况吗？？下面来进行分析

insert插入新节点的迭代器，因此insert不可能会出现失效的问题。

 而earse必然会失效，因为该迭代器对应的节点被删除了。如果我们想继续用的话，就得利用返回值去更新迭代器，返回值是被删除元素的下一个位置的迭代器。

List中sort的效率测试

void test_op()
{srand((unsigned int)time(NULL));const int N = 1000000;vector<int> v;v.reserve(N);list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){int e = rand();lt1.push_back(e);lt2.push_back(e);}// 拷贝到vector排序，排完以后再拷贝回来int begin1 = clock();for (auto e : lt1){v.push_back(e);}sort(v.begin(), v.end());size_t i = 0;for (auto& e : lt1){e = v[i++];}int end1 = clock();//list调用自己的sortint begin2 = clock();lt2.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}

会发现哪怕我先拷贝到vector排完再拷贝回去效率都比list的sort效率高，所以list的sort实际中意义不是很大！！

list 容器的模拟实现思想

模块分析

根据 list 容器图可以分析一下 模拟实现 list容器 都要准备什么？

• 存储元素需要结点--->结点类
• 使用迭代器访问结点--->迭代器类
• 总体--->list类

作用分析

节点类

作用：存储 list容器 的元素，因为list里面要存储各种类型的元素，所以结点类需要定义成模版。结点类中的成员变量则是有三个，分别是：指向前一个结点的_prev指针，指向后一个结点的_next指针，存储结点元素的_data变量。

迭代器类 

• 此时大家可以思考这样一个问题，在模拟实现vector类时，我们是直接用结点指针作为迭代器来使用的，并没有自己实现迭代器类。list中为什么需要单独实现迭代器类？

原因：如上图所示。vector容器是数组，它的空间是连续的，所以结点指针完全可以通过自增的方式来指向下一个结点。可是list容器是链表，它的空间并不连续，自然不可能直接通过结点指针的自增来指向下一个链表结点，所以我们才需要自己实现迭代器类，并且重载自增与自减运算符，这样就可以通过迭代器的自增或自减来指向前后结点了。 

list类

 

 作用：实现链表各项功能的类，为主要部分 

list_node类设计 

list本身 和 list的结点 是两个不同的结构，需要分开设计。以下是list的节点结构

首先，我们在自己的命名空间内模拟实现 list（为了防止与库冲突），上面的代码就是list节点的结构。在这里并没有使用 class，因为 struct 默认访问权限是 public，又因为节点是需要经常访问的，所以使用struct更好。但是此结构体非C语言的结构体，已经是类了

list 的迭代器类设计

迭代器类--存在的意义

之前 模拟实现 string 和 vector 时都没有说要实现一个迭代器类，为什么实现list的时候就需要实现一个迭代器类了呢？

因为 string 和 vector 对象都将其数据存储在了一块连续的内存空间，我们通过指针进行自增、自减以及解引用等操作，就可以对相应位置的数据进行一系列操作，因此string和vector当中的迭代器就是原生指针。

但是对于 list 来说，其各个结点在内存当中的位置是随机的，并不是连续的，我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作。

•  而迭代器的意义就是，让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问。
• 既然 list 的结点指针的行为不满足迭代器定义，那么我们可以对这个结点指针进行封装，对结点指针的各种运算符操作进行重载，使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。例如，当你使用 list 当中的迭代器进行自增操作时，实际上执行了p = p->next语句，只是你不知道而已。

迭代器类--模拟实现

模板参数 和 成员变量

我们知道指针有两种const形势，一种是const T* ptr1;另一种是T* const  ptr2，那我们的const的迭代器是哪一种呢？

我们知道const迭代器是可以++的，它只是限制内容不能修改，但是它指针本身是可以++的。所以肯定是const T* prt1这种形式。T* const  ptr2的const本身修饰的是指针不能修改的

typedef const  _list_iterator<T> const_iterator;那我们这样写能行吗？

不行的，这样就是迭代器本身不能修改了。我们要的是它指向的内容不能修改的，那该怎么办呢？

我们只需要让它重载的*加上const就可以了 const T& operator*() 这样当调用*的时候，就会提示不能修改内容了。

但是这样设计太臃肿了。我们发现const_iterator和普通的iterator只有operator*()的返回值不一样

那我们能不能通过一个类型去控制这个返回值呢？肯定是可以的，我们可以增加个模板参数

template<class T, class Ref, class Ptr>

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;

我们知道一个类模板给两个不同的参数就是两个类 

• 这里我们就可以看出，迭代器类 的模板参数列表当中的 Ref 和 Ptr 分别代表的是 引用类型（T&） 和 指针类型（T *）。 
• 当我们使用 普通迭代器 时，编译器就会实例化出一个 普通迭代器 对象；当我们使用 const迭代器时，编译器就会实例化出一个 const迭代器对象。 
• 若该迭代器类不设计三个模板参数，那么就不能很好的区分-- 普通迭代器 和-- const迭代器。 

---

 因为 结点类 和 迭代器类 自身的类型名太长，写起来太麻烦，所以我们用 typedef关键字 给这两个类型取了别名。

我们为 结点类 的类型取的别名是 Node，为 迭代器类 取的别名是 Self。

template<typename T, typename Ref, typename Ptr>
struct _list_iterator 
{typedef ListNode<T> Node;                //为结点类取别名typedef _list_iterator<T, Ref, Ptr> self;  //为正向迭代器类取别名//成员变量Node* _node;                             //指向结点的指针
}

看这个代码 list<int>::iterator it = lt.begin(); 这里会发生拷贝构造，因为我们没有自己写，所以编译器会调用默认拷贝构造。对于自定义类型的默认拷贝构造是值拷贝(浅拷贝)。那会有问题吗？

答案是否定的，我们要的就是浅拷贝。对于 迭代器 来说，浅拷贝通常是完全合适的，因为：

• 迭代器本身只是容器中的一个元素的访问者，它并不拥有实际的容器数据。它只是持有容器中元素的位置（指针或类似机制），而不直接管理数据。
• 所以拷贝一个迭代器通常不会影响容器的所有权或内存的生命周期，因为它只是一个指向容器的指针，拷贝它只是创建一个新的指针来访问同样的容器数据。
• 容器本身会负责管理数据，迭代器只需要能够访问和遍历这些数据，所以浅拷贝是安全且有效的。

那为什么it和begin()都指向了第一个节点，不崩溃呢？

这个时候我们就要想想值拷贝崩溃的原因是什么了。以前我们了解到值拷贝崩溃的原因是进行了两次析构。但是迭代器我们没写析构函数呀。因为这个节点不是属于迭代器的，迭代器不是要做管理节点的工作，它只是访问节点 

构造函数 

迭代器类 实际上就是对 结点指针进行了封装，其成员变量就只有一个，那就是结点指针，其构造函数直接根据所给结点指针构造一个迭代器对象即可。

//正向迭代器构造函数
_list_iterator(Node* node = nullptr)       // 默认构造函数:_node(node){}

* 运算符的重载

当我们使用 解引用操作符 时，是想得到该位置的数据内容。因此，我们直接返回当前结点指针所指结点的数据即可，但是这里需要使用引用返回，因为解引用后可能需要对数据进行修改。

//重载*
//返回迭代器指向的结点的值域// T& operator*()Ref operator*() 
{return _node->_data;
}

++运算符的重载  

自增运算符的 重载 是迭代器类的核心。前置++重载中，要让当前迭代器指向下一个结点后，再把迭代器返回。后置++中是把当前迭代器用临时变量保存一份，再把迭代器指向下一个结点，然后返回临时变量。注意：重载后置++或后置--时，必须在函数参数列表加一个int变量，这是语法规定。

• 重载前置++ 和 后置++ 时的返回值有所不同，前置++返回值类型是--------迭代器类型的引用，而后置++返回值类型是------ 迭代器类型。
• 前置++中，返回的是对 this 的解引用，this并不是局部变量，函数结束后依然存在，所以可以返回它的引用，减少值拷贝次数。
• 后置++中，返回的 temp 是函数中创建的局部对象，在函数结束后会被销毁，所以返回值类型不可以是引用。这里就必须通过值拷贝来返回值。

//重载前置++
//返回迭代器对象自身的引用
//因为对象自身并不是该函数中的局部对象self& operator++() 
{_node = _node->_next;return *this;
}

//重载后置++
//此时需要返回temp对象，而不是引用
//因为temp对象是局部的对象
//函数结束后就被释放self operator++(int a) 
{self temp(*this);_node = _node->_next;return temp;
}

 -- 运算符的重载

前置--和后置--关于函数的返回类型跟重载++类似，这里就不再赘述。

 //重载前置--
self& operator--() 
{_node = _node->_prev;return *this;
}

//重载后置--
self operator--(int a) 
{self temp(*this);_node = _node->_prev;return temp;
}

 重载 != 和 ==

这里只需要比较_node是否相同即可，因为_node本身就是指向结点的指针，保存着结点的地址，只要地址相同，那自然就是同一个结点了

//重载!=
bool operator!=(const self& s)const 
{return _node != s._node;
}//重载==
bool operator==(const self& s)const 
{return _node == s._node;
}

 -> 运算符的重载 

   有时候，实例化的模板参数是自定义类型，我们想要像 指针 一样访问访问自定义类型力的成员变量，这样显得更通俗易懂，所以就要重载 -> 运算符，它的返回值是 T* 

想想如下场景： 

当 list容器 当中的每个结点存储的不是内置类型，而是自定义类型，例如数据存储类，那么当我们拿到一个位置的迭代器时，我们可能会使用 ->运算符访问 Data 的成员： 

struct Data
{Data(int a = int(), double b = double(), char c = char()):_a(a), _b(b), _c(c){}int _a;double _b;char _c;
};void TestList()
{list<Data> lt;lt.push_back(Data(1, 2.2, 'A'));auto it = lt.begin();cout << (*it)._a << endl;	//不使用 operator->() 比较别扭cout << it.operator->()->_b << endl;	//这种写法是真实调用情况cout << it->_c << endl;	//编译器直接优化为 it->
}int main()
{TestList();return 0;
}

list 结构的完善

成员变量和模板参数

• 因为 list 可以存储各种类型的元素，因此 list 类要设置为模板，T就是存储的元素的类型。
• 因为 结点类 和 迭代器类 的类名太长，所以用 typedef 关键为它们取了别名。这里迭代器的三个参数之所以设置为<T , T& , T*>，是因为list类只给出了一个模板参数，而迭代器类应该有三个，因此用 T& 和 T* 作为另外两个参数。

//带头结点的双向链表
template<class T>
class list 
{typedef ListNode<T> Node;
public:typedef _list_iterator<T, T&, T*> Iterator;                   //正向迭代器typedef _list_iterator<T, const T&, const T*> const_iterator;
private:Node* _head;              //指向头结点的指针
}

默认成员函数

构造函数

list 的成员变量是 一个节点类，在构造头节点时，需要将这单个头节点构造成一个双向循环链表；

//构造函数
list()
{_head = new Node;     //new一个节点出来_head->_prev = _head; _head->_next = _head; //_prev 和 _next 同时指向了头结点，形成了双向循链表
}

拷贝构造 

拷贝构造是用一个已有对象去构造出另一个对象，首先将待构造对象进行初始化，然后利用迭代器区间去构造一个和 lt1 一样的临时的 tmp 对象，再进行数据的交换，达到深拷贝的目的。  

//拷贝构造 --- 现代写法 lt2(lt1)
list(const list<T>& lt)
{_head = new Node;_head->_prev = _head;_head->_next = _head;list<T> tmp(lt.begin(), lt.end());std::swap(_head, tmp._head);
}

迭代器区间构造  

由于list可以存储各种类型的元素，所以区间构造时自然也会用到各种类型的迭代器，因此区间构造也应该定义为模版，需要给出模版参数列表。具体实现和上一个函数是差不多的。

//迭代器区间构造
template<class iterator>
list(iterator first, iterator last)
{_head = new Node;_head->_prev = _head;_head->_next = _head;while (first != last){push_back(*first);//尾插数据，会根据不同类型的迭代器进行调用++first;}
}

n个相同元素构造  

通过用 n 个 val 来对对象进行初始化，需要注意这里的 T( )是一个匿名对象，作为 val 的缺省参数，因为我们并不知道传给val的是一个对象还是一个整形（或其他），给缺省参数的好处在于，对于自定义类型编译器会去调用自定义类型的构造函数来对val进行初始化，如果是内置类型，它也是有自己的构造函数

//用n个val个构造      			   
list(int n, const T& val = T())        			   
{												   _head = new Node;_head->_prev = _head;_head->_next = _head;for (int i = 0; i < n; i++){push_back(val);}
}

赋值重载 

将赋值运算符重载的参数定义为 list 类型的对象而不是对象的引用，传参时会发生值拷贝。因此我们可以把 list对象 的 this指针 和 拷贝出来的参数 L 指向头结点的指针交换，这样 this指针 就直接指向了拷贝出来的L的头结点。L则指向了list对象的头结点，在函数结束后，作为局部对象的L将被销毁，它指向的空间也会被释放。

//传统写法
list<T>& operator=(const list<T>& lt)
{if (this != &lt) //避免自己给自己赋值{clear(); //清空容器for (const auto& e : lt){push_back(e); //将容器lt当中的数据一个个尾插到链表后面}}return *this; //支持连续赋值
}

析构函数 

对对象进行析构时，首先调用clear函数清理容器当中的数据，然后将头结点释放，最后将头指针置空即可。

//析构函数
~list()
{clear(); //清理容器delete _head; //释放头结点_head = nullptr; //头指针置空
}

迭代器相关函数

begin 和 end  

首先我们应该明确的是：begin 函数返回的是第一个有效数据的迭代器，end函数返回的是最后一个有效数据的下一个位置的迭代器。

对于 list 这个 带头双向循环链表 来说，其第一个有效数据的迭代器就是使用头结点后一个结点的地址构造出来的迭代器，而其最后一个有效数据的下一个位置的迭代器就是使用头结点的地址构造出来的迭代器。（最后一个结点的下一个结点就是头结点）

iterator begin()
{//返回使用头结点后一个结点的地址构造出来的普通迭代器return iterator(_head->_next); //这里也可以是隐式类型转换
}
iterator end()
{//返回使用头结点的地址构造出来的普通迭代器return iterator(_head);
}

• 当然，还需要重载一对用于 const对象 的 begin函数 和 end函数。

const_iterator begin() const
{//返回使用头结点后一个结点的地址构造出来的const迭代器return const_iterator(_head->_next);
}
const_iterator end() const
{//返回使用头结点的地址构造出来的普通const迭代器return const_iterator(_head);
}

访问容器相关函数

fron 和 back 

front 和 back 函数分别用于获取第一个有效数据和最后一个有效数据，因此，实现front和back函数时，直接返回第一个有效数据和最后一个有效数据的引用即可。 

T& front()
{return *begin(); //返回第一个有效数据的引用
}
T& back()
{return *(--end()); //返回最后一个有效数据的引用
}

• 当然，这也需要重载一对用于const对象 的front函数 和 back函数，因为 const对象 调用front和back函数后所得到的数据不能被修改。

const T& front() const
{return *begin(); //返回第一个有效数据的const引用
}const T& back() const
{return *(--end()); //返回最后一个有效数据的const引用
}

增删改查相关函数

insert

insert函数可以在所给迭代器之前插入一个新结点。 

• 先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，接着根据所给数据x构造一个待插入结点，之后再建立新结点与cur之间的双向关系，最后建立新结点与prev之间的双向关系即可。

//插入函数
void insert(iterator pos, const T& x)
{assert(pos._node); //检测pos的合法性node* cur = pos._node; //迭代器pos处的结点指针node* prev = cur->_prev; //迭代器pos前一个位置的结点指针node* newnode = new Node(x); //根据所给数据x构造一个待插入结点//建立newnode与cur之间的双向关系newnode->_next = cur;cur->_prev = newnode;//建立newnode与prev之间的双向关系newnode->_prev = prev;prev->_next = newnode;
}

earse 

先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，以及后一个位置的结点指针next，紧接着释放cur结点，最后建立prev和next之间的双向关系即可。

//删除函数
iterator erase(iterator pos)
{assert(pos._node); //检测pos的合法性assert(pos != end()); //删除的结点不能是头结点node* cur = pos._node; //迭代器pos处的结点指针node* prev = cur->_prev; //迭代器pos前一个位置的结点指针node* next = cur->_next; //迭代器pos后一个位置的结点指针delete cur; //释放cur结点//建立prev与next之间的双向关系prev->_next = next;next->_prev = prev;return iterator(next); //返回所给迭代器pos的下一个迭代器
}

这里如果返回当前的位置，也会有迭代器失效问题 

push_back 和 pop_back

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

push_front 和 pop_front

 push_front函数就是在第一个有效结点前插入结点，而pop_front就是删除第一个有效结点。

//头插
void push_front(const T& x)
{insert(begin(), x); //在第一个有效结点前插入结点
}
//头删
void pop_front()
{erase(begin()); //删除第一个有效结点
}

容量相关函数

size

size函数用于获取当前容器当中的有效数据个数，因为list是链表，所以只能通过遍历的方式逐个统计有效数据的个数。 

size_t size() const
{size_t sz = 0; //统计有效数据个数const_iterator it = begin(); //获取第一个有效数据的迭代器while (it != end()) //通过遍历统计有效数据个数{sz++;it++;}return sz; //返回有效数据个数
}

resize 

resize函数的规则：

1. 若当前容器的size小于所给n，则尾插结点，直到size等于n为止。
2. 若当前容器的size大于所给n，则只保留前n个有效数据。

实现resize函数时，不要直接调用size函数获取当前容器的有效数据个数，因为当你调用size函数后就已经遍历了一次容器了，而如果结果是size大于n，那么还需要遍历容器，找到第n个有效结点并释放之后的结点。

void resize(size_t n, const T& val = T())
{iterator i = begin(); //获取第一个有效数据的迭代器size_t len = 0; //记录当前所遍历的数据个数while (len < n&&i != end()){len++;i++;}if (len == n) //说明容器当中的有效数据个数大于或是等于n{while (i != end()) //只保留前n个有效数据{i = erase(i); //每次删除后接收下一个数据的迭代器}}else //说明容器当中的有效数据个数小于n{while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n{push_back(val);len++;}}
}

empty

empty函数用于判断容器是否为空，我们直接判断该容器的begin函数和end函数所返回的迭代器，是否是同一个位置的迭代器即可。（此时说明容器当中只有一个头结点）

bool empty() const
{return begin() == end(); //判断是否只有头结点
}

clear

clear函数用于清空容器，我们通过遍历的方式，逐个删除结点，只保留头结点即可。

void clear()
{iterator it = begin();while (it != end()) //逐个删除结点，只保留头结点{it = erase(it);}
}

可能会有同学问：这个是清除全部操作 为啥没有对it++进行遍历删除呢

这里 erase(it) 会删除当前迭代器 it 指向的元素，并返回一个指向下一个元素的迭代器。所以就相当于++了

list 容器的模拟实现整体代码

list.h 

#pragma once
#include <iostream>
#include <string>
#include <assert.h>
using std::ostream;
using std::istream;
using std::cin;
using std::cout;
using std::endl;// 为了避免和库里的 list 产生冲突，在自己的命名空间内实现 list
// 带头---双向---循环---链表
namespace xas_list
{// 通过模板能够实现不同类型的数据存储template<class T>// 链表节点的构造struct ListNode{ListNode<T>* _next;   // 指向后面节点的指针ListNode<T>* _prev;   // 指向前面节点的指针T _data;              // 一个节点中的数据// 构造函数ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};// 模拟实现迭代器template<class T, class Ref, class Ptr>// 模式一个迭代器 类型struct _list_iterator{typedef ListNode<T> Node;       // 为节点类 取别名//只要用自己的类型，就对其typedef成self，方便后续使用typedef _list_iterator<T, Ref, Ptr> self;   // 为正向迭代器类 取别名// 成员变量Node* _node;                     // _node 表示一个节点_list_iterator(Node* node = nullptr)       // 默认构造函数:_node(node){}// ++it 重载前置++ —— 让链表能够像数组一样去++操作，访问元素// 注意：这里的 this 不是局部变量，函数结束不会被销毁，可以使用引用返回，减少拷贝次数self& operator++(){//前置++返回的是++之后的值，直接让当前位置的结点指向下一个节点_node = _node->_next;return *this;}//重载后置++//此时需要返回temp对象，而不是引用//因为temp对象是局部的对象//函数结束后就被释放//it++ 重载后置++ —— （这里需要加上int作为一个站位符，与前置++区分）self operator++(int a){self temp(*this);_node = _node->_next; //后置++返回的是++之前的值，需要保存当前节点，再指向下一个节点return temp;}//重载前置--self& operator--() {_node = _node->_prev;return *this;}//重载后置--self operator--(int a) {self temp(*this);_node = _node->_prev;return temp;}// 赋值重载重载  * //返回迭代器指向的结点的值域Ref operator*(){return _node->_data;}// 重载 -> 操作符 ---实现指针访问元素Ptr operator->(){return &_node->date;}// 赋值重载 !=bool operator!=(const self& s)  const{return _node != s._node;}// 赋值重载 ==bool operator==(const self& s)  const{return _node == s._node;}};template<class T>// 创建一个 list 类class list{typedef ListNode<T> Node;            // 重新命名节点(结构体)的名称public:typedef _list_iterator<T, T&, T*> iterator;  // 为 迭代器类型取 别名typedef _list_iterator<T, const T&, const T*> const_iterator;// 正向迭代器 和 正向 const 迭代器iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;// 默认成员函数list();                             // 构造函数   --- 无参构造list(int n, const T& val = T());    // 用 n个val 构造template<class iterator>list(iterator first, iterator last) // 迭代器区间构造{empty_init();while (first != last){push_back(*first);++first;}}~list();                            // 析构函数list(list<T>& lt);                  // 拷贝构造void empty_init();                  // 初始化一个循环链表list<T>& operator=(list<T> lt);     // 赋值运算符符重载// 容量相关的函数size_t size() const;                // 计算节点的有效个数bool Empty()const;                  // 判空 不为空时，返回 truevoid clear();                       // 清空数据void resize(size_t n, const T& val = T());    // 设置list对象的有效元素个数// 访问容器相关函数T& front();                         // 返回第一个有效数据T& back();                          // 返回最后一个有效数据const T& front() const;                   const T& back() const;// 修改容器内容的相关函数void push_back(const T& x);                 // 尾插iterator insert(iterator pos, const T& x);  // 插入void push_front(const T& x);                // 头插iterator erase(iterator pos);               // 删除void pop_back();                            // 尾删void pop_front();                           // 头删void swap(list<T>& temp);                   // 交换函数private:Node* _head;};// 打印函数void printf_list(const list<int>& lt);
}

list.cpp

#include "list.h"template<class T>
xas_list::list<T>::list()    // 构造函数   --- 无参构造
{_head = new Node;     //申请创建一个新的节点  --- 双向循环_head->_next = _head;  _head->_prev = _head;
}template<class T>       // 用 n个val 进行构造
xas_list::list<T>::list(int n, const T& val)
{// 创建一个空节点_head = new Node;// 形成一个带头双向循环链表_head->_prev = _head;_head->_next = _head;for (int i = 0; i < n; i++){push_back(val);}
}template<class T>
xas_list::list<T>::~list()                     // 析构函数
{clear();delete _head;_head = nullptr;}// 初始化一个循环链表
template<class T>
void xas_list::list<T>::empty_init()
{//申请创建一个新的节点  --- 双向循环_head = new Node;_head->_next = _head;_head->_prev = _head;
}template<class T>
xas_list::list<T>::list( list<T>& lt)
{//申请创建一个新的节点  --- 双向循环empty_init();for (auto& e : lt){push_back(e);}
}template<class T>
void xas_list::list<T>::swap(list<T>& temp)
{std::swap(_head, temp._head);
}// lt1 = lt2;  --- 赋值重载
template<class T>
xas_list::list<T>& xas_list::list<T>::operator=(list<T> lt)
{//if (this != &lt)  // 判断一下是否有给自己赋值//{//	// 将lt1 先清空，再将lt2 插入到 lt1中//	// 注意 this 指针//	clear();//	for (const auto& e : lt)//	{//		push_back(e);//	}//}swap(lt);return *this;
}template<class T>
void xas_list::list<T>::clear()        // 清空数据
{//复用eraseiterator it = begin();while (it != end()){it = erase(it);//用it接收删除后的下一个结点的位置}
}// 正向迭代器 
// begin迭代器指向的是正方向第一个有效结点，也就是头结点的下一个结点。
// 因为有 哨兵位的存在
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::begin()
{return iterator(_head->_next);
}// end迭代器指向的是正方向最后一个有效结点的下一个结点，也就是头结点。
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::end()
{return iterator(_head);
}template<class T>
typename xas_list::list<T>::const_iterator xas_list::list<T>::begin()const
{return const_iterator(_head->_next);
}template<class T>
typename xas_list::list<T>::const_iterator xas_list::list<T>::end()const
{return const_iterator(_head);
}template<class T>
// ListNode(const T& x = T())  这里的 T() 的给一个缺省值
void xas_list::list<T>::push_back(const T& x)   // 尾插
{// 创建一个新的节点  ----  Node//Node* newnode = new Node(x);//Node* tail = _head->_prev;     // 找尾节点--------头节点的前一个节点进行尾插//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;insert(end(), x);
}// 头插
template<class T>
void xas_list::list<T>::push_front(const T& x)
{insert(begin(), x);
}// 插入
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::insert(iterator pos, const T& x)
{// 保存当前节点Node* cur = pos._node;Node* prev = cur->_prev;// 创建一个新的节点Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);
}// 删除
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::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);
}// 尾删
template<class T>
void xas_list::list<T>::pop_back()
{erase(--end());
}// 头删
template<class T>
void  xas_list::list<T>::pop_front()
{erase(begin());
}// 判断 list 的有效链表个数
template<class T>
size_t xas_list::list<T>::size() const
{size_t count = 0;list<T>::const_iterator it = begin();while (it != end()){count++;it++;}return count;
}// 判断 list 是否为空
template<class T>
bool xas_list::list<T>::Empty() const
{return _head->_next == _head;
}template<class T>
void xas_list::list<T>::resize(size_t n, const T& val)
{list<T>::iterator it = begin(); //获取第一个有效数据的迭代器size_t len = 0; //记录当前所遍历的数据个数while (len < n && it != end()){len++;it++;}if (len == n) //说明容器当中的有效数据个数大于或是等于n{while (it != end()) //只保留前n个有效数据{it = erase(it); //每次删除后接收下一个数据的迭代器}}else //说明容器当中的有效数据个数小于n{while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n{push_back(val);len++;}}
}template<class T>
T& xas_list::list<T>::front()
{return *begin();
}template<class T>
T& xas_list::list<T>::back()
{return *(--end());
}template<class T>
const T& xas_list::list<T>::front() const
{return *begin();
}template<class T>
const T& xas_list::list<T>::back() const
{return *(--end());
}// 打印对应的链表
void xas_list::printf_list(const list<int>& lt)
{list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;
}// 遍历的测试
void test1()
{xas_list::list<int> lt(5,6);lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_front(0);// 头删lt.pop_back();// 尾删lt.pop_front();// -------------迭代器测试------------------// cout << "迭代器的测试" << endl;xas_list::list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;cout << "范围for的测试" << endl;// -------------范围 for 测试------------------// for (auto e : lt){cout << e << " ";}cout << endl;cout << "清空数据" << endl;// 清空数据lt.clear();for (auto e : lt){cout << e << " ";}cout << endl;}void test2()
{xas_list::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;cout << "拷贝构造" << endl;xas_list::list<int> copy(lt);for (auto e : copy){cout << e << " ";}cout << endl;cout << "赋值重载" << endl;xas_list::list<int> lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(33);lt = lt1;for (auto e : lt){cout << e << " ";}cout << endl;}// const 迭代器
void test3()
{xas_list::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);int arr[] = { 1,2,3,4,5,6,7,8,9,10 };xas_list::list<int> l3(arr, arr + 10); //迭代器区间构造cout << l3.size() << endl;cout << l3.Empty() << endl;l3.resize(12,2);cout << l3.back() << endl;cout << l3.front() << endl;printf_list(l3);
}int main()
{test3();return 0;}