C++ deque 底层原理及 queue、stack 容器的使用详解
目錄
元素訪問
迭代器
容量
修改操作
std::erase,?std::erase_if?(std::deque)
std::swap(std::deque)
stack
queue
簡介
雙端隊(duì)列 (double-ended queue，縮寫為deque)是一個(gè)容量可以動(dòng)態(tài)變化，并且可以在兩端插入或刪除的順序容器。既然它是順序容器，那么容器中的元素就是按照嚴(yán)格的線性順序排序，可以使用類似數(shù)組的方法訪問對應(yīng)的元素。deque 實(shí)際分配的內(nèi)存數(shù)超過容納當(dāng)前所有有效元素的數(shù)量，因?yàn)?/span>空閑的空間會在增加元素的時(shí)候被利用。雙端隊(duì)列提供了類似 vector 的功能，不僅可以在容器末尾，還可以在容器開頭高效地插入或刪除元素。
?
底層結(jié)構(gòu)
這里需要簡單的了解?deque?的底層結(jié)構(gòu)，從而更好的理解和使用?deque?。deque 是由一段一段的定量連續(xù)空間構(gòu)成。一旦有必要在 deque 的前端或尾端增加新空間，便配置一段定量連續(xù)空間，串接在整個(gè) deque 的頭端或尾端。deque 的最大任務(wù)，便是在這些分段的定量連續(xù)空間上，維護(hù)其整體連續(xù)的假象，并提供隨機(jī)存取的接口。避開了“重新配置、復(fù)制、釋放”的輪回，代價(jià)則是復(fù)雜的迭代器結(jié)構(gòu)。
deque 采用一塊所謂的 map (不是STL的map容器) 作為主控。map 是一小塊連續(xù)空間，其中每個(gè)元素 (此處稱為一個(gè)節(jié)點(diǎn)，node)都是指針，指向另一段(較大的)連續(xù)線性空間，稱為緩沖區(qū)，而緩沖區(qū)才是deque的儲存空間主體。
deque 和 vector 的不同點(diǎn)從上述圖片就可以體現(xiàn)出來，vector 的存儲空間是連續(xù)的，而 deque 的存儲空間是由若干個(gè)連續(xù)空間組成的。deque 巧妙的引入了 map 作為主控，讓使用者以為使用的空間是完全連續(xù)的。這就好比我們使用的筆記本一樣，我們不需要為了做筆記而買一個(gè)幾百頁的筆記本，只需要準(zhǔn)備若干個(gè)小筆記本即可。當(dāng)一個(gè)筆記本使用完畢后，開始使用下一個(gè)筆記本。此時(shí)，只要對筆記本進(jìn)行編號就可以正確無誤的使用它們了。比如，看完了第二本筆記本的內(nèi)容，那么還需要繼續(xù)往下看，那么理所當(dāng)然的去使用第三本筆記本。
deque?的分段連續(xù)空間，維持其"整體連續(xù)"假象的這一艱巨的任務(wù)，落在了迭代器的 operator++ 和 operator-- 兩個(gè)運(yùn)算符重載身上。仔細(xì)琢磨上圖就很容易理解了。還是以筆記本為例，當(dāng)看到第二本的末尾時(shí)，還需要查看后面的內(nèi)容，那么就需要找到第三本筆記本?；蛘呤强茨骋槐竟P記本時(shí)，突然要查閱基礎(chǔ)知識?(往前查看內(nèi)容)。完成這兩個(gè)操作最重要的就是要知道筆記本的編號。在 deque 中由 map 主控完成這一任務(wù)，因?yàn)樗拇嬖?#xff0c;迭代器才能找到某一連續(xù)空間的前一段或后一段的地址，而這一過程是較為復(fù)雜的。deque 的中控器、緩沖區(qū)、迭代器的相互關(guān)系如下：
適配器概念
適配器(配接器)在STL組件中，扮演者軸承、轉(zhuǎn)換器的角色。adapter這個(gè)概念，事實(shí)上是一種設(shè)計(jì)模式。定義如下：將一個(gè)class 的接口轉(zhuǎn)換為另一個(gè) class 的接口，使原本因接口不兼容而不能合作的 class，可以一起運(yùn)作。其中改變?nèi)萜鹘涌诘?#xff0c;我們稱之為容器適配器(container adapter)。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?源自：《STL源碼剖析》
下面的 queue 和 stack，其實(shí)是一種適配器。它們修飾 deque 的接口而成就出另一種容器風(fēng)貌。由于 deque 兩端都可以完成插入和刪除操作，那么如果限制只能在一端完成插入和刪除，這樣便提供了棧的功能。如果限制只能在一端只能插入，而另一端只能刪除，便提供了隊(duì)列的功能。
std::stack?類是容器適配器，它給予程序員棧的功能——?FILO （先進(jìn)后出）數(shù)據(jù)結(jié)構(gòu)。
std::queue?類是容器適配器，它給予程序員隊(duì)列的功能——?FIFO （先進(jìn)先出）數(shù)據(jù)結(jié)構(gòu)。
?
?
元素訪問
at用于返回位于指定位置?pos?的元素的引用
reference ? ? ? at(?size_type pos?); const_reference at(?size_type pos?)?const;使用 at 時(shí)，會有有邊界檢查。若?pos?不在容器范圍內(nèi)，則拋出?std::out_of_range?類型的異常。
?
operator[]用于返回位于指定位置?pos?的元素的引用
reference ? ? ? operator[](?size_type pos?); const_reference operator[](?size_type pos?)?const;使用以上形式，不進(jìn)行邊界檢查。
#include <deque> #include <iostream>int main() {std::deque<int> numbers {2, 4, 6, 8};std::cout << "Second element: " << numbers[1] << '\n';numbers[0] = 5;std::cout << "All numbers:";for (auto i : numbers) {std::cout << ' ' << i;}std::cout << '\n'; }輸出： Second element: 4 All numbers: 5 4 6 8?
front用于返回到容器首元素的引用
reference front(); const_reference front()?const;?
back用于返回容器最后一個(gè)元素的引用
reference back(); const_reference back()?const; #include <deque> #include <iostream>int main() {std::deque<char> letters {'o', 'm', 'g', 'w', 't', 'f'};if (!letters.empty()) {std::cout << "The first character is: " << letters.front() << '\n';std::cout << "The last character is: " << letters.back() << '\n';} }輸出： The first character is o The last character is f?
迭代器
begin() & cbegin()
iterator begin()?noexcept; const_iterator begin()?const?noexcept; const_iterator cbegin()?const?noexcept;返回指向?deque?首元素的迭代器。若?deque?為空，則返回的迭代器將等于 end()。
?
end() & cend()
iterator end()?noexcept; const_iterator end()?const?noexcept; const_iterator cend()?const?noexcept;返回指向?deque?末尾元素后一元素的迭代器。此元素表現(xiàn)為占位符，試圖訪問它導(dǎo)致未定義行為。
#include <iostream> #include <deque> #include <string>int main() {std::deque<int> ints {1, 2, 4, 8, 16};std::deque<std::string> fruits {"orange", "apple", "raspberry"};std::deque<char> empty;// 求和 deque ints 中的所有整數(shù)（若存在），僅打印結(jié)果。int sum = 0;for (auto it = ints.cbegin(); it != ints.cend(); it++)sum += *it;std::cout << "Sum of ints: " << sum << "\n";// 打印 deque fruits 中的首個(gè)水果，而不檢查是否有一個(gè)。std::cout << "First fruit: " << *fruits.begin() << "\n";if (empty.begin() == empty.end())std::cout << "deque 'empty' is indeed empty.\n"; }輸出： Sum of ints: 31 First fruit: orange deque 'empty' is indeed empty.?
rbegin() & crbegin()
reverse_iterator rbegin()?noexcept; const_reverse_iterator rbegin()?const?noexcept; const_reverse_iterator crbegin()?const?noexcept;返回指向逆向?deque?首元素的逆向迭代器。它對應(yīng)非逆向?deque?的末尾元素。若?deque?為空，則返回的迭代器等于 rend()?。
?
rend() & crend()
reverse_iterator rend()?noexcept; const_reverse_iterator rend()?const?noexcept; const_reverse_iterator crend()?const?noexcept;返回指向逆向?deque?末元素后一元素的逆向迭代器。它對應(yīng)非逆向?deque?首元素的前一元素。此元素表現(xiàn)為占位符，試圖訪問它導(dǎo)致未定義行為。
?
容量
empty()
[[nodiscard]]?bool?empty()?const?noexcept;檢查容器是否無元素，即是否?begin()?==?end()?。
#include <deque> #include <iostream>int main() {std::deque<int> numbers;std::cout << "Initially, numbers.empty(): " << numbers.empty() << '\n';numbers.push_back(42);numbers.push_back(13317); std::cout << "After adding elements, numbers.empty(): " << numbers.empty() << '\n'; }輸出： Initially, numbers.empty(): 1 After adding elements, numbers.empty(): 0?
size()
size_type size()?const?noexcept;返回容器中的元素?cái)?shù)，即?std::distance(begin(), end())?。
?
max_size()
size_type max_size()?const?noexcept;返回根據(jù)系統(tǒng)或庫實(shí)現(xiàn)限制的容器可保有的元素最大數(shù)量，即對于最大容器的?std::distance(begin(), end())?。
#include <deque> #include <iostream>int main() {std::deque<int> numbers;std::cout << "Initially, numbers.empty(): " << numbers.empty() << '\n';numbers.push_back(42);numbers.push_back(13317); std::cout << "After adding elements, numbers.empty(): " << numbers.empty() << '\n'; }輸出： Initially, numbers.empty(): 1 After adding elements, numbers.empty(): 0?
shrink_to_fit()
void?shrink_to_fit();請求移除未使用的空間。它是減少使用內(nèi)存而不更改序列的大小非強(qiáng)制性請求，請求是否達(dá)成依賴于實(shí)現(xiàn)。
#include <deque>int main() {std::deque<int> nums(1000, 42);nums.push_front(1);nums.pop_front();nums.clear();// nums 現(xiàn)在不含項(xiàng)目，但它仍保有分配的內(nèi)存。// 調(diào)用 shrink_to_fit 可能會釋放任何不使用的內(nèi)存。nums.shrink_to_fit(); }?
修改操作
clear()
void?clear()?noexcept;從容器擦除所有元素。此調(diào)用后 size()?返回零。
?
insert()
(1)terator insert(?const_iterator pos,?const?T&?value?); (2)iterator insert(?const_iterator pos, T&&?value?); (3)iterator insert(?const_iterator pos, size_type count,?const?T&?value?); (4)template<?class?InputIt?>iterator insert(?const_iterator pos, InputIt first, InputIt last?); (5)iterator insert(?const_iterator pos,?std::initializer_list<T>?ilist?);插入元素到容器中的指定位置。
(1-2)?在?pos?前插入?value?。
(3)?在?pos?前插入?value?的?count?個(gè)副本。
(4)?在?pos?前插入來自范圍?[first, last)?的元素。
(5)?在?pos?前插入來自 initializer_list?ilist?的元素。
所有迭代器，含尾后迭代器，都被非法化。引用亦被非法化，除非?pos?==?begin()?或?pos?==?end()?，該情況下它們不被非法化。
?
emplace()
template<?class...?Args?>? iterator emplace(?const_iterator pos, Args&&...?args?);直接于?pos?前插入元素到容器中。通過 std::allocator_traits::construct?構(gòu)造元素，它典型地用布置 new 在容器所提供的位置原位構(gòu)造元素。將參數(shù)?args...?作為?std::forward<Args>(args)...?轉(zhuǎn)發(fā)給構(gòu)造函數(shù)。所有迭代器，含尾后迭代器，都被非法化。引用亦被非法化，除非?pos?==?begin()?或?pos?==?end()?，該情況下它們不被非法化。
?
emplace_back()
template<?class...?Args?> reference emplace_back(?Args&&...?args?);添加新元素到容器尾。元素通過?std::allocator_traits::construct??構(gòu)造，它典型地用布置 new 于容器所提供的位置原位構(gòu)造元素。參數(shù)?args...?以?std::forward<Args>(args)...?轉(zhuǎn)發(fā)到構(gòu)造函數(shù)。所有迭代器，包含尾后迭代器，都被非法化。沒有引用被非法化。
#include <deque> #include <string> #include <iostream>struct President {std::string name;std::string country;int year;President(std::string p_name, std::string p_country, int p_year): name(std::move(p_name)), country(std::move(p_country)), year(p_year){std::cout << "I am being constructed.\n";}President(President&& other): name(std::move(other.name)), country(std::move(other.country)), year(other.year){std::cout << "I am being moved.\n";}President& operator=(const President& other) = default; };int main() {std::deque<President> elections;std::cout << "emplace_back:\n";elections.emplace_back("Nelson Mandela", "South Africa", 1994);std::deque<President> reElections;std::cout << "\npush_back:\n";reElections.push_back(President("Franklin Delano Roosevelt", "the USA", 1936));std::cout << "\nContents:\n";for (President const& president: elections) {std::cout << president.name << " was elected president of "<< president.country << " in " << president.year << ".\n";}for (President const& president: reElections) {std::cout << president.name << " was re-elected president of "<< president.country << " in " << president.year << ".\n";} }輸出： emplace_back: I am being constructed.push_back: I am being constructed. I am being moved.Contents: Nelson Mandela was elected president of South Africa in 1994. Franklin Delano Roosevelt was re-elected president of the USA in 1936.?
emplace_front()
template<?class...?Args?> reference emplace_front(?Args&&...?args?);插入新元素到容器起始。通過?std::allocator_traits::construct?構(gòu)造元素，它典型地用布置 new 在容器所提供的位置原位構(gòu)造元素。將參數(shù)?args...?作為?std::forward<Args>(args)...?轉(zhuǎn)發(fā)給構(gòu)造函數(shù)。
?
erase()
iterator erase(?const_iterator pos?); iterator erase(?const_iterator first, const_iterator last?);從容器去除指定的元素。
(1)?移除位于?pos?的元素。
(2)?移除范圍?[first; last)?中的元素。
所有迭代器和引用都被非法化，除非被擦除的元素在容器的首或尾，該情況下僅指向被擦除元素的迭代器或引用被非法化。迭代器?pos?必須合法且可解引用。從而不能以?end()?迭代器（合法，但不可解引用）為?pos?的值。若?first==last?則迭代器?first?不必可解引用：擦除空范圍是無操作。
#include <deque> #include <iostream>int main( ) {std::deque<int> c{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};for (auto &i : c) {std::cout << i << " ";}std::cout << '\n';c.erase(c.begin());for (auto &i : c) {std::cout << i << " ";}std::cout << '\n';c.erase(c.begin()+2, c.begin()+5);for (auto &i : c) {std::cout << i << " ";}std::cout << '\n'; }輸出： 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 6 7 8 9?
push_back()
void?push_back(?const?T&?value?); void?push_back(?T&&?value?);將給定元素?value?附到容器最后一個(gè)元素之后。
(1)?初始化新元素為?value?的副本。
(2)?移動(dòng)?value?進(jìn)新元素。
#include <deque> #include <iostream> #include <iomanip>int main() {std::deque<std::string> numbers;numbers.push_back("abc");std::string s = "def";numbers.push_back(std::move(s));std::cout << "deque holds: ";for (auto&& i : numbers) std::cout << std::quoted(i) << ' ';std::cout << "\nMoved-from string holds " << std::quoted(s) << '\n'; }輸出： deque holds: "abc" "def" Moved-from string holds ""?
push_front()
void?push_front(?const?T&?value?); void?push_front(?T&&?value?);將給定元素?value?附到容器第一個(gè)元素之前。
?
pop_back()
void?pop_back();移除容器的最末元素，在空容器上調(diào)用?pop_back?是未定義的。
#include <deque> #include <iostream>template<class T> void print(T const & xs) {std::cout << "[ ";for(auto && x : xs) {std::cout << x << ' ';}std::cout << "]\n"; }int main() {std::deque<int> numbers;print(numbers); numbers.push_back(5);numbers.push_back(3);numbers.push_back(4);print(numbers); numbers.pop_back();print(numbers); }輸出： [ ] [ 5 3 4 ] [ 5 3 ]?
pop_front()
void?pop_front();移除容器首元素，若容器中無元素，則行為未定義。
?
resize()
void?resize(?size_type count?); void?resize(?size_type count,?const?value_type&?value?);重設(shè)容器大小以容納?count?個(gè)元素。若當(dāng)前大小大于?count?，則減小容器為其首?count?個(gè)元素。
若當(dāng)前大小小于?count?，
(1)?則后附額外的默認(rèn)插入的元素
(2)?則后附額外的?value?的副本
#include <iostream> #include <deque> int main() {std::deque<int> c = {1, 2, 3};std::cout << "The deque holds: ";for(auto& el: c) std::cout << el << ' ';std::cout << '\n';c.resize(5);std::cout << "After resize up to 5: ";for(auto& el: c) std::cout << el << ' ';std::cout << '\n';c.resize(2);std::cout << "After resize down to 2: ";for(auto& el: c) std::cout << el << ' ';std::cout << '\n'; }輸出： The deque holds: 1 2 3 After resize up to 5: 1 2 3 0 0 After resize down to 2: 1 2?
swap()
void?swap(?deque&?other?)?noexcept();將內(nèi)容與?other?的交換。不在單個(gè)元素上調(diào)用任何移動(dòng)、復(fù)制或交換操作。所有迭代器和引用保持合法，尾后迭代器被非法化。
?
?
std::erase,?std::erase_if?(std::deque)
(1)template<?class?T,?class?Alloc,?class?U?>typename?std::deque<T,Alloc>::size_typeerase(std::deque<T,Alloc>&?c,?const?U&?value); (2)template<?class?T,?class?Alloc,?class?Pred?>typename?std::deque<T,Alloc>::size_typeerase_if(std::deque<T,Alloc>&?c, Pred pred);(1)?從容器中擦除所有比較等于?value?的元素。等價(jià)于
auto it = std::remove(c.begin(), c.end(), value); auto r = std::distance(it, c.end()); c.erase(it, c.end()); return r;(2)?從容器中擦除所有滿足?pred?的元素。等價(jià)于
auto it = std::remove_if(c.begin(), c.end(), pred); auto r = std::distance(it, c.end()); c.erase(it, c.end()); return r; #include <iostream> #include <numeric> #include <deque>void print_container(const std::deque<char>& c) {for (auto x : c) {std::cout << x << ' ';}std::cout << '\n'; }int main() {std::deque<char> cnt(10);std::iota(cnt.begin(), cnt.end(), '0');std::cout << "Init:\n";print_container(cnt);auto erased = std::erase(cnt, '3');std::cout << "Erase \'3\':\n";print_container(cnt);std::erase_if(cnt, [](char x) { return (x - '0') % 2 == 0; });std::cout << "Erase all even numbers:\n";print_container(cnt);std::cout << "In all " << erased << " even numbers were erased.\n"; }輸出： Init: 0 1 2 3 4 5 6 7 8 9 Erase '3': 0 1 2 4 5 6 7 8 9 Erase all even numbers: 1 3 7 9 In all 5 even numbers were erased.?
std::swap(std::deque)
(1)template<?class?T,?class?Alloc?>void?swap(?deque<T,Alloc>&?lhs,?deque<T,Alloc>&?rhs?);(2)template<?class?T,?class?Alloc?>void?swap(?deque<T,Alloc>&?lhs,?deque<T,Alloc>&?rhs?)?noexcept();為?std::deque?特化 std::swap?算法。交換?lhs?與?rhs?的內(nèi)容。調(diào)用?lhs.swap(rhs)?。
?
?
stack
top用于返回 stack 中頂元素的引用
reference top(); const_reference top()?const;它是最近推入的元素。此元素將在調(diào)用?pop()?時(shí)被移除。等效于調(diào)用 deque 中的?c.back()，之后的函數(shù)都是調(diào)用deque中與之功能對應(yīng)的函數(shù)?。
?
empty()檢查底層容器是否為空
[[nodiscard]]?bool?empty()?const;?
size()返回底層容器中的元素?cái)?shù)
size_type size()?const;?
push()推入給定的元素?value?到棧頂
void?push(?const?value_type&?value?); void?push(?value_type&&?value?);?
emplace()
template<?class...?Args?> decltype(auto)?emplace(?Args&&...?args?);推入新元素到 stack 頂。原位構(gòu)造元素，即不進(jìn)行移動(dòng)或復(fù)制操作。以與提供給函數(shù)者準(zhǔn)確相同的參數(shù)調(diào)用元素的構(gòu)造函數(shù)。
等效地調(diào)用?c.emplace_back(std::forward<Args>(args)...);?。
?
pop()從棧頂移除元素
void?pop();?
swap()交換容器適配器的內(nèi)容
void?swap(?stack&?other?)?noexcept(); #include <stack> #include <iostream>int main() {std::stack<int> s;s.push( 2 );s.push( 6 );s.push( 51 );std::cout << s.size() << " elements on stack\n";std::cout << "Top element: "<< s.top() // 保留元素在 stack 上<< "\n";std::cout << s.size() << " elements on stack\n";s.pop();std::cout << s.size() << " elements on stack\n";std::cout << "Top element: " << s.top() << "\n";return 0; }輸出： 3 elements on stack Top element: 51 3 elements on stack 2 elements on stack Top element: 6?
?
queue
front()返回到 queue 中首個(gè)元素的引用
reference front(); const_reference front()?const;此元素將是調(diào)用?pop()?時(shí)第一個(gè)移除的元素。等效于調(diào)用deque中的?front()?。
?
back()返回到 queue 中末尾元素的引用
reference back(); const_reference back()?const;?
empty()檢查底層容器是否為空
[[nodiscard]]?bool?empty()?const;?
size()返回底層容器中的元素?cái)?shù)
size_type size()?const;?
push()推入給定的元素?value?到隊(duì)尾
void?push(?const?value_type&?value?); void?push(?value_type&&?value?);?
emplace()
template<?class...?Args?> decltype(auto)?emplace(?Args&&...?args?);推入新元素到 queue 結(jié)尾。原位構(gòu)造元素，即不進(jìn)行移動(dòng)或復(fù)制操作。以與提供給函數(shù)者準(zhǔn)確相同的參數(shù)調(diào)用元素的構(gòu)造函數(shù)。
?
pop()從隊(duì)首移除元素
void?pop();?
swap()交換容器適配器的內(nèi)容
void?swap(?queue&?other?)?noexcept();?
參考：《STL源碼剖析》
https://www.wandouip.com/t5i250718/
總結(jié)
以上是生活随笔為你收集整理的C++ deque 底层原理及 queue、stack 容器的使用详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C++ 动态二维数组(二维vector)
- 下一篇： Linux gdb多进程、多线程调试