C / C++ / 系统课时

vector、deque、list 怎么选

vector、deque、list 怎么选

面对“顺序存一批元素”这个需求,vector、deque 和 list 都能完成,但它们擅长的访问与修改模式完全不同。选择容器时,重点不是记住谁“更快”,而是判断是否需要随机访问、双端操作、中间插入,以及良好的内存局部性。

学习目标

  • 能从随机访问、首尾操作和中间插入三个维度比较 vector、deque 与 list
  • 理解连续存储、分段存储和链式节点对内存局部性的影响
  • 能根据实际操作模式选择合适的顺序容器,而不是只看单个复杂度

先看三种容器的核心差异

vector 的元素连续存储,支持常数时间随机访问,遍历时通常也最有利于 CPU 缓存。尾部追加通常是摊还常数时间,但在头部或中间插入元素时,需要移动后续元素。

deque 支持常数时间随机访问,同时擅长在首尾两端插入和删除。它通常采用分段存储,不保证所有元素位于一整块连续内存,因此局部性一般不如 vector,但适合频繁的双端操作。

list 是双向链表,不支持下标随机访问。已知插入位置的迭代器时,插入和删除本身是常数时间;但如果先要从头查找第 N 个位置,查找过程仍然是线性时间。每个节点通常独立分配,也会带来额外指针和较弱的缓存局部性。

vector、deque 与 list 的内存组织对比

用表格快速做第一轮筛选

需求 vector deque list
随机访问 c[i] 支持,O(1) 支持,O(1) 不支持
尾部插入/删除 通常很合适,摊还 O(1) 很合适,O(1) O(1)
头部插入/删除 O(n) 很合适,O(1) O(1)
已知位置后中间插入/删除 O(n) O(n) O(1)
内存局部性 最好 较好但非整体连续 较弱
单个元素额外开销 低 有分段管理开销 通常较高,节点含链接信息

用同一组操作感受差别

下面的完整程序分别完成“尾部追加、头部插入、访问第三个元素”三个动作。vector 和 deque 可以直接随机访问,而 list 必须通过迭代器向前移动。

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

int main() {
    std::vector<int> v{20, 30};
    std::deque<int> d{20, 30};
    std::list<int> l{20, 30};

    v.push_back(40);
    d.push_back(40);
    l.push_back(40);

    // vector 没有 push_front,只能在 begin() 位置插入并移动后续元素。
    v.insert(v.begin(), 10);
    d.push_front(10);
    l.push_front(10);

    std::cout << "vector third = " << v[2] << '\n';
    std::cout << "deque third = " << d[2] << '\n';

    auto it = l.begin();
    std::advance(it, 2);  // list 只能沿链表移动到第三个元素。
    std::cout << "list third = " << *it << '\n';
}

预期输出

text
vector third = 30
deque third = 30
list third = 30

这段程序说明的是接口和访问方式,不代表三种操作的真实耗时相同。容器性能还要结合数据规模、元素类型、内存分配和实际访问模式评估。

一个实用的选择顺序

优先考虑 vector:大多数顺序数据都适合它,尤其是需要频繁遍历、下标访问、排序,或要把数据交给要求连续内存的接口时。

当业务明确需要频繁从头尾两端压入和弹出,同时仍希望随机访问时,再考虑 deque。典型场景包括双端队列、滑动窗口和某些任务调度结构。

只有在“经常拿着已有迭代器在中间插入或删除”,并且不依赖随机访问与连续内存时,list 才更可能体现优势。不要因为“链表插入是 O(1)”就默认选择它;遍历成本、缓存未命中和节点分配开销往往同样重要。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

vector、deque、list 怎么选

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通