插入元素

Created: November-22, 2018

只有当元素的键尚未出现在地图中时，才能将元素插入到 std::map 中。举个例子：

std::map< std::string, size_t > fruits_count;

通过 insert() 成员函数将键值对插入到 std::map 中。它需要一个 pair 作为参数：
```
fruits_count.insert({"grapes", 20});
fruits_count.insert(make_pair("orange", 30));
fruits_count.insert(pair<std::string, size_t>("banana", 40));
fruits_count.insert(map<std::string, size_t>::value_type("cherry", 50));
```
insert() 函数返回一个由迭代器和 bool 值组成的 pair：
- 如果插入成功，则迭代器指向新插入的元素，bool 值为 true。
- 如果已经存在具有相同 key 的元素，则插入失败。当发生这种情况时，迭代器指向导致冲突的元素，而 bool 的值是 false。
以下方法可用于组合插入和搜索操作：
```
auto success = fruits_count.insert({"grapes", 20});
if (!success.second) {           // we already have 'grapes' in the map
    success.first->second += 20; // access the iterator to update the value
}
```
为方便起见，std::map 容器提供了下标操作符来访问映射中的元素，如果它们不存在则插入新元素：
```
fruits_count["apple"] = 10;
```
虽然更简单，但它可以防止用户检查元素是否已经存在。如果缺少一个元素，std::map::operator[] 会隐式创建它，使用默认构造函数初始化它，然后用提供的值覆盖它。
insert() 可用于使用支撑的对列表一次添加多个元素。此版本的 insert() 返回 void：
```
fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}}); 
```

insert() 也可以用于通过使用表示 value_type 值的开始和结束的迭代器来添加元素：

std::map< std::string, size_t > fruit_list{ {"lemon", 0}, {"olive", 0}, {"plum", 0}};
fruits_count.insert(fruit_list.begin(), fruit_list.end());

例：

std::map<std::string, size_t> fruits_count;
std::string fruit;
while(std::cin >> fruit){
    // insert an element with 'fruit' as key and '1' as value
    // (if the key is already stored in fruits_count, insert does nothing)
    auto ret = fruits_count.insert({fruit, 1});
    if(!ret.second){            // 'fruit' is already in the map 
        ++ret.first->second;    // increment the counter
    }
}

插入操作的时间复杂度为 O（log n），因为 std::map 实现为树。

Version >= C++ 11

可以使用 make_pair() 和 emplace() 明确构建 pair：

std::map< std::string , int > runs;
runs.emplace("Babe Ruth", 714);
runs.insert(make_pair("Barry Bonds", 762));

如果我们知道将插入新元素的位置，那么我们可以使用 emplace_hint() 来指定迭代器 hint。如果可以在 hint 之前插入新元素，则可以在恒定时间内完成插入。否则它的行为方式与 emplace() 相同：

std::map< std::string , int > runs;
auto it = runs.emplace("Barry Bonds", 762); // get iterator to the inserted element
// the next element will be before "Barry Bonds", so it is inserted before 'it'
runs.emplace_hint(it, "Babe Ruth", 714);