C++标准模板库--list

list

介绍

        list 是序列容器，允许在序列内的任何位置进行常量时间的插入和删除操作，以及两个方向的迭代。列表容器被实现为双向带头链表；双链表可以将它们包含的每个元素存储在差别且不相关的存储位置。排序是通过与前面元素的链接和反面元素的链接的每个元素的关联在内部保持的。它们与 forward_list非常相似：主要区别在于forward_list对象是单链表，因此它们只能向前迭代，以调换更小和更高效。与其他根本标准序列容器（array、vector和deque）相比，list 在容器内的任何位置插入、提取和移动元素（迭代器已经得到）方面通常体现更好，因此在大量使用列表的算法（如排序算法）中也体现更好。与其他序列容器相比，list 和 forward_list的主要缺点是它们无法通过位置直接访问元素；比方，要访问列表中的第六个元素，必须从已知位置（如开始或结束）迭代到该位置，这必要在两者之间的间隔上花费线性时间。它们还斲丧一些额外的内存来生存与每个元素相关联的链接信息（对于包含小元素的大型列表来说，这可能是一个告急因素）。
        根据官方对 list 的介绍，我们可以相识到 list 中使用的是双向带头链表，其优点有高效的元素插入和删除、双向遍历、迭代器失效题目较小、顺应性强等。 

---

使用

         list的构造

函数名称接口说明list (size_type n, const value_type& val = value_type())构造的list中包含n个值为val的元素list()构造空的listlist (const list& x)拷贝构造函数list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list 代码演示：

1. // list的构造
2. void TestList1()
3. {
4.     list<int> l1;                         // 构造空的l1
5.     list<int> l2(4, 100);                 // l2中放4个值为100的元素
6.     list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3
7.     list<int> l4(l3);                    // 用l3拷贝构造l4
9.     // 以数组为迭代器区间构造l5
10.     int array[] = { 16,2,77,29 };
11.     list<int> l5(array, array + sizeof(array) / sizeof(int));
13.     // 列表格式初始化C++11
14.     list<int> l6{ 1,2,3,4,5 };
16.     // 用迭代器方式打印l5中的元素
17.     list<int>::iterator it = l5.begin();
18.     while (it != l5.end())
19.     {
20.         cout << *it << " ";
21.         ++it;
22.     }
23.     cout << endl;
25.     // C++11范围for的方式遍历
26.     for (auto& e : l5)
27.         cout << e << " ";
29.     cout << endl;
30. }

复制代码

        list迭代器的使用

函数名称接口说明begin+end返回第一个元素的迭代器+返回末了一个元素的下一个位置的迭代器rbegin+rend返回末了一个元素的迭代器，即end-1，返回末了一个元素下一个位置的迭代器即begin-1位置 注意：
1. begin与end为正向迭代器，对迭代器实验++操作，迭代器向后(右)移动。
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器实验++操作，迭代器向前(左)移动。
代码演示：

1. // list迭代器的使用
2. // 注意：遍历链表只能用迭代器和范围for
3. void PrintList(const list<int>& l)
4. {
5.     // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
6.     for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
7.     {
8.         cout << *it << " ";
9.         // *it = 10; 编译不通过
10.     }
12.     cout << endl;
13. }
15. void TestList2()
16. {
17.     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
18.     list<int> l(array, array + sizeof(array) / sizeof(array[0]));
19.     // 使用正向迭代器正向list中的元素
20.     // list<int>::iterator it = l.begin();   // C++98中语法
21.     auto it = l.begin();                     // C++11之后推荐写法
22.     while (it != l.end())
23.     {
24.         cout << *it << " ";
25.         ++it;
26.     }
27.     cout << endl;
29.     // 使用反向迭代器逆向打印list中的元素
30.     // list<int>::reverse_iterator rit = l.rbegin();
31.     auto rit = l.rbegin();
32.     while (rit != l.rend())
33.     {
34.         cout << *rit << " ";
35.         ++rit;
36.     }
37.     cout << endl;
38. }

复制代码

        list的容量与首尾

函数名称接口说明empty检测 list 是否为空，是返回 true，否则返回 false。size返回list中的有效节点的个数。front返回list第一个节点中的值的引用back返回list末了一恶搞节点中的值的引用         list的增删查改

函数名称接口说明push_front在list首元素前插入值val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中末了一个元素insert在list中pos的位置中插入置为val的元素erase删除list中在pos位置的元素swap互换两个list中的元素clear清空list中的有效元素 代码演示：

