=========================================================================

個人主頁點擊直達：小白不是程序媛

C++專欄：C++干貨鋪

代碼倉庫：Gitee

=========================================================================

目錄

list的介紹及使用

list的介紹

list的使用

list的構造

list迭代器的使用

list的增刪查改

list的模擬實現

結點的封裝

迭代器的封裝

list成員變量

構造函數

拷貝構造函數

operator=

析構函數和清理空間

insert

erase

push_back、push_front、pop_back、pop_front

begin+end、cbegin+cend

list和vector的對比

---

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的構造

函數名稱? ? ? ?	函數作用
list(size_t type n,const value_type	構造的list中包含n個值為val的元素
list()	構造空list
list(const list&x)	拷貝構造函數
list(first,last)	迭代器區間中的元素構造list

	list<int> lt1(10, 1);list<int> lt2;list<int> lt3(lt1);list<int> lt4(lt3.begin(), lt3.end());list<int>::iterator lt = lt4.begin();while (lt != lt4.end()){cout << *lt << " ";lt++;}cout << endl;for (auto e : lt4){cout << e << " ";}cout << endl;

list迭代器的使用

函數名稱	函數作用
begin+end	返回第一個元素的迭代器+返回最后一個元素下一個位置的迭代器
rbegin+rend	返回第一個元素的reverse_iterator,即end位置，返回最后一個元素下一個位置的 reverse_iterator,即begin位置

list的增刪查改

函數名稱	函數作用
push_back	在list尾部插入值為val的元素
push_front	在list首元素前插入值為val的元素
pop_back	刪除list中最后一個元素
pop_front	刪除list中第一個元素
insert	在list position 位置中插入值為val的元素
erase	刪除list position位置的元素

	list<int> lt(5,9);//頭插lt.push_front(1);//尾插lt.push_back(2);for (auto e : lt){cout << e << " ";}cout << endl;//尾刪lt.pop_back();//頭刪lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.insert(lt.begin(), 30);for (auto e : lt){cout << e << " ";}cout << endl;lt.erase(lt.begin());for (auto e : lt){cout << e << " ";}

?

---

list的模擬實現

list通過一個一個結構體的結點實現，節點中包括指向下一個位置、指向前一個位置的指針和有效數值組成。

結點的封裝

使用struct而不是class是因為默認為公開的

	template<class T>//封裝結點struct list_node{list_node(const T& x=T()):_data(x),_next(nullptr),_prev(nullptr){}T _data;list_node* _next;list_node* _prev;};

迭代器的封裝

list和順序表最大的不同是list物理上不連續，需要使用指針進行移動直線下一個或者指向其他的操作，而不像順序表物理上是連續的，++、--都可以拿到有效數據；因此需要對迭代器單獨封裝。

//迭代器封裝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){}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;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};

list成員變量

指向結構體節點的指針和有效數據的個數

		Node* _node;size_t _size;

構造函數

		typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;void empty_init(){_node = new Node;_node->_next = _node;_node->_prev = _node;_size = 0;}list(){empty_init();}

拷貝構造函數

	list(list<T>& x){empty_init();for (auto e : x){push_back(e);}}

operator=

		void swap(list<T>& lt){std::swap(_node, lt._node);std::swap(_size, lt._size);}list<int>& operator=(list<int> lt){swap(lt);return *this;}

析構函數和清理空間

		~list(){clear();delete _node;_node = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

insert

		void insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;_size++;}

erase

iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;return next;}

push_back、push_front、pop_back、pop_front

		void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}

begin+end、cbegin+cend

		const_iterator begin() const{return const_iterator(_node->_next);}const_iterator end() const{return const_iterator(_node);}iterator end(){return _node;}iterator begin(){return _node->_next;}

list和vector的對比

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

---

今天對list的介紹和底層模擬實現的分享到這就結束了，希望大家讀完后有很大的收獲，也可以在評論區點評文章中的內容和分享自己的看法。您三連的支持就是我前進的動力，感謝大家的支持！！?!