17370845950

std::deque是支持首尾高效增删的随机访问容器，关键区别在于：deque首尾操作为O(1)，vector为O(n)；deque内存不连续、迭代器稳定性较弱，vector内存连续且迭代器更稳定。

std::deque 是什么，和 std::vector 有什么关键区别

std::deque（double-ended queue）是 C++ 标准库中支持在**首尾高效插入/删除**的序列容器，底层通常以分段连续内存（如块链表）实现。它不是“队列”语义的封装，而是一个可随机访问的容器——这点和 std::queue（适配器）完全不同。std::deque 的 push_front()、pop_front() 平均时间复杂度是 O(1)，而 std::vector 做同样操作是 O(n)，因为要移动全部元素。

但代价是：迭代器稳定性弱于 std::vector（中间插入/删除不使所有迭代器失效，但 push_front/pop_front 可能使指向首元素的迭代器失效）；缓存局部性略差；且不保证整体内存连续（&a[1] == &a[0] + 1 不一定成立）。

初始化与常用增删操作（带边界注意事项）

构造方式灵活，但要注意默认构造不分配空间，at() 和 [] 访问空容器会触发未定义行为或异常。

• std::deque dq = {1, 2, 3}; —— 初始化列表，最常用
• std::deque dq(5, 42); —— 构造 5 个值为 42 的元素
• std::deque dq(other_dq.begin(), other_dq.end()); —— 迭代器范围构造

增删操作必须区分首尾：

std::deque dq;
dq.push_back(10);   // 尾插 → [10]
dq.push_front(20);  // 首插 → [20, 10]
dq.pop_back();      // 尾删 → [20]
dq.pop_front();     // 首删 → []
// ⚠️ 对空 deque 调用 pop_front/pop_back 是未定义行为！
// 建议先检查：if (!dq.empty()) dq.pop_front();

安全访问元素：at() vs [] vs front()/back()

at() 会做边界检查并

抛出 std::out_of_range；[] 不检查，越界是未定义行为；front()/back() 对空容器调用也是未定义行为。

• 需要异常保障时用 dq.at(0)
• 确定索引合法且追求极致性能时用 dq[0]
• 取首尾元素且已确认非空时，dq.front() 比 dq[0] 更语义清晰，也比 dq.at(0) 快

示例：

std::deque names = {"Alice", "Bob"};
if (!names.empty()) {
    std::cout << names.front() << "\n"; // Alice
    std::cout << names.back()  << "\n"; // Bob
    try {
        std::cout << names.at(5) << "\n"; // 抛出 std::out_of_range
    } catch (const std::out_of_range&) {
        std::cout << "index out of range\n";
    }
}

迭代器失效规则与 erase() 的特殊行为

std::deque 的迭代器失效规则比 std::vector 复杂：仅被擦除元素的迭代器失效；首尾插入/删除会使所有指向首/尾元素的迭代器失效；但中间插入/删除不影响其他位置的迭代器（这是关键优势）。

erase() 返回下一个有效迭代器，适合循环中条件删除：

std::deque dq = {1, 2, 3, 4, 5};
for (auto it = dq.begin(); it != dq.end(); ) {
    if (*it % 2 == 0) {
        it = dq.erase(it); // 返回下一个，不重复 ++it
    } else {
        ++it;
    }
}
// 结果：{1, 3, 5}

注意：erase(pos) 中的 pos 必须是合法迭代器，不能是 dq.end()（除非你传入 end()-1 之类合法位置）；批量擦除用 erase(first, last)，last 是开区间端点。

真正容易被忽略的是：虽然 std::deque 支持随机访问，但它对「频繁中间插入」并无优化——每次 insert(pos, value) 仍是 O(n) 时间，因为要移动该位置之后的所有元素。如果业务需要高频中间修改，应考虑 std::list 或手写结构，而不是误以为 deque 能替代链表。