1. // list插入和删除
2. // push_back/pop_back/push_front/pop_front
3. void TestList3()
4. {
5.     int array[] = { 1, 2, 3 };
6.     list<int> L(array, array + sizeof(array) / sizeof(array[0]));
8.     // 在list的尾部插入4，头部插入0
9.     L.push_back(4);
10.     L.push_front(0);
11.     PrintList(L);
13.     // 删除list尾部节点和头部节点
14.     L.pop_back();
15.     L.pop_front();
16.     PrintList(L);
17. }
19. // insert /erase
20. void TestList4()
21. {
22.     int array1[] = { 1, 2, 3 };
23.     list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));
25.     // 获取链表中第二个节点
26.     auto pos = ++L.begin();
27.     cout << *pos << endl;
29.     // 在pos前插入值为4的元素
30.     L.insert(pos, 4);
31.     PrintList(L);
33.     // 在pos前插入5个值为5的元素
34.     L.insert(pos, 5, 5);
35.     PrintList(L);
37.     // 在pos前插入[v.begin(), v.end)区间中的元素
38.     vector<int> v{ 7, 8, 9 };
39.     L.insert(pos, v.begin(), v.end());
40.     PrintList(L);
42.     // 删除pos位置上的元素
43.     L.erase(pos);
44.     PrintList(L);
46.     // 删除list中[begin, end)区间中的元素，即删除list中的所有元素
47.     L.erase(L.begin(), L.end());
48.     PrintList(L);
49. }
51. // resize/swap/clear
52. void TestList5()
53. {
54.     // 用数组来构造list
55.     int array1[] = { 1, 2, 3 };
56.     list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
57.     PrintList(l1);
59.     // 交换l1和l2中的元素
60.     list<int> l2;
61.     l1.swap(l2);
62.     PrintList(l1);
63.     PrintList(l2);
65.     // 将l2中的元素清空
66.     l2.clear();
67.     cout << l2.size() << endl;
68. }

复制代码

        list的迭代器失效题目

        此处各人可以将迭代器暂时明白成雷同于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头节点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效。而且失效的只是只想被删除节点的迭代器，其他迭代器不会受到影响。
代码演示：

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

复制代码

---

list底层的模仿实现

框架：

1.         template<class T>
2.         struct list_node
3.         {
4.                 T _data;
5.                 list_node<T>* _next;
6.                 list_node<T>* _prev;
7.         };
9.         template<class T, class Ref, class Ptr>
10.         struct list_iterator
11.         {
12.                 typedef list_node<T> Node;
13.                 typedef list_iterator<T, Ref, Ptr> Self;
14.                 Node* _node;
15.         };
16.         template<class T>
17.         class list
18.         {
19.         //typedef后的Node受访问限定符的影响。
20.                 typedef list_node<T> Node;
21.         public:
22.                 //迭代器
23.                 typedef list_iterator<T, T&, T*> iterator;
24.                 typedef list_iterator<T, const T&, const T*> const_iterator;
26.         private:
27.                 Node* _head;
28.                 size_t _size;
29.         };

复制代码

解析：

• list_node 类：是一个模板结构，存储恣意类型 T 的数据。此中_data是存储节点的数据；_next是指向下一个节点的指针；_prev是指向前一个节点的指针。
  
• list_iterator 类：是一个模板结构，使用三个类型参数 T、Ref（引用类型）、Ptr（指针类型）。此中Node：为 list_node<T>的重定名，方便在迭代器中使用；Self：为list_iterator<T, Ref, Ptr>的重定名，使得在迭代器中可以使用自身的类型；_node是指向当前迭代器所指向的节点。
  
• list 类：是一个模板类，存储类型 T 的元素。此中Node：为 list_node<T>的重定名，便于使用；iterator：定义为 list_iterator<T, T&, T*>，表现指向 T 类型元素的可修改迭代器；const_iterator：定义为 list_iterator<T, const T&, const T*>，表现指向 T 类型元素的只读迭代器。_head：是指向链表头部的节点指针；_size：记录链表中节点的数目。
  

        本质上是以 list 类为主体，先封装了一个 list_node 类用于记录链表节点的值、前驱指针和后继指针；后封装了一个 list_iterator 迭代器，迭代器以三参数模板可以根据必要灵活调整类型，这里分别构造了平凡迭代器和 const 迭代器，满足了差别的访问需求；而且只需定义一个模板类 list_iterator，就能创建差别类型的迭代器，减少重复代码。
