• 【C++】list的介绍及使用 | 模拟实现list（万字详解）

    目录

    一、list的介绍及使用

    什么是list？

    list的基本操作

    增删查改

    获取list元素

    不常见操作的使用说明

    ​编辑

    接合splice

    ​编辑

    移除remove

    去重unique

    二、模拟实现list

    大框架

    构造函数

    尾插push_back

    迭代器__list_iterator

    list的迭代器要如何跑起来

    iterator的构造函数

    begin()与end()

    operator++

    operator*

    operator!=

    测试

    operator->

    const迭代器

    增删查改

    insert()

    ❗erase()

    pop_back()

    完整代码

    List.h

    test.cpp

    一、list的介绍及使用

    什么是list？

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

    2.其底层是双向链表结构。

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

    3.list与forward_list非常相似。

    最主要的不同在于forward_list是单链表，只能朝前迭代。（这也使得它更加得简单高效）

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

    5.与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问。

    比如：要访问list的第6个元素，必须从已知的位置（如头部 或 尾部）迭代到该位置，在这段位置上迭代需要线性的时间开销。

    list还需要一些额外的空间，以保存每个节点的相关联信息。（对于存储类型较小元素的大list来说，这可能是一个重要的因素）

    list的基本操作

    包头文件：

    就和我们用过的vector一样，list也是个类模板：

    1. #include
    2. #include
    3. using namespace std;
    4. ​
    5. int main() {
    6.     list<int> lt;
    7.     return 0;
    8. }

    list的大部分操作，我们不需要记忆，因为很多用起来和vector、string的差不多，就算忘了，直接查文档即可。所以这里就一笔带过。

    增删查改

    函数名功能
    assign覆盖
    push_front头插
    pop_front头删
    push_back尾插
    pop_back尾删
    insert插入
    erase删除
    swap交换
    resize改变大小
    clear清空

    注：

    1.因为list不是连续的结构，它是指针串起来的链表，所以不支持随机访问，“方括号+下标”的访问方式不能用了！

    2.我们要遍历list的话就用范围for 或者 迭代器。

    3.和vector一样，list里没有专门再实现find，要想查找就用下的find。

    在调用find时，用第二种方式：

    因为find是函数模板，不是vector里的。

    在学vector时，我们在insert和erase处，讲到了迭代器失效的问题。这个问题是否同样存在于list中呢？

    实际上，list中进行insert操作是不存在迭代器失效的问题的，而erase操作则会有。

    因为insert仅需要改变指针间的指向关系即可，不存在变成野指针的问题：

    而erase会导致 指向被删节点的指针 变成野指针的问题，所以存在迭代器失效的情况。

    获取list元素

    函数名功能
    front返回list的第一个节点中值的引用
    back返回list的最后一个节点中值的引用

    不常见操作的使用说明

    这些操作很少用，但由于很多我们之前没见过，所以这里也做下说明。

    接合splice

    splice意为“接合”，即把一个链表接合到另一个链表上去。

    示例：

    1. int main() {
    2.     list<int> l1(4,0);
    3.     for (auto e : l1) {
    4.         cout << e << " ";
    5.     }
    6.     cout << endl;
    7. ​
    8.     list<int> l2(2, 1);
    9.     for (auto e : l2) {
    10.         cout << e << " ";
    11.     }
    12.     cout << endl;
    13. ​
    14.     l1.splice(l1.begin(), l2);
    15.     for (auto e : l1) {
    16.         cout << e << " ";
    17.     }
    18.     cout << endl;
    19.     return 0;
    20. }
    移除remove

    remove可以移除所有的待找元素。

    示例：

    1. int main() {
    2.     list<int> lt;
    3.     lt.push_back(1);
    4.     lt.push_back(1);
    5.     lt.push_back(1);
    6.     lt.push_back(2);
    7.     lt.push_back(3);
    8.     lt.push_back(4);
    9.     lt.remove(1);
    10.     for (auto e : lt) {
    11.         cout << e << " ";
    12.     }
    13.     return 0;
    14. }

    相关函数remove_if()用于删除 满足特定条件的元素。

    去重unique

    unique仅对 有序的元素集合 有效，所以，在使用unique前 要先对集合排序！

    示例：

    1. int main() {
    2.     list<int> lt;
    3.     lt.push_back(4);
    4.     lt.push_back(1);
    5.     lt.push_back(9);
    6.     lt.push_back(2);
    7.     lt.push_back(2);
    8.     lt.push_back(4);
    9.     lt.sort();
    10.     lt.unique();
    11.     for (auto e : lt) {
    12.         cout << e << " ";
    13.     }
    14.     cout << endl;
    15.     return 0;
    16. }

    其余还有：合并merge、排序sort、逆置reverse，就不详讲了，最重要的是 要培养阅读文档的能力。

    二、模拟实现list

    从0开始 实现一遍list，可以让我们清晰地认识list的结构。

    大框架

    先把大框架搭出来，再慢慢填充血肉。

    list是链表结构，本身要定义出一个类去描述它；而list的每个节点list_node，也需要定义一个类来描述。

     

    1. namespace jzy 
    2. {
    3.     template<class T>
    4.     class list_node
    5.     {
    6.     public:
    7.         list_node* _pre;   
    8.         list_node* _next;
    9.         T _data;
    10.     };
    11. ​
    12.     template<class T>
    13.     class list
    14.     {
    15.         typedef list_node Node;    //list_node太长了，改成Node用着顺手
    16.     public:
    17. ​
    18.     private:
    19.         Node* _head;    //list是带头结点的链表，所以成员变量只需一个头节点
    20.     };
    21. }
     

     
 
    注：要把list_node的类设成public，这样类外才能访问到。如果不写public的话，默认权限是private。
     
 
    或者设计成struct{};，struct的默认访问权限是public。
     

     

     

    构造函数
     

    先实现 节点的构造函数：
     

    我们想要达到的效果是：构造出的list，内含一个头点node，这个node已被初始化过。
     

    如图：list为双向循环链表，其node被初始化：
     

     

    既然想要node在创建伊始就被初始化，那我们可以直接写个node的构造函数：
     

    1. class list_node
    2.     {
    3.     public:
    4.         T _data;
    5.         list_node* _pre;
    6.         list_node* _next;
    7. ​
    8.         list_node(const T& x = T())
    9.             :_data(x)
    10.             ,_pre(nullptr)
    11.             ,_next(nullptr)
    12.         {}
    13.     };
     

    这样，我们每创建出一个node，就是被初始化过的了。
     

    1. class list_node
    2. {
    3. public:
    4.     T _data;
    5.     list_node* _pre;
    6.     list_node* _next;
    7.  
    8.     list_node(const T& x = T())
    9.         :_data(x)
    10.         ,_pre(nullptr)
    11.         ,_next(nullptr)
    12.     {}
    13. };
     

     

     

    再实现list的构造函数：
     

    因为是带头双向循环列表，所以创建伊始，就有个哨兵位的头节点。
     

    1. namespace jzy
    2. {
    3.     template<class T>
    4.     class list_node
    5.     {
    6.     public:
    7.         T _data;
    8.         list_node* _pre;
    9.         list_node* _next;
    10. ​
    11.         list_node(const T& x = T())
    12.             :_data(x)
    13.             ,_pre(nullptr)
    14.             ,_next(nullptr)
    15.         {}
    16.     };
    17. ​
    18.     template<class T>
    19.     class list
    20.     {
    21.         typedef list_node Node;
    22.     public:
    23.         list() {
    24.             _head = new Node;
    25.             _head->_next = _head;
    26.             _head->_pre = _head;
    27.         }
    28. ​
    29.     private:
    30.         Node* _head;
    31.     };
    32. }
     

    ​
     

     

    尾插push_back
     

    步骤：
     

    1.找到尾节点tail
     

    2.创建newNode
     

    3.改变_head、tail的指针与newNode的指向关系
     

     

    1. void push_back(const T& val) {  
    2.     Node* tail = _head->_pre;
    3.     Node* newNode = new Node(val);  //实例化出一个值为val的node
    4. ​
    5.     tail->_next = newNode;    //改变指针的指向关系
    6.     newNode->_pre = tail;
    7.     newNode->_next = _head;
    8.     _head->_pre = newNode;
    9. }
     

     

     

    迭代器__list_iterator
     

    list的迭代器要如何跑起来
     

    我们之前实现过string、vector的迭代器，它们的迭代器都是原生指针，当时我们说过：“就当作指针来用”，可以解引用，也可以++。
     

    所以迭代器用起来真的很方便：
     

    1. vector<int>::iterator it=v.begin();
    2. while(it!=v.end()){
    3.     cout<<*it<<" ";
    4.     it++;
    5. }
     

     

    list的迭代器本质也同样是一个指向node的指针。但是！list的迭代器不能 解引用和++，所以目前没法跑起来。
     

     
 
    list不同于string、vector，它不是一块连续的存储空间，++是无法走到下一个节点的；节点是自定义类型，没法单纯地进行解引用。
     
 
     
 
    对此的解决方案是：
     
 
    封装一个list迭代器类，在类里将++、!=、*等运算符进行重载。
     
 
    这样，就能让list迭代器 像string的一样直接使用，而不用关心它的底层实现。
     

     

     

    接下来，我们先把 __list_iterator类 的框架搭出来，然后挨个实现里面的运算符。
     

     

    list迭代器的框架：
     

    1. template<class T>
    2. class __list_iterator
    3. {
    4. public:
    5.     typedef list_node Node;      //这俩名字都太长了，typedef个短点儿的，好使
    6.     typedef __list_iterator iterator;
    7. ​
    8.     Node* node;     //list迭代器本质是一个指向node的指针
    9. };
     

     
 
    注：
     
 
    1.typedef会受访问限定符控制。
     
 
    此外，若是在类里定义typedef，其作用域仅限于类里；若是在类外定义，其作用域为整个文件。因为类定义了一个新的作用域。
     
 
     
 
    2.__list_iterator类 要定义在list类 的前面，因为编译是从上往下的顺序，在list里遇到iterator只会往上找，不会往下找。
     
 
     
 
    3.__list_iterator类 是定义在 list类 的外面的！不是list的内部类。
     
 
    为了保证iterator的封装性，我们把它单独定义为了一个类。node、list、iterator三个类是分开定义的。
     
 
     

     

     

    iterator的构造函数
     

    1. template<class T>
    2. class __list_iterator     
    3. {                                                                               
    4. public:
    5.     typedef list_node Node;
    6.     typedef __list_iterator iterator;  
    7.     Node* node;
    8. ​
    9.     //构造函数：当iterator被构造出来时，其实就是构造了一个指向特定节点的指针
    10.     __list_iterator(Node* pn)   //这里小心，返回值不能写成iterator
    11.         :node(pn)
    12.     {}
    13. };
     

     
 
    这里补充说明一下，返回值为什么不能写成iterator：
     
 
    因为被重命名成iterator的对象是_ _list_iterator，而不是 __list_iterator。后者是模板，前者是模板被实例化出的类型。
     
 
    两者本质是不一样的，注意区分！我们用的iterator，不是模板了，它是指向具体类型的指针。
     

     

     

    begin()与end()
     

    begin()为第一个元素的位置，end()为最后一个元素的后一个位置：
     

     

    因为begin与end返回的是list的位置，所以要把这两个函数实现在list类里，而不是__list_iterator里。
     

    1. iterator begin() {
    2.     return iterator(_head->_next);   //返回匿名对象
    3. }
    4. ​
    5. iterator end() {
    6.     return iterator(_head);
    7. }
     

     

    operator++
     

    ++操作包括：前置++、后置++。两者区分点在于后置++有占位符int。
     

     
 
    注意：
     
 
    后置加加的占位符就是int（这是规定）。不要写Node这种 其他类型。
     

     

    1. //operator++
    2. //前置++
    3. iterator& operator++() {   //为什么返回类型是iterator? 就跟int++完还是int一样，迭代器++完，还得是迭代器。。。
    4.     node = node->_next;
    5.     return *this;  
    6. }
    7. ​
    8. //后置++
    9. iterator operator++(int) {    
    10.     __list_iterator copy_it(*this);  
    11.     node = node->_next;
    12.     return copy_it;
    13. }
     

     

    operator*
     

    1. T& operator*() {
    2.     return node->_data;
    3. }
     

     

    operator!=
     

    1. bool operator!=(const iterator& it) {  
    2.     return node != it.node;     //node是it的成员变量        
    3. }
     

     
 
    注：这里的形参一定要被const修饰！
     
 
     
 
    说到const修饰形参，我们就趁此回顾下这个知识点。
     
 
    如果是传值传参，那没必要用const修饰。反正形参只是实参的拷贝，它的改变压根不会影响形参，所以对于实参而言，形参有没有被const修饰都一样。
     
 
     
 
    如果是传指针传参or引用传参，那尽量给形参加上const修饰！
     
 
    记住这句话：从现在起，要养成好习惯！传指针传参or传值传参时，加上const修饰形参！当然，前提是函数内不改变形参~
     
 
     
 
    因为，const修饰的形参，既能接受普通实参，又能接收const实参。而未经const修饰的形参，只能接收普通实参，无法接受const实参。（因为权限大的能调用权限小的，而反过来不行）
     
 
     
 
    所以说，使用引用传参时，如果函数内不作改变，那尽量采用const引用传参。
     

     

     

    测试
     

    测试一下：
     

    1. #include"List.h"
    2. using namespace jzy;
    3. void test1()
    4. {
    5.     list<int> lt;
    6.     lt.push_back(1);
    7.     lt.push_back(2);
    8.     lt.push_back(3);
    9.     lt.push_back(4);
    10. ​
    11.     list<int>::iterator it = lt.begin();
    12.     while (it != lt.end()) {
    13.         cout << *it << " ";
    14.         it++;
    15.     }
    16. }
    17. int main()
    18. {
    19.     test1();
    20.     return 0;
    21. }
     

     

    之前说过，范围for的底层就是替换成了迭代器。只要迭代器实现出来，那范围for也自然能用了。
     

     

    operator->
     

    迭代器模拟的是指针p，p在访问 自定义类型的成员 时，有两种方式：
     

    1.(*p).XX
     

    2.p->XX
     

    我们已经实现了*运算符，现在就来完善下，实现箭头运算符。这样，迭代器就能通过->，访问自定义类型的成员了。
     

     

    。。。
     

    这个箭头运算符，我准备实现的时候i，发现一点头绪都没有。。。
     

    所以我们还是看下源码，学习下大佬是怎么实现的吧。
     

    源码：
     

    1. T* operator->() {
    2.     return &(operator*());
    3. }
     

     

    这个源码比较难理解，我来解释一下：
     

     
 
    刚刚实现的operator*：
     
 
    1. T& operator*() {
    2.     return node->_data;
    3. }
     
 
    所以，operator->就相当于返回了&(node->_data)，即指向T的指针。
     
 
     
 
    在使用时，iterator->XX，其实是编译器做了省略之后的结果。
     
 
    它原本的样子是iterator-> ->XX，两个箭头，可这样的话，代码可读性太差了，于是编译器做了优化，省略了一个箭头。
     
 
     
 
    那实际上，应为( iterator.operator->() ).operator->() XX。对operator->做了两次调用。
     
 
    第一次调用，返回一个指向T的指针。就相当于返回了一个原生指针，再用这个原生指针调用operator->，去访问它的成员。
     

     

     

     

    测试一下：
     

    先在List.h里写一个自定义类型，然后我们用迭代器去访问name。
     

    1. struct student     
    2. {
    3.     char name[100];
    4.     size_t age;
    5.     char tele[100];
    6. };
     

    test.cpp：
     

    1. void test2() {
    2.     list lt;
    3.     lt.push_back({ "Tom",12,"110" });
    4.     lt.push_back({ "Billy",10,"888" });
    5.     
    6.     list::iterator it = lt.begin();
    7.     while (it != lt.end()) {
    8.         cout << it->name << " ";     //->
    9.         it++;
    10.     }
    11. }
     

     

    const迭代器
     

    我们来看下面这个情境：
     

    1. void Print(const list<int> lt) {      //lt被const修饰
    2.     list<int>::iterator it = lt.begin();
    3.     while (it != lt.end()) {
    4.         cout << *it << " ";
    5.         it++;
    6.     }
    7. }
    8. void test3() {
    9.     list<int> lt;
    10.     lt.push_back(1);
    11.     lt.push_back(2);
    12.     lt.push_back(3);
    13.     lt.push_back(4);
    14.     Print(lt);
    15. }
     

     

    const对象lt 是没法调用普通迭代器的，因为权限小的 没法调用 权限大的。const对象要调用const迭代器。
     

     

    那怎么实现const迭代器呢？
     

    其实，const迭代器与普通迭代器 的内部实现是一样的，唯一区别就是普通迭代器返回T&，可读可写，而const迭代器返回const T&，可读不可写。
     

    最笨的办法，就是copy一份刚刚的迭代器代码，然后给每个函数的返回值加上const修饰，再把名称改成_const __ list__iterator。
     

     

    先来展示一下笨办法：
     

    1. #pragma once
    2. #include
    3. using namespace std;
    4. namespace jzy
    5. {
    6.     template<class T>
    7.     class list_node
    8.     {
    9.       ……
    10.     };
    11. ​
    12.     template<class T>
    13.     class __list_iterator      
    14.     {                                                                                   
    15.       ……
    16.     };
    17. ​
    18.     template<class T>              //拷贝一份__list_iterator的代码
    19.     class _const__list_iterator    //所做的修改：1.把iterator换成const_iterator(换个名字而已)  2.在T&、T*前加上const
    20.     {                                                                           
    21.     public:
    22.         typedef list_node Node;
    23.         typedef _const__list_iterator const_iterator;          
    24.         Node* node;
    25. ​
    26.         //构造函数
    27.         _const__list_iterator(Node* pn)  
    28.             :node(pn)
    29.         {}
    30. ​
    31.         //operator++
    32.         //前置++
    33.         const_iterator& operator++() {   
    34.             node = node->_next;
    35.             return *this;
    36.         }
    37. ​
    38.         //后置++
    39.         const_iterator operator++(int) {
    40.             __list_iterator copy_it(*this);
    41.             node = node->_next;
    42.             return copy_it;
    43.         }
    44. ​
    45.         const T& operator*() {
    46.             return node->_data;
    47.         }
    48. ​
    49.         //operator--
    50.         //前置--
    51.         const_iterator& operator--() {
    52.             node = node->_pre;
    53.             return *this;
    54.         }
    55. ​
    56.         //后置--
    57.         const_iterator operator--(int) {
    58.             __list_iterator copy_it(*this);
    59.             node = node->_pre;
    60.             return copy_it;
    61.         }
    62. ​
    63.         bool operator!=(const const_iterator& it) {
    64.             return node != it.node;            
    65.         }
    66. ​
    67.         const T* operator->() {
    68.             return &(operator*());
    69.         }
    70.     };
    71.     
    72.     template<class T>
    73.     class list
    74.     {
    75.     public:
    76.         typedef list_node Node;
    77.         typedef __list_iterator iterator;
    78.         typedef _const__list_iterator const_iterator;   
    79.         
    80.         ……
    81. ​
    82.         iterator begin() {
    83.             return iterator(_head->_next);  
    84.         }
    85. ​
    86.         const_iterator begin() const{      //begin()和end()也要实现const版本，供const对象调用
    87.             return const_iterator(_head->_next);  
    88.         }
    89. ​
    90.         iterator end() {
    91.             return iterator(_head);
    92.         }
    93. ​
    94.         const_iterator end() const{
    95.             return const_iterator(_head);
    96.         }
    97. ​
    98.     private:
    99.         Node* _head;
    100.     };
    101. }
     

    测试下，当我们尝试修改const对象：
     

     

    很好，修改不了~
     

     

    但是！上面的代码重复度太高了，并不是好的解决思路。库里的思路是：用模板实现const迭代器！
     

     

    其实我们观察可以发现，iterator和const_iterator的实现中，只有operator* 和operator->的返回值不一样，普通迭代器的返回值是 T& 与T*，后者是const T&与const T *。
     

    所以，可以把T&和T *用类模板Ref（reference）、Ptr（pointer）表示，即现在设三个模板参数：
     

    template<class T,class Ref,class Ptr >
     

    这样一来，我们传iterator / const_iterator，编译器就能自动匹配。
     

     

    你现在一定很多问号，这一块的确不好理解。
     

    我就着下面这张图，为你解释下为什么传三个模板参数就能起到自动匹配的效果：
     

     

     
 
    拿iterator的情况举例：
     
 
    首先，程序的编译进行到了第一部分，lt要调用begin()，这里的lt没有被const修饰，那它的迭代器就是iterator，lt所调用的begin()函数 也是返回值为iterator的那个。（此时程序由第一部分跳至二）
     
 
     
 
    而iterator追根溯源，找到当初被重命名的对象：__list _iterator。（此时程序由第二部分跳至三）
     
 
     
 
    __list _iterator回到当初定义它的结构体 那边，此时作为模板参数跟一一匹配。
     
 
    结构体中的Ref被自动匹配为T&，Ptr则被匹配为T*。（此时程序由第三部分跳至四）
     
 
     
 
    const_iterator同理。
     

     

     

     

     
 
    同时这里要注意，因为模板参数是三个：
     
 
    template<class T,class Ref,class Ptr >
     
 
    所以我们在typedef时，也要注意同样写三个参数，不然没法与模板参数匹配：
     
 
    1. typedef __list_iterator iterator;   //√
    2. typedef __list_iterator iterator;       //×
    3. typedef __list_iterator iterator;       //×
     
 
     
 
    我当初对typedef __ list_iterator iterator;非常不理解，当时误以为，它可以拆分成 typedef __ list_iterator iterator;或者typedef __list_iterator iterator;
     
 
    现在才明白，这个并不是拆分来看的，这里之所以要写T,T&,T*，是为了和参数模板一一匹配。
     

     

     

    实现：
     

    1. template<class T,class Ref,class Ptr>
    2. class __list_iterator     
    3. {                                                                               
    4. public:
    5.     typedef list_node Node;
    6.     typedef __list_iterator iterator;
    7.     Node* node;
    8. ​
    9.     ……     //省略掉的部分都和之前的一样
    10. ​
    11.     Ref operator*() {
    12.         return node->_data;
    13.     }
    14. ​
    15.     ……
    16. ​
    17.     Ptr operator->() {
    18.         return &(operator*());
    19.     }
    20. };
     

    不光是__list_iterator要改，list也要相应地作出改动：
     

    1. template<class T>
    2. class list
    3. {
    4. public:
    5.     typedef list_node Node;
    6.     typedef __list_iterator iterator;
    7.     typedef __list_iteratorconst T&, const T*> const_iterator; 
    8. ​
    9.     ……  //和之前相同的部分 省略不写
    10. ​
    11.     iterator begin() {
    12.         return iterator(_head->_next);  
    13.     }
    14. ​
    15.     const_iterator begin() const{    
    16.         return const_iterator(_head->_next);  
    17.     }
    18. ​
    19.     iterator end() {
    20.         return iterator(_head);
    21.     }
    22. ​
    23.     const_iterator end() const{
    24.         return const_iterator(_head);
    25.     }
    26. ​
    27. private:
    28.     Node* _head;
    29. };
     

     

    增删查改等功能
     

    insert()
     

    1. iterator insert(iterator pos, const T& val) {  
    2.     Node* cur = pos.node;   //注意iterator和node的关系，node是它的成员
    3.     Node* pre = cur->_pre;
    4.     Node* pNew = new Node(val);  
    5. ​
    6.     pre->_next = pNew;    //注意：指针是双向的
    7.     pNew->_pre = pre;
    8.     pNew->_next = cur;
    9.     cur->_pre = pNew;
    10. ​
    11.     return iterator(pNew);
    12. }
     

    有了insert()，我们就可以复用它来进行头插了：
     

    1. void push_front(const T& val) {
    2.     insert(begin(), val);
    3. }
     

     

    ❗erase()
     

    1. void erase(iterator pos) {
    2.     assert(pos!= end());
    3. ​
    4.     Node* cur = pos.node;
    5.     Node* pre = cur->_pre;
    6.     Node* next = cur->_next;
    7.     pre->_next = next;
    8.     next->_pre = pre;
    9.     delete[] cur;
    10. }
     

    但是，这样写真的对吗？
     

     

    还记得我们在vector那里，花了很大篇幅说到的insert/erase迭代器失效的问题吗？
     

    这里也同样要考虑迭代器失效的问题。
     

     

    修改后的正确版本：
     

    1. iterator erase(iterator pos) {
    2.     assert(pos!= end());
    3. ​
    4.     Node* cur = pos.node;
    5.     Node* pre = cur->_pre;
    6.     Node* next = cur->_next;
    7.     pre->_next = next;
    8.     next->_pre = pre;
    9.     delete[] cur;
    10. ​
    11.     return iterator(next);
    12. }
     

     

    pop_back()
     

    1. void pop_back() {
    2.     Node* EndNode = end().node;
    3.     Node* ToBeErase = EndNode->_pre;
    4.     Node* pre = ToBeErase->_pre;
    5.     pre->_next = EndNode;
    6.     EndNode->_pre = pre;
    7.     delete[] ToBeErase;
    8. }
     

     

    至于find()，你问我为啥不实现find()？没必要呀！算法库里就有find()模板，直接拿来用就好。
     

     

    clear()
     

    delete只能释放连续的物理空间，所以链表的这种内存不连续的情况，只能挨个挨个释放。
     

    1. void clear() {
    2.     iterator it = begin();
    3.     while (it != end()) {
    4.         iterator copy_it = it++;
    5.         delete copy_it.node;
    6.     }
    7.     _head->_next = _head;
    8.     _head->_pre = _head;
    9. }
     

    这里要注意的一点是，别忘了最后处理_head的前后指针，我一开始忘了，导致它们变成了野指针。
     

    实现了clear()，我们就可以复用它来实现析构函数：
     

    1. ~list() {
    2.     clear();
    3.     delete _head;
    4.     _head = nullptr;
    5. }
     

    赋值
     

    1. list& operator=(const list& lt) {
    2.     if (this != <) {
    3.         clear();
    4.         for (auto e : lt) {
    5.             push_back(e);
    6.         }
    7.     }
    8.     return *this;
    9. }
     

    或者这样写：
     

    1. list& operator=(list lt) {
    2.     swap(_head, lt._head);
    3.     return *this;
    4. }
     

     

    拷贝构造
     

    1. list(const list& lt) {
    2.     _head = new Node;
    3.     _head->_pre = _head;
    4.     _head->_next = _head;
    5.     for (auto e : lt) {
    6.         push_back(e);
    7.     }
    8. }
     

     

    完整代码
     

    List.h
     

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6. namespace jzy
    7. {
    8. 	template<class T>
    9. 	class list_node
    10. 	{
    11. 	public:
    12. 		T _data;
    13. 		list_node* _pre;
    14. 		list_node* _next;
    15.  
    16. 		list_node(const T& x = T())
    17. 			:_data(x)
    18. 			,_pre(nullptr)
    19. 			,_next(nullptr)
    20. 		{}
    21. 	};
    22.  
    23. 	template<class T,class Ref,class Ptr>
    24. 	class __list_iterator     
    25. 	{																		        
    26. 	public:
    27. 		typedef list_node Node;
    28. 		typedef __list_iterator iterator;
    29. 		Node* node;
    30.  
    31. 		//构造函数
    32. 		__list_iterator(Node* pn)   
    33. 			:node(pn)
    34. 		{}
    35.  
    36. 		//operator++
    37. 		//前置++
    38. 		iterator& operator++() { 
    39. 			node = node->_next;
    40. 			return *this;  
    41. 		}
    42.  
    43. 		//后置++
    44. 		iterator operator++(int) {    
    45. 			__list_iterator copy_it(*this);   
    46. 			node = node->_next;
    47. 			return copy_it;
    48. 		}
    49.  
    50. 		Ref operator*() {
    51. 			return node->_data;
    52. 		}
    53.  
    54. 		//operator--
    55. 		//前置--
    56. 		iterator& operator--() {
    57. 			node = node->_pre;
    58. 			return *this;
    59. 		}
    60.  
    61. 		//后置--
    62. 		iterator operator--(int) {
    63. 			__list_iterator copy_it(*this);
    64. 			node = node->_pre;
    65. 			return copy_it;
    66. 		}
    67.  
    68. 		bool operator!=(const iterator& it) { 
    69. 			return node != it.node;             
    70. 		}
    71.  
    72. 		Ptr operator->() {
    73. 			return &(operator*());
    74. 		}
    75. 	};
    76.  
    77. 	//template
    78. 	//class _const__list_iterator     
    79. 	//{																	        
    80. 	//public:
    81. 	//	typedef list_node Node;
    82. 	//	typedef _const__list_iterator const_iterator;          
    83. 	//	Node* node;
    84.  
    85. 	//	//构造函数
    86. 	//	_const__list_iterator(Node* pn)  
    87. 	//		:node(pn)
    88. 	//	{}
    89.  
    90. 	//	//operator++
    91. 	//	//前置++
    92. 	//	const_iterator& operator++() {   
    93. 	//		node = node->_next;
    94. 	//		return *this;
    95. 	//	}
    96.  
    97. 	//	//后置++
    98. 	//	const_iterator operator++(int) {
    99. 	//		__list_iterator copy_it(*this);
    100. 	//		node = node->_next;
    101. 	//		return copy_it;
    102. 	//	}
    103.  
    104. 	//	const T& operator*() {
    105. 	//		return node->_data;
    106. 	//	}
    107.  
    108. 	//	//operator--
    109. 	//	//前置--
    110. 	//	const_iterator& operator--() {
    111. 	//		node = node->_pre;
    112. 	//		return *this;
    113. 	//	}
    114.  
    115. 	//	//后置--
    116. 	//	const_iterator operator--(int) {
    117. 	//		__list_iterator copy_it(*this);
    118. 	//		node = node->_pre;
    119. 	//		return copy_it;
    120. 	//	}
    121.  
    122. 	//	bool operator!=(const const_iterator& it) {
    123. 	//		return node != it.node;            
    124. 	//	}
    125.  
    126. 	//	const T* operator->() {
    127. 	//		return &(operator*());
    128. 	//	}
    129. 	//};
    130. 	
    131. 	template<class T>
    132. 	class list
    133. 	{
    134. 	public:
    135. 		typedef list_node Node;
    136. 		typedef __list_iterator iterator;
    137. 		typedef __list_iteratorconst T&, const T*> const_iterator;  
    138. 		iterator begin() {
    139. 			return iterator(_head->_next);
    140. 		}
    141.  
    142. 		const_iterator begin() const {
    143. 			return const_iterator(_head->_next);
    144. 		}
    145.  
    146. 		iterator end() {
    147. 			return iterator(_head);
    148. 		}
    149.  
    150. 		const_iterator end() const {
    151. 			return const_iterator(_head);
    152. 		}
    153.  
    154. 		list() {
    155. 			_head = new Node;
    156. 			_head->_next = _head;
    157. 			_head->_pre = _head;
    158. 		}
    159.  
    160. 		list(size_t n, const T& val = T()) {
    161. 			_head = new Node;
    162. 			Node* cur = _head;
    163.  
    164. 			size_t sz = n;
    165. 			while (sz) {
    166. 				Node* p = new Node(val);
    167. 				cur->_next = p;
    168. 				p->_pre = cur;
    169.  
    170. 				cur = cur->_next;
    171. 				sz--;
    172. 			}
    173. 			cur->_next = _head;
    174. 			_head->_pre = cur;
    175. 		}
    176. 		
    177. 		//拷贝构造
    178. 		list(const list& lt) {
    179. 			_head = new Node;
    180. 			_head->_pre = _head;
    181. 			_head->_next = _head;
    182. 			for (auto e : lt) {
    183. 				push_back(e);
    184. 			}
    185. 		}
    186.  
    187. 		void clear() {
    188. 			iterator it = begin();
    189. 			while (it != end()) {
    190. 				iterator copy_it = it++;
    191. 				delete copy_it.node;
    192. 			}
    193. 			_head->_next = _head;
    194. 			_head->_pre = _head;
    195. 		}
    196.  
    197. 		~list() {
    198. 			clear();
    199. 			delete _head;
    200. 			_head = nullptr;
    201. 		}
    202.  
    203. 		//赋值
    204. 		//Way1
    205. 		/*list& operator=(list lt) {
    206. 			swap(_head, lt._head);
    207. 			return *this;
    208. 		}*/
    209.  
    210. 		//Way2
    211. 		list& operator=(const list& lt) {
    212. 			if (this != <) {
    213. 				clear();
    214. 				for (auto e : lt) {
    215. 					push_back(e);
    216. 				}
    217. 			}
    218. 			return *this;
    219. 		}
    220.  
    221. 		void push_back(const T& val) {	
    222. 			Node* tail = _head->_pre;
    223. 			Node* newNode = new Node(val);  
    224.  
    225. 			tail->_next = newNode;    
    226. 			newNode->_pre = tail;
    227. 			newNode->_next = _head;
    228. 			_head->_pre = newNode;
    229. 		}
    230.  
    231. 		iterator insert(iterator pos, const T& val) {  
    232. 			Node* cur = pos.node;
    233. 			Node* pre = cur->_pre;
    234. 			Node* pNew = new Node(val);  
    235. 			pre->_next = pNew;   
    236. 			pNew->_pre = pre;
    237. 			pNew->_next = cur;
    238. 			cur->_pre = pNew;
    239.  
    240. 			return iterator(pNew);
    241. 		}
    242.  
    243. 		void push_front(const T& val) {
    244. 			insert(begin(), val);
    245. 		}
    246.  
    247. 		iterator erase(iterator pos) {
    248. 			assert(pos!= end());
    249.  
    250. 			Node* cur = pos.node;
    251. 			Node* pre = cur->_pre;
    252. 			Node* next = cur->_next;
    253. 			pre->_next = next;
    254. 			next->_pre = pre;
    255. 			delete[] cur;
    256.  
    257. 			return iterator(next);
    258. 		}
    259.  
    260. 		void pop_back() {
    261. 			Node* EndNode = end().node;
    262. 			Node* ToBeErase = EndNode->_pre;
    263. 			Node* pre = ToBeErase->_pre;
    264. 			pre->_next = EndNode;
    265. 			EndNode->_pre = pre;
    266. 			delete[] ToBeErase;
    267. 		}
    268.  
    269.  
    270. 	private:
    271. 		Node* _head;
    272. 	};
    273.  
    274. 	//这个是测试用的
    275. 	struct student
    276. 	{
    277. 		char name[100];
    278. 		size_t age;
    279. 		char tele[100];
    280. 	};
    281. }
    282.  
     

     

    test.cpp
     

    1. #include"List.h"
    2. using namespace jzy;
    3. void test1()
    4. {
    5. 	list<int> lt;
    6. 	lt.push_back(1);
    7. 	lt.push_back(2);
    8. 	lt.push_back(3);
    9. 	lt.push_back(4);
    10.  
    11. 	list<int>::iterator it = lt.begin();
    12. 	while (it != lt.end()) {
    13. 		cout << *it << " ";
    14. 		it++;
    15. 	}
    16. 	cout << endl;
    17.  
    18. 	for (auto e : lt) {
    19. 		cout << e << " ";
    20. 	}
    21. }
    22. void test2() {
    23. 	list lt;
    24. 	lt.push_back({ "Tom",12,"110" });
    25. 	lt.push_back({ "Billy",10,"888" });
    26. 	list::iterator it = lt.begin();
    27. 	while (it != lt.end()) {
    28. 		cout << it->name << " ";
    29. 		it++;
    30. 	}
    31. 	cout << endl;
    32. }
    33.  
    34. void Print(const list<int>& lt) {
    35. 	list<int>::const_iterator it = lt.begin();  
    36. 	while (it != lt.end()) {
    37. 		//*it = 100;
    38. 		cout << *it << " ";       
    39. 		it++;
    40. 	}
    41. }
    42. void test3() {
    43. 	list<int> lt;
    44. 	lt.push_back(1);
    45. 	lt.push_back(2);
    46. 	lt.push_back(3);
    47. 	lt.push_back(4);
    48. 	Print(lt);
    49. }
    50. void test4() {
    51. 	list<int> lt;
    52. 	lt.push_back(1);
    53. 	lt.push_back(2);
    54. 	lt.push_back(3);
    55. 	list<int>::iterator pos = lt.begin();
    56. 	lt.insert(pos, 9);
    57. 	lt.push_front(99);
    58. 	list<int>::iterator pos2 = lt.begin();
    59. 	lt.erase(pos2);
    60. 	lt.pop_back();
    61.  
    62. 	for (auto e : lt) {
    63. 		cout << e << " ";
    64. 	}
    65. }
    66. void test5() {
    67. 	list<int> lt1(5,1);
    68. 	list<int> lt2(3,0);
    69. 	lt2 = lt1;
    70. 	for (auto e : lt2) {
    71. 		cout << e << " ";
    72. 	}
    73. 	cout << endl;
    74.  
    75. 	list<int> lt3=lt1; 
    76. 	for (auto e : lt3) {
    77. 		cout << e << " ";
    78. 	}
    79. }
    80. int main()
    81. {
    82. 	//test1();
    83. 	//test2();
    84. 	//test3();
    85. 	//test4();
    86. 	test5();
    87. 	return 0;
    88. }
     

     

    四、对比vector和list
     

    vector：
     

    vector是一个动态增长的数组。
     

    优点：能够随机访问，所以可以很好地支持排序、堆算法、二分查找等。
     

    缺点：中间插入元素的效率低，因为要先挪动数据；空间不够了，增容要付出的代价大，你要开新空间、拷数据、释放旧空间，不方便。
     

     

    list：
     

    list是一个带头双向循环的链表。
     

    优点：任意位置插入、删除效率高，时复O(1)。
     

    缺点：不支持随机访问。
     

     

    总结来看，vector和list是互补的容器。
    
                
    
                    
    
                
    • 

                
  • 

                    相关阅读:
    
                    
C++深搜例题代码加讲解                            
    
快速入门logback日志框架与SpringEvent事件通知机制                            
    
16. python-es-8.3.3-重要或异常词项聚合significant_terms                            
    
虚拟机设置固定ip                            
    
搞懂索引，真的很重要                            
    
Netty UDP不能发送大于2048字节包的问题                            
    
【BOOST C++】教程2：最简程序段（Hello World)                            
    
通过添加注解实现按顺序输出类属性                            
    
C语言数据结构---时间复杂度、空间复杂度                            
    
10. Spring Boot配置加载顺序                            
    
                        
                
    • 
                
  • 
                    原文地址：https://blog.csdn.net/2301_76540463/article/details/134052569
                
    •