向std::map实例中高效并有条件的插入元素

我们需要用键值对填充一个map实例时，会碰到两种不同的情况：

  1. 键不存在。创建一个全新的键值对。
  2. 键已存在。修改键所对应的值。

我通常会使用insert或emplace函数对map插入新元素，如果插入不成功，那么就是第二种情况，就需要去修改现有的元素。insert和emplace都会创建一个新元素尝试插入到map实例中，不过在第二种情况下，这个新生成的元素会被扔掉。两种情况下，我们都会多余调用一次构造函数。

C++17中，添加了try_emplace函数，其只有在满足条件的情况下，才能插入新元素。让我们实现一个程序，建立一张表，列出各国亿万富翁的数量。我们例子中不会使用很大开销进行元素创建，不过我们的例子来源于生活，其能让你明白如何使用try_emplace。

How to do it…

本节中，我们将实现一个应用，其能创建一张百万富翁的列表。这个列表中按国家区分，里面记录了各国富人的数量。

  1. 包含头文件和声明命名空间。

    1. #include <iostream>
    2. #include <functional>
    3. #include <list>
    4. #include <map>
    6. using namespace std;

  2. 定义一个结构器，代表对应的富翁。

    1. struct billionaire {
    2.     string name;
    3.     double dollars;
    4.     string country;
    5. };

  3. 主函数中，我们定义了一个百万富翁的列表。世界上有很多百万富翁，所以我们创建一个有限列表来存储这些富翁的信息。这个列表是已排序的。2017年福布斯富豪名单，世界百万富翁排行榜可以在 https://www.forbes.com/billionaires/list 查到。

    1. int main()
    2. {
    3.     list<billionaire> billionaires {
    4.         {"Bill Gates", 86.0, "USA"},
    5.         {"Warren Buffet", 75.6, "USA"},
    6.         {"Jeff Bezos", 72.8, "USA"},
    7.         {"Amancio Ortega", 71.3, "Spain"},
    8.         {"Mark Zuckerberg", 56.0, "USA"},
    9.         {"Carlos Slim", 54.5, "Mexico"},
    10.         // ...
    11.         {"Bernard Arnault", 41.5, "France"},
    12.         // ...
    13.         {"Liliane Bettencourt", 39.5, "France"},
    14.         // ...
    15.         {"Wang Jianlin", 31.3, "China"},
    16.         {"Li Ka-shing", 31.2, "Hong Kong"}
    17.         // ...
    18.     };

  4. 现在让我们定义一个表。这个表由表示国家名的字符串和一个组对构成。组对中会具有上面列表的一个(const)副本。这也就是每个国家最富有的人。组对中另一个变量是一个计数器，其会统计某国的富豪人数。

    1.     map<string, pair<const billionaire, size_t>> m;

  5. 现在，让我们将列表中的数据尝试插入到组对中。每个组对中都包含了对应国家的百万富翁，并将计数器的值置成1。

    1.     for (const auto &b : billionaires) {
    2.         auto [iterator, success] = m.try_emplace(b.country, b, 1);

  6. 如果这一步成功，那就不用再做其他事了。我们使用b和1创建的组对已经插入到表中。如果因为键已存在而插入失败，那么组对就不会构建。当我们百万富翁结构体非常大时，我们需要将运行时拷贝的时间节省下来。不过，在不成功的情况下，我们还是要对计数器进行增加1的操作。

    1.     if (!success) {
    2.         iterator->second.second += 1;
    3.         }
    4.     }

  7. 现在，我们来打印一下每个国家百万富翁的数量，以及各个国家中最富有的人。

    1.     for (const auto & [key, value] : m) {
    2.         const auto &[b, count] = value;
    3.         cout << b.country << " : " << count
    4.                 << " billionaires. Richest is "
    5.              << b.name << " with " << b.dollars
    6.              << " B$\n";
    7.     }
    8. }

  8. 编译并运行程序，就会得到下面的输出(这里的输出是不完整的，因为列表比较长)。

    1. $ ./efficient_insert_or_modify
    2. China : 1 billionaires. Richest is Wang Jianlin with 31.3 B$
    3. France : 2 billionaires. Richest is Bernard Arnault with 41.5 B$
    4. Hong Kong : 1 billionaires. Richest is Li Ka-shing with 31.2 B$
    5. Mexico : 1 billionaires. Richest is Carlos Slim with 54.5 B$
    6. Spain : 1 billionaires. Richest is Amancio Ortega with 71.3 B$
    7. USA : 4 billionaires. Richest is Bill Gates with 86 B$

How it works…

本节围绕着std::map中的try_emplace函数展开，这个函数是C++17添加的。下面是其函数声明之一：

  1. std::pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);

其函数第一个参数k是插入的键，args表示这个键对应的值。如果我们成功的插入了元素，那么函数就会返回一个迭代器，其指向新节点在表中的位置，组对中布尔变量的值被置为true。当插入不成功，组对中的布尔变量值会置为false，并且迭代器指向与新元素冲突的位置。

这个特性在我们的例子中非常有用——可以完美处理第一次访问到，和之后访问到的情况。

Note：

std::map中insert和emplace方法完全相同。try_emplace与它们不同的地方在于，在遇到已经存在的键时，不会去构造组对。当相应对象的类型需要很大开销进行构造时，这对于程序性能是帮助的。

There’s more…

如果我们将表的类型从std::map换成std::unordered_map，程序照样能工作。这样的话，当不同类型的表具有较好的性能特性时，我们就可以快速的进行切换。例子中，唯一可观察到的区别是，亿万富翁表不再按字母顺序打印，因为哈希表和搜索树不同，其不会对对象进行排序。