默认成员函数

1.         template<class T>
2.         struct list_node
3.         {
4.                 T _data;
5.                 list_node<T>* _next;
6.                 list_node<T>* _prev;
7.                 //默认构造
8.                 list_node(const T& x = T())
9.                         :_data(x)
10.                         ,_next(nullptr)
11.                         ,_prev(nullptr)
12.                 {}
13.         };
15.         template<class T, class Ref, class Ptr>
16.         struct list_iterator
17.         {
18.                 typedef list_node<T> Node;
19.                 typedef list_iterator<T, Ref, Ptr> Self;
20.                 Node* _node;
21.                 //带参构造
22.                 list_iterator(Node* node)
23.                         :_node(node)
24.                 {}
25.         };
28.         template<class T>
29.         class list
30.         {
31.                 typedef list_node<T> Node;
32.         public:
33.                 //初始化空链表
34.                 void empty_init()
35.                 {
36.                         _head = new Node();
37.                         _head->_next = _head;
38.                         _head->_prev = _head;
39.                         _size = 0;
40.                 }
41.                 //默认构造
42.                 list()
43.                 {
44.                         empty_init();
45.                 }
46.                 //initializer_list
47.                 list(initializer_list<T>& li)
48.                 {
49.                         empty_init();
50.                         for (auto& e : li)
51.                         {
52.                                 push_back(e);
53.                         }
54.                 }
55.                 //拷贝构造
56.                 list(const list<T>& lt)
57.                 {
58.                         empty_init();
59.                         for (auto& e : lt)
60.                         {
61.                                 push_back(e);
62.                         }
63.                 }
64.                 //swap
65.                 void swap(list<T>& lt)
66.                 {
67.                         std::swap(_head, lt._head);
68.                         std::swap(_size, lt._size);
69.                 }
70.                 //赋值重载
71.                 list<T>& operator=(list<T> lt)
72.                 {
73.                         swap(lt);
74.                         return *this;
75.                 }
76.                 //clear
77.                 void clear()
78.                 {
79.                         auto it = begin();
80.                         while (it != end())
81.                         {
82.                                 it = erase(it);
83.                         }
84.                 }
85.                 //析构函数
86.                 ~list()
87.                 {
88.                         clear();
89.                         delete _head;
90.                         _head = nullptr;
91.                 }
92.         private:
93.                 Node* _head;
94.                 size_t _size;
95.         };

复制代码

list_node 中的默认构造函数：

• 默认参数：构造函数的参数 x 有一个默认值 T()，意味着如果没有提供值，节点的数据将被初始化为类型 T 的默认构造值（比方，对于内置类型，通常是 0）。
  
• 成员初始化：
  
  
  
  • _data 初始化为 x，允许用户在创建节点时传入特定值。
    
  • _next 和 _prev 初始化为 nullptr，表现新节点在链表中尚未毗连到其他节点。
    
  
  

list_iterator 中的构造函数：

• 带参构造：该构造函数接受一个指向 list_node 的指针，并将其赋值给成员变量 _node。这允许用户创建一个指向特定节点的迭代器，便于在链表中遍历。
  

 list 中的默认成员函数：

• 默认构造函数：空链表初始化，调用 empty_init() 方法，创建一个空的链表头节点，并将头节点的 _next 和 _prev 指针指向自身。_size 初始化为 0，表现链表当前没有元素。
  
• initializer_list 构造函数：允许使用初始化列表创建链表，通过 push_back 方法逐个插入元素。
  
• 拷贝构造函数：复制另一个链表的内容，同样调用 empty_init() 初始化新链表，然后逐个插入元素。
  
• 赋值运算符重载：通过传值方式吸收参数，利用拷贝构造函数创建一个暂时对象 lt，然后互换内部数据，确保赋值操作的安全性和高效性。
  
• 析构函数：资源管理，调用 clear() 清除所有节点，释放它们的内存，末了释放链表头节点的内存，避免内存泄漏。
  

迭代器类中的运算符重载函数 

