目錄

一.核心特性

1.雙向循環鏈表結構

2.頭文件：#include

3.時間復雜度

4.內存特性

二.構造函數

三.list iterator的使用

1.學習list iterator之前我們要知道iterator的區分

?編輯

?2.begin()+end()

3.rbegin()+rend()?

?四.list關鍵接口

1.empty()

2. size()

3.front()

4. back()

5.push_front()

6.?pop_front()

7.push_back()

8. pop_back()

9.insert ()

10.erase()

11.swap()

12.clear()

五.list的迭代器失效

六.模擬實現list

1.List.h?

2.test.cpp

?七.list與vector的對比

---

一.核心特性

---

1.雙向循環鏈表結構

每個節點包含前驅和后繼指針

2.頭文件：#include <list>

3.時間復雜度

任意位置插入/刪除：O(1)

隨機訪問：O(n)

排序：O(n log n)

4.內存特性

非連續內存存儲

每個元素需要額外存儲兩個指針（前驅+后繼）

內存占用 ≈ sizeof(T)2 + 2指針大小

二.構造函數

---

int main()
{list<T> lst1;            // 空鏈表list<T> lst2(n);         // n個默認初始化元素list<T> lst3(n, value);  // n個value副本list<T> lst4(begin, end);// 迭代器范圍構造list<T> lst5(init_list); // 初始化列表 C++11list<T> lst6(lst4);      // 拷貝構造
}

三.list iterator的使用

---

1.學習list iterator之前我們要知道iterator的區分

功能上區分：

iterator	普通迭代器
reverse_iterator	反向迭代器
const_iterator	只讀迭代器
const_reverse_iterator	只讀反向迭代器

性質上區分：

名稱	代表容器	支持操作
單向迭代器（ForwardIterator）	Forward_list(單鏈表)，unordered_map	++
雙向迭代器（BidirectionalIterator）	list(鏈表)，map，set	++/--
隨機迭代器（RandomAccessIterator）	vector，string，deque	++/--/+/-

通過底層結構決定可以實現哪些算法

比如算法庫里的sort要求使用隨機迭代器，list就無法使用這個算法

對于算法庫里的reverse和find可以正常使用?

可以得知，功能是向上兼容得?

此處，大家可暫時將迭代器理解成一個指針，該指針指向list中的某個節點?

?2.begin()+end()

返回第一個元素的迭代器+返回最后一個元素下一個位置的迭代器

3.rbegin()+rend()?

返回第一個元素的reverse_iterator,即end位置，返回最后一個元素下一個位置的reverse_iterator,即begin位置

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto it = lt.rbegin();while (it != lt.rend()){cout << *it << " ";  //4 3 2 1++it;}cout << endl;

• begin與end為正向迭代器，對迭代器執行++操作，迭代器向后移動
• rbegin(end)與rend(begin)為反向迭代器，對迭代器執行++操作，迭代器向前移動

?四.list關鍵接口

---

1.empty()

檢測list是否為空，是返回true，否則返回false

	list<int> lt;cout<<lt.empty()<<endl;   //1lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << lt.empty();    //0

2. size()

返回list中有效節點的個數

	list<int> lt;cout<<lt.size()<<endl;   //0lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << lt.size();    //4

3.front()

返回list的第一個節點中值的引用

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << lt.front();    //1

4. back()

返回list的最后一個節點中值的引用

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << lt.back();    //4

5.push_front()

在list首元素前插入值為val的元素

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);    //5 1 2 3 4

6.?pop_front()

刪除list中第一個元素

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.pop_front();    //2 3 4

7.push_back()

在list尾部插入值為val的元素

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);    //1 2 3 4 5

8. pop_back()

刪除list中最后一個元素

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.pop_back();    //1 2 3 

9.insert ()

在list position 位置中插入值為val的元素

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);std::list<int>::iterator it;it=lt.begin();int k = 3;while (k--){++it;}lt.insert(it, 30); 1 2 3 30 4

10.erase()

刪除list position位置的元素

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);std::list<int>::iterator it;it=lt.begin();int k = 2;while (k--){++it;}lt.erase(it);  //1 2 4

