STL容器之list类

STL容器之list类

1、list的介绍

• list是序列容器，允许在序列中的任何地方进行常数时间插入和删除操作，以及双向迭代。

• list容器是由双向链表实现；双向链表可以将它们包含的每个元素存储在不同和不相关的存储位置。在节点中通过指针指向其前一个元素和后一个元素。

• list与forward_list非常相似：主要区别在于forward_list对象是单链表，只能朝前迭代，以让其更简单高效。

• 与其他基本标准序列容器（array、vector和deque）相比，list可以在任何位置插入、提取和移动元素方面通常表现更好，因此在密集使用这些元素的算法（如排序算法）中也表现更好。

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

• list底层是带头双向循环链表。

  

---

2、list的使用

2.1、list的常见构造

(constructor )函数名称	接口说明
list (size_type n, const value_type& val = value_type())	构造一个长度为n的list，每个元素的值为val
list()	构造空的list
list (InputIterator first, InputIterator last)	用迭代区间[first,last)构造list
list (const list& x)	拷贝构造list

#include 

#include 

using namespace std;

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

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

    list<int> lt1(10,2);
    for (auto e: lt1) {
        cout << e << " ";
    }
    cout << endl;

    list<int> lt2(lt1.begin(),lt1.end());
    for (auto e: lt2) {
        cout << e << " ";
    }
    cout << endl;

    list<int> lt3(lt2);
    for (auto e: lt3) {
        cout << e << " ";
    }
    cout << endl;
    
}

