關聯性容器

關聯容器是指C++標準模板庫中的一套類模板，實現了有序關聯數組。可用於存放任意數據類型的元素。C++標準中定義的關聯容器有： `set`, `map`, `multiset`, `multimap`。

關聯容器類似於C++中的無序關聯容器。差別為：

- 關聯容器是紅黑樹實現，無序關聯容器是哈希表實現。
- 關聯容器保證按鍵值有序遍歷，因此可以做範圍查找，而無序關聯容器不可以。關聯支持一些導航類的操作，如求出給定鍵最鄰近的鍵，最大鍵、最小鍵操作。
- 關聯容器的迭代器不會失效，除非所指元素被刪除。無序關聯容器的iterator在修改元素時可能會失效。所以對關聯容器的遍歷與修改在一定程度上可並行
- 哈希表查找時候要算hash，這個最壞時間複雜度是O(key的長度)；基於比較的有序關聯容器通常只使用頭幾個字符進行比較

## 成員函數

`set`｜`map`｜`multiset`｜`multimap`｜描述

(constructor)｜ (constructor)｜ (constructor)｜ (constructor)｜構造

(destructor)｜ (destructor)｜ (destructor)｜ (destructor)｜析構

`[http://en.cppreference.com/w/cpp/container/set/operator= operator=]`｜`[http://en.cppreference.com/w/cpp/container/map/operator= operator=]`｜`[http://en.cppreference.com/w/cpp/container/multiset/operator= operator=]`｜`[http://en.cppreference.com/w/cpp/container/multimap/operator= operator=]`｜容器賦值

`[http://en.cppreference.com/w/cpp/container/set/get_allocator get_allocator]`｜`[http://en.cppreference.com/w/cpp/container/map/get_allocator get_allocator]`｜`[http://en.cppreference.com/w/cpp/container/multiset/get_allocator get_allocator]`｜`[http://en.cppreference.com/w/cpp/container/multimap/get_allocator get_allocator]`｜返回分配器，用於給容器的成員分配空間

Element access｜不適用｜`[http://en.cppreference.com/w/cpp/container/map/at at]`｜不適用｜不適用｜訪問特定元素，帶邊界檢查

不適用｜ operator`[]`｜不適用｜不適用｜訪問特定元素，不帶邊界檢查

Iterators｜`[http://en.cppreference.com/w/cpp/container/set/begin begin]`｜`[http://en.cppreference.com/w/cpp/container/map/begin begin]`｜`[http://en.cppreference.com/w/cpp/container/multiset/begin begin]`｜`[http://en.cppreference.com/w/cpp/container/multimap/begin begin]`｜返回容器開始處的迭代器

`[http://en.cppreference.com/w/cpp/container/set/end end]`｜`[http://en.cppreference.com/w/cpp/container/map/end end]`｜`[http://en.cppreference.com/w/cpp/container/multiset/end end]`｜`[http://en.cppreference.com/w/cpp/container/multimap/end end]`｜返回容器結束處的迭代器

`[http://en.cppreference.com/w/cpp/container/set/rbegin rbegin]`｜`[http://en.cppreference.com/w/cpp/container/map/rbegin rbegin]`｜`[http://en.cppreference.com/w/cpp/container/multiset/rbegin rbegin]`｜`[http://en.cppreference.com/w/cpp/container/multimap/rbegin rbegin]`｜返回容器逆向開始處的逆向迭代器

`[http://en.cppreference.com/w/cpp/container/set/rend rend]`｜`[http://en.cppreference.com/w/cpp/container/map/rend rend]`｜`[http://en.cppreference.com/w/cpp/container/multiset/rend rend]`｜`[http://en.cppreference.com/w/cpp/container/multimap/rend rend]`｜返回容器逆向結束處的逆向迭代器

Capacity｜`[http://en.cppreference.com/w/cpp/container/set/empty empty]`｜`[http://en.cppreference.com/w/cpp/container/map/empty empty]`｜`[http://en.cppreference.com/w/cpp/container/multiset/empty empty]`｜`[http://en.cppreference.com/w/cpp/container/multimap/empty empty]`｜檢查容器是否為空

