網(wǎng)上有很多關(guān)于pos機(jī)身序列號(hào),STL 序列式容器一文全帶走的知識(shí)，也有很多人為大家解答關(guān)于pos機(jī)身序列號(hào)的問題，今天pos機(jī)之家(m.afbey.com)為大家整理了關(guān)于這方面的知識(shí)，讓我們一起來看下吧!
本文目錄一覽：
pos機(jī)身序列號(hào)
作者:herongwei
來源:微信公眾號(hào):herongwei
出處:https://mp.weixin.qq.com/s/NcrnwsB2gjq9h7W2hIZ6PQ
在 STL 編程中，容器是我們經(jīng)常會(huì)用到的一種數(shù)據(jù)結(jié)構(gòu)，容器分為序列 式 容器和關(guān)聯(lián)式容器。
兩者的本質(zhì)區(qū)別在于： 序列式容器是 通過元素在容器中的位置順序存儲(chǔ)和訪問元素，而關(guān)聯(lián)容器則是通過鍵 (key) 存儲(chǔ)和讀取元素。
本篇著重剖析序列式容器相關(guān)背后的知識(shí)點(diǎn)。
容器分類前面提到了，根據(jù)元素存儲(chǔ)方式的不同，容器可分為序列式和關(guān)聯(lián)式，那具體的又有哪些分類呢，這里我畫了一張圖來看一下。
限于篇幅，這篇文章小賀會(huì)來重點(diǎn)講解一下經(jīng)常使用到的那些容器，比如 vector，list，deque，以及衍生的棧和隊(duì)列其背后核心的設(shè)計(jì)和奧秘，不多 BB， 馬上就來分析。vector寫 C++ 的小伙伴們，應(yīng)該對 vector 都非常熟悉了，vector 基本能夠支持任何類型的對象，同時(shí)它也是一個(gè)可以動(dòng)態(tài)增長的數(shù)組，使用起來非常的方便。
但如果我問你，知道它是如何做到動(dòng)態(tài)擴(kuò)容的嗎？哎，是不是一時(shí)半會(huì)答不上來了，哈哈，沒事，我們一起來看看。
vector 基本數(shù)據(jù)結(jié)構(gòu)基本上，STL 里面所有的容器的源碼都包含至少三個(gè)部分：
迭代器，遍歷容器的元素，控制容器空間的邊界和元素的移動(dòng)；構(gòu)造函數(shù)，滿足容器的多種初始化；屬性的獲取，比如 begin()，end()等；vector 也不例外，其實(shí)看了源碼之后就發(fā)現(xiàn)，vector 相反是所有容器里面最簡單的一種。
template <class T, class Alloc = alloc>class vector {public: // 定義 vector 自身的嵌套型別 typedef T value_type; typedef value_type* pointer; typedef const value_type* const_pointer; // 定義迭代器, 這里就只是一個(gè)普通的指針 typedef value_type* iterator; typedef const value_type* const_iterator; typedef value_type& reference; typedef const value_type& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; ... protected: typedef simple_alloc<value_type, Alloc> data_allocator; // 設(shè)置其空間配置器 iterator start; // 當(dāng)前使用空間的頭 iterator finish; // 當(dāng)前使用空間的尾 iterator end_of_storage; // 當(dāng)前可用空間的尾 ...};
因?yàn)?vector 需要表示用戶操作的當(dāng)前數(shù)據(jù)的起始地址，結(jié)束地址，還需要其真正的最大地址。所以總共需要 3 個(gè)迭代器，分別來指向數(shù)據(jù)的頭(start)，數(shù)據(jù)的尾(finish)，數(shù)組的尾(end_of_storage)。
構(gòu)造函數(shù)
vector 有多個(gè)構(gòu)造函數(shù), 為了滿足多種初始化。
我們看到，這里面，初始化滿足要么都初始化成功， 要么一個(gè)都不初始化并釋放掉拋出異常，在 STL 里面，異常機(jī)制這塊拿捏的死死的呀。
因?yàn)?vector 是一種 class template， 所以呢，我們并不需要手動(dòng)的釋放內(nèi)存， 生命周期結(jié)束后就自動(dòng)調(diào)用析構(gòu)從而釋放調(diào)用空間，當(dāng)然我們也可以直接調(diào)用析構(gòu)函數(shù)釋放內(nèi)存。
void deallocate() { if (start) data_allocator::deallocate(start, end_of_storage - start);}// 調(diào)用析構(gòu)函數(shù)并釋放內(nèi)存~vector() { destroy(start, finish); deallocate();}屬性獲取
下面的部分就涉及到了位置參數(shù)的獲取， 比如返回 vector 的開始和結(jié)尾，返回最后一個(gè)元素，返回當(dāng)前元素個(gè)數(shù)，元素容量，是否為空等。
這里需要注意的是因?yàn)?end() 返回的是 finish，而 finish 是指向 最后一個(gè)元素的后一個(gè)位置的指針 ，所以使用 end() 的時(shí)候要注意。
public: // 獲取數(shù)據(jù)的開始以及結(jié)束位置的指針. 記住這里返回的是迭代器, 也就是 vector 迭代器就是該類型的指針. iterator begin() { return start; } iterator end() { return finish; } reference front() { return *begin(); } // 獲取值 reference back() { return *(end() - 1); } ... size_type size() const { return size_type(end() - begin()); } // 數(shù)組元素的個(gè)數(shù) size_type max_size() const { return size_type(-1) / sizeof(T); } // 最大能存儲(chǔ)的元素個(gè)數(shù) size_type capacity() const { return size_type(end_of_storage - begin()); } // 數(shù)組的實(shí)際大小 bool empty() const { return begin() == end(); } //判斷 vector 是否為空， 并不是比較元素為 0，是直接比較頭尾指針。push 和 pop 操作
vector 的 push 和 pop 操作都只是對尾進(jìn)行操作， 這里說的尾部是指數(shù)據(jù)的尾部。 當(dāng)調(diào)用 push_back 插入新元素的時(shí)候，首先會(huì)檢查是否有備用空間，如果有就直接在備用空間上構(gòu)造元素，并調(diào)整迭代器 finish。
當(dāng)如果沒有備用空間，就擴(kuò)充空間(重新配置-移動(dòng)數(shù)據(jù)-釋放原空間)，這里實(shí)際是調(diào)用了另外一個(gè)函數(shù)：insert_aux 函數(shù)。
在上面這張圖里，可以看到，push_back 這個(gè)函數(shù)里面又判斷了一次 finish != end_of_storage 這是因?yàn)樯赌?？這里的原因是因?yàn)?insert_aux 函數(shù)可能還被其他函數(shù)調(diào)用哦。
在下面的 else 分支里面，我們看到了 vector 的動(dòng)態(tài)擴(kuò)容機(jī)制 ：如果原空間大小為 0 則分配 1 個(gè)元素，如果大于 0 則分配原空間兩倍的新空間，然后把數(shù)據(jù)拷貝過去。
pop 元素：從尾端刪除一個(gè)元素。
public: //將尾端元素拿掉 并調(diào)整大小 void pop_back() { --finish;//將尾端標(biāo)記往前移動(dòng)一個(gè)位置 放棄尾端元素 destroy(finish); }erase 刪除元素
erase 函數(shù)清除指定位置的元素， 其重載函數(shù)用于清除一個(gè)范圍內(nèi)的所有元素。實(shí)際實(shí)現(xiàn)就是將刪除元素后面所有元素往前移動(dòng)，對于 vector 來說刪除元素的操作開銷還是很大的，所以說 vector 它不適合頻繁的刪除操作，畢竟它是一個(gè)數(shù)組。
//清楚[first, last)中的所有元素 iterator erase(iterator first, iterator last) { iterator i = copy(last, finish, first); destroy(i, finish); finish = finish - (last - first); return first; } //清除指定位置的元素 iterator erase(iterator position) { if (position + 1 != end()) copy(position + 1, finish, position);//copy 全局函數(shù) } --finish; destroy(finish); return position; } void clear() { erase(begin(), end()); }
我們結(jié)合圖解來看一下:
清楚范圍內(nèi)的元素，第一步要將 finish 迭代器后面的元素拷貝回去，然后返回拷貝完成的尾部迭代器，最后在刪除之前的。
刪除指定位置的元素就是實(shí)際就是將指定位置后面的所有元素向前移動(dòng), 最后析構(gòu)掉最后一個(gè)元素。
insert 插入元素vector 的插入元素具體來說呢，又 分三種情況：
1、如果備用空間足夠且插入點(diǎn)的現(xiàn)有元素多于新增元素；
2、如果備用空間足夠且插入點(diǎn)的現(xiàn)有元素小于新增元素；
3、如果備用空間不夠；
我們一個(gè)一個(gè)來分析。
插入點(diǎn)之后的現(xiàn)有元素個(gè)數(shù) > 新增元素個(gè)數(shù)插入點(diǎn)之后的現(xiàn)有元素個(gè)數(shù) <= 新增元素個(gè)數(shù)如果備用空間不足
這里呢，要注意一個(gè)坑，就是所謂的 迭代器失效問題 。通過圖解我們就明白了，所謂的迭代器失效問題是由于元素空間重新配置導(dǎo)致之前的迭代器訪問的元素不在了，總結(jié)來說有兩種情況：
由于插入元素，使得容器元素整體遷移導(dǎo)致存放原容器元素的空間不再有效，從而使得指向原空間的迭代器失效。由于刪除元素，使得某些元素次序發(fā)生變化導(dǎo)致原本指向某元素的迭代器不再指向期望指向的元素。前面提到的一些全局函數(shù)，這里在總結(jié)一下：
copy(a,b,c)：將(a,b)之間的元素拷貝到(c,c-(b-a))位置uninitialized_copy(first, last, result)：具體作用是將 [first,last)內(nèi)的元素拷貝到 result 從前往后拷貝copy_backward(first, last, result)：將 [first,last)內(nèi)的元素拷貝到 result 從后往前拷貝vector 總結(jié)到這里呢，vector 分析的就差不多了，最后提醒需要注意的是：vector 的成員函數(shù)都不做邊界檢查 (at方法會(huì)拋異常)，使用者要自己確保迭代器和索引值的合法性。
我們來總結(jié)一下 vector 的優(yōu)缺點(diǎn)。
優(yōu)點(diǎn)
在內(nèi)存中是分配一塊連續(xù)的內(nèi)存空間進(jìn)行存儲(chǔ)，可以像數(shù)組一樣操作，并且支持動(dòng)態(tài)擴(kuò)容。因此元素的隨機(jī)訪問方便，支持下標(biāo)訪問和 vector.at() 操作。節(jié)省空間。缺點(diǎn)
由于其順序存儲(chǔ)的特性，vector 插入刪除操作的時(shí)間復(fù)雜度是 O(n)。只能在末端進(jìn)行 pop 和 push。當(dāng)動(dòng)態(tài)長度超過默認(rèn)分配大小后，要整體重新分配、拷貝和釋放空間。list好了，下面我們來看一下 list，list 是一種雙向鏈表。
list 的設(shè)計(jì)更加復(fù)雜一點(diǎn)，好處是每次插入或刪除一個(gè)元素，就配置或釋放一個(gè)元素，list 對于空間的運(yùn)用有絕對的精準(zhǔn)，一點(diǎn)也不浪費(fèi)。而且對于任何位置的元素插入或刪除，list 永遠(yuǎn)是常數(shù)空間。
注意：list 源碼里其實(shí)分了兩個(gè)部分，一個(gè)部分是 list 結(jié)構(gòu)，另一部分是 list 節(jié)點(diǎn)的結(jié)構(gòu)。
那這里不妨思考一下，為什么 list 節(jié)點(diǎn)分為了兩個(gè)部分，而不是在一個(gè)結(jié)構(gòu)體里面呢? 也就是說為什么指針變量和數(shù)據(jù)變量分開定義呢？
如果看了后面的源碼就曉得了，這里是為了給迭代器做鋪墊，因?yàn)榈鞅闅v的時(shí)候不需要數(shù)據(jù)成員的，只需要前后指針就可以遍歷該 list。
list 的節(jié)點(diǎn)結(jié)構(gòu)如下圖所示：
list 數(shù)據(jù)結(jié)構(gòu)-節(jié)點(diǎn)__list_node 用來實(shí)現(xiàn)節(jié)點(diǎn)，數(shù)據(jù)結(jié)構(gòu)中就儲(chǔ)存前后指針和屬性。
template <class T> struct __list_node { // 前后指針 typedef void* void_pointer; void_pointer next; void_pointer prev; // 屬性 T data;};
來瞅一瞅，list 的節(jié)點(diǎn)長啥樣，因?yàn)?list 是一種雙向鏈表，所以基本結(jié)構(gòu)就是下面這個(gè)樣子：
基本類型
template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, T&, T*> iterator; // 迭代器 typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __list_iterator<T, Ref, Ptr> self; // 迭代器是bidirectional_iterator_tag類型 typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef size_t size_type; typedef ptrdiff_t difference_type; ... };
構(gòu)造函數(shù)
template<class T, class Ref, class Ptr> struct __list_iterator { ... // 定義節(jié)點(diǎn)指針 typedef __list_node<T>* link_type; link_type node; // 構(gòu)造函數(shù) __list_iterator(link_type x) : node(x) {} __list_iterator() {} __list_iterator(const iterator& x) : node(x.node) {} ... };
重載
template<class T, class Ref, class Ptr> struct __list_iterator { ... // 重載 bool operator==(const self& x) const { return node == x.node; } bool operator!=(const self& x) const { return node != x.node; } ... // ++和--是直接操作的指針指向next還是prev, 因?yàn)閘ist是一個(gè)雙向鏈表 self& operator++() { node = (link_type)((*node).next); return *this; } self operator++(int) { self tmp = *this; ++*this; return tmp; } self& operator--() { node = (link_type)((*node).prev); return *this; } self operator--(int) { self tmp = *this; --*this; return tmp; }};list 結(jié)構(gòu)
list 自己定義了嵌套類型滿足 traits 編程， list 迭代器是 bidirectional_iterator_tag 類型，并不是一個(gè)普通指針。
list 在定義 node 節(jié)點(diǎn)時(shí)， 定義的不是一個(gè)指針，這里要注意。
template <class T, class Alloc = alloc>class list {protected: typedef void* void_pointer; typedef __list_node<T> list_node; // 節(jié)點(diǎn) 就是前面分析過的 typedef simple_alloc<list_node, Alloc> list_node_allocator; // 空間配置器public: // 定義嵌套類型 typedef T value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef list_node* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; protected: // 定義一個(gè)節(jié)點(diǎn), 這里節(jié)點(diǎn)并不是一個(gè)指針. link_type node; public: // 定義迭代器 typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; ...};list 構(gòu)造和析構(gòu)函數(shù)實(shí)現(xiàn)
構(gòu)造函數(shù)前期準(zhǔn)備：
每個(gè)構(gòu)造函數(shù)都會(huì)創(chuàng)造一個(gè)空的 node 節(jié)點(diǎn)，為了保證我們在執(zhí)行任何操作都不會(huì)修改迭代器。
list 默認(rèn)使用 alloc 作為空間配置器，并根據(jù)這個(gè)另外定義了一個(gè) list_node_allocator，目的是更加方便以節(jié)點(diǎn)大小來配置單元。
template <class T, class Alloc = alloc>class list {protected: typedef void* void_pointer; typedef __list_node<T> list_node; // 節(jié)點(diǎn) typedef simple_alloc<list_node, Alloc> list_node_allocator; // 空間配置器
其中，list_node_allocator(n) 表示配置 n 個(gè)節(jié)點(diǎn)空間。以下四個(gè)函數(shù)，分別用來配置，釋放，構(gòu)造，銷毀一個(gè)節(jié)點(diǎn)。
class list {protected: // 配置一個(gè)節(jié)點(diǎn)并返回 link_type get_node() { return list_node_allocator::allocate(); } // 釋放一個(gè)節(jié)點(diǎn) void put_node(link_type p) { list_node_allocator::deallocate(p); } // 產(chǎn)生(配置并構(gòu)造)一個(gè)節(jié)點(diǎn)帶有元素初始值 link_type create_node(const T& x) { link_type p = get_node(); __STL_TRY { construct(&p->data, x); } __STL_UNWIND(put_node(p)); return p; }//銷毀(析構(gòu)并釋放)一個(gè)節(jié)點(diǎn) void destroy_node(link_type p) { destroy(&p->data); put_node(p); } // 對節(jié)點(diǎn)初始化 void empty_initialize() { node = get_node(); node->next = node; node->prev = node; } };基本屬性獲取
template <class T, class Alloc = alloc>class list { ...public: iterator begin() { return (link_type)((*node).next); } // 返回指向頭的指針 const_iterator begin() const { return (link_type)((*node).next); } iterator end() { return node; } // 返回最后一個(gè)元素的后一個(gè)的地址 const_iterator end() const { return node; } // 這里是為旋轉(zhuǎn)做準(zhǔn)備, rbegin返回最后一個(gè)地址, rend返回第一個(gè)地址. 我們放在配接器里面分析 reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } // 判斷是否為空鏈表, 這是判斷只有一個(gè)空node來表示鏈表為空. bool empty() const { return node->next == node; } // 因?yàn)檫@個(gè)鏈表, 地址并不連續(xù), 所以要自己迭代計(jì)算鏈表的長度. size_type size() const { size_type result = 0; distance(begin(), end(), result); return result; } size_type max_size() const { return size_type(-1); } // 返回第一個(gè)元素的值 reference front() { return *begin(); } const_reference front() const { return *begin(); } // 返回最后一個(gè)元素的值 reference back() { return *(--end()); } const_reference back() const { return *(--end()); } // 交換 void swap(list<T, Alloc>& x) { __STD::swap(node, x.node); } ...};template <class T, class Alloc>inline void swap(list<T, Alloc>& x, list<T, Alloc>& y) { x.swap(y);}list 的頭插和尾插
因?yàn)?list 是一個(gè)循環(huán)的雙鏈表， 所以 push 和 pop 就必須實(shí)現(xiàn)是在頭插入，刪除還是在尾插入和刪除。
在 list 中，push 操作都調(diào)用 insert 函數(shù)， pop 操作都調(diào)用 erase 函數(shù)。
template <class T, class Alloc = alloc>class list { ... // 直接在頭部或尾部插入 void push_front(const T& x) { insert(begin(), x); } void push_back(const T& x) { insert(end(), x); } // 直接在頭部或尾部刪除 void pop_front() { erase(begin()); } void pop_back() { iterator tmp = end(); erase(--tmp); } ...};
上面的兩個(gè)插入函數(shù)內(nèi)部調(diào)用的 insert 函數(shù)。
class list { ...public: // 最基本的insert操作, 之插入一個(gè)元素 iterator insert(iterator position, const T& x) { // 將元素插入指定位置的前一個(gè)地址 link_type tmp = create_node(x); tmp->next = position.node; tmp->prev = position.node->prev; (link_type(position.node->prev))->next = tmp; position.node->prev = tmp; return tmp; }
這里需要注意的是
節(jié)點(diǎn)實(shí)際是以 node 空節(jié)點(diǎn)開始的。插入操作是將元素插入到指定位置的前一個(gè)地址進(jìn)行插入的。刪除操作刪除元素的操作大都是由 erase 函數(shù)來實(shí)現(xiàn)的，其他的所有函數(shù)都是直接或間接調(diào)用 erase。
list 是鏈表，所以鏈表怎么實(shí)現(xiàn)刪除元素， list 就在怎么操作：很簡單，先保留前驅(qū)和后繼節(jié)點(diǎn)， 再調(diào)整指針位置即可。
由于它是雙向環(huán)狀鏈表，只要把邊界條件處理好，那么在頭部或者尾部插入元素操作幾乎是一樣的，同樣的道理，在頭部或者尾部刪除元素也是一樣的。
template <class T, class Alloc = alloc>class list { ... iterator erase(iterator first, iterator last); void clear(); // 參數(shù)是一個(gè)迭代器 修改該元素的前后指針指向再單獨(dú)釋放節(jié)點(diǎn)就行了 iterator erase(iterator position) { link_type next_node = link_type(position.node->next); link_type prev_node = link_type(position.node->prev); prev_node->next = next_node; next_node->prev = prev_node; destroy_node(position.node); return iterator(next_node); } ...};...}
list 內(nèi)部提供一種所謂的遷移操作(transfer)：將某連續(xù)范圍的元素遷移到某個(gè)特定位置之前，技術(shù)上實(shí)現(xiàn)其實(shí)不難，就是節(jié)點(diǎn)之間的指針移動(dòng)，只要明白了這個(gè)函數(shù)的原理，后面的 splice，sort，merge 函數(shù)也就一一知曉了，我們來看一下 transfer 的源碼：
template <class T, class Alloc = alloc>class list { ...protected: void transfer(iterator position, iterator first, iterator last) { if (position != last) { (*(link_type((*last.node).prev))).next = position.node; (*(link_type((*first.node).prev))).next = last.node; (*(link_type((*position.node).prev))).next = first.node; link_type tmp = link_type((*position.node).prev); (*position.node).prev = (*last.node).prev; (*last.node).prev = (*first.node).prev; (*first.node).prev = tmp; } } ...};
上面代碼的七行分別對應(yīng)下圖的七個(gè)步驟，看明白應(yīng)該不難吧。
另外 list 的其它的一些成員函數(shù)這里限于篇幅，就不貼出源碼了，簡單說一些注意點(diǎn)。
splice函數(shù)：將兩個(gè)鏈表進(jìn)行合并：內(nèi)部就是調(diào)用的 transfer 函數(shù)。
merge 函數(shù)：將傳入的 list 鏈表 x 與原鏈表按從小到大合并到原鏈表中(前提是兩個(gè)鏈表都是已經(jīng)從小到大排序了). 這里 merge 的核心就是 transfer 函數(shù)。
reverse 函數(shù)：實(shí)現(xiàn)將鏈表翻轉(zhuǎn)的功能：主要是 list 的迭代器基本不會(huì)改變的特點(diǎn), 將每一個(gè)元素一個(gè)個(gè)插入到 begin 之前。
sort 函數(shù)：list 這個(gè)容器居然還自己實(shí)現(xiàn)一個(gè)排序，看一眼源碼就發(fā)現(xiàn)其實(shí)內(nèi)部調(diào)用的 merge 函數(shù)，用了一個(gè)數(shù)組鏈表用來存儲(chǔ) 2^i 個(gè)元素, 當(dāng)上一個(gè)元素存儲(chǔ)滿了之后繼續(xù)往下一個(gè)鏈表存儲(chǔ), 最后將所有的鏈表進(jìn)行 merge歸并(合并), 從而實(shí)現(xiàn)了鏈表的排序。
賦值操作：需要考慮兩個(gè)鏈表的實(shí)際大小不一樣時(shí)的操作：如果 原鏈表大 : 復(fù)制完后要?jiǎng)h除掉原鏈表多余的元素；如果原鏈表小 : 復(fù)制完后要還要將x鏈表的剩余元素以插入的方式插入到原鏈表中。
resize 操作：重新修改 list 的大小， 傳入一個(gè) new_size，如果鏈表舊長度大于 new_size 的大小, 那就刪除后面多余的節(jié)點(diǎn)。
clear 操作：清除所有節(jié)點(diǎn)：遍歷每一個(gè)節(jié)點(diǎn)，銷毀(析構(gòu)并釋放)一個(gè)節(jié)點(diǎn)。
remove 操作：清除指定值的元素：遍歷每一個(gè)節(jié)點(diǎn)，找到就移除。
unique 操作：清除數(shù)值相同的連續(xù)元素，注意只有“連續(xù)而相同的元素”，才會(huì)被移除剩一個(gè)：遍歷每一個(gè)節(jié)點(diǎn)，如果在此區(qū)間段有相同的元素就移除之。
感興趣的讀者可以自行去閱讀源碼體會(huì)。
list 總結(jié)
我們來總結(jié)一下。
list 是一種雙向鏈表。每個(gè)結(jié)點(diǎn)都包含一個(gè)數(shù)據(jù)域、一個(gè)前驅(qū)指針 prev 和一個(gè)后驅(qū)指針 next。
由于其鏈表特性，實(shí)現(xiàn)同樣的操作，相對于 STL 中的通用算法， list 的成員函數(shù)通常有更高的效率，內(nèi)部僅需做一些指針的操作，因此盡可能選擇 list 成員函數(shù)。
優(yōu)點(diǎn)在內(nèi)部方便進(jìn)行插入刪除操作。可在兩端進(jìn)行push和pop操作。缺點(diǎn)不支持隨機(jī)訪問，即下標(biāo)操作和.at()。相對于 vector 占用內(nèi)存多。deque下面到了本篇最硬核的內(nèi)容了，接下來我們學(xué)習(xí)一下 雙端隊(duì)列 deque 。
deque 的功能很強(qiáng)大。
首先來一張圖吧。
上面就是 deque 的示例圖，deque 和 vector 的最大差異一在于 deque 允許常數(shù)時(shí)間內(nèi)對頭端或尾端進(jìn)行元素的插入或移除操作。
二在于 deque 沒有所謂的容量概念，因?yàn)樗莿?dòng)態(tài)地以分段連續(xù)空間組合而成 隨時(shí)可以增加一塊新的空間并拼接起來。
雖然 deque 也提供 隨機(jī)訪問的迭代器，但它的迭代器和前面兩種容器的都不一樣，其設(shè)計(jì)相當(dāng)復(fù)雜度和精妙，因此，會(huì)對各種運(yùn)算產(chǎn)生一定影響，除非必要，盡可能的選擇使用 vector 而非 deque。一一來探究下吧。
deque 的中控器deque 在邏輯上看起來是連續(xù)空間，內(nèi)部確實(shí)是由一段一段的定量連續(xù)空間構(gòu)成。
一旦有必要在 deque 的前端或尾端增加新空間，deque 便會(huì)配置一段定量的連續(xù)空間，串接在整個(gè) deque 的頭部或尾部。
設(shè)計(jì) deque 的大師們，想必設(shè)計(jì)的時(shí)候遇到的最大挑戰(zhàn)就是如何在這些分段的定量連續(xù)空間上，還能維護(hù)其整體連續(xù)的假象，并提供其隨機(jī)存取的接口，從而避開了像 vector 那樣的“重新配置-復(fù)制-釋放”開銷三部曲。
這樣一來，雖然開銷降低，卻提高了復(fù)雜的迭代器架構(gòu)。
因此 deque 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和迭代器前進(jìn)或后退等操作都非常復(fù)雜。
deque 采用一塊所謂的 map （注意不是 STL 里面的 map 容器）作為中控器，其實(shí)就是一小塊連續(xù)空間，其中的每個(gè)元素都是指針，指向另外一段較大的連續(xù)線性空間，稱之為 緩沖區(qū)。 在后面我們看到，緩沖區(qū)才是 deque 的儲(chǔ)存空間主體。
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUGtemplate <class T, class Ref, class Ptr, size_t BufSiz>class deque {public: typedef T value_type; typedef value_type* pointer; ...protected: typedef pointer** map_pointer; map_pointer map;//指向 map，map 是連續(xù)空間，其內(nèi)的每個(gè)元素都是一個(gè)指針。 size_type map_size; ...};
其示例圖如下：deque 的結(jié)構(gòu)設(shè)計(jì)中，map 和 node-buffer 的關(guān)系如下：
deque 的迭代器deque 是分段連續(xù)空間，維持其“整體連續(xù)”假象的任務(wù)，就靠它的迭代器來實(shí)現(xiàn)，也就是 operator++ 和 operator-- 兩個(gè)運(yùn)算子上面。
在看源碼之前，我們可以思考一下，如果讓你來設(shè)計(jì)，你覺得 deque 的迭代器應(yīng)該具備什么樣的結(jié)構(gòu)和功能呢？
首先第一點(diǎn)，我們能想到的是，既然是分段連續(xù)，迭代器應(yīng)該能指出當(dāng)前的連續(xù)空間在哪里；
其次，第二點(diǎn)因?yàn)榫彌_區(qū)有邊界，迭代器還應(yīng)該要能判斷，當(dāng)前是否處于所在緩沖區(qū)的邊緣，如果是，一旦前進(jìn)或后退，就必須跳轉(zhuǎn)到下一個(gè)或上一個(gè)緩沖區(qū)；
第三點(diǎn)，也就是實(shí)現(xiàn)前面兩種情況的前提，迭代器必須能隨時(shí)控制中控器。
有了這樣的思想準(zhǔn)備之后，我們再來看源碼，就顯得容易理解一些了。
template <class T, class Ref, class Ptr, size_t BufSiz>struct __deque_iterator { // 迭代器定義 typedef __deque_iterator<T, T&, T*, BufSiz> iterator; typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator; static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); } // deque是random_access_iterator_tag類型 typedef random_access_iterator_tag iterator_category; // 基本類型的定義, 滿足traits編程 typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef size_t size_type; typedef ptrdiff_t difference_type; // node typedef T** map_pointer; map_pointer node; typedef __deque_iterator self; ...};
deque 的每一個(gè)緩沖區(qū)由設(shè)計(jì)了三個(gè)迭代器（為什么這樣設(shè)計(jì)？）
struct __deque_iterator { ... typedef T value_type; T* cur; T* first; T* last; typedef T** map_pointer; map_pointer node; ...};
對啊，它為什么要這樣設(shè)計(jì)呢？回到前面我們剛才說的，因?yàn)樗欠侄芜B續(xù)的空間。
下圖描繪了 deque 的中控器、緩沖區(qū)、迭代器之間的相互關(guān)系：
看明白了嗎，每一段都指向一個(gè)緩沖區(qū) buffer，而緩沖區(qū)是需要知道每個(gè)元素的位置的，所以需要這些迭代器去訪問。
其中 cur 表示當(dāng)前所指的位置；
first 表示當(dāng)前數(shù)組中頭的位置；
last 表示當(dāng)前數(shù)組中尾的位置。
這樣就方便管理， 需要注意的是 deque 的空間是由 map 管理的， 它是一個(gè)指向指針的指針， 所以三個(gè)參數(shù)都是指向當(dāng)前的數(shù)組，但這樣的數(shù)組可能有多個(gè)，只是每個(gè)數(shù)組都管理這3個(gè)變量。
那么，緩沖區(qū)大小是誰來決定的呢？這里呢，用來決定緩沖區(qū)大小的是一個(gè)全局函數(shù):
inline size_t __deque_buf_size(size_t n, size_t sz) { return n != 0 ? n : (sz < 512 ? size_t(512 / sz): size_t(1));}//如果 n 不為0，則返回 n，表示緩沖區(qū)大小由用戶自定義//如果 n == 0，表示 緩沖區(qū)大小默認(rèn)值//如果 sz = (元素大小 sizeof(value_type)) 小于 512 則返回 521/sz//如果 sz 不小于 512 則返回 1
我們來舉例說明一下：
假設(shè)我們現(xiàn)在構(gòu)造了一個(gè) int 類型的 deque，設(shè)置緩沖區(qū)大小等于 32，這樣一來，每個(gè)緩沖區(qū)可以容納 32/sizeof(int) = 4 個(gè)元素。經(jīng)過一番操作之后，deque 現(xiàn)在有 20 個(gè)元素了，那么成員函數(shù) begin() 和 end() 返回的兩個(gè)迭代器應(yīng)該是怎樣的呢？
如下圖所示：
20 個(gè)元素需要 20/(sizeof(int)) = 3 個(gè)緩沖區(qū)。
所以 map 運(yùn)用了三個(gè)節(jié)點(diǎn)，迭代器 start 內(nèi)的 cur 指針指向緩沖區(qū)的第一個(gè)元素，迭代器 finish 內(nèi)的 cur 指針指向緩沖區(qū)的最后一個(gè)元素(的下一個(gè)位置)。
注意，最后一個(gè)緩沖區(qū)尚有備用空間，如果之后還有新元素插入，則直接插入到備用空間。
deque 迭代器的操作主要就是兩種：前進(jìn)和后退。
operator++ 操作代表是需要切換到下一個(gè)元素，這里需要先切換再判斷是否已經(jīng)到達(dá)緩沖區(qū)的末尾。
self& operator++() { ++cur; //切換至下一個(gè)元素 if (cur == last) { //如果已經(jīng)到達(dá)所在緩沖區(qū)的末尾 set_node(node+1); //切換下一個(gè)節(jié)點(diǎn) cur = first; } return *this;}
operator-- 操作代表切換到上一個(gè)元素所在的位置，需要先判斷是否到達(dá)緩沖區(qū)的頭部，再后退。
self& operator--() { if (cur == first) { //如果已經(jīng)到達(dá)所在緩沖區(qū)的頭部 set_node(node - 1); //切換前一個(gè)節(jié)點(diǎn)的最后一個(gè)元素 cur = last; } --cur; //切換前一個(gè)元素 return *this;} //結(jié)合前面的分段連續(xù)空間，你在想一想這樣的設(shè)計(jì)是不是合理呢？deque 的構(gòu)造和析構(gòu)函數(shù)
deque 的構(gòu)造函數(shù)有多個(gè)重載函數(shù)，接受大部分不同的參數(shù)類型，基本上每一個(gè)構(gòu)造函數(shù)都會(huì)調(diào)用 create_map_and_nodes，這就是構(gòu)造函數(shù)的核心，后面我們來分析這個(gè)函數(shù)的實(shí)現(xiàn)。
template <class T, class Alloc = alloc, size_t BufSiz = 0> class deque { ...public: // Basic types deque() : start(), finish(), map(0), map_size(0){ create_map_and_nodes(0); } // 默認(rèn)構(gòu)造函數(shù) deque(const deque& x) : start(), finish(), map(0), map_size(0) { create_map_and_nodes(x.size()); __STL_TRY { uninitialized_copy(x.begin(), x.end(), start); } __STL_UNWIND(destroy_map_and_nodes()); } // 接受 n:初始化大小, value:初始化的值 deque(size_type n, const value_type& value) : start(), finish(), map(0), map_size(0) { fill_initialize(n, value); } deque(int n, const value_type& value) : start(), finish(), map(0), map_size(0) { fill_initialize(n, value); } deque(long n, const value_type& value) : start(), finish(), map(0), map_size(0){ fill_initialize(n, value); } ...
下面我們來看一下 deque 的中控器是如何配置的。
void deque<T,Alloc,BufSize>::create_map_and_nodes(size_type_num_elements) { //需要節(jié)點(diǎn)數(shù)= (每個(gè)元素/每個(gè)緩沖區(qū)可容納的元素個(gè)數(shù)+1) //如果剛好整除，多配一個(gè)節(jié)點(diǎn) size_type num_nodes = num_elements / buffer_size() + 1; //一個(gè) map 要管理幾個(gè)節(jié)點(diǎn)，最少 8 個(gè)，最多是需要節(jié)點(diǎn)數(shù)+2 map_size = max(initial_map_size(), num_nodes + 2); map = map_allocator::allocate(map_size); // 計(jì)算出數(shù)組的頭前面留出來的位置保存并在nstart. map_pointer nstart = map + (map_size - num_nodes) / 2; map_pointer nfinish = nstart + num_nodes - 1; map_pointer cur;//指向所擁有的節(jié)點(diǎn)的最中央位置 ...}
注意了，看了源碼之后才知道： deque 的 begin 和 end 不是一開始就是指向 map 中控器里開頭和結(jié)尾的，而是指向所擁有的節(jié)點(diǎn)的最中央位置 。
這樣帶來的好處是可以使得頭尾兩邊擴(kuò)充的可能性和一樣大，換句話來說，因?yàn)?deque 是頭尾插入都是 O(1)， 所以 deque 在頭和尾都留有空間方便頭尾插入。
那么，什么時(shí)候 map 中控器 本身需要調(diào)整大小呢？觸發(fā)條件在于 reserve_map_at_back 和 reserve_map_at_front 這兩個(gè)函數(shù)來判斷，實(shí)際操作由 reallocate_map 來執(zhí)行。
那 reallocate_map 又是如何操作的呢？這里先留個(gè)懸念。
// 如果 map 尾端的節(jié)點(diǎn)備用空間不足，符合條件就配置一個(gè)新的map(配置更大的，拷貝原來的，釋放原來的)void reserve_map_at_back (size_type nodes_to_add = 1) { if (nodes_to_add + 1 > map_size - (finish.node - map)) reallocate_map(nodes_to_add, false);}// 如果 map 前端的節(jié)點(diǎn)備用空間不足，符合條件就配置一個(gè)新的map(配置更大的，拷貝原來的，釋放原來的)void reserve_map_at_front (size_type nodes_to_add = 1) { if (nodes_to_add > start.node - map) reallocate_map(nodes_to_add, true);}deque 的插入元素和刪除元素
因?yàn)?deque 的是能夠雙向操作，所以其 push 和 pop 操作都類似于 list 都可以直接有對應(yīng)的操作，需要注意的是 list 是鏈表，并不會(huì)涉及到界線的判斷， 而deque 是由數(shù)組來存儲(chǔ)的，就需要隨時(shí)對界線進(jìn)行判斷。
push 實(shí)現(xiàn)
template <class T, class Alloc = alloc, size_t BufSiz = 0> class deque { ...public: // push_* and pop_* // 對尾進(jìn)行插入 // 判斷函數(shù)是否達(dá)到了數(shù)組尾部. 沒有達(dá)到就直接進(jìn)行插入 void push_back(const value_type& t) { if (finish.cur != finish.last - 1) { construct(finish.cur, t); ++finish.cur; } else push_back_aux(t); } // 對頭進(jìn)行插入 // 判斷函數(shù)是否達(dá)到了數(shù)組頭部. 沒有達(dá)到就直接進(jìn)行插入 void push_front(const value_type& t) { if (start.cur != start.first) { construct(start.cur - 1, t); --start.cur; } else push_front_aux(t); } ...};
pop 實(shí)現(xiàn)
template <class T, class Alloc = alloc, size_t BufSiz = 0> class deque { ...public: // 對尾部進(jìn)行操作 // 判斷是否達(dá)到數(shù)組的頭部. 沒有到達(dá)就直接釋放 void pop_back() { if (finish.cur != finish.first) { --finish.cur; destroy(finish.cur); } else pop_back_aux(); } // 對頭部進(jìn)行操作 // 判斷是否達(dá)到數(shù)組的尾部. 沒有到達(dá)就直接釋放 void pop_front() { if (start.cur != start.last - 1) { destroy(start.cur); ++start.cur; } else pop_front_aux(); } ...};
pop 和 push 都先調(diào)用了 reserve_map_at_XX 函數(shù)，這些函數(shù)主要是為了判斷前后空間是否足夠。
刪除操作不知道還記得，最開始構(gòu)造函數(shù)調(diào)用 create_map_and_nodes 函數(shù)，考慮到 deque 實(shí)現(xiàn)前后插入時(shí)間復(fù)雜度為O(1)，保證了在前后留出了空間，所以 push 和 pop 都可以在前面的數(shù)組進(jìn)行操作。
現(xiàn)在就來看 erase，因?yàn)?deque 是由數(shù)組構(gòu)成，所以地址空間是連續(xù)的，刪除也就像 vector一樣，要移動(dòng)所有的元素。
deque 為了保證效率盡可能的高，就判斷刪除的位置是中間偏后還是中間偏前來進(jìn)行移動(dòng)。
template <class T, class Alloc = alloc, size_t BufSiz = 0> class deque { ...public: // erase iterator erase(iterator pos) { iterator next = pos; ++next; difference_type index = pos - start; // 刪除的地方是中間偏前, 移動(dòng)前面的元素 if (index < (size() >> 1)) { copy_backward(start, pos, next); pop_front(); } // 刪除的地方是中間偏后, 移動(dòng)后面的元素 else { copy(next, finish, pos); pop_back(); } return start + index; } // 范圍刪除, 實(shí)際也是調(diào)用上面的erase函數(shù). iterator erase(iterator first, iterator last); void clear(); ...};
最后講一下 insert 函數(shù)
deque 源碼的基本每一個(gè)insert 重載函數(shù)都會(huì)調(diào)用了 insert_auto 判斷插入的位置離頭還是尾比較近。
如果離頭進(jìn)：則先將頭往前移動(dòng)，調(diào)整將要移動(dòng)的距離，用 copy 進(jìn)行調(diào)整。
如果離尾近：則將尾往前移動(dòng)，調(diào)整將要移動(dòng)的距離，用 copy 進(jìn)行調(diào)整。
注意 :push_back 是先執(zhí)行構(gòu)造在移動(dòng) node，而 push_front 是先移動(dòng) node 在進(jìn)行構(gòu)造，實(shí)現(xiàn)的差異主要是 finish 是指向最后一個(gè)元素的后一個(gè)地址而 first指 向的就只第一個(gè)元素的地址，下面 pop 也是一樣的。
deque 源碼里還有一些其它的成員函數(shù)，限于篇幅，這里就不貼出來了，簡單的過一遍
reallocate_map：判斷中控器的容量是否夠用，如果不夠用，申請更大的空間，拷貝元素過去，修改 map 和 start，finish 的指向。
fill_initialize 函數(shù)：申請空間，對每個(gè)空間進(jìn)行初始化，最后一個(gè)數(shù)組單獨(dú)處理。畢竟最后一個(gè)數(shù)組一般不是會(huì)全部填充滿。
clear 函數(shù)：刪除所有元素，分兩步執(zhí)行：
首先從第二個(gè)數(shù)組開始到倒數(shù)第二個(gè)數(shù)組一次性全部刪除，這樣做是考慮到中間的數(shù)組肯定都是滿的，前后兩個(gè)數(shù)組就不一定是填充滿的，最后刪除前后兩個(gè)數(shù)組的元素。
deque 的 swap 操作：只是交換了 start, finish, map，并沒有交換所有的元素。
resize 函數(shù)：重新將 deque 進(jìn)行調(diào)整, 實(shí)現(xiàn)與 list一樣的。
析構(gòu)函數(shù)：分步釋放內(nèi)存。
deque 總結(jié)deque 其實(shí)是在功能上合并了 vector 和 list。
優(yōu)點(diǎn)：
1、隨機(jī)訪問方便，即支持 [ ] 操作符和 vector.at()；
2、在內(nèi)部方便的進(jìn)行插入和刪除操作；
3、可在兩端進(jìn)行 push、pop
缺點(diǎn)：因?yàn)樯婕氨容^復(fù)雜，采用分段連續(xù)空間，所以占用內(nèi)存相對多。
使用區(qū)別：1、如果你需要高效的隨即存取，而不在乎插入和刪除的效率，使用 vector。
2、如果你需要大量的插入和刪除，而不關(guān)心隨機(jī)存取，則應(yīng)使用 list。
3、如果你需要隨機(jī)存取，而且關(guān)心兩端數(shù)據(jù)的插入和刪除，則應(yīng)使用 deque 。
棧和隊(duì)列以 deque 為底層容器的適配器
最后要介紹的三種常用的數(shù)據(jù)結(jié)構(gòu)，準(zhǔn)確來說其實(shí)是一種適配器，底層都是已其它容器為基準(zhǔn)。
棧-stack：先入后出，只允許在棧頂添加和刪除元素，稱為出棧和入棧。
隊(duì)列-queue：先入先出，在隊(duì)首取元素，在隊(duì)尾添加元素，稱為出隊(duì)和入隊(duì)。
優(yōu)先隊(duì)列-priority_queue：帶權(quán)值的隊(duì)列。
常見棧的應(yīng)用場景包括括號(hào)問題的求解，表達(dá)式的轉(zhuǎn)換和求值，函數(shù)調(diào)用和遞歸實(shí)現(xiàn)，深度優(yōu)先遍歷 DFS 等；
常見的隊(duì)列的應(yīng)用場景包括計(jì)算機(jī)系統(tǒng)中各種資源的管理，消息緩沖隊(duì)列的管理和廣度優(yōu)先遍歷 BFS 等。
翻一下源碼，就知道 stack 和 queue 的底層其實(shí)就是使用 deque，用 deque 為底層容器封裝。
stack 的源碼：
#ifndef __STL_LIMITED_DEFAULT_TEMPLATEStemplate <class T, class Sequence = deque<T> >#elsetemplate <class T, class Sequence>#endifclass stack {public: typedef typename Sequence::value_type value_type; typedef typename Sequence::size_type size_type; typedef typename Sequence::reference reference; typedef typename Sequence::const_reference const_reference;protected: Sequence c;
queue 的源碼：
#ifndef __STL_LIMITED_DEFAULT_TEMPLATEStemplate <class T, class Sequence = deque<T> >#elsetemplate <class T, class Sequence>#endifclass queue {public: typedef typename Sequence::value_type value_type; typedef typename Sequence::size_type size_type; typedef typename Sequence::reference reference; typedef typename Sequence::const_reference const_reference;protected: Sequence c;heap堆
最后我們來看一下，heap ，heap 并不是一個(gè)容器，所以他沒有實(shí)現(xiàn)自己的迭代器，也就沒有遍歷操作，它只是一種算法。
push_heap 插入元素插入函數(shù)是 push_heap， heap 只接受 RandomAccessIterator 類型的迭代器。
template <class RandomAccessIterator>inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) { __push_heap_aux(first, last, distance_type(first), value_type(first));}template <class RandomAccessIterator, class Distance, class T>inline void __push_heap_aux(RandomAccessIterator first, RandomAccessIterator last, Distance*, T*) { // 這里傳入的是兩個(gè)迭代器的長度, 0, 還有最后一個(gè)數(shù)據(jù) __push_heap(first, Distance((last - first) - 1), Distance(0), T(*(last - 1)));}pop_heap 刪除元素
pop 操作其實(shí)并沒有真正意義去刪除數(shù)據(jù)，而是將數(shù)據(jù)放在最后，只是沒有指向最后的元素而已，這里使用 arrary 也可以，畢竟沒有對數(shù)組的大小進(jìn)行調(diào)整。
pop 的實(shí)現(xiàn)有兩種，這里都羅列了出來，另一個(gè)傳入的是 cmp 仿函數(shù)。
template <class RandomAccessIterator, class Compare>inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp) { __pop_heap_aux(first, last, value_type(first), comp);}template <class RandomAccessIterator, class T, class Compare>inline void __pop_heap_aux(RandomAccessIterator first, RandomAccessIterator last, T*, Compare comp) { __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp, distance_type(first));}template <class RandomAccessIterator, class T, class Compare, class Distance>inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result, T value, Compare comp, Distance*) { *result = *first; __adjust_heap(first, Distance(0), Distance(last - first), value, comp);}template <class RandomAccessIterator, class T, class Distance>inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result, T value, Distance*) { *result = *first; // 因?yàn)檫@里是大根堆, 所以first的值就是最大值, 先將最大值保存. __adjust_heap(first, Distance(0), Distance(last - first), value);}
make_heap 將數(shù)組變成堆存放
template <class RandomAccessIterator>inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) { __make_heap(first, last, value_type(first), distance_type(first));}template <class RandomAccessIterator, class T, class Distance>void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*, Distance*) { if (last - first < 2) return; // 計(jì)算長度, 并找出中間的根值 Distance len = last - first; Distance parent = (len - 2)/2; while (true) { // 一個(gè)個(gè)進(jìn)行調(diào)整, 放到后面 __adjust_heap(first, parent, len, T(*(first + parent))); if (parent == 0) return; parent--; }}sort_heap 實(shí)現(xiàn)堆排序
其實(shí)就是每次將第一位數(shù)據(jù)彈出從而實(shí)現(xiàn)排序功。
template <class RandomAccessIterator>void sort_heap(RandomAccessIterator first, RandomAccessIterator last) { while (last - first > 1) pop_heap(first, last--);}template <class RandomAccessIterator, class Compare>void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp) { while (last - first > 1) pop_heap(first, last--, comp);}priority_queue 優(yōu)先隊(duì)列
最后我們來看一下 priority_queue。
上一節(jié)分析 heap 其實(shí)就是為 priority_queue 做準(zhǔn)備，priority_queue 是一個(gè)優(yōu)先級(jí)隊(duì)列，是帶權(quán)值的， 支持插入和刪除操作，其只能從尾部插入，頭部刪除， 并且其順序也并非是根據(jù)加入的順序排列的。
priority_queue 因?yàn)橐彩顷?duì)列的一種體現(xiàn)， 所以也就跟隊(duì)列一樣不能直接的遍歷數(shù)組，也就沒有迭代器。
priority_queue 本身也不算是一個(gè)容器，它是 以 vector 為容器以 heap為數(shù)據(jù)操作的配置器。
類型定義
#ifndef __STL_LIMITED_DEFAULT_TEMPLATEStemplate <class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type> >#elsetemplate <class T, class Sequence, class Compare>#endifclass priority_queue {public: // 符合traits編程規(guī)范 typedef typename Sequence::value_type value_type; typedef typename Sequence::size_type size_type; typedef typename Sequence::reference reference; typedef typename Sequence::const_reference const_reference;protected: Sequence c; // 定義vector容器的對象 Compare comp; // 定義比較函數(shù)(偽函數(shù)) ...};
屬性獲取
priority_queue 只有簡單的 3 個(gè)屬性獲取的函數(shù), 其本身的操作也很簡單, 只是實(shí)現(xiàn)依賴了 vector 和 heap 就變得比較復(fù)雜。
class priority_queue { ...public: bool empty() const { return c.empty(); } size_type size() const { return c.size(); } const_reference top() const { return c.front(); } ...};
push 和 pop 實(shí)現(xiàn)
push 和 pop 具體都是采用的 heap 算法。
priority_queue 本身實(shí)現(xiàn)是很復(fù)雜的，但是當(dāng)我們已經(jīng)了解過 vector，heap 之后再來看，它其實(shí)就簡單了。
就是將 vector 作為容器， heap 作為算法來操作的配置器，這也體現(xiàn)了 STL 的靈活性： 通過各個(gè)容器與算法的結(jié)合就能實(shí)現(xiàn)另一種功能。
最后，來自實(shí)踐生產(chǎn)環(huán)境的一個(gè)體會(huì)：上面所列的所有容器的一個(gè)原則：為了避免拷貝開銷，不要直接把大的對象直接往里塞，而是使用指針。
好了，本期的內(nèi)容就到這里了，我們下期再見。
PS：看有多少人 點(diǎn)贊，下期不定期更新關(guān)聯(lián)式容器哦，先買個(gè)關(guān)子，下期有個(gè)硬核的內(nèi)容帶大家手撕紅黑樹源碼，紅黑樹的應(yīng)用可以說很廣了，像 Java 集合中的 TreeSet 和 TreeMap、STL 中的 set 和 map、Linux 虛擬內(nèi)存的管理都用到了哦。
參考
1、《STL 源碼剖析》
2、https://github.com/FunctionDou/STL
作者:herongwei
來源:微信公眾號(hào):herongwei
出處:https://mp.weixin.qq.com/s/NcrnwsB2gjq9h7W2hIZ6PQ
以上就是關(guān)于pos機(jī)身序列號(hào),STL 序列式容器一文全帶走的知識(shí)，后面我們會(huì)繼續(xù)為大家整理關(guān)于pos機(jī)身序列號(hào)的知識(shí)，希望能夠幫助到大家！
