您好,登錄后才能下訂單哦!
這篇文章主要介紹了怎么用C++模擬實(shí)現(xiàn)STL容器的相關(guān)知識(shí),內(nèi)容詳細(xì)易懂,操作簡(jiǎn)單快捷,具有一定借鑒價(jià)值,相信大家閱讀完這篇怎么用C++模擬實(shí)現(xiàn)STL容器文章都會(huì)有所收獲,下面我們一起來(lái)看看吧。
列表是一種順序容器,它允許在序列中的任何位置執(zhí)行常量時(shí)間插入和刪除操作,并允許在兩個(gè)方向上進(jìn)行迭代。它的底層是一個(gè)帶頭雙向循環(huán)鏈表。
list不能用算法庫(kù)的sort進(jìn)行排序。算法庫(kù)中的sort的底層是一個(gè)快排,需滿足三數(shù)取中,需要傳入隨機(jī)訪問(wèn)迭代器,所以list并不適用。
當(dāng)然list中提供了一個(gè)自己的sort,它的底層是一個(gè)歸并排序。但是這個(gè)sort比vector使用算法庫(kù)的sort還慢,甚至比list的數(shù)據(jù)先push_back到vector到再用算法庫(kù)的sort還要慢。
insert,迭代器不失效
earse失效
1、單向迭代器:只能++,不能--。例如單鏈表,哈希表;
2、雙向迭代器:既能++也能--。例如雙向鏈表;
3、隨機(jī)訪問(wèn)迭代器:能++--,也能+和-。例如vector和string。
迭代器是內(nèi)嵌類型(內(nèi)部類或定義在類里)
普通迭代器
迭代器的實(shí)現(xiàn)需要支持解引用(為了取數(shù)據(jù)),支持++--。
博主模擬實(shí)現(xiàn)string和vector時(shí),直接將原生指針typedef成迭代器,是因?yàn)閿?shù)組的結(jié)構(gòu)正好滿足迭代器的行為(注:string和vector可以用原生指針實(shí)現(xiàn),但是vs中采用自定義類型封裝的方式實(shí)現(xiàn)),但是list中的節(jié)點(diǎn)地址是不連續(xù)的,不能使用原生指針,需要使用類進(jìn)行封裝+運(yùn)算符重載實(shí)現(xiàn)。
//用類封裝迭代器 template <class T> struct __list_iterator { typedef list_node<T> node; //用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造 __list_iterator(node* p) :_pnode(p) {} //迭代器運(yùn)算符的重載 T& operator*() { return _pnode->_data; } __list_iterator<T>& operator++()//返回值不要寫成node* operator++(),因?yàn)榈?+肯定返回迭代器啊,你返回節(jié)點(diǎn)指針類型不對(duì) { //return _pnode->_next; _pnode=_pnode->_next; return *this;//返回的是迭代器 } bool operator!=(const __list_iterator<T>& it) { return _pnode != it._pnode; } public: node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針 };
const迭代器
const迭代器的錯(cuò)誤寫法:
typedef __list_iterator<T> iterator; const list<T>::iterator it=lt.begin();
因?yàn)閠ypedef后,const修飾的是迭代器it,只能調(diào)用operator*(),調(diào)不了operator++()。(重載operator++()為const operator++()也不行,因?yàn)閏onst版本++還是改變不了)
正確寫法:想實(shí)現(xiàn)const迭代器,不能在同一個(gè)類里面動(dòng)腦筋,需要再寫一個(gè)const版本迭代器的類。
//用類封裝const迭代器 template <class T> struct __list_const_iterator { typedef list_node<T> node; //用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造 __list_const_iterator(node* p) :_pnode(p) {} //迭代器運(yùn)算符的重載 const T& operator*()const { return _pnode->_data; } __list_const_iterator<T>& operator++()//返回值不要寫成node*,因?yàn)榈?+肯定返回迭代器啊,你返回節(jié)點(diǎn)指針類型不對(duì) { //return _pnode->_next;//返回類型錯(cuò)誤的 _pnode = _pnode->_next; return *this;//返回的是迭代器 } __list_const_iterator<T>& operator--() { _pnode = _pnode->_prev; return *this; } bool operator!=(const __list_const_iterator<T>& it)const { return _pnode != it._pnode; } public: node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針 }; typedef __list_const_iterator<T> const_iterator;
當(dāng)然,這樣寫__list_iterator和__list_const_iterator這兩個(gè)類會(huì)出現(xiàn)代碼重復(fù)。STL庫(kù)中是通過(guò)類模板多給一個(gè)參數(shù)來(lái)實(shí)現(xiàn),這樣,同一份類模板就可以生成兩種不同的類型的迭代器(以下為仿STL庫(kù)的模擬實(shí)現(xiàn)):
//用類封裝普通/const迭代器 template <class T,class Ref> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T,Ref> Self; //用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造 __list_iterator(node* p) :_pnode(p) {} //迭代器運(yùn)算符的重載 Ref operator*() { return _pnode->_data; } Self& operator++()//返回值不要寫成node*,因?yàn)榈?+肯定返回迭代器啊,你返回節(jié)點(diǎn)指針類型不對(duì) { //return _pnode->_next;//返回類型錯(cuò)誤的 _pnode=_pnode->_next; return *this;//返回的是迭代器 } Self& operator--() { _pnode = _pnode->_prev; return *this; } bool operator!=(const Self& it) { return _pnode != it._pnode; } public: node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針 }; typedef __list_iterator<T, T&> iterator; typedef __list_iterator<T, const T&> const_iterator;
1、封裝底層實(shí)現(xiàn),不暴露底層實(shí)現(xiàn)的細(xì)節(jié);
2、多種容器提供統(tǒng)一的訪問(wèn)方式,降低使用成本;
C語(yǔ)言沒(méi)有運(yùn)算符重載和引用等語(yǔ)法,是實(shí)現(xiàn)不了迭代器的。
迭代器的用法就是模擬指針的行為,如果現(xiàn)在有一個(gè)指向結(jié)構(gòu)的指針,那么就需要用到->來(lái)解引用。
//*的重載:返回節(jié)點(diǎn)的數(shù)據(jù) Ref operator*() { return _pnode->_data; } //->的重載:返回?cái)?shù)據(jù)的指針 T* operator->() { return &_pnode->_data; }
但是operator->使用T*做返回值類型,這樣無(wú)論是普通迭代器和const迭代器都能修改,所以operator->的返回值類型應(yīng)該改為泛型:
template <class T, class Ref,class Ptr> Ptr operator->() { return &_pnode->_data; } typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator;
1、調(diào)用拷貝構(gòu)造時(shí),鏈表內(nèi)節(jié)點(diǎn)數(shù)據(jù)為什么已經(jīng)是深拷貝了?
2、類名和類型的區(qū)別
普通類:類名等于類型
類模板:類名不等價(jià)于類型,例如list類模板類名是list,類型list<int>等。
所以我們平常寫函數(shù)形參和返回值時(shí),總會(huì)帶上形參和返回值的類型:
// 賦值運(yùn)算符重載寫法2(賦值運(yùn)算符重載都可以這么干) list<T>& operator=(list<T> lt) { swap(lt); return *this; }
但是C++在類模板里面可以用類名代替類型:
// 賦值運(yùn)算符重載寫法2(賦值運(yùn)算符重載都可以這么干) list& operator=(list lt) { swap(lt); return *this; }
建議寫代碼的時(shí)候嚴(yán)格區(qū)分類型和類名,讓自己和別人能夠看的很明白。(了解下C++有這種坑語(yǔ)法即可)
vector和list像左右手一樣,是互補(bǔ)關(guān)系,缺一不可。vector的優(yōu)點(diǎn)正是list的缺點(diǎn),list的優(yōu)點(diǎn)也是vector的缺點(diǎn),實(shí)際選用容器時(shí),按照需求擇優(yōu)選用。
vector的優(yōu)點(diǎn)(結(jié)構(gòu)厲害):
1、支持下標(biāo)的隨機(jī)訪問(wèn);
2、尾插尾刪效率高(當(dāng)然擴(kuò)容的那一次尾插尾刪會(huì)較慢);
3、CPU高速緩存命中高(數(shù)據(jù)從緩存加載至CPU中,會(huì)加載連續(xù)的一段數(shù)據(jù),vector因?yàn)榻Y(jié)構(gòu)連續(xù),高速緩存命中高)。
vector的缺點(diǎn):
1、非尾插尾刪效率低;
2、擴(kuò)容有消耗,并存在一定的空間浪費(fèi)。
vector迭代器失效問(wèn)題:
insert/erase均失效。(如果string的insert和erase形參是迭代器,那么也會(huì)失效,但是大部分接口是下標(biāo)傳參,不考慮失效問(wèn)題,只有幾個(gè)接口是迭代器傳參,需要注意迭代器失效問(wèn)題)
list的優(yōu)點(diǎn):
1、按需申請(qǐng)釋放,無(wú)需擴(kuò)容;
2、任意位置插入刪除時(shí)間O(1);(這里說(shuō)的是插入刪除,不要加上查找的時(shí)間)
list的缺點(diǎn):
1、不支持下標(biāo)的隨機(jī)訪問(wèn);
2、CPU高速緩存命中率低;
3、每一個(gè)節(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外,還需要額外存儲(chǔ)兩個(gè)指針。
list迭代器失效問(wèn)題:
insert不失效,erase失效。
#pragma once #include <iostream> #include <algorithm> #include <assert.h> #include <vector> using std::cout; using std::endl; namespace jly { //鏈表節(jié)點(diǎn)的類 template <class T> struct list_node { list_node(const T& x = T())//給一個(gè)缺省值,變成默認(rèn)構(gòu)造函數(shù) :_next(nullptr) , _prev(nullptr) , _data(x) {} list_node* _next; list_node* _prev; T _data; }; //用類封裝普通/const迭代器 template <class T, class Ref,class Ptr> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T, Ref,Ptr> Self; //用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造 __list_iterator(node* p) :_pnode(p) {} //迭代器運(yùn)算符的重載 Ref operator*() { return _pnode->_data; } Ptr operator->() { return &_pnode->_data; } Self& operator++()//返回值不要寫成node*,因?yàn)榈?+肯定返回迭代器啊,你返回節(jié)點(diǎn)指針類型不對(duì) { //return _pnode->_next;//返回類型錯(cuò)誤的 _pnode = _pnode->_next; return *this;//返回的是迭代器 } Self operator++(int)//后置++ { _pnode = _pnode->_next; return Self(_pnode->_next); } Self& operator--() { _pnode = _pnode->_prev; return *this; } Self operator--(int)//后置-- { _pnode = _pnode->_prev; return Self(_pnode->_prev); } bool operator!=(const Self& it)const { return _pnode != it._pnode; } bool operator==(const Self& it)const { return _pnode == it._pnode; } public: node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針 }; //用類封裝const迭代器 //template <class T> //struct __list_const_iterator //{ // typedef list_node<T> node; // //用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造 // __list_const_iterator(node* p) // :_pnode(p) // {} // //迭代器運(yùn)算符的重載 // const T& operator*()const // { // return _pnode->_data; // } // __list_const_iterator<T>& operator++()//返回值不要寫成node*,因?yàn)榈?+肯定返回迭代器啊,你返回節(jié)點(diǎn)指針類型不對(duì) // { // //return _pnode->_next;//返回類型錯(cuò)誤的 // _pnode = _pnode->_next; // return *this;//返回的是迭代器 // } // __list_const_iterator<T>& operator--() // { // _pnode = _pnode->_prev; // return *this; // } // bool operator!=(const __list_const_iterator<T>& it)const // { // return _pnode != it._pnode; // } //public: // node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針 //}; //鏈表類(控制哨兵位) 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; //typedef __list_const_iterator<T> const_iterator; //構(gòu)造函數(shù) void empty_initialize()//用于初始化哨兵位 { _head = new node; _head->_next = _head; _head->_prev = _head; _size = 0; } list() { empty_initialize(); } template <class InputIterator> list(InputIterator first, InputIterator last)//迭代器區(qū)間構(gòu)造 { empty_initialize(); while (first != last) { push_back(*first); ++first; } } //析構(gòu)函數(shù) ~list() { clear(); delete _head; _head = nullptr; } //拷貝構(gòu)造 list(const list<T>& lt) { 先初始化*this //empty_initialize(); //for (const auto& e : lt)//取lt的數(shù)據(jù)給e //{ // push_back(e); //} //工具人寫法 list<T> tmp(lt.begin(),lt.end()); empty_initialize(); swap(tmp); } void swap(list<T>& lt) { std::swap(_head, lt._head);//交換頭指針 std::swap(_size,lt._size); } 賦值運(yùn)算符重載寫法1 //list<T>& operator=(const list<T>& lt) //{ // //防止自己給自己賦值 // if (this != <) // { // clear(); // for (const auto& e : lt) // { // push_back(e); // } // } // return *this; //} // 賦值運(yùn)算符重載寫法2(賦值運(yùn)算符重載都可以這么干) list<T>& operator=(list<T> lt) { swap(lt);//直接交換 return *this; } //插入刪除 void push_back(const T& x) { /*node* newNode = new node(x); node* tail = _head->_prev; newNode->_prev = tail; newNode->_next = _head; tail->_next = newNode; _head->_prev = newNode;*/ 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* prev = pos._pnode->_prev; node* cur = pos._pnode; newNode->_prev = prev; newNode->_next = cur; prev->_next = newNode; cur->_prev = newNode; //return iterator(newNode); pos._pnode = newNode; ++_size; return pos; } iterator erase(iterator pos) { assert(!empty()); node* prev = pos._pnode->_prev; node* next = pos._pnode->_next; prev->_next = next; next->_prev = prev; delete pos._pnode; --_size; //return iterator(next); pos._pnode = next; return pos; } //鏈表小接口 bool empty()const { return _head->_next == _head; } void clear() { /*assert(!empty); node* cur = _head->_next; while (cur != _head) { node* next = cur->_next; delete cur; cur = next; }*/ iterator it = begin(); while (it != end()) { it = erase(it);//erase返回刪除元素的下一個(gè) } } size_t size()const { return _size; } //普通begin(),end()迭代器 iterator begin() { //return iterator(_head->_next); return __list_iterator<T, T&,T*>(_head->_next); } iterator end() { return __list_iterator<T, T&,T*>(_head); } //const begin(),end()迭代器 const_iterator begin()const { //return const_iterator(_head->_next); return __list_iterator<T, const T&,const T*>(_head->_next); } const_iterator end()const { return __list_iterator<T, const T&,const T*>(_head); } private: node* _head;//哨兵位 size_t _size;//用于統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù),空間換時(shí)間 //不加這個(gè)私有變量,統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)時(shí)間O(N),有這個(gè)私有變量,時(shí)間O(1),但是每個(gè)節(jié)點(diǎn)的體積變大 }; //測(cè)試函數(shù) struct Pos { int _row; int _col; Pos(int row = 0, int col = 0) :_row(row) , _col(col) {} }; void test() { list<Pos> i; i.push_back(Pos(1, 2)); i.push_back(Pos(2, 5)); i.push_back(Pos(4, 3)); list<Pos>::iterator it = i.begin(); while (it != i.end()) { cout << (&( * it))->_row;//*it取數(shù)據(jù),再取地址、解引用得到_row,多此一舉 cout << it->_row;//同第三種寫法,編譯器為了可讀性,省略了一個(gè)-> cout << it.operator->()->_row;//it.operator->()是顯示調(diào)用,->_row是解引用得到_row it++; } } void test1() { list<std::vector<int>> i; std::vector<int> v1(1, 2); std::vector<int> v2(2, 4); std::vector<int> v3(3, 5); i.push_back(v1); i.push_back(v2); i.push_back(v3); list<std::vector<int>> m(i); i = m; cout << m.size(); } }
關(guān)于“怎么用C++模擬實(shí)現(xiàn)STL容器”這篇文章的內(nèi)容就介紹到這里,感謝各位的閱讀!相信大家對(duì)“怎么用C++模擬實(shí)現(xiàn)STL容器”知識(shí)都有一定的了解,大家如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。