全面了解STL Deque

STL（Standard Template Library）是C++語言的標準庫，其中的deque（雙端隊列）是一個非常重要的容器。

一、deque基礎

deque可以視作一個序列的集合，每個序列頭尾相接而形成一個圓形緩衝區。它支持O(1)常數時間下以下操作：

• 在序列前後插入元素
• 在序列前後刪除元素
• 隨機訪問序列中的元素
• 獲取序列中元素的數量

deque使用動態數組存儲元素，默認情況下在序列的前後各預留一定數量的空間，從而保證在插入或刪除元素時在O(1)時間內完成。

#include 
#include 
using namespace std;
int main(){
    deque dq;
    dq.push_front(1);
    dq.push_back(2);
    dq.pop_front();
    dq.pop_back();
    dq.clear();
    dq.empty();
    dq.size();
}

二、insert和erase操作

deque提供了insert和erase操作，用於在序列中插入和刪除元素，這兩個操作非常強大。

（一）insert操作

insert操作有以下幾種形式：

• 在指定位置插入單個元素
• 在指定位置插入n個相同的元素
• 在指定位置插入區間[first, last)內的元素

#include 
#include 
using namespace std;
int main(){
    deque dq {1,2,3,4};
    auto it = dq.begin() + 2;
    dq.insert(it, 5);    // 1 2 5 3 4
    
    dq.insert(it, 2, 6); // 1 2 6 6 5 3 4
    
    vector v {7,8};
    dq.insert(it, v.begin(), v.end());    // 1 2 7 8 6 6 5 3 4
}

（二）erase操作

erase操作有以下幾種形式：

• 刪除指定位置的單個元素
• 刪除區間[first, last)內的元素
• 刪除所有元素

#include 
#include 
using namespace std;
int main(){
    deque dq {1,2,3,4};
    auto it = dq.begin() + 2;
    dq.erase(it);   // 1 2 4
    
    dq.erase(it, dq.end()); // 1 2
    
    dq.clear(); // 空序列
}

三、deque和vector的比較

deque和vector都是STL提供的序列容器，它們的最大區別在於存儲結構不同，因而導致不同的性能表現。

vector使用連續的動態數組存儲元素，支持在序列末尾追加元素，但是在序列頭部或中間插入或刪除元素的代價較大。

deque使用的是一種雙層結構，底層是一個數組的指針序列，每個指針指向一個動態數組，上層提供了更為方便的接口。由於deque採用了類似於虛擬內存的方式，因此其無論在序列首尾或中間插入或刪除元素的代價都是O(1)的，除此之外，deque還支持高效地在序列兩端執行插入和刪除操作。

#include 
#include 
#include 
#include 
using namespace std;
int main(){
    deque dq;
    vector v;
    auto t1 = chrono::high_resolution_clock::now();
    for(int i=0;i<100000;i++)
        dq.push_back(i);
    auto t2 = chrono::high_resolution_clock::now();
    for(int i=0;i<100000;i++)
        v.push_back(i);
    auto t3 = chrono::high_resolution_clock::now();
    cout << "deque push_back: " << chrono::duration_cast(t2-t1).count() << "ms" << endl;
    cout << "vector push_back: " << chrono::duration_cast(t3-t2).count() << "ms" << endl;
}

四、總結

deque在實際運用中表現出的優異性能和靈活性使其成為STL中重要的序列容器之一，我們可以根據需要靈活地選擇存儲結構相對固定的vector或者支持高效操作的deque作為容器。通過深入了解deque的相關函數和性能表現，能夠更加靈活和高效地應用它來解決我們的問題。