Chapter26 容器和字符串扩展

C++标准库的容器也有很多微小的改进，将在这一章进行讨论。

26.1 节点句柄

C++17引入了把某个节点从关联或无序容器中移入或移出的功能，使用这个功能你可以轻易地：

  • 修改(unordered) map的key或者(unordered) set的value
  • 在(unordered) set和map中使用move语义
  • 在(unordered) set和map中移动元素
  • 把一个(unordered) set或map合并到另一个中

26.1.1 修改key

例如，考虑下面的程序：

  1. #include <iostream>
  2. #include <string>
  3. #include <map>
  5. int main()
  6. {
  7.     std::map<int, std::string> m{{1, "mango"},
  8.                                  {2, "papaya"},
  9.                                  {3, "guava"}};
  11.     auto nh = m.extract(2); // nh的类型为decltype(m)::node_type
  12.     nh.key() = 4;
  13.     m.insert(std::move(nh));
  15.     for (const auto& [key, value] : m) {
  16.         std::cout << key << ": " << value << '\n';
  17.     }
  18. }

在如下定义和初始化一个map之后：

  1. std::map<int, std::string> m{{1, "mango"},
  2.                              {2, "papaya"},
  3.                              {3, "guava"}};

你可以像下面这样修改key 2：

  1. auto nh = m.extract(2); // nh的类型为decltype(m)::node_type
  2. nh.key() = 4;
  3. m.insert(std::move(nh));

这段代码先是把key为2的元素节点移出容器，然后修改了key，最后又移进了容器， 这个过程如图26.1所示。 Chapter26 容器和字符串扩展 - 图1

注意在C++17之前如果想修改一个key，必须先删除旧节点然后再插入一个value相同的新节点（key是 const的，因为key的值决定了它们在容器中的位置，所以必须保持稳定）。 如果我们使用节点句柄，将不会发生内存分配，并且所有指向元素的指针和引用都保持有效， 然而，当元素还在节点句柄里而不在容器里的时候使用这些指针或者引用会导致未定义的行为。

节点句柄的类型是 container::node_type。它提供了下列成员：

  • 所有(unordered) set类型都有value()成员
  • 所有(unordered) map类型都有key()和mapped()成员

26.1.2 在容器之间移动节点句柄

你也可以使用节点句柄把一个元素从一个容器move( splice )到另一个容器。 即使容器的类型有如下不同也没有问题：

  • 一个支持重复而另一个不支持（例如，你可以把一个元素从multimap移动到map）
  • 比较函数和哈希函数都不同

例如，考虑下面的程序：

  1. #include <iostream>
  2. #include <string>
  3. #include <map>
  5. template<typename T1, typename T2>
  6. void print(const T1& coll1, const T2& coll2) {
  7.     std::cout << "values:\n";
  8.     for (const auto& [key, value] : coll1) {
  9.         std::cout << "  [" << key << ":" << value << "]";
  10.     }
  11.     std::cout << '\n';
  12.     for (const auto& [key, value] : coll2) {
  13.         std::cout << "  [" << key << ":" << value << "]";
  14.     }
  15.     std::cout << '\n';
  16. }
  18. int main()
  19. {
  20.     std::multimap<double, std::string> src{{1.1, "one"},
  21.                                            {2.2, "two"},
  22.                                            {3.3, "three"}};
  23.     std::map<double, string> dst{{3.3, "old data"}};
  25.     print(src, dst);
  27.     // 把一些元素从multimap src中移动到map dst中：
  28.     dst.insert(src.extract(src.find(1.1)));     // 使用迭代器移动
  29.     dst.insert(src.extract(2.2));               // 使用key移动
  31.     print(src, dst);
  32. }

我们两次从src中提取元素（一次传递迭代器一次传递key）并把它们插入dst。 因此，程序会有如下输出：

  1. values:
  2.   [1.1:one]  [2.2:two]  [3.3:three]
  3.   [3.3:old data]
  4. values:
  5.   [3.3:three]
  6.   [1.1:one]  [2.2:two]  [3.3:old data]

注意当不允许重复时（set、map、unordered set、unordered map），以节点句柄为参数 的insert()成员函数会返回一个有三个成员的结构体类型 container::insert_return_type， 三个成员分别是（按照如下顺序）：

  • 一个迭代器 position ，当插入成功时（不存在相同key的元素时）指向插入的新元素， 当插入失败时指向已经存在的元素。
  • 一个bool值 inserted 来表示插入是否成功。
  • 一个 container::node_type类型的 node ，当插入失败时作为节点句柄。

也就是说，关键信息是第二个成员inserted。通过使用结构化绑定，你可以像下面这样使用返回值：

  1. auto [pos, done, node] = dst.insert(src.extract(3.3));
  2. if (!done) {
  3.     std::cout << "insert() of node handle failed:"
  4.               << " tried to insert key '" << node.key()
  5.               << "' with value '" << node.mapped()
  6.               << "' but key exists with value '" << pos->second << "'\n";
  7. }

如果一个元素被提取之后再也没有被重新插入，那么节点句柄的析构函数会释放该元素的内存。 因此，在这段代码中，即使插入失败也不会有内存泄露。

