雙端隊(duì)列和C++ std::deque詳解
1. 雙端隊(duì)列和std::duque
雙端隊(duì)列實(shí)際上是
std::duque（double-venden queue, 雙端隊(duì)列）是C++容器庫里中有下標(biāo)順序容器，它允許在首尾部兩端快速的插入和刪除元素。其與std::vector的存儲(chǔ)方式不同，deque的元素不是連續(xù)存儲(chǔ)的。
2. deque的用法
2.1 deque的定義和聲明
std::deque在頭文件<deque>中定義，其聲明如下：
template<
? ?class T,
? ?class Allocator = std::allocator<T>
> class deque;
namespace pmr {
? ?template< class T >
? ?using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>; ? ? //C++17 起
}
其中，參數(shù)T為容器要存儲(chǔ)的元素類型，對(duì)于T需要滿足：
可復(fù)制賦值和可復(fù)制構(gòu)造（C++11前）。
可擦除，即元素類型的對(duì)象能以給定的分配器（Allocator）銷毀（C++11 起）。
Allocator為用于獲取/釋放內(nèi)存及構(gòu)造/析構(gòu)內(nèi)存中元素的分配器。
2.2 成員函數(shù)
2.2.1 元素訪問
assign
assign函數(shù)的主要作用是將元素從 deque 中清除并將新的元素序列復(fù)制到目標(biāo)deque。其函數(shù)聲明如下：
//以count份value的副本替換內(nèi)容。
void assign( size_type count, const T& value );
//以范圍[first, last)中元素的副本替換內(nèi)容。
template< class InputIt >
void assign( InputIt first, InputIt last );
//以來自initializer_list ilist的元素替換內(nèi)容。
void assign( std::initializer_list<T> ilist ); //C++11 起
其具體用法如下：
std::deque<char> char_deque;
char_deque.assign(5, 'a');//此時(shí)char_deque = {'a', 'a', 'a', 'a', 'a'}
const std::string str(6, 'b');
char_deque.assign(str.begin(), str.end());//此時(shí)char_deque存儲(chǔ)的元素分別為{'b', 'b', 'b', 'b', 'b', 'b'}
char_deque.assign({'C', '+', '+', '1', '1'});//此時(shí)char_deque存儲(chǔ)的元素分別為{'C', '+', '+', '1', '1'}
at
at用于訪問指定的元素，同時(shí)進(jìn)行越界檢查，該函數(shù)返回位于指定位置pos的元素的引用，如果pos不在容器的范圍內(nèi)，則拋出std::out_of_range異常。其函數(shù)聲明如下：
reference ? ? ? at( size_type pos );
const_reference at( size_type pos ) const;
其具體用法如下：
std::deque<int> data = {1, 2, 3};
std::cout<<data.at(1)<<std::endl; //2
data.at(1)=8; //此時(shí)data={1, 8, 3}
try{
?data.at(6) = 6;
}catch(std::cout_of_range const& exc){
?std::cout<<exc.what()<<std::endl;
?//打印輸出：deque::_M_range_check: __n (which is 6)>= this->size() (which is 6)
}
operator[]
operator[]與at功能相同，即用來訪問指定的元素，但其與at不同的是：operator[]不進(jìn)行邊界的檢查。其函數(shù)聲明如下所示：
reference ? ? ? operator[]( size_type pos );
const_reference operator[]( size_type pos ) const;
front
front用于訪問容器的第一個(gè)元素，其返回值為容器首元素的引用，其函數(shù)原型如下：
reference front();
const_reference front() const;
back
back主要功能是用來訪問容器最后一個(gè)元素，其返回值為容器最后一個(gè)元素的引用，其函數(shù)原型如下所示：
reference back();
const_reference back() const;
2.2.2 迭代器
begin、end和cbegin、cend
begin和cbegin返回指向deque首元素的迭代器，end和cend返回指向deque末元素后一元素的迭代器。其函數(shù)聲明如下：
iterator begin(); //C++11 前
iterator begin() noexcept; //C++11 起
const_iterator begin() const; //C++11 前
const_iterator begin() const noexcept; //C++11 起
const_iterator cbegin() const noexcept; //C++11 起
iterator end(); //C++11 前
iterator end() noexcept; //C++11 起
const_iterator end() const; //C++11 前
const_iterator end() const noexcept; //C++11 起
const_iterator cend() const noexcept; //C++11 起
如果deque為空，則返回的迭代器將等于end或cend。end和cend指向deque末元素后一元素的迭代器，該元素的表現(xiàn)為占位符，試圖訪問它將導(dǎo)致未定義行為。
rbegin、rend和crbegin、crend
rbegin和crbegin返回指向deque首元素的逆向迭代器。它對(duì)應(yīng)非逆向deque的末元素，若deque為空，則返回的迭代器等于rend或crend。crbegin和crend返回指向逆向deque末元素后一元素的逆向迭代器，它對(duì)應(yīng)非逆向deque首元素的前一元素，此元素表現(xiàn)為占位符，試圖訪問它導(dǎo)致未定義行為。它們的聲明如下：
reverse_iterator rbegin(); //C++11 前
reverse_iterator rbegin() noexcept; //C++11 起
const_reverse_iterator rbegin() const; //C++11 前
const_reverse_iterator rbegin() const noexcept; //C++11 起
const_reverse_iterator crbegin() const noexcept; //C++11 起
reverse_iterator rend(); //C++11 前
reverse_iterator rend() noexcept; //C++11 起
const_reverse_iterator rend() const; //C++11 前
const_reverse_iterator rend() const noexcept; //C++11 起
const_reverse_iterator crend() const noexcept; //C++11 起
2.2.3 容量
empty
empty用來檢查容器是否為空，若為空則返回true，否則為false。其函數(shù)聲明如下：
bool empty() const; //C++11 前
bool empty() const noexcept; //C++11 起, C++20 前
[[nodiscard]] bool empty() const noexcept; //C++20 起
其底層實(shí)現(xiàn)就是檢查容器是否無元素，即判斷是否begin() == end()。
size
size函數(shù)返回容器中元素?cái)?shù)量，即std::distance(begin(), end())。其函數(shù)聲明如下：
size_type size() const; //C++11 前
size_type size() const noexcept; //C++11 起
max_size
max_size函數(shù)返回根據(jù)系統(tǒng)或庫實(shí)現(xiàn)限制的容器可保有的元素最大數(shù)量，此值通常反映容器大小上的理論極限，運(yùn)行時(shí)，可用 RAM 總量可能會(huì)限制容器大小到小于 max_size() 的值。其函數(shù)聲明為：
size_type max_size() const; //C++11 前
size_type max_size() const noexcept; //C++11 起
shrink_to_fit
shrink_to_fit函數(shù)主要是用來請(qǐng)求移除未使用的容量，通過釋放未使用的內(nèi)存來減少對(duì)內(nèi)存的使用，但其是減少使用內(nèi)存而不更改序列大小的非強(qiáng)制請(qǐng)求，其請(qǐng)求是否達(dá)成依賴于具體實(shí)現(xiàn)。其函數(shù)原型如下：
void shrink_to_fit();
2.2.4 修改器
clear
clear函數(shù)主要用來擦除所有元素，使用clear()后，再次調(diào)用size()，size函數(shù)返回0。clear函數(shù)的聲明如下：
void clear(); //C++11 前
void clear() noexcept; //C++11 起
insert
insert函數(shù)主要用于插入元素到容器的指定位置，其函數(shù)原型如下所示：
//在pos前插入value，其返回值為指向被插入value的迭代器
iterator insert( const_iterator pos, const T& value );
//在pos前插入value，其返回值為指向被插入value的迭代器
iterator insert( const_iterator pos, T&& value ); //C++11 起
//在pos前插入count個(gè)value，其返回值為指向首個(gè)被插入元素的迭代器，或者在 count == 0 時(shí)返回 pos。
iterator insert( const_iterator pos, size_type count, const T& value );
//在pos前插入[first, kast)的元素，如果 first 和 last 是指向 *this 中的迭代器，那么該行為未定義。
//其返回值為指向首個(gè)被插入元素的迭代器，或者在 first == last 時(shí)返回 pos
template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last );
//在pos前插入來自initializer_list ilist 的元素，其返回值為指向首個(gè)被插入元素的迭代器，或者在 ilist 為空時(shí)返回 pos。
iterator insert( const_iterator pos, std::initializer_list<T> ilist ); //C++11 起
具體用法示例如下：
std::deque<int> c1(3, 100); //初始化一個(gè)int行的雙端隊(duì)列c1，此時(shí)c1 = {100, 100, 100}
auto it = c1.begin();
it = c1.insert(it, 200); //在it前插入元素200
//c1 = {200，100, 100, 100}
c1.insert(it, 2, 300); //在it前插入兩個(gè)元素值都為300
//c1 = {300，300，200，100, 100, 100}
// 將 it 重新指向開頭
it = c1.begin();
std::deque<int> c2(2, 400); //c2 = {400, 400}
c1.insert(std::next(it, 2), c2.begin(), c2.end()); //在it后兩個(gè)元素（即200）的前面插入c2
//c1 = {300，300，400，400，200，100, 100, 100}
int arr[] = {501, 502, 503};
c1.insert(c1.begin(), arr, arr + std::size(arr));
//c1 = {501，502，503，300，300，400，400，200，100, 100, 100}
c1.insert(c1.end(), {601, 602, 603});
//c1 = {501，502，503，300，300，400，400，200，100, 100, 100，601，602，603}
emplace
emplace函數(shù)的聲明如下：
/*----------------------------------
?pos：將構(gòu)造新元素到其前的迭代器
?args：轉(zhuǎn)發(fā)給元素構(gòu)造函數(shù)的參數(shù)
?返回值iterator：指向被安置的元素的迭代器
------------------------------------*/
template< class... Args >
iterator emplace( const_iterator pos, Args&&... args ); //C++11 起
其主要作用就是原位構(gòu)造元素并將其在pos前插入到容器中。
earse
earse的函數(shù)主要功能是擦除元素，其聲明如下：
//移除位于pos的元素
//返回值：最后移除元素之后的迭代器。如果pos指代末元素，則返回end()迭代器
iterator erase( iterator pos ); //C++11 前
iterator erase( const_iterator pos ); //C++11 起
//移除范圍[first, last)中的元素。
/*返回值：最后移除元素之后的迭代器。
? ? ? ? 如果在移除前l(fā)ast == end()，那么最終返回end()迭代器
? ? ? ? 如果范圍[first, last) 為空，那么返回 last。*/
iterator erase( iterator first, iterator last ); //C++11 前
iterator erase( const_iterator first, const_iterator last ); //C++11 起
具體的用法如下所示：
std::deque<int> c{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
c.erase(c.begin());
//c = {1, 2, 3, 4, 5, 6, 7, 8, 9}
c.erase(c.begin() + 2, c.begin() + 5);
//c = {1, 2, 6, 7, 8, 9}
// 移除所有偶數(shù)
for (std::deque<int>::iterator it = c.begin(); it != c.end();)
{
?if (*it % 2 == 0)
? ?it = c.erase(it);
?else
? ?++it;
}
//c = {1, 7, 9}
push_back
push_back函數(shù)的主要作用是將元素添加到容器末尾，其聲明如下：
void push_back( const T& value );
void push_back( T&& value ); //C++11 起
emplace_back
emplace_back函數(shù)與emplace類似，只不過是在容器末尾就地構(gòu)造元素，其函數(shù)聲明如下：
template< class... Args >
void emplace_back( Args&&... args ); //C++11 起, C++17 前
template< class... Args >
reference emplace_back( Args&&... args ); //C++17 起
由于emplace_back是原地構(gòu)造元素，因此其插入效率要高于push_back。
pop_back
pop_back函數(shù)的主要作用就是移除末元素，其函數(shù)聲明如下：
void pop_back();
如果在空容器上調(diào)用pop_back會(huì)導(dǎo)致未定義行為。
push_front
push_front函數(shù)的主要作用就是插入元素到容器起始位置，其函數(shù)原型如下：
void push_front( const T& value );
void push_front( T&& value ); //C++11 起
emplace_front
emplace_front函數(shù)的作用是在容器頭部原位構(gòu)造元素，即插入新元素到容器起始，由于其也是在容器所提供的位置原位構(gòu)造函數(shù)，因此其效率也高于push_front。其函數(shù)聲明為：
template< class... Args >
void emplace_front( Args&&... args ); //C++11 起, C++17 前
template< class... Args >
reference emplace_front( Args&&... args ); //C++17 起
pop_front
pop_front函數(shù)主要作用是移除容器首元素。若容器中無元素，則行為未定義。其函數(shù)聲明為：
void pop_front();
resize
resize函數(shù)的主要作用是改變?nèi)萜髦锌纱鎯?chǔ)元素的個(gè)數(shù)，通過該函數(shù)可以重新設(shè)置容器大小，其函數(shù)聲明如下：
/*
該函數(shù)重設(shè)容器的大小為count，在count==size()時(shí)不做任何操作。
如果當(dāng)前大小大于 count，那么減小容器到它的開頭 count 個(gè)元素。
如果當(dāng)前大小小于 count，那么后附額外的默認(rèn)插入的元素。
*/
void resize( size_type count );
/*
該函數(shù)重設(shè)容器的大小為count，在count==size()時(shí)不做任何操作。
如果當(dāng)前大小大于 count，那么減小容器到它的開頭 count 個(gè)元素。
如果當(dāng)前大小小于 count，那么后附額外的 value 的副本
*/
void resize( size_type count, const value_type& value );
其具體用法示例如下：
std::deque<int> c = {1, 2, 3};
c.resize(5); //將其size增加大小到5
//c = {1, 2, 3, 0, 0}
c.resize(2); //將其size減少大小到2
//c = {1, 2}
c.resize(6, 4); //將其size增加大小到6，填充值為4";
//c = {1, 2, 4, 4, 4，4}
swap
swap函數(shù)的主要作用是交換兩個(gè)deque容器的內(nèi)容，不在單獨(dú)的元素上調(diào)用任何移動(dòng)、復(fù)制或交換操作。所有迭代器和引用保持有效。end()迭代器會(huì)失效。其函數(shù)聲明如下：
void swap( deque& other ); //C++17 前
void swap( deque& other ) noexcept(); //C++17 起
其用法示例如下圖所示：
std::deque<int> a1{1, 2, 3}, a2{4, 5};
auto it1 = std::next(a1.begin()); //*it1 = 2
auto it2 = std::next(a2.begin()); //*it2 = 5
int& ref1 = a1.front(); //ref1 = 1
int& ref2 = a2.front(); //ref1 = 4
std::cout <<*it1 << ' ' << *it2 << ' ' << ref1 << ' ' << ref2 << '\n';
//打印結(jié)果為2 5 1 4
a1.swap(a2);
//此時(shí)a1 = {4, 5}，a2 = {1, 2, 3}
std::cout <<*it1 << ' ' << *it2 << ' ' << ref1 << ' ' << ref2 << '\n';
//打印結(jié)果仍為2 5 1 4
/*注：
? ?交換后迭代器與引用保持與原來的元素關(guān)聯(lián)，
? ?例如盡管 'a1' 中值為 2 的元素被移動(dòng)到 'a2' 中，
? ?原來指向它的 it1 仍指向同一元素。*/
3. 總結(jié)
雙端隊(duì)列的的優(yōu)劣：
優(yōu)點(diǎn)
支持恒定時(shí)間內(nèi)隨機(jī)訪問，且開銷小。
支持快速遍歷，適合線性搜索。
兩端插入和刪除性能好。
插入不會(huì)使指向元素的引用/指針無效。
劣勢(shì)
如果在隨機(jī)位置的插入/擦除操作占主導(dǎo)地位，則可能會(huì)變慢。
如果元素類型具有較高的復(fù)制/分配成本，則可能會(huì)變慢（重新排序元素需要復(fù)制/移動(dòng)它們）
對(duì)于非常大量的值，分配時(shí)間可能很長。
文章首發(fā)公眾號(hào)：iDoitnow如果喜歡話，可以關(guān)注一下
