1 概述

  deque（通常发音像“deck”）是双端队列的一个不规则缩写。双端队列是具有动态大小的序列容器，可以在两端（前端或后端）进行扩展或收缩。
  特定的库可以以不同的方式实现deques，通常作为某种形式的动态数组。但在任何情况下，它们都允许通过随机访问迭代器直接访问单个元素，并根据需要通过扩展和收缩容器来自动处理存储。
  因此，它们提供了类似于矢量的功能，但也在序列的开始处，而不仅仅是在序列的结束处，有效地插入和删除元素。但是，与向量不同的是，deque不能保证将其所有元素存储在连续的存储位置：通过将指针偏移到另一个元素来访问deque中的元素会导致未定义的行为。
  vectors和deque都提供了非常相似的接口，可以用于类似的目的，但在内部都以完全不同的方式工作：虽然vectors使用一个偶尔需要重新分配才能增长的数组，但deque的元素可以分散在不同的存储块中，容器在内部保留必要的信息，以便在恒定时间内直接访问其任何元素，并具有统一的顺序接口（通过迭代器）。因此，deques的内部比向量复杂一点，但这使它们在某些情况下能够更有效地生长，尤其是在非常长的序列中，重新定位变得更加昂贵。
  对于涉及在除开头或结尾以外的位置频繁插入或删除元素的操作，与列表和前向列表相比，deques的性能更差，迭代器和引用的一致性也更低。

其类图如下：

2 使用实例

void DequeSuite::push_back()
{
   
    int array[] = {
    1, 2, 3, 4, 5 };
    std::deque<int> a;

    for(size_t i = 0; i < ARRAY_SIZE(array); i++)
        a.push_back(array[i]);

    for(size_t i = 0; i < a.size(); i++)
        TEST_ASSERT_EQUALS(array[i],  a[i])
}

void DequeSuite::push_front()
{
   
    int array[] = {
    1, 2, 3, 4, 5 };
    std::deque<int> a;
    std::deque<int> b;

    for(size_t i = 0; i < ARRAY_SIZE(array); i++)
        a.push_front(array[i]);

    int index = 0;
    for(auto it = a.crbegin(); it != a.crend(); ++it)
        TEST_ASSERT_EQUALS(array[index++],  *it)
}

3 接口使用

3.1 construct

std::deque<int> getDeque(int size, int value)
{
   
    return std::deque<int>(size, value);
}
void DequeSuite::construct()
{
   
    std::deque<int> a;
    std::deque<int> b(4); // 0 0 0 0
    std::deque<int> c(4, 5);// 5 5 5 5
    std::deque<int> d({
   1, 2, 3, 4, 5});
    std::deque<int> e(d.begin(), d.end());
    std::deque<int> f(d);
    std::deque<int> g(getDeque(6, 8));

    TEST_ASSERT_EQUALS(0, a.size())
    TEST_ASSERT_EQUALS(4, b.size())
    TEST_ASSERT_EQUALS(4, c.size())
    TEST_ASSERT_EQUALS(5, d.size())
    TEST_ASSERT_EQUALS(5, e.size())
    TEST_ASSERT_EQUALS(5, f.size())
    TEST_ASSERT_EQUALS(6, g.size())
}

3.2 assigns

void DequeSuite::assigns()
{
   
    std::deque<int> a;
    std::deque<int> b;
    std::deque<int> c;
    a = {
    1, 2, 3, 4, 5 };
    b = a;
    c = getDeque(5, 10);

    TEST_ASSERT_EQUALS(5, a.size