C++ deque容器详解

C++ 标准库提供了很多种容器，其中 vector 容器可以使用下标随机访问元素，但插入、删除元素时效率较低；list容器则恰恰相反，插入、删除元素效率较高，但不能使用下标随机访问。

在 C++ 标准库中，deque（双端队列）是一种允许在两端进行插入和删除操作的容器。与 vector 和 list 容器不同，deque 容器既能使用下标随机访问元素，也能快速地在两端进行插入和删除。

deque容器的构造

deque容器容器本质是一个模板类，定义在<deque>头文件中。deque 模板类提供了多种构造函数，以便适应不同的应用场景，包括：

// 创建一个空的deque容器
explicit deque (const allocator_type& alloc = allocator_type());  

// 创建一个有 n 个元素的 deque，并进行默认初始化
explicit deque (size_type n);
// 创建一个有 n 个元素的 deque，并初始化每个元素的值为 val
deque (size_type n, const value_type& val, const allocator_type& alloc = allocator_type());

// 从另一个迭代器范围 [first, last) 创建一个 deque
template <class InputIterator>  deque (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

//拷贝构造函数，创建一个与 x 相同的新 deque。
deque (const deque& x);
deque (const deque& x, const allocator_type& alloc);

//移动构造函数，创建一个新的 deque 容器，并从 x 中“移动”数据
deque (deque&& x);
deque (deque&& x, const allocator_type& alloc);
  
//从一个初始化列表 il 中复制元素到新的 deque 容器中
deque (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

下面的 C++ 代码示例演示了如何使用 deque 容器的各种构造函数。

#include <iostream>
#include <deque>
#include <iterator>
#include <vector>

int main() {
    // 使用默认构造函数创建一个空的 deque
    std::deque<int> emptyDeque;
    std::cout << "Empty deque size: " << emptyDeque.size() << std::endl;

    // 创建一个包含 5 个元素的 deque，默认初始化为0
    std::deque<int> dequeWithFiveElements(5);
    std::cout << "Deque with 5 elements (default initialized): ";
    for (auto x : dequeWithFiveElements) std::cout << x << " ";
    std::cout << std::endl;

    // 创建一个包含 5 个元素的 deque，每个元素初始化为3
    std::deque<int> dequeWithFiveThrees(5, 3);
    std::cout << "Deque with 5 elements (each set to 3): ";
    for (auto x : dequeWithFiveThrees) std::cout << x << " ";
    std::cout << std::endl;

    // 使用迭代器创建一个 deque
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::deque<int> dequeFromIterators(vec.begin(), vec.end());
    std::cout << "Deque from iterators: ";
    for (auto x : dequeFromIterators) std::cout << x << " ";
    std::cout << std::endl;

    // 使用拷贝构造函数创建一个新的 deque
    std::deque<int> dequeCopy(dequeFromIterators);
    std::cout << "Deque from copy constructor: ";
    for (auto x : dequeCopy) std::cout << x << " ";
    std::cout << std::endl;

    // 使用移动构造函数创建一个新的 deque
    std::deque<int> dequeMoved(std::move(dequeCopy));
    std::cout << "Deque from move constructor: ";
    for (auto x : dequeMoved) std::cout << x << " ";
    std::cout << std::endl;

    // 使用初始化列表创建一个新的 deque
    std::deque<int> dequeFromInitList = {10, 20, 30, 40, 50};
    std::cout << "Deque from initializer list: ";
    for (auto x : dequeFromInitList) std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

运行结果为：

Empty deque size: 0
Deque with 5 elements (default initialized): 0 0 0 0 0
Deque with 5 elements (each set to 3): 3 3 3 3 3
Deque from iterators: 1 2 3 4 5
Deque from copy constructor: 1 2 3 4 5
Deque from move constructor: 1 2 3 4 5
Deque from initializer list: 10 20 30 40 50

deque容器的使用

和 vector 容易类似，deque 容器也能够快速随时访问元素。在插入、删除元素方面，deque 容器更擅长的是操作两端的元素，而操作中间位置元素的效率较低。

下表罗列了 deque 模板类提供的所有成员函数。

表 1 deque 容器的成员函数

函数成员	函数功能
begin()	返回指向容器中第一个元素的迭代器。
end()	返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。
rbegin()	返回指向最后一个元素的迭代器。
rend()	返回指向第一个元素所在位置前一个位置的迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
size()	返回实际元素个数。
max_size()	返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 232-1，我们很少会用到这个函数。
resize()	改变实际元素的个数。
empty()	判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
shrink _to_fit()	将内存减少到等于当前元素实际所使用的大小。
at()	使用经过边界检查的索引访问元素。
front()	返回第一个元素的引用。
back()	返回最后一个元素的引用。
assign()	用新元素替换原有内容。
push_back()	在序列的尾部添加一个元素。
push_front()	在序列的头部添加一个元素。
pop_back()	移除容器尾部的元素。
pop_front()	移除容器头部的元素。
insert()	在指定的位置插入一个或多个元素。
erase()	移除一个元素或一段元素。
clear()	移出所有的元素，容器大小变为 0。
swap()	交换两个容器的所有元素。
emplace()	在指定的位置直接生成一个元素。
emplace_front()	在容器头部生成一个元素。和 push_front() 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程。
emplace_back()	在容器尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。

下面的 C++ 程序演示了表中部分成员函数的用法：

#include <iostream>
#include <deque>

int main() {
    std::deque<int> deq;

    // 尾部插入
    deq.push_back(1);
    deq.push_back(2);

    // 头部插入
    deq.push_front(0);
    deq.push_front(-1);

    // 随机访问
    std::cout << "第一个元素: " << deq[0] << std::endl;
    std::cout << "第四个元素: " << deq[3] << std::endl;

    // 删除
    deq.pop_back();
    deq.pop_front();

    // 遍历
    for(int i : deq) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

示例中演示了 deque 的一些基本操作，比如尾部插入 （push_back）、头部插入（push_front）、随机访问 （operator[]）和两端删除（pop_back 和 pop_front）。

运行程序，输出结果为：

第一个元素: -1
第四个元素: 2
0 1

总结

deque 是一个非常灵活和高效的容器，特别适用于需要快速随机访问和两端插入删除操作的场景。然而，与其他容器相比，它在内存使用和中间元素插入删除操作上可能不是最优的选择。