26.1.3 合并容器

以节点句柄API为基础，现在所有的关联和无序容器都提供了成员函数merge()， 它可以把一个容器中的所有元素合并到另一个容器中。

再强调一次，即使容器的类型有如下不同也没有问题：

  • 一个支持重复而另一个不支持（例如，你可以把一个元素从multimap移动到map）
  • 比较函数和哈希函数都不同

如果源容器中的某个元素因为在目标容器里已经有了与key相同的元素而无法移动， 那么它会仍然留在源容器中。

例如，下面的程序：

  1. #include <iostream>
  2. #include <string>
  3. #include <map>
  5. template<typename T1, typename T2>
  6. void print(const T1& coll1, const T2& coll2)
  7. {
  8.     std::cout << "values:\n";
  9.     for (const auto& [key, value] : coll1) {
  10.         std::cout << "  [" << key << ":" << value << "]";
  11.     }
  12.     std::cout << '\n';
  13.     for (const auto& [key, value] : coll2) {
  14.         std::cout << "  [" << key << ":" << value << "]";
  15.     }
  16.     std::cout << '\n';
  17. }
  19. int main()
  20. {
  21.     std::multimap<double, std::string> src {{1.1, "one"},
  22.                                             {2.2, "two"},
  23.                                             {3.3, "three"}};
  24.     std::map<double, std::string> dst {{3.3, "old data"}};
  26.     print(src, dst);
  28.     // 把src中的所有元素合并到dst中：
  29.     dst.merge(src);
  31.     print(src, dst);
  32. }

会有如下输出：

  1. values:
  2.   [1.1:one]  [2.2:two]  [3.3:three]
  3.   [3.3:old data]
  4. values:
  5.   [3.3:three]
  6.   [1.1:one]  [2.2:two]  [3.3:old data]

指向被合并元素的指针和引用仍然有效，只不过指向的容器发生了变化。

26.2 emplace改进

26.2.1 emplace函数的返回类型

对于顺序容器std::vector<>、std::deque<>、std::list<>和std::forward_list<>， 还有容器适配器std::queue<>和std::stack<>，它们的emplace函数现在 返回新插入的对象的引用（关联容器以前就已经是这样了）。 这允许我们实现类似于如下的代码：

  1. foo(myVector.emplace_back(...));

来代替：

  1. myVector.emplace_back(...);
  2. foo(myVector.back());

26.2.2 map的try_emplace()和insert_or_assign()

这两个成员函数让我们能够稍稍更简单或者更高效的编写处理map和unordered map的代码：

  • try_emplace()用移动语义构造一个新的值。
  • insert_or_assign()稍微改进了插入/更新元素的方法。

26.2.3 try_emplace()

考虑下列代码：

  1. std::map<int, std::string> m;
  2. m[42] = "hello";
  3. std::string s{"world"};
  4. m.emplace(42, std::move(s));    // 可能移动，但如果42已经存在时可能不会移动

这个调用之后s是否仍然保持原本的值是未定义的。 同样，对unordered_map使用了insert()之后也是这样：

  1. m.insert({42, std::move(s)});   // 可能移动，但如果42已经存在时可能不会移动

注意根据移动语义的规则这个行为并不是错误。当使用std::move(s)时， 我们只是表明我们对s的值不再感兴趣，std::move()会把对象标记为 可移动的但不会立刻移动走它的值。因此，在这样的调用之后，s 可能还有也可能没有 原本的值了。

然而，你可能会惊讶于即使没有成功插入s的值也可能会被移动走（这种情况的发生和实现细节有关）。 有时，程序员可能想或者必须知道对象的值到底有没有被移走，或者想在只有插入成功时才移动走对象的值。 特别的，当使用只能移动的对象例如线程或者独占指针时就是这种情况。

例如，下面的代码是无效的，因为你必须在一个std::thread的析构函数被调用之前 调用它的join()（或者detach()）函数：

  1. std::map<int, std::thread> m;
  2. std::thread t1{...};
  3. m.insert({42, std::move(t1)});      // 即使没能插入也可能move

这里，即使t1没有被插入也可能会被move，这会导致core dump， 因为之后t1会在调用内部被销毁并且没有调用t1.join()。 作为代替，你可能必须像下面这样写：

  1. auto pos = m.find(42);
  2. if (pos == m.end()) {
  3.     m.insert({42, std::move(t1)});  // 如果不存在则插入（并move）
  4. }

这样写不仅代码变复杂了，还需要查找新的元素两次。

新的成员函数try_emplace()保证在没有已存在元素时才会move走传入的值：

  1. m.try_emplace(42, std::move(t1));   // 如果插入失败则不会move

事实上，它类似于如下写法的缩写：

  1. auto pos = m.find(42);
  2. if (pos == m.end()) {
  3.     m.emplace(42, std::move(t1));   // 插入
  4. }

不过相比之下一个好处是只会查找一次要插入的位置。

