# Associative Containers

There are two kinds of associative containers in STL: unordered associative containers and ordered associative containers.

### Unordered Associative Containers

Unordered associative containers implement unsorted data structures that can be quickly searched. Their underlying data structure are hash tables, which support _O(1)_ element access.

#### _unordered\_set_, _unordered\_multiset_

```cpp
#include <unordered_set>
```

Sets are collections of keys, in which _unordered\_set_ stores unique keys, while keys in _unordered\_multiset_ can be repeated.

**Adding:**

`us.insert(key);` Insert elements into the container. Time complexity is _O(1)_.

**Inquiry：**

`unordered_set::iterator` Iterator of the container.

`us.find(key);` Find element with specific key, and return its iterator. If no key is found, return the _end()_ iterator. Time complexity is _O(1)_.

**Deleting:**

`us.erase(key);` Delete elements from the container with the key. Time complexity is _O(1)_.

`us.erase(it);` Delete elements from the container with the iterator. Time complexity is _O(1)_.

#### _unordered\_map_, _unordered\_multimap_

```cpp
#include <unordered_map>
```

Maps are collections of key-value pairs. Keys are unique in _unordered\_map_, while keys in _unordered\_multimap_ can be repeated.

A _pair_ object has two members, _first_ and _second_. In map containers, _first_ refers to the key, and _second_ refers to the value. We can use _make\_pair()_ to pack key and value into a _pair_ object.

**Adding:**

`um.insert(makepair(key, value));` Insert pairs into the container. Time complexity is _O(1)_. We can also use `um.insert({key, value});`.

**Inquiry：**

`unordered_set::iterator` Iterator of the container.

`um.find(key);` Find pair with specific key, and return its iterator. If no key is found, return the _end()_ iterator. Time complexity is _O(1)_.

`operator[key]` We can also use operator `[]` to get the value from a key. What needs to be paid attention to is that, if the key doesn't exist, a new pair _{key, value()}_ will be inserted into the container, where the default constructor is called for the value.

**Deleting:**

`us.erase(key);` Delete pairs from the container with the key. Time complexity is _O(1)_.

`us.erase(it);` Delete pairs from the container with the iterator. Time complexity is _O(1)_.

_unordered\_set_ and _unordered\_map_ is widely used in checking or eliminating duplicates of massive data because of their excellent performance in accessing elements. In the following example, we use an _unordered\_map_ to count how many times each number is repeated in 100,000 numbers.

```cpp
int main() {
    const int ARR_LEN = 100000;
    int arr[ARR_LEN] = {0};
    for (int i = 0; i < ARR_LEN; ++i) {
        arr[i] = rand() % 10000 + 1;
    }
    unordered_map<int, int> dict;
    for (int k : arr) {
        map[k]++;
    }
    for (auto it = dict.begin(); it != dict.end(); ++it) {
        cout << "key: " << it->first << " count: " << it->second << endl;
    }
}
```

Since keys in an _unordered\_map_ is unique, we use the map to store unique numbers. If we encounter a new number, `map[k]++` will insert a new key-value pair and increment the count by 1.

### Ordered Associative Containers

```cpp
#include <set>
#include <map>
```

Associative containers implement sorted data structures. Similar to unordered associative containers, there are also four types of ordered associative containers: _set_, _multiset_, _map_ and _multimap_. The difference is that their underlying data structure is a Red-Black Tree, and elements in the container are ordered. Instead of _O(1)_ in unordered associative containers, now all the operations have the time complexity of _O(log(n))_.

```cpp
int main() {
    set<int> s;
    for (int i = 0; i < 20; ++i) {
        s.insert(rand()%20 + 1);
    }
    for (int v : s) {
        cout << v << " ";   // 1 2 3 4 7 8 10 11 13 14 16 17 18 20 
    }
    return 0;
}
```

Since Red-Black Tree needs the elements to be comparable to remain sorted, we need to implement the overloaded function for operator `<` if we want to store custom class objects in the containers. What's more, _map_ or _multimap_ requires the existence of default constructor, because it needs to be called in operator `[]` to insert a new pair.
