STL-list

一、 list的先容
std::list 是 C++ 标准模板库（STL）中的一种双向链表容器。每个元素包罗指向前后节点的指针，支持高效插入和删除利用，但随机访问性能较差。

 

 

 

 

1. list是可以在常数范围内在任意位置举行插入和删除的序列式容器，而且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简朴高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置举行插入、移除元素的实行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，好比：要访问list的第6个元素，必须从已知的位置(好比头部大概尾部)迭代到该位置，在这段位置上迭代必要线性的时间开销；list还必要一些额外的空间，以保存每个节点的相关联信息(对于存储范例较小元素的大list来说这大概是一个重要的因素

 二、list的使用

1. #include <iostream>
2. #include <list>
3. #include <algorithm>  // 用于 find 示例
5. using namespace std;
7. void printList(const string& hint, const list<int>& lst)
8. {
9.     cout << hint << ": ";
10.     for (const auto& val : lst) cout << val << " ";
11.     cout << "\n\n";
12. }
14. int main()
15. {
16.     // ================== 初始化 ==================
17.     list<int> lst1;                  // 空列表
18.     list<int> lst2(3, 100);          // 3个100
19.     list<int> lst3 = { 7, 2, 5, 1 };   // 初始化列表
20.     list<int> lst4(lst3);            // 拷贝构造
22.     printList("lst2 (填充构造)", lst2);
23.     printList("lst3 (初始化列表)", lst3);
24.     printList("lst4 (拷贝构造)", lst4);
26.     // ================== 增删操作 ==================
27.     lst3.push_front(9);      // 头部插入
28.     lst3.push_back(3);       // 尾部插入
29.     printList("push_front(9) + push_back(3)", lst3); // 9 7 2 5 1 3
31.     lst3.pop_front();        // 删除头部
32.     lst3.pop_back();         // 删除尾部
33.     printList("pop_front() + pop_back()", lst3);     // 7 2 5 1
35.     auto it = lst3.begin();
36.     advance(it, 2);                   // 移动到第3个元素(5)
37.     lst3.insert(it, 99);               // 在5前面插入99
38.     printList("insert(99) at pos3", lst3);  // 7 2 99 5 1
40.     it = lst3.begin();
41.     advance(it, 3);
42.     lst3.erase(it);                   // 删除第4个元素(5)
43.     printList("erase(pos4)", lst3);   // 7 2 99 1
45.     lst3.remove(99);                  // 删除所有99
46.     printList("remove(99)", lst3);    // 7 2 1
48.     // ================== 容量操作 ==================
49.     cout << "size: " << lst3.size() << endl;          // 3
50.     cout << "empty: " << boolalpha << lst3.empty() << endl; // false
51.     lst3.clear();
52.     printList("after clear()", lst3);                // 空列表
53.     cout << "empty after clear: " << lst3.empty() << endl << endl; // true
55.     // ================== 元素访问 ==================
56.     lst3 = { 10, 20, 30 };
57.     cout << "front: " << lst3.front() << endl;  // 10
58.     cout << "back: " << lst3.back() << endl;     // 30
59.     cout << endl;
61.     // ================== 特殊操作 ==================
62.     list<int> lstA = { 5, 3, 1, 4, 2 };
63.     lstA.sort();
64.     printList("sorted lstA", lstA);  // 1 2 3 4 5
66.     lstA.unique();                   // 无连续重复元素时无效
67.     printList("unique (无变化)", lstA);
69.     lstA.reverse();
70.     printList("reversed lstA", lstA);  // 5 4 3 2 1
72.     // splice示例
73.     list<int> lstB = { 100, 200, 300 };
74.     auto splice_pos = lstA.begin();
75.     advance(splice_pos, 2);  // 插入到第3个位置前
76.     lstA.splice(splice_pos, lstB);
77.     printList("splice lstB into lstA", lstA);  // 5 4 100 200 300 3 2 1
78.     printList("lstB after splice", lstB);      // 空列表
80.     // merge示例（需要两个列表已排序）
81.     list<int> lstC = { 2, 5, 8 };
82.     list<int> lstD = { 1, 3, 6 };
83.     lstC.merge(lstD);
84.     printList("merged lstC", lstC);  // 1 2 3 5 6 8
85.     printList("lstD after merge", lstD);  // 空列表
87.     // ================== 遍历方式 ==================
88.     cout << "迭代器遍历: ";
89.     for (auto it = lstC.begin(); it != lstC.end(); ++it)
90.     {
91.         cout << *it << " ";
92.     }
93.     cout << "\n范围遍历: ";
94.     for (const auto& val : lstC)
95.     {
96.         cout << val << " ";
97.     }
98.     cout << "\n\n";
100.     // ================== 算法库结合示例 ==================
101.     list<int> nums = { 5, 3, 9, 1, 7 };
102.     auto find_it = find(nums.begin(), nums.end(), 9);
103.     if (find_it != nums.end())
104.     {
105.         cout << "Found 9 at position: " << distance(nums.begin(), find_it) << endl;
106.     }
108.     return 0;
109. }

复制代码

三、list的模拟实现

1. #include <iostream>
2. #include <cassert>
3. #include <stdexcept>
5. // 双向链表节点的模板定义
6. template<typename T>
7. struct ListNode
8. {
9.     T data;           // 节点存储的数据
10.     ListNode* prev;   // 指向前一个节点的指针
11.     ListNode* next;   // 指向后一个节点的指针
12.     ListNode(const T& val) : data(val), prev(nullptr), next(nullptr) {}  // 构造函数初始化节点值
13. };
15. // 双向链表的模板类
16. template<typename T>
17. class List
18. {
19. private:
20.     ListNode<T>* head;  // 指向链表头节点的指针
21.     ListNode<T>* tail;  // 指向链表尾节点的指针
22.     size_t size;        // 链表中元素的数量
24. public:
25.     // 默认构造函数：初始化一个空链表
26.     List() : head(nullptr), tail(nullptr), size(0) {}
27.    
28.     // 析构函数：清空链表释放内存
29.     ~List() { clear(); }
31.     // 拷贝构造函数：创建一个新链表，内容与另一个链表相同
32.     List(const List& other) : head(nullptr), tail(nullptr), size(0)
33.     {
34.         ListNode<T>* current = other.head;
35.         while (current != nullptr)
36.         {
37.             push_back(current->data);  // 逐个复制元素
38.             current = current->next;
39.         }
40.     }
42.     // 移动构造函数：从另一个链表转移资源，避免深拷贝
43.     List(List&& other) noexcept : head(other.head), tail(other.tail), size(other.size)
44.     {
45.         other.head = nullptr;  // 原链表置空
46.         other.tail = nullptr;
47.         other.size = 0;
48.     }
50.     // 拷贝赋值运算符：先清空当前链表，再复制另一个链表的内容
51.     List& operator=(const List& other)
52.     {
53.         if (this != &other)
54.         {
55.             clear();  // 清空当前链表
56.             ListNode<T>* current = other.head;
57.             while (current != nullptr)
58.             {
59.                 push_back(current->data);  // 逐个复制元素
60.                 current = current->next;
61.             }
62.         }
63.         return *this;
64.     }
66.     // 移动赋值运算符：先清空当前链表，再转移另一个链表的资源
67.     List& operator=(List&& other) noexcept
68.     {
69.         if (this != &other)
70.         {
71.             clear();  // 清空当前链表
72.             head = other.head;
73.             tail = other.tail;
74.             size = other.size;
75.             other.head = nullptr;  // 原链表置空
76.             other.tail = nullptr;
77.             other.size = 0;
78.         }
79.         return *this;
80.     }
82.     // 迭代器类：用于遍历链表
83.     class iterator
84.     {
85.         ListNode<T>* current;  // 当前指向的节点
86.     public:
87.         iterator(ListNode<T>* node = nullptr) : current(node) {}  // 构造函数
88.         
89.         T& operator*() const { return current->data; }  // 解引用操作符
90.         
91.         // 前置自增运算符：指向下一个节点
92.         iterator& operator++()
93.         {
94.             current = current->next;
95.             return *this;
96.         }
97.         
98.         // 后置自增运算符：返回当前迭代器，然后指向下一个节点
99.         iterator operator++(int)
100.         {
101.             iterator tmp = *this;
102.             current = current->next;
103.             return tmp;
104.         }
105.         
106.         // 相等比较运算符
107.         bool operator==(const iterator& other) const { return current == other.current; }
108.         
109.         // 不等比较运算符
110.         bool operator!=(const iterator& other) const { return current != other.current; }
111.         
112.         // 获取当前节点指针（供内部使用）
113.         ListNode<T>* getCurrent() const { return current; }
114.     };
116.     iterator begin() const { return iterator(head); }  // 返回指向第一个元素的迭代器
117.     iterator end() const { return iterator(nullptr); }  // 返回指向尾后的迭代器
119.     // 判断链表是否为空
120.     bool empty() const { return size == 0; }
121.    
122.     // 返回链表中元素的数量
123.     size_t get_size() const { return size; }
125.     // 返回第一个元素的引用
126.     T& front()
127.     {
128.         if (empty()) throw std::out_of_range("List is empty");
129.         return head->data;
130.     }
132.     // 返回最后一个元素的引用
133.     T& back()
134.     {
135.         if (empty()) throw std::out_of_range("List is empty");
136.         return tail->data;
137.     }
139.     // 在链表尾部添加元素
140.     void push_back(const T& value)
141.     {
142.         ListNode<T>* newNode = new ListNode<T>(value);
143.         if (!tail)  // 链表为空的情况
144.         {
145.             head = tail = newNode;
146.         }
147.         else  // 链表不为空的情况
148.         {
149.             tail->next = newNode;
150.             newNode->prev = tail;
151.             tail = newNode;
152.         }
153.         size++;
154.     }
156.     // 在链表头部添加元素
157.     void push_front(const T& value)
158.     {
159.         ListNode<T>* newNode = new ListNode<T>(value);
160.         if (!head)  // 链表为空的情况
161.         {
162.             head = tail = newNode;
163.         }
164.         else  // 链表不为空的情况
165.         {
166.             newNode->next = head;
167.             head->prev = newNode;
168.             head = newNode;
169.         }
170.         size++;
171.     }
173.     // 删除链表尾部的元素
174.     void pop_back()
175.     {
176.         if (empty()) return;
177.         ListNode<T>* temp = tail;
178.         if (head == tail)  // 链表只有一个元素的情况
179.         {
180.             head = tail = nullptr;
181.         }
182.         else  // 链表有多个元素的情况
183.         {
184.             tail = tail->prev;
185.             tail->next = nullptr;
186.         }
187.         delete temp;  // 释放内存
188.         size--;
189.     }
191.     // 删除链表头部的元素
192.     void pop_front()
193.     {
194.         if (empty()) return;
195.         ListNode<T>* temp = head;
196.         if (head == tail)  // 链表只有一个元素的情况
197.         {
198.             head = tail = nullptr;
199.         }
200.         else  // 链表有多个元素的情况
201.         {
202.             head = head->next;
203.             head->prev = nullptr;
204.         }
205.         delete temp;  // 释放内存
206.         size--;
207.     }
209.     // 清空链表：删除所有元素
210.     void clear()
211.     {
212.         while (!empty())
213.         {
214.             pop_front();  // 逐个删除元素
215.         }
216.     }
218.     // 在指定位置前插入元素，返回指向新插入元素的迭代器
219.     iterator insert(iterator pos, const T& value)
220.     {
221.         if (pos == begin())  // 在头部插入
222.         {
223.             push_front(value);
224.             return begin();
225.         }
226.         else if (pos == end())  // 在尾部插入
227.         {
228.             push_back(value);
229.             return iterator(tail);
230.         }
231.         else  // 在中间插入
232.         {
233.             ListNode<T>* newNode = new ListNode<T>(value);
234.             ListNode<T>* curr = pos.getCurrent();
235.             newNode->prev = curr->prev;
236.             newNode->next = curr;
237.             curr->prev->next = newNode;
238.             curr->prev = newNode;
239.             size++;
240.             return iterator(newNode);
241.         }
242.     }
244.     // 删除指定位置的元素，返回指向下一个元素的迭代器
245.     iterator erase(iterator pos)
246.     {
247.         if (pos == end()) return end();
248.         ListNode<T>* curr = pos.getCurrent();
249.         if (curr == head)  // 删除头部元素
250.         {
251.             pop_front();
252.             return begin();
253.         }
254.         else if (curr == tail)  // 删除尾部元素
255.         {
256.             pop_back();
257.             return end();
258.         }
259.         else  // 删除中间元素
260.         {
261.             ListNode<T>* prev = curr->prev;
262.             ListNode<T>* next = curr->next;
263.             prev->next = next;
264.             next->prev = prev;
265.             delete curr;  // 释放内存
266.             size--;
267.             return iterator(next);
268.         }
269.     }
270. };
272. // 测试用例：验证链表实现的正确性
273. int main()
274. {
275.     // 测试默认构造函数
276.     List<int> list1;
277.     assert(list1.empty());
278.     assert(list1.get_size() == 0);
280.     // 测试push_back和front/back方法
281.     list1.push_back(1);
282.     assert(list1.get_size() == 1);
283.     assert(list1.front() == 1);
284.     assert(list1.back() == 1);
286.     list1.push_back(2);
287.     assert(list1.get_size() == 2);
288.     assert(list1.front() == 1);
289.     assert(list1.back() == 2);
291.     // 测试push_front方法
292.     List<int> list2;
293.     list2.push_front(2);
294.     assert(list2.get_size() == 1);
295.     assert(list2.front() == 2);
296.     list2.push_front(1);
297.     assert(list2.get_size() == 2);
298.     assert(list2.front() == 1);
299.     assert(list2.back() == 2);
301.     // 测试pop_back方法
302.     list2.pop_back();
303.     assert(list2.get_size() == 1);
304.     assert(list2.back() == 1);
305.     list2.pop_back();
306.     assert(list2.empty());
308.     // 测试pop_front方法
309.     List<int> list3;
310.     list3.push_back(1);
311.     list3.push_back(2);
312.     list3.pop_front();
313.     assert(list3.get_size() == 1);
314.     assert(list3.front() == 2);
315.     list3.pop_front();
316.     assert(list3.empty());
318.     // 测试clear方法
319.     List<int> list4;
320.     list4.push_back(1);
321.     list4.push_back(2);
322.     list4.clear();
323.     assert(list4.empty());
324.     assert(list4.get_size() == 0);
325.     try
326.     {
327.         list4.front();  // 尝试访问空链表的元素，应该抛出异常
328.         assert(false);  // 如果没有抛出异常，断言失败
329.     }
330.     catch (const std::out_of_range&) {}  // 捕获预期的异常
332.     // 测试拷贝构造函数
333.     List<int> list5;
334.     list5.push_back(1);
335.     list5.push_back(2);
336.     List<int> list6(list5);  // 拷贝构造
337.     assert(list6.get_size() == 2);
338.     assert(list6.front() == 1);
339.     assert(list6.back() == 2);
340.     list5.pop_front();  // 修改原链表
341.     assert(list5.get_size() == 1);
342.     assert(list6.get_size() == 2);  // 验证拷贝的链表不受影响
344.     // 测试移动构造函数
345.     List<int> list7(std::move(list5));  // 移动构造
346.     assert(list7.get_size() == 1);
347.     assert(list5.empty());  // 原链表应该被置空
349.     // 测试拷贝赋值运算符
350.     List<int> list8;
351.     list8 = list6;  // 拷贝赋值
352.     assert(list8.get_size() == 2);
353.     list6.pop_back();  // 修改被拷贝的链表
354.     assert(list8.get_size() == 2);  // 验证拷贝的链表不受影响
356.     // 测试移动赋值运算符
357.     List<int> list9;
358.     list9 = std::move(list8);  // 移动赋值
359.     assert(list9.get_size() == 2);
360.     assert(list8.empty());  // 原链表应该被置空
362.     // 测试插入和迭代器
363.     List<int> list10;
364.     list10.push_back(1);
365.     list10.push_back(3);
366.     auto it = list10.begin();
367.     ++it;  // 指向元素3
368.     list10.insert(it, 2);  // 在3之前插入2
369.     assert(list10.get_size() == 3);
370.     auto iter = list10.begin();
371.     assert(*iter == 1);
372.     ++iter;
373.     assert(*iter == 2);
374.     ++iter;
375.     assert(*iter == 3);
376.     ++iter;
377.     assert(iter == list10.end());  // 验证迭代器到达尾部
379.     // 测试删除
380.     it = list10.begin();
381.     ++it;  // 指向元素2
382.     it = list10.erase(it);  // 删除元素2，it应该指向元素3
383.     assert(*it == 3);
384.     assert(list10.get_size() == 2);
385.     assert(list10.front() == 1);
386.     assert(list10.back() == 3);
388.     std::cout << "All tests passed!" << std::endl;
389.     return 0;
390. }

复制代码

四、list的迭代器失效及反向迭代器
前面说过，此处各人可将迭代器暂时明确成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中举行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，而且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

改正：
 

 反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭
代器的实现可以借助正向迭代器，即：反向迭代器内部可以包罗一个正向迭代器，对正向迭代器的接口举行包装即可。
五、list和vector的区别

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