C++ 容器

C++ 标准容器负责保存元素并管理其存储，容器选择还决定访问成本、元素是否连续，以及更新后旧引用是否继续有效。准备容器题时，需要把“底层是什么结构”落实成具体操作：一次扩容是否使指针失效，查一个不存在的键是否改变了容器，哈希表是否真的保证常数时间。本文以 C++17 为准。

1. 面试核心

先记住这几条，再读正文

• vector<T>（除 vector<bool> 特化）提供连续元素存储，随机访问是常数时间，尾部追加是摊还常数时间；中间插入和删除通常要移动后续元素。
• STL 中容器保存元素，迭代器连接算法与元素范围；容器适配器通过底层容器提供栈、队列等接口，替换底层类型要满足所需操作。卡 · STL 组件协作
• size() 表示已有元素数，capacity() 表示当前存储容量，reserve() 不创建元素，resize() 才改变元素数量。卡 · vector 容量与失效
• 扩容、插入和删除可能让迭代器、指针或引用失效，必须按具体容器和操作判断，不能记成统一规则。卡 · vector 容量与失效
• map 按比较关系有序，unordered_map 按哈希组织，平均常数查找不等于最坏情况常数查找。卡 · 访问需求与结构
• map 和 unordered_map 的 operator[] 会在键不存在时插入元素，只读查找应选择 find() 或适合的接口。
• 容器拥有元素对象，但元素若是裸指针，销毁容器不会自动销毁指针指向的对象；资源责任仍由元素类型表达。

2. 访问需求与结构

卡 · map 与 unordered_map 的底层组织和复杂度有何区别？卡 · STL 的组件怎样协作，常见容器适配器有哪些？

选择容器先看主要操作，而不是固定从链表或哈希表开始：

容器	组织方式与优势	需要接受的代价
vector<T>	连续元素、下标访问、顺序扫描、尾部增长	扩容会迁移元素，中间更新会移动后续部分
deque<T>	支持两端增长和随机访问	不保证所有元素处于一整块连续存储，失效规则与 vector 不同
list<T>	双向链接，已知位置可常数时间插入或删除	不能常数时间按下标找位置，节点分配与访问局部性有成本
map<K,V>	按键有序、查找与更新通常为对数时间	需要比较，不能提供平均常数的哈希定位
unordered_map<K,V>	按哈希查找，平均常数时间	哈希冲突、重新分桶及最坏线性成本，不提供键顺序

list 的常数时间插入以“已经拿到位置”为条件。如果先从头查找第 n 个元素，定位本身就可能是线性时间。map 常见实现采用红黑树，但标准主要约束行为与复杂度，不要求唯一一种内部树实现。

树与哈希的基本关系可复用二叉搜索树和哈希表。这里继续关注 C++ 容器对调用者提供的契约。

2.1 STL 组件协作

STL（Standard Template Library）通常指以泛型容器、迭代器和算法为核心的一组库设施；它不是整个 C++ 标准库的另一个名字。介绍组件时，可以沿着“一批元素怎样被保存和处理”解释它们的分工：

组件	在这条链路中的职责	例子
容器（container）	保存元素，提供访问和更新接口	vector<int> 保存整数
迭代器（iterator）	表示位置，让算法按能力要求访问一段元素	begin() 与 end() 描述左闭右开范围
算法（algorithm）	在满足要求的范围上执行排序、查找等操作	std::sort 排序
函数对象（function object）	对象可像函数一样调用，向算法提供比较或判定规则	std::greater<int> 提供大于比较
分配器（allocator）	按类型请求和归还原始存储，由容器协调元素构造、销毁与存储管理	vector 默认使用 std::allocator<T>
适配器（adaptor）	基于已有组件提供另一种受约束的接口	stack 在底层容器上提供栈操作

算法不必知道容器的全部内部结构，但它会要求迭代器具备特定能力。例如 C++17 的 std::sort 要求随机访问迭代器，所以能处理 vector 的迭代器，不能直接用于 list；后者可以使用自己的 list::sort()。函数对象也不等同于 std::function，前者是一类可调用对象，后者是标准库提供的一种可调用目标包装器。

2.2 容器适配器

容器适配器在底层容器上限制访问方式，使调用者按栈、队列或优先队列的规则操作元素。它并不要求重新发明一种底层存储结构。

适配器	对外规则	默认底层容器	替换底层容器的条件
stack<T>	后进先出，top() 访问栈顶	deque<T>	支持 back()、push_back()、pop_back()；如 vector、deque、list
queue<T>	先进先出，front() 访问队头	deque<T>	支持 front()、back()、push_back()、pop_front()；如 deque、list
priority_queue<T>	每次访问比较规则确定的最高优先级元素	vector<T>	支持随机访问迭代器及 front()、push_back()、pop_back()；如 vector、deque

例如 vector 可以作为 stack 的底层容器，但没有 pop_front()，不能作为完整可用的 queue 底层容器。list 能支持普通队列，却没有随机访问迭代器，不能直接用于 priority_queue。这些约束解释了为什么底层类型不是任意替换的。

