C++ deque詳解及用法

一、c++ deque函數

C++ STL中的deque是一種支持雙端插入和刪除的線性容器。deque中的元素可以在兩端進行push和pop。下面是deque常用的函數：

#include <deque>

// deque構造函數
deque();
deque(int n);
deque(int n, const T& v);
deque(const deque& x);

// 元素訪問
reference operator[](int n);
reference at(int n);
reference front();
reference back();

// 容量
bool empty() const;
size_type size() const;
size_type max_size() const;

// 修改容器
void clear();
iterator insert(iterator position, const T& x);
void insert(iterator position, int n, const T& x);
void insert(iterator position, InputIterator first, InputIterator last);
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
void push_back(const T& x);
void push_front(const T& x);
void pop_back();
void pop_front();
void swap(deque& x);

// 比較器
bool operator==(const deque& x, const deque& y);
bool operator!=(const deque& x, const deque& y);
bool operator<(const deque& x, const deque& y);
bool operator<=(const deque& x, const deque& y);
bool operator>(const deque& x, const deque& y);
bool operator>=(const deque& x, const deque& y);

二、c++ deque實現

c++ STL中deque的實現一般是由一個中控器（指針數組）與多個緩衝區組成，中控器維持着整個deque的結構，每個緩衝區存放着一定數量的元素，以此來保證deque的雙端插入和刪除。下面是一個簡單的deque實現：

template <typename T, typename Alloc = alloc, size_t BufSiz = 0>
class deque {
public:
    typedef T value_type;
    typedef value_type* pointer;
    typedef size_t size_type;

private:
    typedef simple_alloc data_allocator;
    typedef simple_alloc map_allocator;

    typedef pointer* map_pointer;

    size_type initial_map_size() const { return 8; }

    map_pointer map_;
    size_type map_size_;

    pointer allocate_node() { return data_allocator::allocate(buffer_size()); }
    void deallocate_node(pointer p) { data_allocator::deallocate(p, buffer_size()); }
    size_type buffer_size() const { return BufSiz != 0 ? BufSiz : sizeof(T) < 512 ? 512 / sizeof(T) : 1; }

public:
    deque() : map_(nullptr), map_size_(0) { create_map_and_nodes(0); }
    deque(int n, const value_type& value) : map_(nullptr), map_size_(0) { fill_initialize(n, value); }

    void push_front(const value_type& value);
    void push_back(const value_type& value);
    void pop_front() {}
    void pop_back() {}
    reference operator[](size_type n) const {}
    reference at(size_type n) const {}
    reference front() const {}
    reference back() const {}
    size_type size() const {}
    bool empty() const {}
    void swap(deque& rhs) {}
    iterator begin() const {}
    iterator end() const {}

    ~deque() {}
};

三、c++ deque用法

deque的使用方式與vector類似，不同的是deque可以在頭尾兩端進行操作。下面是一個簡單的deque使用例子：

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> myDeque;
    myDeque.push_back(1);        // insert 1 at the end of deque
    myDeque.push_front(2);       // insert 2 at the beginning of deque
    myDeque.insert(myDeque.end(), 3);    // insert 3 before the position pointed by the iterator
    myDeque.pop_back();          // remove the last element of deque
    myDeque.pop_front();         // remove the first element of deque
    myDeque.clear();             // remove all of the elements of deque
    return 0;
}

四、c++ deque底層實現

deque底層一般由中控器和多個緩衝區組成，中控器維護着整個deque的結構，每個緩衝區存放着一定數量的元素，通過緩衝區之間的連接，形成了一個雙向鏈表的結構，支持雙端插入和刪除。deque底層實現的優越性在於可以避免插入或刪除時的數據遷移，但在空間利用率上不如vector（vector只需要一個連續的內存空間即可存放所有元素）。

五、c++的缺點

在使用deque時需要考慮與vector等其他容器的選擇，c++的缺點主要在於對於大規模數據的處理嚴重依賴於底層硬件。同時在程序設計的過程中，需要注意指針空指針問題、內存泄漏等缺陷與陷阱。

六、c和指針選取

c和指針是很常用的高級編程語言，但與c++相比，c的面向對象能力較弱，在程序設計的過程中需要手動維護內存、支持分離編譯等功能，但也由於這些特性使得c代碼執行速度快、內存佔用小。