11.swap()

交換兩個list中的元素

	std::list<int> first(3, 100);   // 100 100 100std::list<int> second(5, 200);  // 200 200 200 200 200first.swap(second);   // 200 200 200 200 200

12.clear()

清空list中的有效元素

	std::list<int> mylist;mylist.push_back(1101);   //1101mylist.clear();mylist.push_back(2202);   //2202return 0;

五.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;}
}
// 改正 
void TestListIterator() {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()) {l.erase(it++); // it = l.erase(it);}
}

六.模擬實現list

---

1.List.h?

#pragma once  // 防止頭文件重復包含
#include<assert.h>  // 斷言檢查// 實現雙向鏈表及相關迭代器
class bit
{// 鏈表節點結構體模板template<class T>struct list_node{T _data;         // 節點存儲的數據list_node<T>* _next; // 后繼指針list_node<T>* _prev; // 前驅指針// 節點構造函數（默認構造空對象）list_node(const T& data = T()):_data(data), _next(nullptr), _prev(nullptr){}};// 鏈表迭代器結構體模板（支持普通/const迭代器）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->_data; }// 成員訪問操作符（返回數據指針）// 使得 it->member 等價于 (&it->)_data->memberPtr operator->() { return &_node->_data; }// 前置++（移動到下一節點）self& operator++() {_node = _node->_next;return *this;}// 前置--（移動到前一節點）self& operator--() {_node = _node->_prev;return *this;}// 后置++（需要返回臨時對象）self operator++(int) {self tmp(*this);_node = _node->_next;return tmp;}// 后置--（同上）self operator--(int) {self tmp(*this);_node = _node->_prev;return tmp;}// 比較操作符重載bool operator!=(const self& s) const { return _node != s._node; }bool operator==(const self& s) const { return _node == s._node; }};// 鏈表類模板template <class T>class list{typedef list_node<T> Node; // 節點類型簡寫public:/*typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;*/  //兩個代碼相似度太高，所以通過增加模板參數實現// 迭代器類型定義（通過模板參數實現const重載）typedef list_iterator<T, T&, T*> iterator;          // 普通迭代器typedef list_iterator<T, const T&, const T*> const_iterator; // const迭代器// 獲取起始迭代器（指向第一個有效節點）iterator begin() { return _head->_next; }// 獲取結束迭代器（哨兵節點）iterator end() { return _head; }// const版本迭代器const_iterator begin() const { return _head->_next; }const_iterator end() const { return _head; }// 初始化哨兵節點（構建空鏈表）void empty_init() {_head = new Node;       // 申請頭節點_head->_next = _head;   // 初始狀態自環_head->_prev = _head;_size = 0;              // 大小置零}// 默認構造函數list() { empty_init(); }// 初始化列表構造（支持花括號初始化）list(std::initializer_list<T> il) {empty_init();for (auto& e : il) {   // 遍歷列表插入元素push_back(e);}}// 拷貝構造函數（深拷貝）list(const list<T>& lt) {empty_init();for (auto& e : lt) {   // 遍歷插入每個元素push_back(e);}}// 賦值運算符（拷貝交換慣用法）list<T>& operator=(list<T> lt) {swap(lt); // 交換資源return *this;}// 析構函數（清理節點）~list() {clear();        // 刪除所有數據節點delete _head;   // 釋放哨兵節點_head = nullptr;}// 清空鏈表（保留哨兵節點）void clear() {auto it = begin();while (it != end()) {   // 逐個刪除節點it = erase(it);}}// 交換兩個鏈表內容void swap(list<T>& lt) {std::swap(_head, lt._head); // 交換頭指針std::swap(_size, lt._size);  // 交換大小}// 尾插（復用insert實現）void push_back(const T& x) { //Node* newnode = new Node(x);//Node* tail = _head->_prev;//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->prev = newnode;  insert(end(), x); //直接調用insert}// 頭插void push_front(const T& x) { insert(begin(), x); }// 在pos位置前插入新節點iterator insert(iterator pos, const T& x) {Node* cur = pos._node;  // 當前節點Node* prev = cur->_prev; // 前驅節點Node* newnode = new Node(x); // 創建新節點// 調整指針鏈接newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;        // 更新大小return newnode; // 返回新節點位置}// 尾刪void pop_back() { erase(--end()); }// 頭刪void pop_front() { erase(begin()); }// 刪除pos位置節點（注意：原代碼此處返回類型應為iterator）iterator erase(iterator pos) {assert(pos != end()); // 不能刪除哨兵節點Node* prev = pos._node->_prev; // 前驅節點Node* next = pos._node->_next; // 后繼節點// 調整鏈接關系prev->_next = next;next->_prev = prev;delete pos._node; // 釋放節點--_size;          // 更新大小return next; // 返回下一位置的迭代器}// 獲取元素數量size_t size() const { return _size; }// 判斷是否為空bool empty() const { return _size == 0; }private:Node* _head;    // 哨兵頭節點size_t _size;   // 元素個數};
};// 打印容器內容（泛型模板）
template<class Container>
void print_container(const Container& con) {// 使用const迭代器遍歷（保證內容不被修改）// const iterator -> 迭代器本身不能修改// const_iterator -> 指向內容不能修改typename Container::const_iterator it = con.begin(); // typename指明依賴類型//auto it = con.begin();或者使用autowhile (it != con.end()) {std::cout << *it << " ";++it;}std::cout << std::endl;// 范圍for遍歷（C++11特性）for (auto e : con) {std::cout << e << " ";}std::cout << std::endl;
}

