C++基础知识（八：STL标准库 deque ）-阿里云开发者社区

动态大小：deque可以动态地增加或减少元素数量。
随机访问：deque支持通过下标直接访问元素，时间复杂度为O(1)。
两端操作：deque可以在头部和尾部进行快速的插入和删除操作，时间复杂度通常为O(1)。
内部实现：deque使用一种复杂的内部结构来实现其特性，它将数据分割成多个连续的块，每个块的大小通常是固定的，这样既保证了随机访问的效率，又允许在两端进行高效的插入和删除。

deque的基本操作：

构造与初始化：

std::deque<int> d; // 创建一个空的deque
std::deque<int> d(10, 5); // 创建一个含有10个元素，每个元素值为5的deque

插入与删除：

d.push_front(1); // 在deque前端插入元素
d.push_back(2); // 在deque后端插入元素
d.pop_front(); // 删除deque前端的元素
d.pop_back(); // 删除deque后端的元素
d.insert(d.begin(), 0); // 在指定位置插入元素
d.erase(d.begin()); // 删除指定位置的元素

访问元素：

d.front(); // 访问deque的第一个元素
d.back(); // 访问deque的最后一个元素
d.at(index); // 访问指定索引的元素，如果索引越界会抛出异常
d[index]; // 直接通过下标访问元素

其他操作：

d.size(); // 获取deque中的元素数量
d.empty(); // 检查deque是否为空
d.clear(); // 清空deque中的所有元素

示例代码：

Cpp

#include <iostream>
#include <deque>
int main()
{
    std::deque<int> d;
    // 插入元素
    d.push_back(1);
    d.push_front(2);
    d.push_back(3);
    // 访问元素
    std::cout << "Front: " << d.front() << ", Back: " << d.back() << std::endl;
    // 删除元素
    d.pop_front();
    d.pop_back();
    for (std::size_t i = 0; i < d.size(); ++i)
    {
        std::cout << "d-value: " << d[i] << std::endl;
    }
    return 0;
}

编辑

什么时候用deque，什么时候用vector，什么时候用list?

std::vector

使用场景：

当你需要频繁的随机访问元素时。
当插入和删除操作主要发生在容器的末端时。
当容器的大小在初始化后变化不大，或者可以预先分配足够空间时。

优点：

提供随机访问，访问时间复杂度为O(1)。
插入和删除元素在末尾时效率高，时间复杂度为O(1)。
内存使用紧凑，元素在一块连续的内存区域中。

缺点：

在中间或开头插入或删除元素时效率低，时间复杂度为O(n)。

std::deque

使用场景：

当你需要在容器的头部和尾部频繁地插入和删除元素时。
当你希望保持随机访问能力时。

优点：

支持在头部和尾部的高效插入和删除，时间复杂度通常为O(1)。
提供随机访问，时间复杂度为O(1)。

缺点：

在中间位置插入或删除元素效率不如std::list。
内存使用比std::vector分散，因为元素分布在多个块中。

std::list

使用场景：

当你需要在容器的任意位置频繁插入和删除元素时。
当随机访问不是主要操作时。

优点：

在列表的任意位置插入和删除元素都非常高效，时间复杂度为O(1)。
不需要连续的内存空间，因此在内存分配方面更灵活。

缺点：

不支持随机访问，访问时间复杂度为O(n)。
遍历整个列表时可能比std::vector或std::deque慢。

总结

如果需要大量随机访问且插入删除操作集中在末尾，使用std::vector。
如果需要在两端高效插入删除且随机访问，使用std::deque。
如果需要在任意位置频繁插入删除且不关心随机访问，使用std::list。

C++基础知识（八：STL标准库 deque ）