C++ 容器：容量、初始化、链表与键值查询

知识概念更新于 2026-10-03编辑本文

容器拥有并组织一组元素。选择时先问：数量是否固定、是否需要按索引访问、是否按键查找、修改发生在哪里，以及已有迭代器是否要保持有效。本页采用C++17，合并了原来分散的array、list和map接口示例。

1. 容器家族

家族	类型	主要取舍
连续序列	`array<T,N>`、`vector<T>`	array大小属于类型且固定；vector大小运行时可变，支持快速随机访问。
双端序列	`deque<T>`	两端增删方便，支持随机访问，但不保证整段内存连续。
链表	`list<T>`、`forward_list<T>`	双向/单向链表；已有合适位置时插删高效，查找位置仍通常线性。
有序关联	`set`、`multiset`、`map`、`multimap`	按比较器维护键顺序；带multi的类型允许等价键重复。
无序关联	`unordered_set`、`unordered_multiset`、`unordered_map`、`unordered_multimap`	哈希与相等关系查找，平均常数时间、最坏可能线性，不保证键排序。

forward_list是单向链表，不是单向数组。map常用平衡树实现，但标准没有要求一定使用红黑树。stack、queue和priority_queue属于容器适配器，接口有不同限制。

2. vector：size是元素数，capacity是可用容量

resize(n)改变实际元素数；增长时构造新元素，缩小时销毁尾部元素。对于默认分配器的 vector<int>，增长的默认插入元素为0。reserve(n)只保证容量至少达到n，不增加size，也不允许访问尚未构造的元素。

#include <cassert>
#include <vector>

int main()
{
    std::vector<int> values{1, 2, 3, 4, 5};
    values.resize(7);
    assert(values.size() == 7 && values.capacity() >= 7);
    assert(values[5] == 0 && values[6] == 0);
    values.reserve(10);
    assert(values.size() == 7 && values.capacity() >= 10);

    values.push_back(6);
    values.insert(values.end(), 2, 8);
    values.insert(values.begin(), 9);
    assert(values.front() == 9 && values.back() == 8);
    values.erase(values.begin());
    values.erase(values.end() - 2, values.end());
    assert((values == std::vector<int>{1, 2, 3, 4, 5, 0, 0, 6}));
    const auto capacity = values.capacity();
    values.clear();
    assert(values.empty() && values.capacity() == capacity);
}

容量增长策略由实现决定，不能把输出硬编码成“resize后capacity必为7、reserve后必为10”。reserve触发重新分配时会使原指针、引用和迭代器失效；clear销毁元素，但保留容量。shrink_to_fit是缩容请求，不保证实现一定收缩。C++工作草案：vector容量

操作	说明
`vector<T> v` / `vector<T> v(n, value)`	空容器/构造n个值。
`v[index]` / `v.at(index)`	都要求索引对应元素；at越界抛异常，下标不提供同样的检查保证。
`push_back/emplace_back`	尾部添加，可能重分配。
`insert/erase`	中间插删通常要移动后续元素。
`front/back`	访问两端，要求非空。
`size/empty/capacity`	分别观察实际大小、是否空和容量。
`swap` / `==`	交换内容/比较元素序列；自定义分配器还有额外规则。
`begin/end`、范围for	遍历已存在的元素。

3. array：固定数量不等于自动清零

对于局部变量 std::array<int,5> values;，元素没有自动获得全零初值，不能直接读取它们。写 values{}才会把本例的int元素值初始化为0；部分列表初始化则将剩余元素补成0。

#include <array>
#include <cassert>
#include <numeric>
#include <stdexcept>

int sum(const std::array<int, 5>& values)
{
    return std::accumulate(values.begin(), values.end(), 0);
}

int main()
{
    std::array<int, 5> zeros{};
    std::array<int, 5> values{1, 2, 3};
    assert(sum(zeros) == 0 && sum(values) == 6);
    assert(values.size() == 5 && !values.empty());
    values[0] = 10;
    assert(values.at(0) == 10 && values.data()[1] == 2);
    bool rejected = false;
    try { (void)values.at(5); }
    catch (const std::out_of_range&) { rejected = true; }
    assert(rejected);
    values.fill(7);
    values.swap(zeros);
    assert(sum(zeros) == 35 && sum(values) == 0);
}

array<int,5>和 array<int,6>是不同类型，固定大小可成为接口约束。array对象的存储位置取决于它自身的存储期和所属对象，并非“array必在栈上”；它不独立为元素申请可增长存储，但也不能据此断言任何场景都比vector快。C++工作草案：array

4. list：先找到位置，再谈常数时间插删

list不支持下标和随机跳转。已有节点迭代器时，插入一个节点或删除指定节点可以是常数时间；从开头找第n项仍需线性前进。

