正文

第 4 章 容器

4.1 线性容器

std::array

（C++11）

看到这个容器的时候肯定会出现这样的问题：

  1. 为什么要引入 std::array 而不是直接使用 std::vector？
  2. 已经有了传统数组，为什么要用 std::array?

先回答第一个问题，与 std::vector 不同，std::array 对象的大小是固定的，如果容器大小是固定的，那么可以优先考虑使用 std::array 容器。 另外由于 std::vector 是自动扩容的，当存入大量的数据后，并且对容器进行了删除操作， 容器并不会自动归还被删除元素相应的内存，这时候就需要手动运行 shrink_to_fit() 释放这部分内存。

std::vector<int> v;
std::cout << "size:" << v.size() << std::endl;         // 输出 0
std::cout << "capacity:" << v.capacity() << std::endl; // 输出 0

// 如下可看出 std::vector 的存储是自动管理的，按需自动扩张
// 但是如果空间不足，需要重新分配更多内存，而重分配内存通常是性能上有开销的操作
v.push_back(1);
v.push_back(2);
v.push_back(3);
std::cout << "size:" << v.size() << std::endl;         // 输出 3
std::cout << "capacity:" << v.capacity() << std::endl; // 输出 4

// 这里的自动扩张逻辑与 Golang 的 slice 很像
v.push_back(4);
v.push_back(5);
std::cout << "size:" << v.size() << std::endl;         // 输出 5
std::cout << "capacity:" << v.capacity() << std::endl; // 输出 8

// 如下可看出容器虽然清空了元素，但是被清空元素的内存并没有归还
v.clear();                                             
std::cout << "size:" << v.size() << std::endl;         // 输出 0
std::cout << "capacity:" << v.capacity() << std::endl; // 输出 8

// 额外内存可通过 shrink_to_fit() 调用返回给系统
v.shrink_to_fit();
std::cout << "size:" << v.size() << std::endl;         // 输出 0
std::cout << "capacity:" << v.capacity() << std::endl; // 输出 0

而第二个问题就更加简单，使用 std::array 能够让代码变得更加“现代化”，而且封装了一些操作函数，比如获取数组大小以及检查是否非空，同时还能够友好的使用标准库中的容器算法，比如 std::sort。

使用 std::array 很简单，只需指定其类型和大小即可：

std::array<int, 4> arr = {1, 2, 3, 4};

arr.empty(); // 检查容器是否为空
arr.size();  // 返回容纳的元素数

// 迭代器支持
for (auto &i : arr)
{
    // ...
}

// 用 lambda 表达式排序
std::sort(arr.begin(), arr.end(), [](int a, int b) {
    return b < a;
});

// 数组大小参数必须是常量表达式
constexpr int len = 4;
std::array<int, len> arr = {1, 2, 3, 4};

// 非法,不同于 C 风格数组，std::array 不会自动退化成 T*
// int *arr_p = arr;

当我们开始用上了 std::array 时，难免会遇到要将其兼容 C 风格的接口，这里有三种做法：

void foo(int *p, int len) {
    return;
}

std::array<int, 4> arr = {1,2,3,4};

// C 风格接口传参
// foo(arr, arr.size()); // 非法, 无法隐式转换
foo(&arr[0], arr.size());
foo(arr.data(), arr.size());

// 使用 `std::sort`
std::sort(arr.begin(), arr.end());

std::forward_list

（C++11）

std::forward_list 是一个列表容器，使用方法和 std::list 基本类似，因此我们就不花费篇幅进行介绍了。

需要知道的是，和 std::list 的双向链表的实现不同，std::forward_list 使用单向链表进行实现， 提供了 O(1) 复杂度的元素插入，不支持快速随机访问（这也是链表的特点）， 也是标准库容器中唯一一个不提供 size() 方法的容器。当不需要双向迭代时，具有比 std::list 更高的空间利用率。

4.2 无序容器

（C++11）

我们已经熟知了传统 C++ 中的有序容器 std::map/std::set，这些元素内部通过红黑树进行实现， 插入和搜索的平均复杂度均为 O(log(size))。在插入元素时候，会根据 < 操作符比较元素大小并判断元素是否相同， 并选择合适的位置插入到容器中。当对这个容器中的元素进行遍历时，输出结果会按照 < 操作符的顺序来逐个遍历。

而无序容器中的元素是不进行排序的，内部通过 Hash 表实现，插入和搜索元素的平均复杂度为 O(constant)， 在不关心容器内部元素顺序时，能够获得显著的性能提升。

C++11 引入了的两组无序容器分别是：std::unordered_map/std::unordered_multimap 和 std::unordered_set/std::unordered_multiset。

它们的用法和原有的 std::map/std::multimap/std::set/set::multiset 基本类似， 由于这些容器我们已经很熟悉了，便不一一举例，我们直接来比较一下std::map和std::unordered_map：

#include <iostream>
#include <string>
#include <unordered_map>
#include <map>