2.test.cpp

#include <iostream>
#include <list>
#include<algorithm>using namespace std;
#include"list.h"void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;/*it = lt.begin();lt.erase(it + 3);*/// 不支持，要求隨機迭代器//sort(lt.begin(), lt.end());string s("dadawdfadsa");cout << s << endl;sort(s.begin(), s.end());cout << s << 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);lt.push_back(6);for (auto e : lt){cout << e << " ";}cout << endl;auto it = lt.begin();int k = 3;while (k--){++it;}lt.insert(it, 30);for (auto e : lt){cout << e << " ";}cout << endl;int x = 0;cin >> x;it = find(lt.begin(), lt.end(), x);if (it != lt.end()){lt.erase(it);}for (auto e : lt){cout << e << " ";}cout << endl;
}
void test_list4()
{// 直接構造list<int> lt0({ 1,2,3,4,5,6 });// 隱式類型轉換list<int> lt1 = { 1,2,3,4,5,6,7,8 };const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };print_container(lt1);
}int main()
{//test_list3();//test_list4();test_list1();}

?七.list與vector的對比

	vector	list
底 層 結 構	動態順序表，一段連續空間	帶頭結點的雙向循環鏈表
隨 機 訪 問	支持隨機訪問，訪問某個元素效率O(1)	不支持隨機訪問，訪問某個元素效率O(N)
插 入 和 刪 除	任意位置插入和刪除效率低，需要搬移元素，時間復雜度為O(N)，插入時有可能需要增容，增容：開辟新空間，拷貝元素，釋放舊空間，導致效率更 低	任意位置插入和刪除效率高，不需要搬移元素，時間復雜度為O(1)
空 間 利 用 率	底層為連續空間，不容易造成內存碎片，空間利用率高，緩存利用率高	底層節點動態開辟，小節點容易造成內存碎片，空間利用率低，緩存利用率低
迭 代 器	原生態指針	對原生態指針(節點指針)進行封裝 ?
迭 代 器 失 效	在插入元素時，要給所有的迭代器重新賦值，因為插入元素有可能會導致重新擴容，致使原來迭代器失效，刪除時，當前迭代器需要重新賦值否則會失效	插入元素不會導致迭代器失效，刪除元素時，只會導致當前迭代器失效，其他迭代器不受影響
使 用 場 景	需要高效存儲，支持隨機訪問，不關心插入刪除效率	大量插入和刪除操作，不關心隨機訪問

?學到C++11時需要補充一些新的接口。