Unordered Containers

In unordered containers, elements have no defined order. Thus, if you insert three elements, they might have any order when you iterate over all the elements in the container. Their order might also change over time. The only important fact is that a specific element is somewhere in the container.
Unordered containers are typically implemented as a hash table, so, internally, they consist of an array of linked lists. The position of an element in the array is determined using a hash function.
If the hash function is fast and effective, inserting and finding an element is very fast and takes constant amortized time (the fastest among all the containers). This is to contrast with associative container that take $O(\log n)$ time, vector and deque that take $O(n)$ time and lists that take $O(1)$ time to insert and $O(n)$ time to search.
Although a hash table provides amortized constant time operations, this performance might degrade because of hash collisions. The worst case is linear (when all the elements are inserted into one bucket).

Unordered Set

An unordered set is a collection of elements without a definitive order.
We can visualize an unordered set like this:

We can create an unordered set of strings:

unordered_set<string> colors = {"red", "blue", "white"};

Similarly to associative containers, we can use the find method to determine if an element is in a set:

auto it = colors.find("blue");
if (it == colors.end()) {
    cout << "Not found" << endl;
} else {
    cout << *it << " is in the set" << endl;
}

We can also use the insert method to insert new values into an unordered set, either by specifying a value directly or by providing a range via iterators:
```
colors.insert("black");
vector<string> v = {"purple", "gray"};
colors.insert(v.begin(), v.end());
```
Unordered containers also provide some hash table-specific API:
- bucket_count() returns the number of buckets in the hash table. This is analogous to the size() method of vector.
- max_bucket_count() returns the maximum number of buckets in the hash table. This is analogous to the capacity() method of vector.
- bucket_size(b) returns the number of elements in the specified bucket b.
- bucket(k) returns the bucket for the specified key k.
- load_factor() returns the ratio between the number of elements and the number of buckets.

Unordered Multiset

An unordered set is just like a set, but allows storing elements with duplicate values.

Unordered Map

Unordered map is very similar to unordered set, except that each element is a pair of a key and a value. It is also similar to a map, but the order of elements is not defined.
We can visualize an unordered_map as follows:
We can use find, insert and erase methods very similarly to how we can with (unordered) sets and maps.
A map or an unordered map can also be used as an associative array, an array that has an arbitrary index type (not just an integer).
- Searching takes $O(\log n)$ time using a map and $O(1)$ time using an unordered_map (but may degrade to $O(n)$ ).
- A multimap and unordered_multimap cannot be used, since they don’t have the operator [].
- As an example, let’s first declare an unordered_map to map colors to their hex codes:
  unordered_map<string, string> colors = { {"white", "#ffffff"}, {"blue", "#0000ff"} };
- Now we can use square brackets just like accessing a regular array:
  cout << colors["white"] << endl;
  We can also use the at method that provides a range check:
  cout << colors.at("white") << endl;
- With arrays or vector, it is invalid to use indices that are not already in the array.
  vector<char> v = {'a', 'b', 'c'}; // error v[4] = 'e';
  However, when we use an unordered_map as an associative array, using a new index will simply create a new value at that index:
  // insert a new value colors["black"] = "#000000";
  The code above is equivalent to
  colors.insert({"black", "#ffffff"});
- One difference between the insert method and the operator [] is that the insert function cannot be used to modify existing elements:
  // will not change the value colors.insert({"white", "#fff"});
  On the other hand, using the operator [] will modify the exising value:
  colors["white"] = "#fff";
- It is important to note that the operator [] provides write access to the (unordered) map. Therefore, it is invalid to use it with constant objects:
  void darken(const unordered_map<string, string> &c) { // will not compile c["white"] = "#eeeeee"; } // ... darken(colors);
  Even if we only use the operator [] to read the value, it will still not work on constant objects:
  void print(const unordered_map<string, string> &c) { // will not compile cout << c["white"] << endl; } // ... print(colors);
  And so what we instead have to do is something like
  void print(const unordered_map<string, string> &c) { auto it = c.find("white"); if (it != c.end()) { cout << *it << endl; } }

Unordered Multimap

An unordered set is just like a set, but allows storing elements with duplicate keys.

Unordered Containers

Unordered Containers

Unordered Set

Unordered Multiset

Unordered Map

Unordered Multimap

results matching ""

No results matching ""