1. 雙端隊列和std::duque

雙端隊列實際上是隊列的一種變形，隊列要求只能在隊尾添加元素，在隊頭刪除元素，而雙端隊列在隊頭和隊尾都可以進行添加和刪除元素的操作。雙端隊列是限定插入和刪除操作在表的兩端進行的線性表。C++中提供deque容器來實現(xiàn)雙端隊列的功能。

std::duque（double-venden queue, 雙端隊列）是C++容器庫里中有下標(biāo)順序容器，它允許在首尾部兩端快速的插入和刪除元素。其與std::vector的存儲方式不同，deque的元素不是連續(xù)存儲的。

2. deque的用法

2.1 deque的定義和聲明

std::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為容器要存儲的元素類型，對于T需要滿足：

• 可復(fù)制賦值和可復(fù)制構(gòu)造（C++11前）。
• 可擦除，即元素類型的對象能以給定的分配器（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');//此時char_deque = {'a', 'a', 'a', 'a', 'a'}

const std::string str(6, 'b');
char_deque.assign(str.begin(), str.end());//此時char_deque存儲的元素分別為{'b', 'b', 'b', 'b', 'b', 'b'}

char_deque.assign({'C', '+', '+', '1', '1'});//此時char_deque存儲的元素分別為{'C', '+', '+', '1', '1'}

at

at用于訪問指定的元素，同時進行越界檢查，該函數(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<

operator[]

operator[]與at功能相同，即用來訪問指定的元素，但其與at不同的是：operator[]不進行邊界的檢查。其函數(shù)聲明如下所示：

reference       operator[]( size_type pos );
const_reference operator[]( size_type pos ) const;

front

front用于訪問容器的第一個元素，其返回值為容器首元素的引用，其函數(shù)原型如下：

reference front();
const_reference front() const;

back

back主要功能是用來訪問容器最后一個元素，其返回值為容器最后一個元素的引用，其函數(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首元素的逆向迭代器。它對應(yīng)非逆向deque的末元素，若deque為空，則返回的迭代器等于rend或crend。rend和crend返回指向逆向deque末元素后一元素的逆向迭代器，它對應(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 起

其底層實現(xiàn)就是檢查容器是否無元素，即判斷是否begin() == end()。

size

size函數(shù)返回容器中元素數(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)或庫實現(xiàn)限制的容器可保有的元素最大數(shù)量，此值通常反映容器大小上的理論極限，運行時，可用 RAM 總量可能會限制容器大小到小于 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ù)主要是用來請求移除未使用的容量，通過釋放未使用的內(nèi)存來減少對內(nèi)存的使用，但其是減少使用內(nèi)存而不更改序列大小的非強制請求，其請求是否達(dá)成依賴于具體實現(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個value，其返回值為指向首個被插入元素的迭代器，或者在 count == 0 時返回 pos。
iterator insert( const_iterator pos, size_type count, const T& value );

//在pos前插入[first, kast)的元素，如果 first 和 last 是指向 *this 中的迭代器，那么該行為未定義。
//其返回值為指向首個被插入元素的迭代器，或者在 first == last 時返回 pos
template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last );

//在pos前插入來自initializer_list ilist 的元素，其返回值為指向首個被插入元素的迭代器，或者在 ilist 為空時返回 pos。
iterator insert( const_iterator pos, std::initializer_list< T > ilist ); //C++11 起

具體用法示例如下：

std::deque< int > c1(3, 100); //初始化一個int行的雙端隊列c1，此時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前插入兩個元素值都為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后兩個元素（即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會導(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)萜髦锌纱鎯υ氐膫€數(shù)，通過該函數(shù)可以重新設(shè)置容器大小，其函數(shù)聲明如下：

/*
該函數(shù)重設(shè)容器的大小為count，在count==size()時不做任何操作。
如果當(dāng)前大小大于 count，那么減小容器到它的開頭 count 個元素。
如果當(dāng)前大小小于 count，那么后附額外的默認(rèn)插入的元素。
*/
void resize( size_type count );

/*
該函數(shù)重設(shè)容器的大小為count，在count==size()時不做任何操作。
如果當(dāng)前大小大于 count，那么減小容器到它的開頭 count 個元素。
如果當(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ù)的主要作用是交換兩個deque容器的內(nèi)容，不在單獨的元素上調(diào)用任何移動、復(fù)制或交換操作。所有迭代器和引用保持有效。end()迭代器會失效。其函數(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 < ' ' < < *it2 < < ' ' < < ref1 < < ' ' < < ref2 < < 'n';
//打印結(jié)果為2 5 1 4

a1.swap(a2);

//此時a1 = {4, 5}，a2 = {1, 2, 3}
std::cout < ' ' < < *it2 < < ' ' < < ref1 < < ' ' < < ref2 < < 'n';
//打印結(jié)果仍為2 5 1 4

/*注：
    交換后迭代器與引用保持與原來的元素關(guān)聯(lián)，
    例如盡管 'a1' 中值為 2 的元素被移動到 'a2' 中，
    原來指向它的 it1 仍指向同一元素。*/

3. 總結(jié)

雙端隊列的的優(yōu)劣：

優(yōu)點

• 支持恒定時間內(nèi)隨機訪問，且開銷小。
• 支持快速遍歷，適合線性搜索。
• 兩端插入和刪除性能好。
• 插入不會使指向元素的引用/指針無效。

劣勢

• 如果在隨機位置的插入/擦除操作占主導(dǎo)地位，則可能會變慢。
• 如果元素類型具有較高的復(fù)制/分配成本，則可能會變慢（重新排序元素需要復(fù)制/移動它們）。
• 對于非常大量的值，分配時間可能很長。