`[http://en.cppreference.com/w/cpp/container/set/size size]`｜`[http://en.cppreference.com/w/cpp/container/map/size size]`｜`[http://en.cppreference.com/w/cpp/container/multiset/size size]`｜`[http://en.cppreference.com/w/cpp/container/multimap/size size]`｜返回容器內元素數量

`[http://en.cppreference.com/w/cpp/container/set/max_size max_size]`｜`[http://en.cppreference.com/w/cpp/container/map/max_size max_size]`｜`[http://en.cppreference.com/w/cpp/container/multiset/max_size max_size]`｜`[http://en.cppreference.com/w/cpp/container/multimap/max_size max_size]`｜返回容器內元素最大可能處理

Modifiers｜`[http://en.cppreference.com/w/cpp/container/set/clear clear]`｜`[http://en.cppreference.com/w/cpp/container/map/clear clear]`｜`[http://en.cppreference.com/w/cpp/container/multiset/clear clear]`｜`[http://en.cppreference.com/w/cpp/container/multimap/clear clear]`｜清空容器內容

`[http://en.cppreference.com/w/cpp/container/set/insert insert]`｜`[http://en.cppreference.com/w/cpp/container/map/insert insert]`｜`[http://en.cppreference.com/w/cpp/container/multiset/insert insert]`｜`[http://en.cppreference.com/w/cpp/container/multimap/insert insert]`｜插入元素

`[http://en.cppreference.com/w/cpp/container/set/emplace emplace]`｜`[http://en.cppreference.com/w/cpp/container/map/emplace emplace]`｜`[http://en.cppreference.com/w/cpp/container/multiset/emplace emplace]`｜`[http://en.cppreference.com/w/cpp/container/multimap/emplace emplace]`｜原地構造元素 (C++11)

`[http://en.cppreference.com/w/cpp/container/set/emplace_hint emplace_hint]`｜`[http://en.cppreference.com/w/cpp/container/map/emplace_hint emplace_hint]`｜`[http://en.cppreference.com/w/cpp/container/multiset/emplace_hint emplace_hint]`｜`[http://en.cppreference.com/w/cpp/container/multimap/emplace_hint emplace_hint]`｜使用hint 原地構造元素(C++11)

`[http://en.cppreference.com/w/cpp/container/set/erase erase]`｜`[http://en.cppreference.com/w/cpp/container/map/erase erase]`｜`[http://en.cppreference.com/w/cpp/container/multiset/erase erase]`｜`[http://en.cppreference.com/w/cpp/container/multimap/erase erase]`｜擦除元素

`[http://en.cppreference.com/w/cpp/container/set/swap swap]`｜`[http://en.cppreference.com/w/cpp/container/map/swap swap]`｜`[http://en.cppreference.com/w/cpp/container/multiset/swap swap]`｜`[http://en.cppreference.com/w/cpp/container/multimap/swap swap]`｜與另一個容器交換內容

Lookup｜`[http://en.cppreference.com/w/cpp/container/set/count count]`｜`[http://en.cppreference.com/w/cpp/container/map/count count]`｜`[http://en.cppreference.com/w/cpp/container/multiset/count count]`｜`[http://en.cppreference.com/w/cpp/container/multimap/count count]`｜返回匹配特點鍵值的元素數量

`[http://en.cppreference.com/w/cpp/container/set/find find]`｜`[http://en.cppreference.com/w/cpp/container/map/find find]`｜`[http://en.cppreference.com/w/cpp/container/multiset/find find]`｜`[http://en.cppreference.com/w/cpp/container/multimap/find find]`｜搜到特定鍵值的元素

`[http://en.cppreference.com/w/cpp/container/set/equal_range equal_range]`｜`[http://en.cppreference.com/w/cpp/container/map/equal_range equal_range]`｜`[http://en.cppreference.com/w/cpp/container/multiset/equal_range equal_range]`｜`[http://en.cppreference.com/w/cpp/container/multimap/equal_range equal_range]`｜返回匹配特定鍵值的所有元素

`[http://en.cppreference.com/w/cpp/container/set/lower_bound lower_bound]`｜`[http://en.cppreference.com/w/cpp/container/map/lower_bound lower_bound]`｜`[http://en.cppreference.com/w/cpp/container/multiset/lower_bound lower_bound]`｜`[http://en.cppreference.com/w/cpp/container/multimap/lower_bound lower_bound]`｜返回鍵值不小於特定值的第一個元素的迭代器