2.         template<class T, class Ref, class Ptr>
3.         struct list_iterator
4.         {
5.                 typedef list_node<T> Node;
6.                 typedef list_iterator<T, Ref, Ptr> Self;
7.                 Node* _node;
8.                 //带参构造
9.                 list_iterator(Node* node)
10.                         :_node(node)
11.                 {}
13.                 Ref operator*()
14.                 {
15.                         return _node->_data;
16.                 }
17.                 Ptr operator->()
18.                 {
19.                         return &_node->_data;
20.                 }
21.                 Self& operator++()
22.                 {
23.                         node = _node->_next;
24.                         return *this;
25.                 }
26.                 Self operator++(int)
27.                 {
28.                         Self tmp(*this);
29.                         _node =  _node->_next;
30.                         return tmp;
31.                 }
32.                 Self& operator--()
33.                 {
34.                         node = _node->_prev;
35.                         return *this;
36.                 }
37.                 Self operator--(int)
38.                 {
39.                         Self tmp(*this);
40.                         _node = _node->_prev;
41.                         return tmp;
42.                 }
43.                 bool operator!=(const Self& node) const
44.                 {
45.                         return _node != node;
46.                 }
47.                 bool operator==(const Self& node) const
48.                 {
49.                         return _node == node;
50.                 }
51.         };

复制代码

list类中的常用函数：

1. //迭代器
2. typedef list_iterator<T, T&, T*> iterator;
3. typedef list_iterator<T, const T&, const T*> const_iterator;
5. iterator begin()
6. {
7.         return _head->_next;
8. }
9. iterator end()
10. {
11.         return _head;
12. }
13. const_iterator begin() const
14. {
15.         return _head->_next;
16. }
17. const_iterator end() const
18. {
19.         return _head;
20. }
21. //insert
22. iterator insert(iterator pos, const T& x)
23. {
24.         Node* cur = pos._node;
25.         Node* prev = cur->_prev;
27.         Node* newnode = new Node(x);
28.         newnode->_next = cur;
29.         newnode->_prev = prev;
30.         prev->_next = newnode;
31.         cur->_prev = newnode;
33.         ++_size;
34.         return newnode;
35. }
36. void push_back(const T& x)
37. {
38.         insert(end(), x);
39. }
40. void push_front(const T& x)
41. {
42.         insert(begin(), x);
43. }
45. //erase
46. iterator erase(iterator pos)
47. {
48.         Node* cur = pos._node;
49.         Node* prev = cur->_prev;
50.         Node* next = cur->_next;
52.         prev->_next = next;
53.         next->_prev = prev;
54.         delete cur;
56.         --_size;
57.         return next;
58. }
59. void pop_back()
60. {
61.         erase(--end());
62. }
63. void pop_front()
64. {
65.         erase(begin());
66. }
69. //size
70. size_t size() const
71. {
72.         return _size;
73. }
74. //empty
75. bool empty()
76. {
77.         return _size == 0;
78. }
79.         private:
80.                 Node* _head;
81.                 size_t _size;

复制代码

        这段代码实现了双向链表的迭代器、插入、删除、大小和空链表查抄的功能，确保链表可以或许灵活操作和高效管理节点。

• iterator：可修改元素的迭代器，指向链表中的节点。
  
• const_iterator：只读迭代器，确保不修改链表中的元素。
  
• begin()：返回指向链表第一个有效元素的迭代器（头节点的下一个节点）。
  
• end()：返回指向链表头节点的迭代器，表现链表的结束。
  
• insert(pos, x)：在指定位置 pos 插入新节点 x。
  
• push_back(x)：在链表末了插入元素 x，通过 insert(end(), x) 实现。
  
• push_front(x)：在链表开头插入元素 x，通过 insert(begin(), x) 实现。
  
• erase(pos)：删除指定位置的节点。
  
• pop_back()：删除链表末了的元素，通过 erase(--end()) 实现。
  
• pop_front()：删除链表开头的元素，通过 erase(begin()) 实现。
  
• size()：返回链表中元素的数目。
  
• empty()：查抄链表是否为空，返回布尔值。
  

---

完整代码展示：