priority_queue<int> 使用默认比较器时，最大值先出；传入 std::greater<int> 后，最小值先出。比较器必须满足严格弱序，不能用 >= 或 <= 随意替换。以下示例把组件协作与三种访问顺序放在一起：

#include <algorithm>
#include <cassert>
#include <functional>
#include <queue>
#include <stack>
#include <vector>

int main() {
    std::vector<int> values{3, 1, 2};
    std::sort(values.begin(), values.end(), std::greater<int>{});
    assert((values == std::vector<int>{3, 2, 1}));

    std::stack<int, std::vector<int>> pending;
    pending.push(1);
    pending.push(2);
    assert(pending.top() == 2);
    pending.pop();
    assert(pending.top() == 1);

    std::queue<int> waiting;
    waiting.push(1);
    waiting.push(2);
    assert(waiting.front() == 1);
    waiting.pop();
    assert(waiting.front() == 2);

    std::priority_queue<int, std::vector<int>, std::greater<int>> smallest;
    for (int value : values) smallest.push(value);
    assert(smallest.top() == 1);
    smallest.pop();
    assert(smallest.top() == 2);
}

sort 经由迭代器访问 values，按 greater 排成 [3,2,1]。pending 最后压入 2，所以先弹出 2；waiting 最早加入 1，所以先取出 1；smallest 按优先级取出 1，而不依赖插入先后。三种适配器的 pop() 都只删除元素、不返回元素，应先用 top() 或 front() 读取；读取和弹出前必须保证非空。

这些适配器不公开普通容器的 begin()、end() 遍历接口。需要遍历所有元素、按任意位置删除或直接改堆中元素时，应重新选择底层结构或算法，不能假定 priority_queue 提供了完整 vector 接口。

3. vector 容量与失效

卡 · vector 的 reserve 和 resize 有什么区别？卡 · 容器更新后，迭代器和引用是否一定同时失效？

容量是容器当前无需重新分配就能容纳的元素上限，大小是已经存在的元素数量。预留容量不是构造出相应数量的元素：

#include <cassert>
#include <vector>

int main() {
    std::vector<int> values;
    values.reserve(8);
    assert(values.empty() && values.capacity() >= 8);
    // values[0] = 7;  // 错误示例：元素尚不存在，不能执行
    values.resize(2);
    assert(values.size() == 2 && values[0] == 0);

    values[0] = 7;
    auto old_capacity = values.capacity();
    values.reserve(old_capacity + 1);
    assert(values.size() == 2 && values[0] == 7);
}

第二次 reserve 请求大于原容量，因此需要重新分配。元素值被保留，但指向旧元素位置的指针、引用和迭代器都失效。重新分配时可能复制或移动元素，具体选择还取决于元素类型和异常保证。

没有重新分配也不意味着所有位置都有效：在 vector 中间插入会影响插入点及其后的迭代器和引用；删除会影响删除点及其后的部分。尾部追加即使没有扩容，旧的尾后迭代器 end() 也会改变。

reserve 的具体增长策略不是固定“两倍”。shrink_to_fit() 只是请求缩减多余容量，不保证实现一定执行。不要把一次实测容量序列当作标准契约。

4. 有序键与哈希键

卡 · map 与 unordered_map 的底层组织和复杂度有何区别？卡 · 容器更新后，迭代器和引用是否一定同时失效？

map 依据比较器确定键的顺序和等价关系。如果 compare(a,b) 与 compare(b,a) 都为假，键在该比较关系下等价；不一定需要通过 operator== 判断。比较器必须满足严格弱序，不能随意用 <= 代替 <。

unordered_map 通过哈希函数和相等判断组织键。相等的键必须得到相同哈希值；不同键可以碰撞，再通过相等判断区分。哈希质量或输入分布不佳时，查找可能退化到线性成本。

#include <cassert>
#include <map>
#include <string>
#include <unordered_map>

int main() {
    std::map<int, std::string> ordered{{2, "two"}, {1, "one"}};
    assert(ordered.begin()->first == 1);

    std::unordered_map<std::string, int> counts;
    assert(counts.find("missing") == counts.end());
    assert(counts.empty());
    int value = counts["missing"];
    assert(value == 0 && counts.size() == 1);
}

find 不插入，operator[] 在键不存在时创建一个对应值，这里的 int 得到 0。如果读路径使用 []，统计、缓存或配置查询可能在“查询”时悄悄改变数据。需要异常形式报告缺失时可考虑 at()；需要条件插入时使用适当的插入接口。

无序容器重新分桶会使迭代器失效，但不会因此使现有元素的引用和指针失效；删除某个元素则会使指向该元素的访问路径失效。这与 vector 扩容不同，说明“迭代器失效”和“元素对象被迁移”不能始终画等号。

5. 删除、字符串与所有权

卡 · 容器更新后，迭代器和引用是否一定同时失效？

删除时应使用操作返回的新位置继续遍历，避免使用已失效迭代器：

#include <cassert>
#include <vector>