`[http://en.cppreference.com/w/cpp/container/set/upper_bound upper_bound]`｜`[http://en.cppreference.com/w/cpp/container/map/upper_bound upper_bound]`｜`[http://en.cppreference.com/w/cpp/container/multiset/upper_bound upper_bound]`｜`[http://en.cppreference.com/w/cpp/container/multimap/upper_bound upper_bound]`｜返回鍵值大於特定值的第一個元素的迭代器

Observers｜`[http://en.cppreference.com/w/cpp/container/set/key_comp key_comp]`｜`[http://en.cppreference.com/w/cpp/container/map/key_comp key_comp]`｜`[http://en.cppreference.com/w/cpp/container/multiset/key_comp key_comp]`｜`[http://en.cppreference.com/w/cpp/container/multimap/key_comp key_comp]`｜返回鍵值比較函數

`[http://en.cppreference.com/w/cpp/container/set/value_comp value_comp]`｜`[http://en.cppreference.com/w/cpp/container/map/value_comp value_comp]`｜`[http://en.cppreference.com/w/cpp/container/multiset/value_comp value_comp]`｜`[http://en.cppreference.com/w/cpp/container/multimap/value_comp value_comp]`｜返回值比較函數。在`set`與`multiset`，該函數equivalent to `key_comp`, 因為元素只有值.

## 用法

下述例子展示如何用`map<string, int>`計數word的次數。用word為鍵值，次數為值。

```cpp
#include <iostream>
#include <string>
#include <map>

int main()
{
    std::map<std::string, int> wordcounts;
    std::string s;

    while (std::cin >> s && s != "end")
        ++wordcounts[s];

    while (std::cin >> s && s != "end")
        std::cout << s << ' ' << wordcounts[s] << '\n';
}
```

執行時，使用者線輸入一系列word，最後以"end"結束輸入。然後輸入word可查詢它出現的次數。

下例展示用insert函數、find函數：

```cpp
#include <iostream>
#include <map>
#include <utility> // make_pair

int main()
{
    typedef std::map<char, int> MapType;
    MapType my_map;

    // insert elements using insert function
    my_map.insert(std::pair<char, int>('a', 1));
    my_map.insert(std::pair<char, int>('b', 2));
    my_map.insert(std::pair<char, int>('c', 3));
    my_map.insert(MapType::value_type('d', 4)); // all standard containers provide this typedef
    my_map.insert(std::make_pair('e', 5));      // can also use the utility function make_pair
    my_map.insert({'f', 6});                    // using C++11 initializer list
    
    //map keys are sorted automatically from lower to higher. 
    //So, my_map.begin() points to the lowest key value not the key which was inserted first.
    MapType::iterator iter = my_map.begin();

    // erase the first element using the erase function
    my_map.erase(iter);

    // output the size of the map
    std::cout << "Size of my_map: " << my_map.size() << '\n';

    std::cout << "Enter a key to search for: ";
    char c;
    std::cin >> c;

    // find will return an iterator to the matching element if it is found
    // or to the end of the map if the key is not found
    iter = my_map.find(c);
    if (iter != my_map.end() ) 
        std::cout << "Value is: " << iter->second << '\n';
    else
        std::cout << "Key is not in my_map" << '\n';

    // clear the entries in the map
    my_map.clear();
}
```

### 迭代器

```cpp
map<Key,T>::iterator it; // declares a map iterator
it->first;               // the key value 
it->second;              // the mapped value
(*it);                   // the "element value", which is of type:  pair<const Key,T>
```

```cpp
#include <iostream>
#include <string>
#include <map>

int main()
{
    std::map <std::string, int> data{
     { "Bobs score", 10 },
     { "Martys score", 15 },
     { "Mehmets score", 34 },
     { "Rockys score", 22 },
     { "Rockys score", 23 } /*overwrites the 22 as keys are identical */
    };
    
    // Iterate over the map and print out all key/value pairs.
    for (const auto& element : data)
    {
        std::cout << "Who(key = first): " << element.first;
        std::cout << " Score(value = second): " << element.second << '\n';
    }

    return 0;
}
```