int main() {
    // 两组结构按同样的顺序初始化
    std::unordered_map<int, std::string> u = {
        {1, "1"},
        {3, "3"},
        {2, "2"}
    };
    std::map<int, std::string> v = {
        {1, "1"},
        {3, "3"},
        {2, "2"}
    };

    // 分别对两组结构进行遍历
    std::cout << "std::unordered_map" << std::endl;
    for( const auto & n : u)
        std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";

    std::cout << std::endl;
    std::cout << "std::map" << std::endl;
    for( const auto & n : v)
        std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
}

最终的输出结果为：

std::unordered_map
Key:[2] Value:[2]
Key:[3] Value:[3]
Key:[1] Value:[1]

std::map
Key:[1] Value:[1]
Key:[2] Value:[2]
Key:[3] Value:[3]

4.3 元组

了解过 Python 的程序员应该知道元组的概念，纵观传统 C++ 中的容器，除了 std::pair 外， 似乎没有现成的结构能够用来存放不同类型的数据（通常我们会自己定义结构）。 但 std::pair 的缺陷是显而易见的，只能保存两个元素。

元组基本操作

（C++11）

关于元组的使用有三个核心的函数：

  1. std::make_tuple: 构造元组
  2. std::get: 获得元组某个位置的值
  3. std::tie: 元组拆包
#include <tuple>
#include <iostream>

auto get_student(int id)
{
    // 返回类型被推断为 std::tuple<double, char, std::string>

    if (id == 0)
        return std::make_tuple(3.8, 'A', "张三");
    if (id == 1)
        return std::make_tuple(2.9, 'C', "李四");
    if (id == 2)
        return std::make_tuple(1.7, 'D', "王五");
    return std::make_tuple(0.0, 'D', "null");
    // 如果只写 0 会出现推断错误, 编译失败
}

int main()
{
    auto student = get_student(0);
    std::cout << "ID: 0, "
    << "GPA: " << std::get<0>(student) << ", "
    << "成绩: " << std::get<1>(student) << ", "
    << "姓名: " << std::get<2>(student) << '\n';

    double gpa;
    char grade;
    std::string name;

    // 元组进行拆包
    std::tie(gpa, grade, name) = get_student(1);
    std::cout << "ID: 1, "
    << "GPA: " << gpa << ", "
    << "成绩: " << grade << ", "
    << "姓名: " << name << '\n';
}

std::get 除了使用常量获取元组对象外，C++14 增加了使用类型来获取元组中的对象：

std::tuple<std::string, double, double, int> t("123", 4.5, 6.7, 8);
std::cout << std::get<std::string>(t) << std::endl;
std::cout << std::get<double>(t) << std::endl; // 非法, 引发编译期错误
std::cout << std::get<3>(t) << std::endl;

运行期索引

如果你仔细思考一下可能就会发现上面代码的问题，std::get<> 依赖一个编译期的常量，所以下面的方式是不合法的：

int index = 1;
std::get<index>(t);

那么要怎么处理？答案是，使用 std::variant<>（C++ 17 引入），提供给 variant<> 的类型模板参数 可以让一个 variant<> 从而容纳提供的几种类型的变量（在其他语言，例如 Python/JavaScript 等，表现为动态类型）：

#include <variant>
template <size_t n, typename... T>
constexpr std::variant<T...> _tuple_index(const std::tuple<T...>& tpl, size_t i) {
    if constexpr (n >= sizeof...(T))
        throw std::out_of_range("越界.");
    if (i == n)
        return std::variant<T...>{ std::in_place_index<n>, std::get<n>(tpl) };
    return _tuple_index<(n < sizeof...(T)-1 ? n+1 : 0)>(tpl, i);
}
template <typename... T>
constexpr std::variant<T...> tuple_index(const std::tuple<T...>& tpl, size_t i) {
    return _tuple_index<0>(tpl, i);
}
template <typename T0, typename ... Ts>
std::ostream & operator<< (std::ostream & s, std::variant<T0, Ts...> const & v) { 
    std::visit([&](auto && x){ s << x;}, v); 
    return s;
}

这样我们就能：

int i = 1;
std::cout << tuple_index(t, i) << std::endl;

元组合并与遍历

还有一个常见的需求就是合并两个元组，这可以通过 std::tuple_cat 来实现：

auto new_tuple = std::tuple_cat(get_student(1), std::move(t));

马上就能够发现，应该如何快速遍历一个元组？但是我们刚才介绍了如何在运行期通过非常数索引一个 tuple 那么遍历就变得简单了， 首先我们需要知道一个元组的长度，可以：

template <typename T>
auto tuple_len(T &tpl) {
    return std::tuple_size<T>::value;
}

这样就能够对元组进行迭代了：

// 迭代
for(int i = 0; i != tuple_len(new_tuple); ++i)
    // 运行期索引
    std::cout << tuple_index(new_tuple, i) << std::endl;

