en	﻿[#regular] = Regular Containers

en	:idprefix: regular_

en	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].

en	For readers without previous experience with hash containers but familiar with normal associative containers (`std::set`, `std::map`, `std::multiset` and `std::multimap`), Boost.Unordered containers are used in a similar manner:

en	But since the elements aren't ordered, the output of:

en	can be in any order. For example, it might be:

en	There are other differences, which are listed in the xref:regular.adoc#comparison[Comparison with Associative Containers] section.

en	Iterator Invalidation

en	It is not specified how member functions other than `rehash` and `reserve` affect the bucket count, although `insert` can only invalidate iterators when the insertion causes the container's load to be greater than the maximum allowed. For most implementations this means that `insert` will only change the number of buckets when this happens. Iterators can be invalidated by calls to `insert`, `rehash` and `reserve`.

en	As for pointers and references, they are never invalidated for node-based containers (`boost::unordered_[multi]set`, `boost::unordered_[multi]map`, `boost::unordered_node_set`, `boost::unordered_node_map`), but they will be when rehashing occurs for `boost::unordered_flat_set` and `boost::unordered_flat_map`: this is because these containers store elements directly into their holding buckets, so when allocating a new bucket array the elements must be transferred by means of move construction.

en	In a similar manner to using `reserve` for ``vector``s, it can be a good idea to call `reserve` before inserting a large number of elements. This will get the expensive rehashing out of the way and let you store iterators, safe in the knowledge that they won't be invalidated. If you are inserting `n` elements into container `x`, you could first call:

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

en	`reserve(n)` reserves space for at least `n` elements, allocating enough buckets

en	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.

en	:idprefix: comparison_

en	Comparison with Associative Containers

en	Associative Containers

en	Unordered Associative Containers

en	Parameterized by an ordering relation `Compare`

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

en	Keys can be compared using `key_compare` which is accessed by member function `key_comp()`, values can be compared using `value_compare` which is accessed by member function `value_comp()`.

en	Keys can be hashed using `hasher` which is accessed by member function `hash_function()`, and checked for equality using `key_equal` which is accessed by member function `key_eq()`. There is no function object for compared or hashing values.

en	Constructors have optional extra parameters for the comparison object.

en	Constructors have optional extra parameters for the initial minimum number of buckets, a hash function and an equality object.

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

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

en	Member function `lower_bound(k)` and `upper_bound(k)`

en	No equivalent. Since the elements aren't ordered `lower_bound` and `upper_bound` would be meaningless.

en	`equal_range(k)` returns an empty range at the position that `k` would be inserted if `k` isn't present in the container.

en	`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. +

en	**Closed-addressing containers:** To find out the bucket that `k` would be inserted into use `bucket(k)`. But remember that an insert can cause the container to rehash - meaning that the element can be inserted into a different bucket.

en	`iterator`, `const_iterator` are of the bidirectional category.

en	`iterator`, `const_iterator` are of at least the forward category.

en	Iterators, pointers and references to the container's elements are never invalidated.

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

en	**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.

en	Iterators iterate through the container in the order defined by the comparison object.

en	Iterators iterate through the container in an arbitrary order, that can change as elements are inserted, although equivalent elements are always adjacent.

en	No equivalent

en	**Closed-addressing containers:** Local iterators can be used to iterate through individual buckets. (The order of local iterators and iterators aren't required to have any correspondence.)

en	Can be compared using the `==`, `!=`, `<`, `\<=`, `>`, `>=` operators.

en	Can be compared using the `==` and `!=` operators.

en	When inserting with a hint, implementations are permitted to ignore the hint.

en	---

en	Operation

en	Associative Containers

en	Unordered Associative Containers

en	Construction of empty container

en	constant

en	O(_n_) where _n_ is the minimum number of buckets.

en	Construction of container from a range of _N_ elements

en	O(_N log N_), O(_N_) if the range is sorted with `value_comp()`

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

en	Insert a single element

en	logarithmic

en	Average case constant, worst case linear

en	Insert a single element with a hint

en	Amortized constant if `t` elements inserted right after hint, logarithmic otherwise

en	Average case constant, worst case linear (ie. the same as a normal insert).

en	Inserting a range of _N_ elements

en	_N_ log(`size()` + _N_)

en	Average case O(_N_), worst case O(_N_ * `size()`)

en	Erase by key, `k`

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

en	Average case: O(`count(k)`), Worst case: O(`size()`)

en	Erase a single element by iterator

en	Amortized constant

en	Average case: O(1), Worst case: O(`size()`)

en	Erase a range of _N_ elements

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

en	Average case: O(_N_), Worst case: O(`size()`)

en	Clearing the container

en	O(`size()`)

en	Find

en	Count

en	`equal_range(k)`

en	`lower_bound`,`upper_bound`

en	n/a