C++：STL中list的使用和模擬實現

C++中的list是標準模板庫（STL）提供的雙向鏈表容器，支持高效的元素插入和刪除操作。在上一篇中講解了vector的使用和模擬實現，vector是具有連續的空間，迭代器是可以隨機的，而list卻于vector不同，list是帶頭雙向循環鏈表，迭代器是雙向的，空間并不是連續的，所以在底層實現上比vector復雜一點。與vector?不同，list?在任意位置插入或刪除元素的時間復雜度為 O(1)，但隨機訪問的性能較差（時間復雜度為 O(n)）。

list的介紹

?list的使用

list的構造

list的插入和刪除?

list訪問元素?

list的大小和容量?

list迭代器的使用?

list的模擬實現?

迭代器中的函數?

list的介紹

1. list是可以在常數范圍內在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。

2. list的底層是雙向鏈表結構，雙向鏈表中每個元素存儲在互不相關的獨立節點中，在節點中通過指針指向其前一個元素和后一個元素。

3. list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡單高效。

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

5. 與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機訪問，比如：要訪問list 的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時間開銷；list還需要一些額外的空間，以保存每個節點的相關聯信息(對于存儲類型較小元素的大list來說這可能是一個重要的因素)

?list的使用

list是帶頭雙向循環鏈表，如果迭代器要進行++、--、*（解引用）等操作是否跟vector一樣呢，當然不是，兩者的結構不同注定迭代器也不一樣，但是為了方便大家使用將list的迭代器進行了封裝，依然是lis<T>iterator來進行各種操作，list的空間不是連續的，所以在實現++、--、*等操作就需要進行運算符重載來定義該運算符的行為，在使用上迭代器vector和list沒什么兩樣，但是在底層卻大大不同。

list的構造

list (size_type n, const value_type& val = value_type()) //構造的list中包含n個值為val的元素list() //構造空的listlist (InputIterator ?rst, InputIterator last) //用[?rst, last)區間中的元素構造list

使用list需要包含頭文件。初始化的方式包括默認構造、指定大小初始化、通過迭代器范圍初始化等。?

示例：

#include <list>
#include <iostream>
using namespace std;int main() {list<int> l1; // 空列表list<int> l2(5, 10); // 包含5個值為10的元素list<int> l3 = {1, 2, 3, 4, 5}; // 列表初始化return 0;
}

list的插入和刪除?

push_back(val)：在末尾插入元素。

push_front(val)：在頭部插入元素。

pop_back(val)：刪除末尾元素。

pop_front(val)：刪除頭部元素。

insert(pos,val)：在指定位置插入元素。

erase(pos)：在指定位置刪除元素。

示例：?

std::list<int> l = {1, 2, 3};
l.push_back(4); // {1, 2, 3, 4}
l.push_front(0); // {0, 1, 2, 3, 4}
l.pop_back(); // {0, 1, 2, 3}
l.pop_front(); // {1, 2, 3}
auto it = l.begin();
it++;
l.insert(it, 10); // {1, 10, 2, 3}
l.erase(it); // {1, 10, 3}

list訪問元素?

front()：返回第一個元素。

back()：返回最后一個元素。

由于list的結構不支持operator【】或者at()隨機訪問。?

示例：

std::list<int> l = {1, 2, 3};
std::cout << l.front() << std::endl; // 輸出1
std::cout << l.back() << std::endl; // 輸出3

list的大小和容量?

在vector中擴容是很常見的，擴容之后需要拷貝，而在list中就不存在這樣的問題，當插入一個值就new一個節點再鏈接起來，不需要拷貝，按需申請。

size()：返回元素數量。

empty()：判斷是否為空。

示例：

std::list<int> l = {1, 2, 3};
std::cout << l.size() << std::endl; // 輸出3
std::cout << l.empty() << std::endl; // 輸出0（false）

list 提供了一些特有操作：

sort()：排序（默認升序，可自定義比較函數）。
merge(other_list)：合并兩個有序列表。
splice(pos, other_list)：將另一個列表的元素移動到指定位置。
unique()：刪除連續重復元素。

示例：?

std::list<int> l1 = {3, 1, 2};
std::list<int> l2 = {5, 4, 6};
l1.sort(); // {1, 2, 3}
l2.sort(); // {4, 5, 6}
l1.merge(l2); // l1: {1, 2, 3, 4, 5, 6}, l2為空
l1.unique(); // 刪除重復元素

list迭代器的使用?

?list提供雙向迭代器，有begin()、end()、rbegin()、和rend()。

std::list<int> l = {1, 2, 3};
for (auto it = l.begin(); it != l.end(); it++) {std::cout << *it << " ";
}
// 輸出：1 2 3

想知道更多list的更多接口可以看這里：https://legacy.cplusplus.com/reference/list/list/?kw=list?