int main() {
    std::vector<int> values{1, 2, 3, 4};
    for (auto it = values.begin(); it != values.end();) {
        if (*it % 2 == 0) it = values.erase(it);
        else ++it;
    }
    assert((values == std::vector<int>{1, 3}));
}

erase 返回删除位置之后的有效迭代位置。不能先 erase(it) 再对原来的 it 执行 ++it；即使某次运行没有崩溃，也没有修复其有效性问题。

std::string 保存字符单元，并不自动理解 Unicode 字符边界。使用 UTF-8 时，一个中文字符可能占多个 char 单元，因此 size() 不能直接解释成用户看见的字符数，按字节下标修改还可能破坏编码。小字符串优化是常见实现手段，不是可依赖的固定长度保证；保存 data() 或 c_str() 指针后，也要注意后续修改造成的失效。

容器析构会销毁元素对象。vector<unique_ptr<T>> 的元素析构会释放各自拥有的 T；vector<T*> 只销毁指针元素，不会自动 delete 目标。向容器里放什么类型，决定了复制、移动和销毁的资源语义。

标准容器也不自动把并发更新变成安全操作。只读访问、不同元素的可并行操作和改变容器结构的操作具有不同条件；共享修改应根据实际操作添加同步，不能因为使用标准容器就省略线程安全分析。

6 · 面试题卡片

先想答案，再翻面先在心里答一遍，再点开卡片对照参考回答。卡片之间可以左右切换，看完会回到这里。

逐张翻看 4 张 →

访问需求与结构

map 与 unordered_map 的底层组织和复杂度有何区别？

考察 1 点 · 相关 §2 §4未标记

vector 容量与失效

vector 的 reserve 和 resize 有什么区别？

本站自测

考察 1 点 · 相关 §3未标记

vector 容量与失效

容器更新后，迭代器和引用是否一定同时失效？

本站自测

考察 1 点 · 相关 §3 §4 §5未标记

STL 组件协作

STL 的组件怎样协作，常见容器适配器有哪些？

考察 1 点 · 相关 §2.1 §2.2未标记

未标记的卡读完后明天进入复习；已标记的按状态安排

本页题目与参考回答

6.1 map 与 unordered_map 的底层组织和复杂度有何区别？

考察重点：有序关系、哈希、平均与最坏成本。

相关内容：访问需求与结构、有序键与哈希键。

参考回答

map 按比较关系保持键有序，常见实现是平衡树；unordered_map 用哈希组织键，不提供键顺序。 map 的主要查找和更新为对数复杂度；unordered_map 查找平均常数、最坏线性。需要范围查询或稳定键顺序时倾向 map，主要做等值查找时再结合哈希成本、数据规模和失效规则选择，不能只凭平均复杂度判断。

6.2 vector 的 reserve 和 resize 有什么区别？

考察重点：容量、元素数量和构造边界。

相关内容：vector 容量与失效。

参考回答

reserve 预留容量，不改变已有元素数；resize 改变大小，必要时构造或销毁元素。 空 vector 只调用 reserve(8) 后仍不能访问 values[0]，因为元素尚不存在。请求容量大于现有容量会重新分配并使旧元素访问路径失效，调用方需要重新取得迭代器或引用。

6.3 容器更新后，迭代器和引用是否一定同时失效？

考察重点：容器、操作与具体失效范围。

相关内容：vector 容量与失效、有序键与哈希键、删除、字符串与所有权。

参考回答

不一定，要按容器和操作分别判断。 vector 重新分配会使所有元素迭代器、引用和指针失效；未扩容的中间插入或删除会影响相应位置及其后的访问路径。unordered_map 重新分桶会使迭代器失效，但现有元素的引用和指针仍有效；删除元素则使对该元素的访问失效。遍历删除时使用 erase 返回的位置继续。

6.4 STL 的组件怎样协作，常见容器适配器有哪些？

考察重点：容器、迭代器与算法的分工，可调用规则和存储管理，以及适配器的接口约束。

相关内容：STL 组件协作、容器适配器。

参考回答

容器保存元素，迭代器把元素范围交给算法；函数对象提供比较等行为，分配器参与存储管理，适配器改变已有组件的使用接口。 例如 sort 经由 vector 的迭代器访问元素，并按传入的比较器排序；它要求随机访问迭代器，因此不能直接用于 list。

容器适配器包括后进先出的 stack、先进先出的 queue 和按优先级取元素的 priority_queue。前两者默认使用 deque，后者默认使用 vector。更换底层容器要满足所需操作：stack 可用 vector，queue 需要 pop_front()，priority_queue 还需要随机访问迭代器。适配器不公开普通容器的遍历接口，pop() 也不返回被删除元素。

7. 参考资料

• C++17 草案 N4659：vector capacity
• C++17 草案 N4659：vector modifiers
• C++17 草案 N4659：Associative containers
• C++17 草案 N4659：Unordered associative containers
• C++17 草案 N4659：Containers library 与 Strings library
• C++17 草案 N4659：Container adaptors
• C++17 草案 N4659：Algorithms library

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明