不过，上面这种「先实现运行期索引、再逐个索引」的遍历方式虽然可行，却相当迂回。如果只是想对元组的每个元素施加同一个操作，更直接、惯用的做法是借助 std::index_sequence（C++14 引入）在编译期展开下标。在 C++17 中可以配合折叠表达式写成：

template <typename Func, typename Tuple, std::size_t... idx>
void iterate_impl(Func&& f, Tuple&& tpl, std::index_sequence<idx...>) {
    (f(std::get<idx>(std::forward<Tuple>(tpl))), ...);
}
template <typename Func, typename Tuple>
void iterate_tuple(Func&& f, Tuple&& tpl) {
    iterate_impl(std::forward<Func>(f), std::forward<Tuple>(tpl),
        std::make_index_sequence<std::tuple_size_v<std::remove_reference_t<Tuple>>>{});
}

到了 C++20，还可以利用允许显式书写模板参数的 Lambda，把辅助函数也一并省去：

template <typename Func, typename... Args>
void iterate_tuple(Func f, const std::tuple<Args...>& tpl) {
    [&]<std::size_t... idx>(std::index_sequence<idx...>) {
        (f(std::get<idx>(tpl)), ...);
    }(std::make_index_sequence<sizeof...(Args)>());
}

这样调用就非常直观了，而且无需事先实现运行期索引：

iterate_tuple([](const auto& v) { std::cout << v << ' '; }, new_tuple);

4.4 std::string_view 与 std::byte

std::string_view

（C++17）

C++17 引入的 std::string_view 是对一段字符序列的非拥有 (non-owning)、只读视图，它仅保存一个指针和一个长度。把函数形参写成 std::string_view 既可以接受 std::string，也可以接受字符串字面量，而且不会发生任何拷贝或内存分配：

#include <string_view>

void print(std::string_view sv) {
    std::cout << sv << " (size = " << sv.size() << ")" << std::endl;
}

std::string_view sv = "hello, world";
print(sv.substr(0, 5)); // "hello"，substr 不分配内存

std::string s = "from std::string";
print(s);               // 隐式转换，无拷贝

需要特别注意其生命周期：string_view 不拥有底层数据，因此必须保证被引用的字符序列在视图存活期间一直有效，否则会产生悬垂引用。

std::byte

（C++17）

std::byte 用于表示一段原始内存中的一个字节。与 char 或 unsigned char 不同，它不是算术类型——标准只为其定义了位运算符，从而在类型层面避免了对原始字节进行意外的算术运算：

#include <cstddef>

std::byte b{0b0000'1100};       // 12
b <<= 2;                        // 48
b |= std::byte{0b0000'0001};    // 49
int v = std::to_integer<int>(b); // 需要显式转换为整数：49

4.5 关联容器的改进

（C++17）

C++17 为 std::map / std::unordered_map 等关联容器增加了若干更精确、也更高效的操作：

#include <map>
#include <string>

std::map<int, std::string> m;
m.try_emplace(1, "one");
m.try_emplace(1, "uno");        // 无效果，键 1 已存在
m.insert_or_assign(1, "ONE");   // 覆盖为 "ONE"

std::map<int, std::string> other;
other.insert(m.extract(1));     // 将节点 1 移动到 other，不拷贝元素

std::map<int, std::string> more{{3, "three"}};
m.merge(more);                  // 将 more 的节点拼接进 m

4.6 多态分配器 std::pmr

（C++17）

C++17 在 <memory_resource> 中引入了 std::pmr 命名空间，提供了基于内存资源 (memory resource) 的多态分配器。它把「从哪里分配内存」这一策略与容器类型解耦：不同内存资源支撑的同一种 pmr 容器仍然是同一个类型，从而避免了模板分配器带来的类型膨胀。

例如，std::pmr::monotonic_buffer_resource 可以从一块预先准备好的缓冲区（甚至是栈上的缓冲区）中分配内存，直到资源析构时才统一释放，非常适合分配密集且生命周期一致的场景：

#include <array>
#include <cstddef>
#include <memory_resource>
#include <vector>

std::array<std::byte, 1024> buffer;
std::pmr::monotonic_buffer_resource pool{buffer.data(), buffer.size()};

std::pmr::vector<int> v{&pool}; // 从栈上的 buffer 分配，而非堆
for (int i = 0; i < 5; ++i) v.push_back(i);

总结

本章简单介绍了现代 C++ 中新增的容器，它们的用法和传统 C++ 中已有的容器类似，相对简单，可以根据实际场景丰富的选择需要使用的容器，从而获得更好的性能。

std::tuple 虽然有效，但是标准库提供的功能有限，没办法满足运行期索引和迭代的需求，好在我们还有其他的方法可以自行实现。

← 第 3 章 语言运行期的强化 第 5 章 智能指针与内存管理 →

欧长坤 © 2016-2026 版权所有， 采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议许可，代码使用 MIT 协议开源。

如果你认为本书对你起到了帮助，可以资助作者。