list的模擬實現?

在實現list之前我們需要知道list的結構是帶頭雙向循環鏈表，迭代器也是和vector不一樣，需要去實現封裝迭代器，list迭代器需要和vector的迭代器有一樣的功能，所以需要定義一個結構體迭代器在該結構體中去實現迭代器的各種行為。而迭代器還有const修飾的迭代器，所以模版參數可不止一個，需要注意的是const修飾的迭代器本身是可以進行++等操作的，而迭代器指向的內容是只讀不可寫的。只要對迭代器的實現完善好接下來的工作就十分好做，模擬實現list的重難點就在于如何去實現迭代器。

代碼展示：

template<class T>//結點struct list_node {list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};template<class T, class Ref, class ptr>//迭代器struct _list_iterator {typedef list_node<T> Node;//節點類型typedef _list_iterator<T, Ref, ptr> Self;Node* _node; \\指向當前鏈表節點的指針\\構造函數：初始化迭代器指向特定節點_list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}ptr operator->(){return &_node->_val;}Self& operator++()//前置{_node = _node->_next;return *this;}Self& operator++(int)//后置{_list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}Self& operator--()//前置{_node = _node->_prev;return *this;}Self& operator--(int)//后置{Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};

模版參數：

T:鏈表元素的類型（如：int、string），與節點定義中的T一致。

Ref：引用類型，用于operator*的返回類型。通常為T&（非const迭代器）或者const T& （const迭代器）

ptr：指針類型，用于operator->的返回類型。通常為T*（非const）或者const T*（const）

對于內部typedef：

typedef list_node<T> Node; 定義節點類型。

typedef _list_iterator<T, Ref, ptr> Self; 定義自身類型，方便使用。

迭代器中的函數?

Ref operator*():解引用運算符，返回當前節點值的引用。

作用：允許*it的語法訪問元素值。例如it是迭代器，*it就可以獲取節點儲存的值。

ptr operator->()：成員訪問運算符，返回指向節點值的指針。

作用：支持it->member語法。例如，如果T是結構體類型，it->member訪問其成員。

Self& operator++()（前置遞增）：移動到下一個節點，并返回更新后的迭代器引用。?

作用：用于++it語法。效率高，因為直接修改并返回自身。?

Self operator++(int)（后置遞增）：返回當前迭代器的副本，然后移動到下一個節點。

作用：用于it++語法。參數int是占位符，用于區分前置和后置版本。注意返回類型是Self（值類型），不是引用，因為返回的是臨時副本。

Self& operator--()（前置遞減）：移動到前一個節點，并返回更新后的迭代器引用。

作用：用于--it語法。正確利用了雙向鏈表的_prev指針?

Self operator--(int)（后置遞減）：返回當前迭代器的副本，然后移動到前一個節點。

作用：用于it--語法。

bool operator!=(const Self& it)：檢查兩個迭代器是否指向不同節點。

作用：用于it1 != it2語法。例如，在循環中判斷是否到達結尾。

此迭代器實現是STL風格雙向鏈表的核心部分：它封裝了節點指針，提供統一的元素訪問和遍歷接口。通過模板參數，優雅地支持const和非const迭代器。運算符重載使迭代器用法類似原生指針（如*it、it->、++it）。

list代碼：

template<class 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;//const T* ptr //const 修飾的是指針指向的內容，不能修改//T* const ptr // const 修飾的是指針，指針不能修改list(){head = new Node;head->_next = head;head->_prev = head;n = 0;}list(const list<T>& lt){head = new Node;head->_next = head;head->_prev = head;n = 0;for (auto& e : lt){push_back(e);}}~list(){clear();}iterator begin(){return head->_next;}iterator end(){return head;}const_iterator begin() const{return const_iterator(head->_next);}const_iterator end() const{return const_iterator(head);}void push_back(const T& x){Node* tail = head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;head->_prev = newnode;newnode->_next = head;n++;//insert(--end(),x);}void pop_back(){erase(--end());}void push_front(const T* x){insert(begin(), x);}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* cur = pos._node->_prev;newnode->_next = cur->_next;newnode->_prev = cur;cur->_next->_prev = newnode;cur->_next = newnode;n++;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node->_next;Node* prev = pos._node->_prev;cur->_prev = prev;prev->_next = cur;/*pos._node->_next = pos._node->_prev = nullptr;*/delete pos._node;n--;return cur;}void swap(list<T>& lt){std::swap(head, lt.head);std::swap(n, lt.n);}list<T>& operator=(list<T> lt){swap(lt);return *this;}void clear(){/*Node* cur = head->_next;while (cur != head){Node* next = cur->_next;delete cur;cur = next;}head->_next = head;head->_prev = head;n = 0;*/iterator it = begin();while (it != end()){it = erase(it);}}size_t size(){return n;}private:Node* head;size_t n;};