文章目錄

• list
• • list的介紹
  • list的優缺點
• list的迭代器失效問題
• 實現的接口
• • 節點部分
  • 迭代器部分
  • list部分
• 代碼實現

---

list

list的介紹

list的文檔介紹

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

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

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

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

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

其實list就是數據結構中的雙向循環鏈表， 實現思路我之前有寫過
帶頭雙向循環鏈表

STL中的list和雙向鏈表大體的思路一樣，只是多了迭代器和模板等c++的特性，所以下面大部分代碼我都直接復用了以前過的代碼

list的優缺點

優點：
1.list的存儲方式不像vector是線性的連續的，它是鏈式的存儲空間，只保持了邏輯上的連續，所以不需要考慮擴容的問題，更加有效的利用空間
2.因為是鏈式的存儲方式，所以不需要像vector一樣插入刪除時需要挪動數據，所以插入刪除時的時間復雜度為O（1）

缺點：
1.因為是鏈式結構，所以不支持下標的隨機訪問，導致很多算法用起來十分麻煩

---

list的迭代器失效問題

list的迭代器失效問題主要就體現在erase上，因為list的空間并不是連續的，而是通過prev和next兩個指針來找到前后的結點，而一旦erase掉一個結點，此時再對那個節點使用++或者–就會導致迭代器失效的報錯問題，因為節點已經被釋放，自然就無法通過自身的prev和next訪問到前后的結點。

---

實現的接口

節點部分

迭代器部分

list的迭代器不再像之前的一樣直接用指針來模擬，而是封裝了一個指向節點類的指針，所以我們還需要重載迭代器的運算符，來保證它能夠像指針一樣使用

__list_node<T>* _next; __list_node<T>* _prev; T _data; __list_node(const T& data = T()); typedef __list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> Self; Node* _node; __list_iterator(Node* node); Ref operator*(); Ptr operator->(); Self& operator++(); Self operator++(int); Self& operator--(); Self operator--(int); bool operator==(const Self& it); bool operator!=(const Self& it);

list部分

默認成員函數部分

list() : _head(new Node); list(const list<T>& l) : _head(new Node); list<T>& operator=(list<T> l); ~list();

迭代器部分

typedef __list_node<T> Node; typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const;

容量部分

size_t size() const; bool empty()const;

元素訪問部分

T& front(); const T& front()const; T& back(); const T& back()const;

修改部分

void clear(); void pop_front(); void push_front(const T& val); void pop_back() ; void push_back(const T& val); iterator erase(iterator pos); iterator insert(iterator pos, const T& val); void swap(list<T>& l);

私有成員

Node* _head; //頭結點

---

代碼實現

#pragma once #include<cassert>namespace lee {//節點template<class T>struct __list_node{__list_node<T>* _next;__list_node<T>* _prev;T _data;__list_node(const T& data = T()): _data(data), _next(nullptr), _prev(nullptr){}};//迭代器//使用三個模板參數來實現代碼復用，可以根據傳的參數來同時實現const_iterator和iterator//為了能夠模擬迭代器，需要重載對應的運算符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，it->_data就等價于it.operator->()->_data。這里重載的部分就返回了指向對象的指針，(*it的類型)->_data，然后再通過那個指針訪問數據。如果存在嵌套的類，這里則會一直遞歸調用對象中重載的->,直到取到數據，但是這里因為編譯器優化 所以只需要寫一次就行*/Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self temp(*this);++(*this);return temp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self temp(*this);--(*this);return temp;}bool operator==(const Self& it){return _node == it._node;}bool operator!=(const Self& it){return _node != it._node;}};template<class T>class list{public:typedef __list_node<T> Node;typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;/*------------------------------------------------------------默認成員函數部分Member functions------------------------------------------------------------*/list() : _head(new Node){_head->_next = _head;_head->_prev = _head;}list(const list<T>& l) : _head(new Node){_head->_next = _head;_head->_prev = _head;for (auto it : l){push_back(it);}}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _head;_head = nullptr;}/*------------------------------------------------------------迭代器部分Iterators:------------------------------------------------------------*/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);}/*------------------------------------------------------------修改部分Modifiers:------------------------------------------------------------*/void swap(list<T>& l){std::swap(_head, l._head);}iterator insert(iterator pos, const T& val){assert(pos._node != nullptr);Node* cur = pos._node;Node* prev = cur->_prev;Node* newNode = new Node(val);prev->_next = newNode;cur->_prev = newNode;newNode->_next = cur;newNode->_prev = prev;return iterator(newNode);}iterator erase(iterator pos){ assert(_head->_next != _head);Node* cur = pos._node;Node* next = cur->_next;next->_prev = cur->_prev;cur->_prev->_next = next;delete cur;return iterator(next);}//和數據結構里面實現的一樣，可以直接復用insert和erasevoid push_back(const T& val){insert(end(), val);//head}void pop_back() { erase(--end()); //head->prev}void push_front(const T& val){insert(begin(), val);//head->next;}void pop_front(){erase(begin());//head->next;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}/*------------------------------------------------------------元素訪問部分Element access:------------------------------------------------------------*/T& front(){return _head->_next->_data;}const T& front()const{return _head->_next->_data;}T& back(){return _head->_prev->_data;}const T& back()const{return _head->_prev->_data;}/*------------------------------------------------------------容量部分Capacity------------------------------------------------------------*/size_t size()const{size_t count = 0;auto it = begin();while (it != end()){count++;it++;}return count;}bool empty()const{return _head->_next == _head;}private:Node* _head;}; }

總結

以上是生活随笔為你收集整理的C++ STL : 模拟实现STL中的list类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。