C++?list常用接口和模擬實現(xiàn)實例代碼
C++中l(wèi)ist容器底層實現(xiàn)是使用帶頭雙向循環(huán)鏈表的結(jié)構(gòu),通過指針指向前一個和后一個節(jié)點。它也具有雙向鏈表的優(yōu)缺點,比如優(yōu)點是對于在任意位置插入和刪除不用移動數(shù)據(jù),缺點是不能任意位置的隨機訪問,必須遍歷到要訪問的節(jié)點才可以;并且list還需要額外的空間來存儲前一個和后一個節(jié)點的信息。
下面了解一下list的常用接口
1.構(gòu)造函數(shù)
//構(gòu)造空的list list() //拷貝構(gòu)造 list (const list& x); //迭代器構(gòu)造,使用模板能適合不同的類型 template <class InputIterator> list (InputIterator first, InputIterator last); //構(gòu)造n個值為val的list list (size_type n, const value_type& val = value_type())
2.迭代器
//返回開始位置的迭代器 iterator begin(); const_iterator begin() const; //返回結(jié)束位置的迭代器 iterator end(); const_iterator end() const;
需要注意的是這里的迭代器在底層并不是原生指針,具體實現(xiàn)在后文給出。
3.容量操作
//判斷是否為空 bool empty() const; //返回有效節(jié)點的個數(shù) size_type size() const;
4.元素獲取
//返回首元素的引用 reference front(); const_reference front() const; //返回末尾元素的引用 reference back(); const_reference back() const;
5.增刪改查
//頭插 void push_front (const value_type& val); //尾插 void push_back (const value_type& val); //頭刪 void pop_front(); //尾刪 void pop_back(); //在任意位置插入 iterator insert (iterator position, const value_type& val); //在任意位置刪除 iterator erase (iterator position); //交換兩個鏈表中的元素 void swap (list& x); //清空鏈表中的元素 void clear();
在了解了鏈表的增刪查改之后我們思考一個問題
list是否會像vector和string一樣出現(xiàn)迭代器失效的原因?由于這里是鏈式結(jié)構(gòu),它的內(nèi)存在物理空間上并不連續(xù),因此如果僅僅是插入一個元素并不會出現(xiàn)迭代器失效的問題,只有刪除時會發(fā)生迭代器失效的問題,并且這里只有刪除節(jié)點的迭代器會失效。
下面給出list的模擬實現(xiàn)
1.節(jié)點list_node設(shè)計
節(jié)點的結(jié)構(gòu)就是雙向鏈表的結(jié)構(gòu),這里也可以寫成結(jié)構(gòu)直接默認類成員公有的也可以。
template<class T> class list_node { public: list_node<T>* _next; list_node<T>* _prev; T _val; list_node(const T& val = T())//默認匿名對象 :_next(nullptr) ,_prev(nullptr) ,_val(val) {} };
2.迭代器設(shè)計
關(guān)于const的迭代器設(shè)計與之前的string和vector都有所不同,對于節(jié)點的指針進行了又一層的封裝。因為這里要支持->箭頭和的重載。我們對于一個指針變量進行解引用通常是要訪問其中存儲的數(shù)據(jù)的內(nèi)容(_val);而->是要訪問數(shù)據(jù)內(nèi)容的成員。從這個特性就可以得到一個結(jié)論,在實現(xiàn)list迭代器時,重載解引用和箭頭的返回類型不同,那么我們要怎樣控制呢?
事實上在這里只需要控制模板參數(shù)就可以實現(xiàn)這種效果。具體代碼如下
template<class T,class Ref ,class Ptr> class _list_iterator { public: //這里事實上迭代器只是借用節(jié)點進行訪問,而不是管理這些節(jié)點,鏈表才管理節(jié)點 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) { self temp(*this); _node = _node->_next; return temp; } //前置-- self& operator--() { _node = _node->_prev; return *this; } //后置-- self operator--(int) { self temp(*this); _node = _node->_prev; return temp; } bool operator!=(const self& it) const { return _node != it._node; } bool operator==(const self& it) const { return _node == it._node; } };
這里的Ref控制解引用的返回類型,Ptr控制箭頭的返回類型;并且在這個類中利用typedef的方法控制自增和自減的返回類型。
并且這樣寫還有一點好處是,對于普通的迭代器使用正常的模板參數(shù)即可,對于const迭代器使用const的模板參數(shù)即可。
3.常用接口的模擬實現(xiàn)
template<class T> class list { typedef list_node<T> Node; public: typedef _list_iterator<T,T&,T*> iterator;//內(nèi)嵌類 typedef _list_iterator<T,const T&,const T*> const_iterator; //這里const迭代器的設(shè)計是錯誤的,因為const迭代器是希望指向內(nèi)容不被修改 //這樣的設(shè)計是迭代器本身不能修改 //typedef const _list_iterator<T> const_iterator; iterator begin() { return _head->_next;//單參數(shù)的構(gòu)造函數(shù)支持隱式類型轉(zhuǎn)換 } const_iterator begin() const { return _head->_next; } iterator end() { return _head; } const_iterator end() const { return _head; } void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; } list() { empty_init(); } //lt2(lt1) list(const list<T>& lt) //list(const list& lt)//不推薦這樣使用 { empty_init(); //遍歷lt1,直接把lt2尾插到lt1 //這里傳引用效率高 for (const auto& e : lt) { push_back(e); } } void swap(list<T>& lt) { std::swap(_head, lt._head); } list<T>& operator=(list<T> lt) //list& operator=(list lt)//這里與上面的拷貝構(gòu)造同理 { swap(lt); return *this; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } void push_back(const T& x) { insert(end(), x); } void pop_back() { erase(--end());//這里調(diào)用--,頭節(jié)點的prev就是尾 } void push_front(const T& x) { insert(begin(), x); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); prev->_next = newnode; newnode->_next = cur; cur->_prev = newnode; newnode->_prev = prev; return newnode; } iterator erase(iterator pos)//這里會有迭代器失效,返回下一個位置的迭代器 { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return next; } size_t size() { size_t sz = 0; iterator it = begin(); while (it != end()) { ++sz; ++it; } return sz; } private: Node* _head; };
這里的常用接口實現(xiàn)都類似與數(shù)據(jù)結(jié)構(gòu)中的帶頭的雙向鏈表。需要注意的就是爹迭代器失效的問題。
最后總結(jié)一下vector和list的各自優(yōu)劣
(1)底層結(jié)構(gòu):vector是連續(xù)存儲的,是一個動態(tài)的順序表;list是不連續(xù)存儲,是一個帶頭的雙向循環(huán)鏈表
(2)隨機訪問:vector支持[]隨機訪問;list不支持隨機訪問
(3)插入和刪除效率:vector的插入和刪除需要移動數(shù)據(jù);list的插入和刪除不需要移動數(shù)據(jù)。
(4)空間利用率:vector底層是連續(xù)的存儲空間,不容易造成內(nèi)存碎片的問題,空間利用率高;list底層是不連續(xù)的存儲空間,小的節(jié)點容易出現(xiàn)內(nèi)存碎片的問題,空間利用率低。
(5)迭代器:vector的迭代器是原生指針;list的迭代器對原生指針進行了再一層的封裝。
(6)迭代器失效的問題:vector再插入和刪除時都會導致迭代器失效,需要重新賦值;list只有再刪除時才會導致迭代器失效。
到此這篇關(guān)于C++ list常用接口和模擬實現(xiàn)實例代碼的文章就介紹到這了,更多相關(guān)C++ list常用接口內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C和C++中的基本數(shù)據(jù)類型的大小及表示范圍詳解
這篇文章主要介紹了C和C++中的基本數(shù)據(jù)類型的大小及表示范圍詳解,基本數(shù)據(jù)類型有int、long、long long、float、double、char、string,正文有詳細介紹,歡迎參考2018-01-01