:idprefix: regular_

Boost.Unordered closed-addressing containers (`boost::unordered_set`, `boost::unordered_map`, `boost::unordered_multiset` and `boost::unordered_multimap`) are fully conformant with the C++ specification for unordered associative containers, so for those who know how to use `std::unordered_set`, `std::unordered_map`, etc., their homonyms in Boost.Unordered are drop-in replacements. The interface of open-addressing containers (`boost::unordered_node_set`, `boost::unordered_node_map`, `boost::unordered_flat_set` and `boost::unordered_flat_map`) is very similar, but they present some minor differences listed in the dedicated xref:compliance.adoc#compliance_open_addressing_containers[standard compliance section].

``` x.reserve(n); ```

so as to not exceed the maximum load factor. + Because the maximum load factor is defined as the number of elements divided by the total number of available buckets, this function is logically equivalent to: + ``` x.rehash(std::ceil(n / x.max_load_factor())) ``` + See the xref:reference/unordered_map.adoc#unordered_map_rehash[reference for more details] on the `rehash` function.

:idprefix: comparison_

Parameterized by a function object `Hash` and an equivalence relation `Pred`

Keys `k1`, `k2` are considered equivalent if `!Compare(k1, k2) && !Compare(k2, k1)`.

Keys `k1`, `k2` are considered equivalent if `Pred(k1, k2)`

`equal_range(k)` returns a range at the end of the container if `k` isn't present in the container. It can't return a positioned range as `k` could be inserted into multiple place. +

xref:regular.adoc#regular_iterator_invalidation[Iterators can be invalidated by calls to insert or rehash]. +

**Node-based containers:** Pointers and references to the container's elements are never invalidated. + **Flat containers:** Pointers and references to the container's elements are invalidated when rehashing occurs.

---

Average case O(_N_), worst case O(_N^2^_)

_N_ log(`size()` + _N_)

O(log(`size()`) + `count(k)`)

O(log(`size()`) + _N_)

O(`size()`)

`equal_range(k)`

`lower_bound`,`upper_bound`

n/a