就像名字暗示的一样，try_emplace()允许我们传递任意数量的参数来 在元素不存在时初始化一个新的元素：

  1. std::map<int, std::string> ms;
  2. ms.try_emplace(42, "hello");    // 尝试插入元素，value为"hello"
  3. ms.try_emplace(43, 8, 'a');     // 尝试插入元素，value为"aaaaaaaa"

然而，注意你不能以这种方式初始化一个容器里的元素：

  1. std::map<int, std::vector<std::string>> vals;
  2. std::string h{"hello"};
  3. std::string w{"world"};
  4. vals.try_emplace(42, std::vector<std::string>{h, w});   // OK
  5. vals.try_emplace(42, h, w);                             // ERROR

可以传递一个额外的迭代器作为第一个参数，它被用作查找新元素应该放置的位置时的提示。

26.2.4 insert_or_assign()

另外，新的成员函数insert_or_assign()保证把值移动到一个新的元素或者已存在的元素中：

  1. m.insert_or_assgin(42, std::move(t1));  // 总是会move

它的行为类似于如下代码的缩写：

  1. auto pos = m.find(42);
  2. if (pos == m.end()) {
  3.     m.insert({42, std::move(t1)});  // 插入
  4. }
  5. else {
  6.     pos->second = std::move(t1);    // 更新
  7. }

类似于

  1. m[42] = std::move(t1);              // key不存在时首先默认初始化value，再覆盖value

不过相比之下的好处是新元素的位置只会查找一次，并且新元素并不是首先用默认构造函数构造然后再覆写。

因此，这个成员函数可以在默认构造函数不能调用的情况下允许我们插入或者更新一个元素。

注意insert_or_assign()把key和value作为分离的参数，而insert() 把它们作为一个整体参数。 另外，可以传递一个额外的迭代器作为第一个参数，它被用作查找新元素应该放置的位置时的提示。

26.3 对不完全类型的容器支持

自从C++17起，std::vector、std::list、std::forward_list被要求支持 不完全类型。

这个特性的主要动机在Matt Austern的一篇标题 为 The Standard Librarian: Containers of Incomplete Types 的文章中进行了解释：

你现在可以定义一个类型，内部递归的包含一个自身类型的容器。例如：

  1. struct Node
  2. {
  3.     std::string value;
  4.     std::vector<Node> children; // 自从C++17起OK（这里Node是一个不完全的类型）
  5. };

这也适用于带有private成员和public API的类。 这里有一个完整的例子：

  1. #ifndef NODE_HPP
  2. #define NODE_HPP
  4. #include <vector>
  5. #include <iostream>
  6. #include <string>
  8. class Node
  9. {
  10. private:
  11.     std::string value;
  12.     std::vector<Node> children; // 自从C++17起OK（这里Node是一个不完全类型）
  13. public:
  14.     // 用单个值创建一个Node：
  15.     Node(std::string s) : value{std::move(s)}, childern{} {
  16.     }
  18.     // 添加子节点：
  19.     void add(Node n) {
  20.         children.push_back(std::move(n));
  21.     }
  23.     // 访问子节点：
  24.     Node& operator[](std::size_t idx) {
  25.         return children.at(idx);
  26.     }
  28.     // 递归打印出节点树：
  29.     void print(int indent = 0) const {
  30.         std::cout << std::string(indent, ' ') << value << '\n';
  31.         for (const auto& n : children) {
  32.             n.print(indent + 2);
  33.         }
  34.     }
  35.     ...
  36. };
  38. #endif  // NODE_HPP

你可以像下面这样使用这个类：

  1. #include "incomplete.hpp"
  2. #include <iostream>
  4. int main()
  5. {
  6.     // 创建节点树：
  7.     Node root{"top"};
  8.     root.add(Node{"elem1"});
  9.     root.add(Node{"elem2"});
  10.     root[0].add(Node{"elem1.1"});
  12.     // 打印节点树：
  13.     root.print();
  14. }

程序会有如下输出：

  1. top
  2. elem1
  3. elem1.1
  4. elem2

26.4 string改进

对于string（类型为basic_string<>)，C++17提供了以下一些改进：

  • 对于非常量string，你现在也可以调用data()把底层的字符序列当作原生C字符串来访问：
    1. std::string mystring{"Hello world"};
    2. auto cstr = mystring.data();
    3. cstr[6] = 'W';                      // 自从C++17起OK
    注意在C++17之前，cstr的类型将是const char*，而现在它的类型是char*。 在C++17之前，把data()的返回值赋值给char*将不能通过编译：
    1. std::string mystring{"Hello world"};
    2. char* cstr = mystring.data();   // 自从C++17起OK
    和以前一样，只要std::string还存在并且没有重新分配内存， 对data()的返回值的访问就是有效的。修改data()返回值的末尾的空终止符仍然是未定义行为。
  • 还提供了一个到std::string_view的隐式转换，然而，这可能会导致一些bug或者歧义。 见关于字符串视图的章节获取详情。
  • 字符串现在也支持多态类型资源，这意味着你可以声明：
    1. std::pmr::string s1;
    2. std::pmr::wstring s1;
    3. std::pmr::u16string s1;
    4. std::pmr::u32string s1;
    见PMR章节获取详情。