C++-list
std::list是C++標準模板庫(STL)提供的雙向鏈表容器，它提供了高效的插入和刪除操作，特別適合頻繁修改的序列。定義在 <list> 頭文件中，屬于 std 命名空間。該類的接口與常規容器接口基本一致。
模板原型：
template < class T, class Alloc = allocator<T> > class list;
allocator<T>：STL空間配置器（內存池）。
基本特性：
-
實現方式：雙向鏈表結構，每個元素包含指向前驅和后繼的指針。
-
內存分配：元素在內存中非連續存儲的，通過指針鏈接。
-
泛型容器：通過模板實現，可以存儲任何類型的元素。
-
迭代器：雙向迭代器（支持++和–操作）。
1. 底層理解
list 底層是 帶頭雙向循環鏈表。
template<typename T>
struct list_node{T val;list_node* prev;list_node* next;list_node(const T& data = T()) :val(data) , prev(nullptr) , next(nullptr) {}
};
template<typename T>
class list {private:list_node<T>* node;
}
2. 成員函數
2.1 成員類型
| 成員類型 | 解釋 |
|---|---|
| value_type | 第一個模板參數（T） |
| allocator_type | 第二個模板參數（Alloc） |
| size_type | 無符號整數（size_t） |
| reference | 類型引用（T&） |
| const_reference | const類型引用（const T&） |
2.2 構造函數
| 序號 | 函數原型 | 說明 |
|---|---|---|
| 1?? | explicit list (const allocator_type& alloc = allocator_type()) | 默認構造 |
| 2?? | list (const list& x) | 拷貝構造 |
| 3?? | explicit list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()) | 使用 n 個 val 值初始化 |
| 4?? | template <class InputIterator> list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()) | 使用一段迭代器區間初始化 |
2.3 賦值重載
| 序號 | 函數原型 | 說明 |
|---|---|---|
| 1?? | list& operator= (const list& x) | 兩個已存在的 list 對象的賦值 |
2.4 迭代器
| 序號 | 函數原型 | 說明 |
|---|---|---|
| 1?? | iterator begin() | 返回指向 list 對象中第一個元素的迭代器 |
| 2?? | const_iterator begin() const | 返回指向 list 對象中第一個元素的 const迭代器 |
| 3?? | iterator end() | 返回指向 list 對象末尾元素之后位置的迭代器 |
| 4?? | const_iterator end() const | 返回指向 list 對象末尾元素之后位置的 const迭代器 |
| 5?? | reverse_iterator rbegin() | 返回指向 list 對象末尾元素的反向迭代器 |
| 6?? | const_reverse_iterator rbegin() const | 返回指向 list 對象末尾元素的const反向迭代器 |
| 7?? | reverse_iterator() rend() | 返回指向 list 對象起始元素之前位置的反向迭代器 |
| 8?? | const_reverse_iterator() rend() const | 返回指向 list 對象起始元素之前位置的const反向迭代器 |
2.5 容量相關的接口
| 序號 | 函數原型 | 說明 |
|---|---|---|
| 1?? | size_type size() const | 返回 list 對象中元素的數量 |
| 2?? | bool empty() const | 判斷當前 list 對象是否為空 |
2.6 元素的訪問
| 序號 | 函數原型 | 說明 |
|---|---|---|
| 1?? | reference front() | 返回 list 對象第一個元素的引用 |
| 2?? | const_reference front() const | 返回 const list 對象第一個元素的 const引用 |
| 3?? | reference back() | 返回 list 對象最后一個元素的引用 |
| 4?? | const_reference back() const | 返回 const list 對象最后一個元素的引用 |
2.7 修改相關的接口
| 序號 | 函數原型 | 說明 |
|---|---|---|
| 1?? | template <class InputIterator> void assign (InputIterator first, InputIterator last) | 使用一段迭代器區間賦值給 list 對象（通常使用其他容器） |
| 2?? | void push_front (const value_type& val) | 在 list 對象頭部插入 val 元素 |
| 3?? | void pop_front() | 在 list 對象頭部刪除一個元素 |
| 4?? | void push_back (const value_type& val) | 在 list 對象尾部插入 val 元素 |
| 5?? | void pop_back() | 在 list 對象尾部刪除一個元素 |
| 6?? | iterator insert (iterator pos, const value_type& val); | 在 list 對象的 pos 位置迭代器插入 val 元素，返回新插入元素的迭代器 |
| 7?? | iterator erase (iterator pos); | 刪除 list 對象的 pos 位置迭代器元素，返回刪除位置元素的下一個迭代器 |
| 8?? | void clear(); | 清空 list 對象中所有元素 |
2.8 其他操作
| 序號 | 函數原型 | 說明 |
|---|---|---|
| 1?? | void reverse() | 逆置 list 對象中的元素 |
| 2?? | void sort() | 排序 list 對象中的元素（默認升序） |
| 3?? | void merge (list& x) | 合并兩個有序的 list，將 x 對象中的所有元素合并到當前 list 中，合并完后 x 將變為空鏈表 |
| 4?? | void unique() | 去重，但前提需要 list 對象有序 |
| 5?? | void remove (const value_type& val) | 移除所有 val 元素 |
| 6?? | void splice (iterator position, list& x) | 將x鏈表中的所有元素移動到當前鏈表的 position迭代器之前，移動后 x 變為空鏈表 |
| 7?? | void splice (iterator position, list& x, iterator i) | 將x鏈表中 i 位置迭代器元素移動到當前鏈表的 position迭代器之前 |
| 8?? | void splice (iterator position, list& x, iterator first, iterator last); | 將x鏈表一段迭代器區間移動到當前鏈表的 position迭代器之前 |
- reverse
- sort
- merge
- unique
- remove
6.splice
3. list迭代器失效
C++中，list 與 vector 迭代器失效有所不同，list迭代器失效主要發生在 元素被刪除時
迭代器失效的情況：
-
erase 時被刪除位置元素迭代器失效。
- 解決方式：通過 erase 返回值重新獲取迭代器（erase返回刪除元素的下一個位置迭代器）
-
整個 list 被銷毀或賦值時，所有迭代器都會失效。
4. list模擬實現
// list.hpp
#pragma once#include <iostream>
#include <cassert>namespace simulate_list {template<typename T>struct list_node{T val;list_node* prev;list_node* next;list_node(const T& data = T()) :val(data) , prev(nullptr) , next(nullptr) {}};template<typename T , typename Ref , typename Ptr>struct __list_iterator {typedef list_node<T> node;typedef __list_iterator<T , Ref , Ptr> self;__list_iterator(node* nodeptr) :cur(nodeptr) {}self& operator++() {cur = cur->next;return *this;}self operator++(int) {self temp(cur);cur = cur->next;return temp;}self& operator--() {cur = cur->prev;return *this;}self operator--(int) {self temp(cur);cur = cur->prev;return temp;}Ref operator*() {return cur->val;}Ptr operator->() {return &(operator*());}bool operator==(const self& s) {return cur == s.cur;}bool operator!=(const self& s) {return cur != s.cur;}node* cur;};template<typename T>class list {typedef list_node<T> node;public:typedef __list_iterator<T , T& , T*> iterator;typedef __list_iterator<T , const T& , const T*> const_iterator;iterator begin() { return iterator(head->next); }iterator end() { return iterator(head); }const_iterator begin() const { return const_iterator(head->next); }const_iterator end() const { return const_iterator(head); }bool empty() const { return head->next == head; }T& front() { assert(!empty()); return head->next->val; }T& back() { assert(!empty()); return head->prev->val; }const T& front() const { assert(!empty()); return head->next->val; }const T& back() const { assert(!empty()); return head->prev->val; }size_t size() const {size_t count = 0;for (auto& a : *this) count++;return count; }void clear() {auto it = begin();while (it != end())it = erase(it);}void initializer_list() {head = new node;head->prev = head;head->next = head;}list<T>() {initializer_list();}list<T>(const list<T>& l) {initializer_list();for (auto& node : l)push_back(node);}list<T>& operator=(list<T> l) {std::swap(head , l.head);return *this;}~list<T>() {clear();delete head;head = nullptr;}iterator insert(iterator position , const T& val);iterator erase(iterator position);void push_front(const T& val) { insert(begin() , val); }void pop_front() { assert(!empty()); erase(begin()); }void push_back(const T& val) { insert(end() , val); }void pop_back() { assert(!empty()); erase(--end()); } private:node* head = nullptr;}; template<typename T>typename list<T>::iterator list<T>::insert(list<T>::iterator position , const T& val) {node* prev = position.cur->prev;node* newnode = new node(val);prev->next = newnode;newnode->prev = prev;newnode->next = position.cur;position.cur->prev = newnode;return iterator(newnode); // 返回新插入節點的迭代器}template<typename T>typename list<T>::iterator list<T>::erase(list<T>::iterator position) {node* prev = position.cur->prev;node* next = position.cur->next;prev->next = next;next->prev = prev;delete position.cur;return iterator(next); // 返回刪除元素的下一個元素}} // namespace simulate_list end