#include <cassert>
#include <iterator>
#include <list>

int main()
{
    std::list<int> values{1, 2, 3, 4, 5};
    values.push_front(0);
    values.push_back(6);
    const auto inserted = values.insert(std::next(values.begin(), 3), 99);
    assert(*inserted == 99);
    values.pop_front();
    values.pop_back();
    values.erase(inserted);
    assert((values == std::list<int>{1, 2, 3, 4, 5}));
    values.reverse();
    assert(values.front() == 5);
    values.sort();
    assert(values.front() == 1 && values.size() == 5);
    values.clear();
    assert(values.empty());
}

这里保留插入位置的迭代器，不再把“去掉头尾后前进3步”误当作仍指向99。原序列 {1,2,99,3,4,5}中，前进3步指向3，99在前进2步的位置。

begin/end与范围for都能遍历；remove、unique、sort、reverse等成员知道链表结构，其中 unique只去掉相邻等价项。splice可转移节点、merge可合并已经按相同规则排序的链表，但需满足分配器和迭代器等前提，不是任意跨容器搬地址。C++工作草案：list操作

5. map：查询和插入是不同动作

map保存键值对，键唯一且按比较器顺序排列。operator[]在键不存在时会插入该键及值初始化的映射值；只想查询时用 find或 at，不要因为“读一下”而改变容器。

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

int main()
{
    std::map<std::string, int> stock{{"apple", 5}, {"banana", 3}};
    stock["orange"] = 7;
    const auto inserted = stock.insert({"apple", 99});
    assert(!inserted.second && stock.at("apple") == 5);
    stock.emplace("pear", 2);

    const auto found = stock.find("banana");
    assert(found != stock.end() && found->second == 3);
    assert(stock.find("missing") == stock.end());
    const auto size = stock.size();
    const int missing = stock["missing"];
    assert(missing == 0 && stock.size() == size + 1);
    stock.erase("missing");

    int total = 0;
    for (const auto& [name, count] : stock) {
        assert(!name.empty());
        total += count;
    }
    assert(total == 17);
    stock.erase(stock.find("banana"));
    assert(stock.count("banana") == 0);
    stock.clear();
    assert(stock.empty());
}

at不存在时抛 out_of_range；erase(iterator)要求不是end，所以上面先用已确定存在的键。lower_bound/upper_bound/equal_range可按有序键定位边界，优先用map成员避免通用迭代器算法额外线性移动。

set只保存键；multiset和multimap允许比较器认定的等价键重复，multimap没有像map那样单值的 operator[]。不能通过普通迭代器直接修改有序容器的键而破坏顺序。

6. unordered容器仍然可以遍历

“无序”表示不保证按键排序，并非不支持范围for。unordered_map有 begin/end，可以访问全部键值对；它没有与有序map相同的按大小定位下界语义。

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

int main()
{
    std::unordered_map<std::string, int> counts{{"a", 2}, {"b", 3}};
    int total = 0;
    for (const auto& entry : counts)
        total += entry.second;
    assert(total == 5 && counts.at("a") == 2);
}

哈希和相等判定必须一致：被判为等价的键应产生相同哈希。rehash可改变遍历顺序并使迭代器失效，因此不要依赖某次输出顺序。C++工作草案：无序关联容器

7. 一个vector能否装不同类型

vector的元素类型固定，但该类型可以是C++17的 variant。variant在编译期列出有限候选类型，每个元素当前保存其中一种值；这不是自动拥有Python list全部动态类型语义。

#include <cassert>
#include <string>
#include <type_traits>
#include <variant>
#include <vector>

int main()
{
    using Item = std::variant<int, std::string>;
    const std::vector<Item> items{42, std::string("Hello")};
    std::string description;
    for (const auto& item : items) {
        description += std::visit([](const auto& value) -> std::string {
            using Type = std::decay_t<decltype(value)>;
            if constexpr (std::is_same_v<Type, int>)
                return std::to_string(value);
            else
                return value;
        }, item);
    }
    assert(description == "42Hello");
}

原图像处理场景的候选可以写成 std::variant<cv::Mat, int, std::string>，再在visitor中增加 cv::Mat分支。这需要OpenCV头文件与正确链接，而且 cv::Mat自己的共享数据/复制规则不由variant改变。本页实测的是上面的纯标准库例子，没有把缺少OpenCV环境的片段标成已运行。

C++17通用lambda可写 [](const auto& value)再用 decltype取类型；原稿 []<typename T>(T&& value)形式的显式模板形参lambda需要C++20，不能悄悄混在C++17示例中。

容器保存裸指针不会自动拥有目标对象；保存 unique_ptr可表达独占所有权，见指针与引用。各容器修改后的引用和迭代器失效还需按迭代器规则检查。