W3 Notes: STL 2

# W3 Notes: STL 2 [ToC] ## C++ [`set`](https://cplusplus.com/reference/set/set/) Sets are associative containers that store unique elements following a specific order. ### Properties - Sets are collections of **unique values**. - The elements are stored in a specific **sorted order**. - In a set, the value of an element uniquely identifies it and is used for sorting. That is, the **value of an element is itself the *key***. - The value of an element cannot be modified once it is added to the set, though it is possible to remove and then add the modified value of that element. Thus, the **values are immutable**. - The set is typically implemented in the language as a **balanced binary search tree**. - The values in a set are **unindexed**. - Because of the balanced-BST implementation, sets allow efficient querying of elements: **insertion (`set::insert`), deletion (`set::erase`), and lookup (`set::find`/`set::count`)** are all done in **logarithmic time**. ### Some useful member functions <table><thead><tr><th></th><th>Name</th><th>Short description</th></tr></thead><tbody><tr><td rowspan="2"></td><td><a href="https://cplusplus.com/reference/set/set/set/" target="_blank" rel="noopener noreferrer">(constructor)</a></td><td>Construct set</td></tr><tr><td><a href="https://cplusplus.com/reference/set/set/operator=/" target="_blank" rel="noopener noreferrer">operator=</a></td><td>Copy container content</td></tr><tr><td rowspan="4">Iterators</td><td><a href="https://cplusplus.com/reference/set/set/begin/" target="_blank" rel="noopener noreferrer">begin</a></td><td>Return iterator to beginning</td></tr><tr><td><a href="https://cplusplus.com/reference/set/set/end/" target="_blank" rel="noopener noreferrer">end</a></td><td>Return iterator to end</td></tr><tr><td><a href="https://cplusplus.com/reference/set/set/rbegin/" target="_blank" rel="noopener noreferrer">rbegin</a></td><td>Return reverse iterator to reverse beginning</td></tr><tr><td><a href="https://cplusplus.com/reference/set/set/rend/" target="_blank" rel="noopener noreferrer">rend</a></td><td>Return reverse iterator to reverse end</td></tr><tr><td rowspan="2">Capacity</td><td><a href="https://cplusplus.com/reference/set/set/empty/" target="_blank" rel="noopener noreferrer">empty</a></td><td>Test whether container is empty</td></tr><tr><td><a href="https://cplusplus.com/reference/set/set/size/" target="_blank" rel="noopener noreferrer">size</a></td><td>Return container size</td></tr><tr><td rowspan="3">Modifiers</td><td><a href="https://cplusplus.com/reference/set/set/insert/" target="_blank" rel="noopener noreferrer">insert</a></td><td>Insert element</td></tr><tr><td><a href="https://cplusplus.com/reference/set/set/erase/" target="_blank" rel="noopener noreferrer">erase</a></td><td>Erase elements</td></tr><tr><td><a href="https://cplusplus.com/reference/set/set/clear/" target="_blank" rel="noopener noreferrer">clear</a></td><td>Clear content</td></tr><tr><td rowspan="5">Operations</td><td><a href="https://cplusplus.com/reference/set/set/find/" target="_blank" rel="noopener noreferrer">find</a></td><td>Get iterator to element</td></tr><tr><td><a href="https://cplusplus.com/reference/set/set/count/" target="_blank" rel="noopener noreferrer">count</a></td><td>Count elements with a specific value</td></tr><tr><td><a href="https://cplusplus.com/reference/set/set/lower_bound/" target="_blank" rel="noopener noreferrer">lower_bound</a></td><td>Return iterator to lower bound (first element that is equal or greater)</td></tr><tr><td><a href="https://cplusplus.com/reference/set/set/upper_bound/" target="_blank" rel="noopener noreferrer">upper_bound</a></td><td>Return iterator to upper bound (first element that is strictly greater)</td></tr><tr><td><a href="https://cplusplus.com/reference/set/set/equal_range/" target="_blank" rel="noopener noreferrer">equal_range</a></td><td>Get range of equal elements</td></tr></tbody></table> ## C++ [`map`](https://cplusplus.com/reference/map/map/) Maps are associative containers that store elements that are eachformed by a combination of a unique key value and a mapped value, following a specific order of the key values. ### Properties - Maps are collections of ***(key, mapped)* pairs**. - The **key values** are used to **sort and uniquely identify** the elements. - The **mapped values** store **content associated** (or "mapped") to their respective key values. - The value of an element's key cannot be modified once the element is added to the map, though it is possible to remove the element and then add it with the modified key value. Thus, the **key values are immutable**. - After accessing an element using its key, its associated content can be modified. Thus, the **mapped values are mutable**. - The map is typically implemented in the language as a **balanced binary search tree**. - The values in a map are **unindexed**. - Because of the balanced-BST implementation, maps allow efficient querying of elements: **insertion (`map::insert`), deletion (`map::erase`), lookup (`map::find`/`map::count`), and access (`map::operator[]`/`map::at`/`map::find`)** are all done in **logarithmic time**. ### Some useful member functions <table><thead><tr><th></th><th>Name</th><th>Short description</th></tr></thead><tbody><tr><td rowspan="2"></td><td><a href="https://cplusplus.com/reference/map/map/map/" target="_blank" rel="noopener noreferrer">(constructor)</a></td><td>Construct map</td></tr><tr><td><a href="https://cplusplus.com/reference/map/map/operator=/" target="_blank" rel="noopener noreferrer">operator=</a></td><td>Copy container content</td></tr><tr><td rowspan="4">Iterators</td><td><a href="https://cplusplus.com/reference/map/map/begin/" target="_blank" rel="noopener noreferrer">begin</a></td><td>Return iterator to beginning</td></tr><tr><td><a href="https://cplusplus.com/reference/map/mapt/end/" target="_blank" rel="noopener noreferrer">end</a></td><td>Return iterator to end</td></tr><tr><td><a href="https://cplusplus.com/reference/map/map/rbegin/" target="_blank" rel="noopener noreferrer">rbegin</a></td><td>Return reverse iterator to reverse beginning</td></tr><tr><td><a href="https://cplusplus.com/reference/map/map/rend/" target="_blank" rel="noopener noreferrer">rend</a></td><td>Return reverse iterator to reverse end</td></tr><tr><td rowspan="2">Capacity</td><td><a href="https://cplusplus.com/reference/map/map/empty/" target="_blank" rel="noopener noreferrer">empty</a></td><td>Test whether container is empty</td></tr><tr><td><a href="https://cplusplus.com/reference/map/map/size/" target="_blank" rel="noopener noreferrer">size</a></td><td>Return container size</td></tr><tr><td rowspan="2">Element access</td><td><a href="https://cplusplus.com/reference/map/map/operator[]/" target="_blank" rel="noopener noreferrer">operator[]</a></td><td>Access element</td></tr><tr><td><a href="https://cplusplus.com/reference/map/map/at/" target="_blank" rel="noopener noreferrer">at</a></td><td>Access element</td></tr><tr><td rowspan="3">Modifiers</td><td><a href="https://cplusplus.com/reference/map/map/insert/" target="_blank" rel="noopener noreferrer">insert</a></td><td>Insert elements</td></tr><tr><td><a href="https://cplusplus.com/reference/map/map/erase/" target="_blank" rel="noopener noreferrer">erase</a></td><td>Erase elements</td></tr><tr><td><a href="https://cplusplus.com/reference/map/map/clear/" target="_blank" rel="noopener noreferrer">clear</a></td><td>Clear content</td></tr><tr><td rowspan="5">Operations</td><td><a href="https://cplusplus.com/reference/map/map/find/" target="_blank" rel="noopener noreferrer">find</a></td><td>Get iterator to element</td></tr><tr><td><a href="https://cplusplus.com/reference/map/map/count/" target="_blank" rel="noopener noreferrer">count</a></td><td>Count elements with a specific key</td></tr><tr><td><a href="https://cplusplus.com/reference/map/map/lower_bound/" target="_blank" rel="noopener noreferrer">lower_bound</a></td><td>Return iterator to lower bound (first element with equal or greater key)</td></tr><tr><td><a href="https://cplusplus.com/reference/map/map/upper_bound/" target="_blank" rel="noopener noreferrer">upper_bound</a></td><td>Return iterator to upper bound (first element with strictly greater key)</td></tr><tr><td><a href="https://cplusplus.com/reference/map/map/equal_range/" target="_blank" rel="noopener noreferrer">equal_range</a></td><td>Get range of equal-key elements</td></tr></tbody></table> ## C++ [`multiset`](https://cplusplus.com/reference/set/multiset/), [`multimap`](https://cplusplus.com/reference/map/multimap/) ### VS `set`, `map` Multisets and multimaps are **multi-key anaologues of sets and maps** respectively. This means that - multisets are similar to sets, except that multiple elements can have the same values. And, similarly, - multimaps are similar to maps, except that multiple elements can have the same keys. ### Deleting elements from `multiset`, `multimap` Let `a` be a multiset or a multimap. - `a.erase(x)` will remove **all elements** in `a` that have keys equal to `x` (if any exists). - `a.erase(a.find(x))` will remove only the **first element** in `a` whose key equals to `x` (if any exists). ## C++ [`unordered_set`](https://cplusplus.com/reference/unordered_set/unordered_set/), [`unordered_map`](https://cplusplus.com/reference/unordered_map/unordered_map/) ### VS `set`, `map` Unorered sets and maps are **hash-table alternatives of sets and maps** respectively. Remember that sets and maps are implemented as binary search trees, which ensures a specific order in the stored elements and querying in logarithmic time. In constrast, hash-table implementation of unordered sets and maps mean that they allow **constant-time querying on average**, but preserve **no particular order** of the elements. :::warning The time complexity of querying (insertion, deletion, and lookup) in unordered sets and maps is $O(1)$ only in the average case and depends on the how "good" the *hash function* is. In the worst case, it can go up to $O(n)$ where $n$ is the size of the array used internally. ::: ### Ordering and iteration in `unordered_set`, `unordered_map` Since unordered sets and maps do not ensure any particular order of their elements, there is no gurantee of which element will be returned by `unordered_set::begin` and `unordered_map::begin`. Also note that they don't have reverse iterators. Moreover, lack of ordering means that, unlike their BST counterparts (sets, multisets, maps, and multimaps), they don't have the functions `lower_bound` and `upper_bound`.