第 4 章 容器

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

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

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

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

    1. std::array<int, 4> arr = {1, 2, 3, 4};
    3. arr.empty(); // 检查容器是否为空
    4. arr.size();  // 返回容纳的元素数
    6. // 迭代器支持
    7. for (auto &i : arr)
    8. {
    9.     // ...
    10. }
    12. // 用 lambda 表达式排序
    13. std::sort(arr.begin(), arr.end(), [](int a, int b) {
    14.     return b < a;
    15. });
    17. // 数组大小参数必须是常量表达式
    18. constexpr int len = 4;
    19. std::array<int, len> arr = {1, 2, 3, 4};
    21. // 非法,不同于 C 风格数组，std::array 不会自动退化成 T*
    22. // int *arr_p = arr;

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

    1. void foo(int *p, int len) {
    2.     return;
    3. }
    5. std::array<int, 4> arr = {1,2,3,4};
    7. // C 风格接口传参
    8. foo(&arr[0], arr.size());
    9. foo(arr.data(), arr.size());
    11. // 使用 `std::sort`
    12. std::sort(arr.begin(), arr.end());

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

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

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

    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：

    1. #include <iostream>
    2. #include <string>
    3. #include <unordered_map>
    4. #include <map>
    6. int main() {
    7.     // 两组结构按同样的顺序初始化
    8.     std::unordered_map<int, std::string> u = {
    9.         {1, "1"},
    10.         {3, "3"},
    11.         {2, "2"}
    12.     };
    13.     std::map<int, std::string> v = {
    14.         {1, "1"},
    15.         {3, "3"},
    16.         {2, "2"}
    17.     };
    19.     // 分别对两组结构进行遍历
    20.     std::cout << "std::unordered_map" << std::endl;
    21.     for( const auto & n : u)
    22.         std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
    24.     std::cout << std::endl;
    25.     std::cout << "std::map" << std::endl;
    26.     for( const auto & n : v)
    27.         std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
    28. }

    最终的输出结果为：

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

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

    1. std::make_tuple: 构造元组
    2. std::get: 获得元组某个位置的值
    3. std::tie: 元组拆包
    1. #include <tuple>
    4. auto get_student(int id)
    5. {
    7. if (id == 0)
    8.     return std::make_tuple(3.8, 'A', "张三");
    9. if (id == 1)
    10.     return std::make_tuple(2.9, 'C', "李四");
    11. if (id == 2)
    12.     return std::make_tuple(1.7, 'D', "王五");
    13.     return std::make_tuple(0.0, 'D', "null");
    14.     // 如果只写 0 会出现推断错误, 编译失败
    15. }
    17. int main()
    18. {
    19.     auto student = get_student(0);
    20.     std::cout << "ID: 0, "
    21.     << "GPA: " << std::get<0>(student) << ", "
    22.     << "成绩: " << std::get<1>(student) << ", "
    23.     << "姓名: " << std::get<2>(student) << '\n';
    25.     double gpa;
    26.     char grade;
    27.     std::string name;
    29.     // 元组进行拆包
    30.     std::tie(gpa, grade, name) = get_student(1);
    31.     std::cout << "ID: 1, "
    32.     << "GPA: " << gpa << ", "
    33.     << "成绩: " << grade << ", "
    34.     << "姓名: " << name << '\n';
    35. }

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

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

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

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

    这样我们就能：

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

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

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

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

    1. template <typename T>
    2. auto tuple_len(T &tpl) {

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

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

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

    | 上一章 |

    本教程由欧长坤撰写，采用许可。项目中代码使用 MIT 协议开源，参见许可。