int main() {
  
    test_list4();
    return 0;
  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

---

2.2、list的iterator的使用

函数名称	接口说明
begin()+end()	获取第一个元素位置的iterator/const_iterator和获取最后一个元素的后一个位置的iterator/const_iterator
rbegin()+rend()	获取最后一个元素位置的reverse_iterator/const_reverse_iterator和获取第一个元素的后一个位置的reverse_iterator/const_reverse_iterator

#include 

#include 

using namespace std;

void test_list5(){
 list<int> lt;
 lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(6);
   
    list<int>::iterator it = lt.begin();
 while(it != lt.end()){
        cout << *it << " ";
        ++it;
    }
    cout <<endl;
   
   
 list<int>::reverse_iterator rit = lt.rbegin();
 while(rit != lt.rend()){
        cout << *rit << " ";
        ++rit;
    }
    cout <<endl;
   }
   
int main() {

 test_list5();
   return 0;
   
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

2.3、list空间增长问题

函数名称	接口说明
empty	判断list是否为空
size	返回list长度/结点个数

#include 

#include 

using namespace std;

void test_list6() {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(6);

    cout << lt.size() << endl;
    cout << lt.empty() << endl;

    lt.assign(0,0);
    cout << lt.size() << endl;
    cout << lt.empty() << endl;
}

int main() {

 test_list6();
 return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

---

2.4、list的增删查改

函数名称	接口说明
front
back
push_front
pop_front
push_back
pop_back
insert
erase
swap
clear

#include 

#include 

using namespace std;

void test_list7() {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(6);

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

    cout << lt.front() << endl;
    cout << lt.back() << endl;

    lt.push_front(10);
    lt.push_back(9);
    for (auto e: lt) {
        cout << e << " ";
    }
    cout << endl;

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

    lt.insert(find(lt.begin(),lt.end(),4),40);
    for (auto e: lt) {
        cout << e << " ";
    }
    cout << endl;

    list<int>::iterator it = lt.erase(find(lt.begin(),lt.end(),6));
    for (auto e: lt) {
        cout << e << " ";
    }
    cout << endl;

    list<int> lt1(10,1);
    swap(lt,lt1);
    for (auto e: lt) {
        cout << e << " ";
    }
    cout << endl;

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

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

}

int main() {

 test_list7();
 return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

---

2.5、list迭代器失效问题

• list迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际是对指针进行了封装。

• 迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。

• 因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

  void TestListIterator1()
  {
      int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
      list<int> l(array, array+sizeof(array)/sizeof(array[0]));
      auto it = l.begin();
      while (it != l.end())
      {
          // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
  //        l.erase(it);
          it = l.erase(it);
          ++it;// 每次跳一个删除
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

---

3、list的模拟实现（含反向迭代器）

注意：list的模拟实现用到了比较多的模版，同时还用到了组合（其中之一就是反向迭代器的实现），相对于string和vector的模拟实现会更难。

• vector.h文件

  //
  // Created by 徐鹏 on 2023/12/10.
  //
    
  #include 
  #include 
  #include 
  #include 
    
  #include "ReverseIterator.h"
    
  using namespace std;
    
  #ifndef DEMO_01_VECTOR_H
  #define DEMO_01_VECTOR_H
    
  #endif //DEMO_01_VECTOR_H
    
  namespace xp {
      template<typename T>
      class vector {
      public:
          typedef T *iterator;
          typedef const T *const_iterator;
    
          typedef ReverseIterator<iterator, T &, T *> reverse_iterator;
          typedef ReverseIterator<const_iterator, const T &, const T *> const_reverse_iterator;
  
  
          vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}
  
  //        vector(const vector &v) {
  //            _start = new T[v.capacity()];
  //            memcpy(_start, v._start, v.size() * sizeof(T));
  //            _finish = _start + v.size();
  //            _end_of_storage = _start + capacity();
  //        }
  
          //拷贝构造函数
          vector(const vector<T> &v) {
              reserve(v.capacity());
              for (const auto &e: v) {
                  push_back(e);
              }
          }
      
          template<class InputIterator>
          //构造迭代器区间
          vector(InputIterator first, InputIterator last) {
              while (first != last) {
                  push_back(*first);
                  ++first;
              }
          }
      
          vector(size_t n, const T &val = T()) {
              resize(n, val);
          }
      
          //防止和上面迭代器区间搞混
          vector(int n, const T &val = T()) {
              resize(n, val);
          }
      
          //赋值 ,这里vector v在传值的时候就已经有拷贝构造了
          vector<T> &operator=(vector<T> v) {
              swap(v);
              return *this;
          }
      
          T &operator[](size_t n) {
              return *(_start + n);
          }
      
          const T &operator[](size_t n) const {
              return *(_start + n);
          }
      
          ~vector() {
              if (_start) {
                  delete[] _start;
                  _start = _finish = _end_of_storage = nullptr;
              }
          }
      
          void swap(vector<T> v) {
              std::swap(_start, v._start);
              std::swap(_finish, v._finish);
              std::swap(_end_of_storage, v._end_of_storage);
          }
      
          void reserve(size_t n) {
              if (n > capacity()) {
                  //开辟新空间
                  size_t old_size = size();
                  iterator tmp = new T[n];
                  //start不为空，在复制完内容需要释放空间
                  if (_start) {
  //                    //对于自定义类型，在进行delete[] _start 之后（自定义类型里面存在指针开辟空间问题的时候），会把原来的_start里面内容进行析构和空间释放
  //                    memcpy(tmp, _start, old_size * sizeof(T));
  
                      //  解决方案，进行深拷贝
                      for (size_t i = 0; i < old_size; ++i) {
                          tmp[i] = _start[i];
                      }
                      delete[] _start;
                  }
                  _start = tmp;
                  //这里要注意，得用之前的size，不然新size使用内联进来就是_finish = _start + _finish - _start
                  _finish = _start + old_size;
                  _end_of_storage = _start + n;
              }
          }
      
          void resize(size_t n, T val = T()) {
              if (n > capacity()) {
                  size_t fill = _start + n - _finish;
                  reserve(n);
                  //填补之前finish后面fill个数据
                  while (fill != 0) {
                      *_finish = val;
                      _finish++;
                      fill--;
                  }
              }
          }
      
          void push_back(const T &val) {
              if (_finish == _end_of_storage) {
                  size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
                  reserve(newCapacity);
              }
              *_finish = val;
              ++_finish;
          }
      
          void pop_back() {
              --_finish;
          }
      
          void insert(iterator pos, const T &val) {
              assert(pos >= _start);
              assert(pos <= _finish);
      
              if (_finish == _end_of_storage) {
                  size_t len = pos - _start;
                  size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
                  reserve(newCapacity);
                  pos = _start + len;//防止增容量后，pos位置还是之前被释放的空间
              }
              //memmove(pos + 1, pos, sizeof(T) * (_finish - pos)); //浅拷贝，扩容可能存在迭代器失效问题
              iterator end = _finish - 1;
              while (pos <= end) {
                  *(end + 1) = *end;
                  --end;
              }
              *pos = val;
              ++_finish;
          }
      
          iterator begin() {
              return _start;
          }
      
          const_iterator begin() const {
              return _start;
          }
      
          iterator end() {
              return _finish;
          }
      
          const_iterator end() const {
              return _finish;
          }
      
          reverse_iterator rbegin() {
              return end();
          }
      
          const_reverse_iterator rbegin() const {
              return end();
          }
      
          reverse_iterator rend() {
              return begin();
          }
      
          const_reverse_iterator rend() const{
              return begin();
          }
  
  
          size_t size() const {
              return _finish - _start;
          }
      
          size_t capacity() const {
              return _end_of_storage - _start;
          }
      
      private:
          iterator _start = nullptr;
          iterator _finish = nullptr;
          iterator _end_of_storage = nullptr;
      };
      
      void test_vector1() {
          vector<char> v;
          v.reserve(10);
          cout << v.size() << " " << v.capacity() << endl;
  //        v.resize(100);
          v.resize(100, 'x');
          cout << v.size() << " " << v.capacity() << endl;
  
      }
      
      void test_vector2() {
          vector<int> v;
          v.push_back(1);
          v.push_back(2);
          v.push_back(3);
          v.push_back(4);
          v.push_back(5);
          for (auto e: v) {
              cout << e << " ";
          }
          cout << endl;
      }
      
      void test_vector3() {
          vector<string> v;
          v.push_back("hh");
          v.insert(v.begin(), "2");
          v.insert(v.begin(), "2");
          v.insert(v.begin(), "2");
          v.insert(v.begin(), "2");
          v.insert(v.begin(), "2");
          v.insert(v.begin(), "2");
          v.insert(v.begin(), "2");
          v.insert(v.begin(), "2");
          for (auto e: v) {
              cout << e << " ";
          }
          cout << endl;
      }
      
      void test_vector4() {
          vector<string> v1;
          v1.push_back("hhh");
          v1.push_back("www");
          for (auto e: v1) {
              cout << e << " ";
          }
          cout << endl;
      
          vector<string> v2;
          v2.push_back("lllll");
          v2.push_back("nnnnn");
          for (auto e: v2) {
              cout << e << " ";
          }
          cout << endl;
          cout << "----------------------" << endl;
          v1 = v2;
          for (auto e: v1) {
              cout << e << " ";
          }
          cout << endl;
          for (auto e: v2) {
              cout << e << " ";
          }
          cout << endl;
      
      }
      
      void test_vector5() {
          vector<string> v;
          v.push_back("w");
          v.push_back("s");
          v.push_back("x");
          v.push_back("p");
          cout << v[1] << endl;
      }
      
      void test_vector6() {
          vector<string> v;
          v.push_back("w");
          v.push_back("s");
          v.push_back("x");
          v.push_back("p");
          v.push_back("p");
          v.push_back("p");
          v.push_back("p");
          v.push_back("p");
          v.push_back("psdf");
          v.push_back("pdsf");
          v.push_back("pfd");
          v.push_back("pdsf");
          v.insert(v.begin(), "sdas");
          for (auto e: v) {
              cout << e << " ";
          }
          cout << endl;
      }
      
      void test_vector7() {
          vector<string> v;
          v.push_back("w");
          v.push_back("s");
          v.push_back("x");
          v.push_back("p");
          v.push_back("p");
          v.push_back("p");
          vector<string> v2(v.begin(), v.end());
          for (auto e: v2) {
              cout << e << " ";
          }
          cout << endl;
      
          int a[] = {1111, 222, 222, 3};
          vector<int> v3(a, a + 4);
          for (auto e: v3) {
              cout << e << " ";
          }
          cout << endl;
      
          list<string> lt;
          lt.push_back("hjakds");
          lt.push_back("wq");
          lt.push_back("qw");
          lt.push_back("w");
      
          vector<string> v4(lt.begin(), lt.end());
          for (auto e: v4) {
              cout << e << " ";
          }
          cout << endl;
      
          vector<int> v5(5, 5);
          for (auto e: v5) {
              cout << e << " ";
          }
          cout << endl;
      }
      
      void test_vector8() {
          vector<int> v;
          v.push_back(1);
          v.push_back(2);
          v.push_back(3);
          v.push_back(4);
          v.push_back(5);
      
          vector<int>::reverse_iterator rit = v.rbegin();
          while (rit != v.rend()) {
              cout << *rit << " ";
              rit++;
          }
          cout << endl;
      }
  
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  145
  146
  147
  148
  149
  150
  151
  152
  153
  154
  155
  156
  157
  158
  159
  160
  161
  162
  163
  164
  165
  166
  167
  168
  169
  170
  171
  172
  173
  174
  175
  176
  177
  178
  179
  180
  181
  182
  183
  184
  185
  186
  187
  188
  189
  190
  191
  192
  193
  194
  195
  196
  197
  198
  199
  200
  201
  202
  203
  204
  205
  206
  207
  208
  209
  210
  211
  212
  213
  214
  215
  216
  217
  218
  219
  220
  221
  222
  223
  224
  225
  226
  227
  228
  229
  230
  231
  232
  233
  234
  235
  236
  237
  238
  239
  240
  241
  242
  243
  244
  245
  246
  247
  248
  249
  250
  251
  252
  253
  254
  255
  256
  257
  258
  259
  260
  261
  262
  263
  264
  265
  266
  267
  268
  269
  270
  271
  272
  273
  274
  275
  276
  277
  278
  279
  280
  281
  282
  283
  284
  285
  286
  287
  288
  289
  290
  291
  292
  293
  294
  295
  296
  297
  298
  299
  300
  301
  302
  303
  304
  305
  306
  307
  308
  309
  310
  311
  312
  313
  314
  315
  316
  317
  318
  319
  320
  321
  322
  323
  324
  325
  326
  327
  328
  329
  330
  331
  332
  333
  334
  335
  336
  337
  338
  339
  340
  341
  342
  343
  344
  345
  346
  347
  348
  349
  350
  351
  352
  353
  354
  355
  356
  357
  358
  359
  360
  361
  362
  363

• list.h文件

  //
  // Created by 徐鹏 on 2024/3/3.
  //
  
  #ifndef DEMO_05_LIST_H
  #define DEMO_05_LIST_H
  
  #endif //DEMO_05_LIST_H
  
  #include "ReverseIterator.h"
  #include 
  
  using namespace std;
  
  
  // list的模拟实现(还未完成)
  
  namespace xp {
  
      // 结点
      template<class T>
      struct ListNode {
          ListNode<T> *_next;
          ListNode<T> *_prev;
          T data;
  
          // 构造函数  -- 创建结点
          ListNode(const T val = T()) : _next(nullptr), _prev(nullptr), data(val) {
  
          }
      };
  
      template<class T, class Ref, class Ptr>
      class __list_iterator {
      public:
          typedef ListNode<T> Node;
          typedef __list_iterator<T, Ref, Ptr> self; // 迭代器本身
  
          // 这里构造函数为了方便begin和end，直接隐式类型转换
          __list_iterator(Node *node) : _node(node) {
  
          }
  
          Ref operator*() {
              return _node->data;
          }
  
          Ptr operator->() {
              return &_node->data;
          }
  
          self &operator++() {
              _node = _node->_next;
              return *this;
          }
  
          self operator++(int) {
              self temp(*this); // 这里*this的类型是self ,调用默认拷贝构造函数！因为是内置类型，不需要自己写
              _node = _node->_next;
              return temp;
          }
  
          self &operator--() {
              _node = _node->_prev;
              return *this;
          }
  
          self &operator--(int) {
              self temp(*this);
              _node = _node->_prev;
              return temp;
          }
  
          bool operator!=(const self &s) {
              return _node != s._node;
          }
  
          bool operator==(const self &s) {
              return _node == s._node;
          }
  
          // 拷贝构造和析构不需要写，析构不能用，不然结点被删除了
  
          // 比如 lt.begin()，这里的类型就是Node*
          Node *_node; // 内置类型不能重载++等操作符，因此对这个内置类型进行封装来实现++等功能
      };
  
  //    template
  //    class __list_const_iterator {
  //    public:
  //        typedef ListNode Node;
  //        typedef __list_const_iterator self; // 迭代器本身
  //
  //        // 这里构造函数为了方便begin和end，直接隐式类型转换
  //        __list_const_iterator(Node *node) : _node(node) {
  //
  //        }
  //
  //        const T &operator*() {
  //            return _node->data;
  //        }
  //
  //        self &operator++() {
  //            _node = _node->_next;
  //            return *this;
  //        }
  //
  //        self operator++(int) {
  //            self temp(*this); // 这里*this的类型是self ,调用默认拷贝构造函数！因为是内置类型，不需要自己写
  //            _node = _node->_next;
  //            return temp;
  //        }
  //
  //        self &operator--() {
  //            _node = _node->_prev;
  //            return *this;
  //        }
  //
  //        self &operator--(int) {
  //            self temp(*this);
  //            _node = _node->_prev;
  //            return temp;
  //        }
  //
  //        bool operator!=(const self &s) {
  //            return _node != s._node;
  //        }
  //
  //        bool operator==(const self &s) {
  //            return _node == s._node;
  //        }
  //
  //        // 拷贝构造和析构不需要写，析构不能用，不然结点被删除了
  //
  //        // 比如 lt.begin()，这里的类型就是Node*
  //        Node *_node; // 内置类型不能重载++等操作符，因此对这个内置类型进行封装来实现++等功能
  //    };
  
      template<class T>
      class list {
      public:
          typedef ListNode<T> Node;
          typedef __list_iterator<T, T &, T *> iterator;
          typedef __list_iterator<T, const T &, const T *> const_iterator;
  
          typedef ReverseIterator<iterator, const T &, const T *> reverse_iterator;
          typedef ReverseIterator<const_iterator, const T &, const T *> const_reverse_iterator;
  
          //构造函数
          list() {
              //创建带头节点的双向循环链表
              _head = new Node;
              _head->_next = _head;
              _head->_prev = _head;
          }
  
          // 拷贝构造函数
          list(list<T> &lt) {
              // 先创个头节点
              _head = new Node;
              _head->_next = _head;
              _head->_prev = _head;
  
              iterator it = lt.begin();
              while (it != lt.end()) {
                  push_back(*it);
                  ++it;
              }
          }
  
          void swap(list<T> &lt) {
              std::swap(_head, lt._head);
          }
  
          // 赋值
          list<T> operator=(list<T> lt) {
              swap(lt);
              return *this;
          }
  
          iterator begin() {
              return _head->_next;
          }
  
          iterator end() {
              return _head;
          }
  
          const_iterator begin() const {
              return _head->_next;
          }
  
          const_iterator end() const {
              return _head;
          }
  
          reverse_iterator rbegin() {
              return end();
          }
  
          reverse_iterator rend() {
              return begin();
          }
  
          const_reverse_iterator rbegin() const {
              return end();
          }
  
          const_reverse_iterator rend() const {
              return begin();
          }
  
          void push_back(const T &val) {
  //            Node *tail = _head->_prev;// 先找到尾
  //
  //            // 创建新节点
  //            Node *newnode = new Node(val);
  //
  //            tail->_next = newnode;
  //            newnode->_prev = tail;
  //
  //            newnode->_next = _head;
  //            _head->_prev = newnode;
  
              insert(end(), val);
          }
  
          iterator insert(iterator pos, const T &val) {
  
              Node *cur = pos._node;
              Node *prev = cur->_prev;
              Node *newnode = new Node(val);
  
              newnode->_next = cur;
              newnode->_prev = prev;
              prev->_next = newnode;
              cur->_prev = newnode;
  
              return newnode;
          }
  
          iterator erase(iterator pos) {
              assert(pos != _head);// _head这个位置就是end()
  
              Node *cur = pos._node;
              Node *prev = cur->_prev;
              Node *tail = cur->_next;
  
              prev->_next = tail;
              tail->_prev = prev;
  
              delete cur;
  
              return tail;
          }
  
          void clear() {
              // 清空所有数据，只留一个头节点
              iterator it = begin();
              while (it != end()) {
                  it = erase(begin());
              }
          }
  
          ~list() {
              clear();
              if (_head) {
                  delete _head;
                  _head = nullptr;
              }
  
          }
  
      private:
          Node *_head;// 头节点 -- 带头双向循环链表
      };
  
      void test_list1() {
          list<int> lt;
          lt.push_back(1);
          lt.push_back(2);
          lt.push_back(3);
          lt.push_back(4);
          lt.push_back(5);
  
          list<int>::iterator it = lt.begin();
          while (it != lt.end()) {
              cout << *it << " ";
              it++;
          }
          cout << endl;
  
          lt.insert(lt.begin(), 10);
          lt.insert(lt.begin(), 20);
          lt.insert(lt.begin(), 30);
  
          for (auto e: lt) {
              cout << e << " ";
          }
          cout << endl;
  
          lt.erase(--lt.end());
          lt.erase(--lt.end());
          for (auto e: lt) {
              cout << e << " ";
          }
          cout << endl;
  
          lt.clear();
          for (auto e: lt) {
              cout << e << " ";
          }
          cout << endl;
      }
  
      void test_list2() {
          list<int> lt;
          lt.push_back(1);
          lt.push_back(2);
          lt.push_back(3);
          lt.push_back(4);
          lt.push_back(5);
  
          list<int> lt1(lt);
          for (auto e: lt1) {
              cout << e << " ";
          }
          cout << endl;
  
          list<int> lt2 = lt;
          for (auto e: lt2) {
              cout << e << " ";
          }
          cout << endl;
      }
  
  
      //  测试const迭代器
      void Print_list(const list<int> &lt) {
          list<int>::const_iterator it = lt.begin();
  
          while (it != lt.end()) {
              cout << *it << " ";
              ++it;
          }
          cout << endl;
      }
  
      void test_list3() {
          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;
  
          Print_list(lt);
      }
  
  
      // 测试list重载->运算符
      struct AA {
          AA(int a1 = 3, int a2 = 4) : _a1(a1), _a2(a2) {
  
          }
  
          int _a1 = 1;
          int _a2 = 2;
      };
  
      void test_list4() {
          list<AA> lt;
          lt.push_back(AA());
          lt.push_back(AA(2, 1));
          lt.push_back(AA(5, 5));
  
          list<AA>::iterator it = lt.begin();
          while (it != lt.end()) {
              cout << (*it)._a1 << " " << (*it)._a2 << endl;
              cout << it->_a1 << " " << it->_a2 << endl;
              cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;//原型，即运算符重载->省略了一个->
              ++it;
          }
      }
  
      void test_list5() {
          list<int> lt;
          lt.push_back(1);
          lt.push_back(2);
          lt.push_back(3);
          lt.push_back(4);
          lt.push_back(5);
  
          list<int>::reverse_iterator rit = lt.rbegin();
          while (rit != lt.rend()) {
              cout << *rit << " ";
              ++rit;
          }
          cout << endl;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  145
  146
  147
  148
  149
  150
  151
  152
  153
  154
  155
  156
  157
  158
  159
  160
  161
  162
  163
  164
  165
  166
  167
  168
  169
  170
  171
  172
  173
  174
  175
  176
  177
  178
  179
  180
  181
  182
  183
  184
  185
  186
  187
  188
  189
  190
  191
  192
  193
  194
  195
  196
  197
  198
  199
  200
  201
  202
  203
  204
  205
  206
  207
  208
  209
  210
  211
  212
  213
  214
  215
  216
  217
  218
  219
  220
  221
  222
  223
  224
  225
  226
  227
  228
  229
  230
  231
  232
  233
  234
  235
  236
  237
  238
  239
  240
  241
  242
  243
  244
  245
  246
  247
  248
  249
  250
  251
  252
  253
  254
  255
  256
  257
  258
  259
  260
  261
  262
  263
  264
  265
  266
  267
  268
  269
  270
  271
  272
  273
  274
  275
  276
  277
  278
  279
  280
  281
  282
  283
  284
  285
  286
  287
  288
  289
  290
  291
  292
  293
  294
  295
  296
  297
  298
  299
  300
  301
  302
  303
  304
  305
  306
  307
  308
  309
  310
  311
  312
  313
  314
  315
  316
  317
  318
  319
  320
  321
  322
  323
  324
  325
  326
  327
  328
  329
  330
  331
  332
  333
  334
  335
  336
  337
  338
  339
  340
  341
  342
  343
  344
  345
  346
  347
  348
  349
  350
  351
  352
  353
  354
  355
  356
  357
  358
  359
  360
  361
  362
  363
  364
  365
  366
  367
  368
  369
  370
  371
  372
  373
  374
  375
  376
  377
  378
  379
  380
  381
  382
  383
  384
  385
  386
  387
  388
  389
  390
  391
  392
  393
  394
  395
  396
  397
  398
  399
  400
  401
  402
  403
  404
  405
  406

• ReverseIterator.h文件

  //
  // Created by 徐鹏 on 2024/3/11.
  //
    
  #ifndef DEMO_05_REVERSEITERATOR_H
  #define DEMO_05_REVERSEITERATOR_H
    
  #endif //DEMO_05_REVERSEITERATOR_H
  
  
  template<class Iterator, class Ref, class Ptr>
  struct ReverseIterator {
      typedef ReverseIterator<Iterator, Ref, Ptr> self;
  
      ReverseIterator(Iterator it) : _it(it) {
      
      }
  
  
      // 这里我们采用和正向迭代器对称的结构
      Iterator _it;
      
      Ref operator*() {
          Iterator tmp = _it;// 不能改变_it的位置，用tmp来指向_it的位置，来改变tmp的位置
          --tmp;
          return *tmp;
      }
      
      Ptr operator->() {
          return &(operator*());
      }
      
      self &operator++() {
          --_it;
          return *this;
      }
      
      self operator++(int) {
          self tmp(*this);
          --_it;
          return tmp;
      }
      
      self &operator--() {
          ++_it;
          return *this;
      }
      
      self operator--(int) {
          self tmp(*this);
          ++_it;
          return tmp;
      }
      
      bool operator!=(const self &s) {
          return _it != s._it;
      }
      
      bool operator==(const self &s) {
          return _it == s._it;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62

• main.cpp文件

  #include "list.h"
  
  int main() {
  //    xp::test_list1();
  //    xp::test_list2();
  //    xp::test_list3();
  //    xp::test_list4();
      xp::test_list5();
      return 0;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

---

OKOK，C++ STL容器之list类就到这里。如果你对Linux和C++也感兴趣的话，可以看看我的主页哦。下面是我的github主页，里面记录了我的学习代码和leetcode的一些题的题解，有兴趣的可以看看。

Xpccccc的github主页