1. #pragma once
2. #include<iostream>
3. #include<list>
4. #include<assert.h>
5. #include<algorithm>
6. using namespace std;
8. namespace zy
9. {
10.         template<class T>
11.         struct list_node
12.         {
13.                 T _data;
14.                 list_node<T>* _next;
15.                 list_node<T>* _prev;
16.                 //默认构造
17.                 list_node(const T& data = T())
18.                         :_data(data)
19.                         ,_next(nullptr)
20.                         ,_prev(nullptr)
21.                 {}
22.         };
23.        
24.         //template<class T>
25.         //struct list_const_iterator
26.         //{
27.         //        typedef list_node<T> Node;
28.         //        typedef list_const_iterator<T> Self;
29.         //       
30.         //        Node* _node;
32.         //        list_const_iterator(Node* node)
33.         //                :_node(node)
34.         //        {}
35.         //        // operator*
36.         //        const T& operator*()
37.         //        {
38.         //                return _node->_data;
39.         //        }
40.         //        // operator->
41.         //        const T* operator->()
42.         //        {
43.         //                return &_node->_data;
44.         //        }
45.         //        // operator++
46.         //        Self& operator++()
47.         //        {
48.         //                _node = _node->_next;
49.         //                return *this;
50.         //        }
51.         //        Self operator++(int)
52.         //        {
53.         //                Self tmp(*this);
54.         //                _node = _node->_next;
55.         //                return tmp;
56.         //        }
57.         //        // operator--
58.         //        Self& operator--()
59.         //        {
60.         //                _node = _node->_prev;
61.         //                return *this;
62.         //        }
63.         //        Self operator--(int)
64.         //        {
65.         //                Self tmp(*this);
66.         //                _node = _node->_prev;
67.         //                return tmp;
68.         //        }
69.         //        // operator!=
70.         //        bool operator!=(const Self& s)
71.         //        {
72.         //                return _node != s._node;
73.         //        }
74.         //};
75.         template<class T, class Ref, class Ptr>
76.         struct list_iterator
77.         {
78.                 typedef list_node<T> Node;
79.                 typedef list_iterator<T, Ref, Ptr> Self;
81.                 Node* _node;
83.                 list_iterator(Node* node)
84.                         :_node(node)
85.                 {}
86.                 // operator*
87.                 Ref operator*()
88.                 {
89.                         return _node->_data;
90.                 }
91.                 // operator->
92.                 Ptr operator->()
93.                 {
94.                         return &_node->_data;
95.                 }
96.                 // operator++
97.                 Self& operator++()
98.                 {
99.                         _node = _node->_next;
100.                         return *this;
101.                 }
102.                 Self operator++(int)
103.                 {
104.                         Self tmp(*this);
105.                         _node = _node->_next;
106.                         return tmp;
107.                 }
108.                 // operator--
109.                 Self& operator--()
110.                 {
111.                         _node = _node->_prev;
112.                         return *this;
113.                 }
114.                 Self operator--(int)
115.                 {
116.                         Self tmp(*this);
117.                         _node = _node->_prev;
118.                         return tmp;
119.                 }
120.                 // operator!=
121.                 bool operator!=(const Self& s) const
122.                 {
123.                         return _node != s._node;
124.                 }
126.                 // operator==
127.                 bool operator==(const Self& s) const
128.                 {
129.                         return _node == s._node;
130.                 }
131.         };
134.         template<class T>
135.         class list
136.         {
137.                 //typedef 也受访问限定符的限制
138.                 typedef list_node<T> Node;
139.         public:
140.                 void empty_init()
141.                 {
142.                         //设置哨兵位
143.                         _head = new Node();
144.                         _head->_next = _head;
145.                         _head->_prev = _head;
146.                 }
147.                 list()
148.                 {
149.                         empty_init();
150.                 }
151.                 list(initializer_list<T>& li)
152.                 {
153.                         empty_init();
154.                         for (auto& e : li)
155.                         {
156.                                 push_back(e);
157.                         }
158.                 }
159.                 //拷贝构造
160.                 list(const list<T>& lt)
161.                 {
162.                         empty_init();
163.                         auto it = lt.begin();
164.                         while (it != lt.end())
165.                         {
166.                                 push_back(it);
167.                                 ++it;
168.                         }
169.                 }
170.                 //swap
171.                 void swap(list<T>& lt)
172.                 {
173.                         std::swap(_head, lt._head);
174.                         std::swap(_size, lt._size);
175.                 }
177.                 //赋值重载
178.                 list<T>& operator=(list<T> lt)
179.                 {
180.                         swap(lt);
181.                         return *this;
182.                 }
184.                 //clear
185.                 void clear()
186.                 {
187.                         auto it = begin();
188.                         while (it != end())
189.                         {
190.                                 it = erase(it);
191.                         }
192.                 }
193.                 //析构
194.                 ~list()
195.                 {
196.                         clear();
197.                         delete _head;
198.                         _head = nullptr;
199.                 }
200.                 //iterator
201.                 typedef list_iterator<T, T&, T*> iterator;
202.                 typedef list_iterator<T, const T&, const T*> const_iterator;
204.                 iterator begin()
205.                 {
206.                         //使用迭代器类创建一个头结点的迭代器
207.                         /*iterator it(_head->_next);
208.                         return it;*/
210.                         //返回匿名对象
211.                         //return iterator(_head->_next);
213.                         //隐式类型转换，返回的节点由iterator类型接收
214.                         return _head->_next;
215.                 }
216.                 iterator end()
217.                 {
218.                         return _head;
219.                 }
220.                 const_iterator begin() const
221.                 {
222.                         return _head->_next;
223.                 }
224.                 const_iterator end() const
225.                 {
226.                         return _head;
227.                 }
229.                 //  push_back
230.                 void push_back(const T& x)
231.                 {
232.                         //new新节点
233.                         //Node* newnode = new Node(x);
234.                         //Node* tail = _head->_prev;
235.                         //插入新节点
236.                         //newnode->_prev = tail;
237.                         //newnode->_next = _head;
238.                         //tail->_next = newnode;
239.                         //_head->_prev = newnode;
240.                         //++_size;
242.                         //直接复用insert
243.                         insert(end(), x);
244.                 }
245.                 //push_front
246.                 void push_front(const T& x)
247.                 {
248.                         //直接复用insert
249.                         insert(begin(), x);
250.                 }
251.                
252.                 // insert
253.                 iterator insert(iterator pos, const T& x)
254.                 {
255.                         //        找到插入位置
256.                         Node* cur = pos._node;
257.                         Node* prev = cur->_prev;
258.                         //new出新节点
259.                         Node* newnode = new Node(x);
260.                         //进行连接
261.                         newnode->_prev = prev;
262.                         newnode->_next = cur;
263.                         cur->_prev = newnode;
264.                         prev->_next = newnode;
265.                         //++size
266.                         ++_size;
268.                         return newnode;
269.                 }
271.                 //pop_front
272.                 void pop_front()
273.                 {
274.                         erase(begin());
275.                 }
276.                 //pop_back
277.                 void pop_back()
278.                 {
279.                         erase(--end());
280.                 }
282.                 //erase
283.                 iterator erase(iterator pos)
284.                 {
285.                         //不能释放哨兵位
286.                         assert(pos != end());
287.                        
288.                         Node* node = pos._node;
289.                         Node* prev = node->_prev;
290.                         Node* next = node->_next;
292.                         prev->_next = next;
293.                         next->_prev = prev;
294.                         delete node;
296.                         --_size;
297.                         //隐式类型转换为iterator
298.                         return next;
299.                 }
302.                 // size
303.                 size_t size() const
304.                 {
305.                         return _size;
306.                 }
307.                 //empty
308.                 bool empty()
309.                 {
310.                         return _size == 0;
311.                 }
312.         private:
313.                 Node* _head;
314.                 size_t _size = 0;
315.         };
317.         // 打印函数
318.         template<class Container>
319.         void print_container(const Container& con)
320.         {
321.                 //auto it = con.begin();
322.                 typename Container::const_iterator it = con.begin();
323.                 while (it != con.end())
324.                 {
325.                         cout << *it << " ";
326.                         ++it;
327.                 }
328.                 cout << endl;
329.         }
331.         void  list_test1()
332.         {
333.                 list<int> lt;
334.                 lt.push_back(1);
335.                 lt.push_back(2);
336.                 lt.push_back(3);
337.                 lt.push_back(4);
338.                 lt.push_back(5);
340.                 list<int>::iterator it = lt.begin();
341.                 while (it != lt.end())
342.                 {
343.                         cout << *it << " ";
344.                         ++it;
345.                 }
346.                 cout << endl;
347.                 print_container(lt);
348.         }
349. }

复制代码

---

list 与 vector 的对比

vectorlist底层结构动态次序表，一段连续的空间带头节点的双向循环链表随机访问支持，访问单个的效率为O(1)不支持，访问单个元素的效率为O(1)插入和删除在恣意位置插入和删除效率低，必要搬移元素，时间复杂度为O(N)，插入时有可能必要增容，增容：开发新空间拷贝元素，释放旧空间，导致效率更低。恣意位置插入和删除效率高，不必要搬移元素，时间复杂度为O(1)。迭代器原生态指针独立封装的节点指针迭代器失效插入删除都可能会导致迭代器失效。只有删除会导致迭代器失效，但是不会影响反面的位置的迭代器。空间利用率空间利用率高，缓存利用率高空间利用率低，缓存利用率低使用场景必要高效储存，支持随机访问，不关心插入和删除效率大量插入删除，不关心随机访问

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。