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代码执行速度快、内存占用小。