插入元素

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);