Regular Containers
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
standard compliance section.
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:
typedef boost::unordered_map<std::string, int> map;
map x;
x["one"] = 1;
x["two"] = 2;
x["three"] = 3;
assert(x.at("one") == 1);
assert(x.find("missing") == x.end());
But since the elements aren’t ordered, the output of:
for(const map::value_type& i: x) {
std::cout<<i.first<<","<<i.second<<"\n";
}
can be in any order. For example, it might be:
two,2
one,1
three,3
There are other differences, which are listed in the Comparison with Associative Containers section.
Iterator Invalidation
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
.
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.
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:
x.reserve(n);
- Note
-
reserve(n)
reserves space for at leastn
elements, allocating enough buckets 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 reference for more details on the
rehash
function.
Comparison with Associative Containers
Associative Containers | Unordered Associative Containers |
---|---|
Parameterized by an ordering relation |
Parameterized by a function object |
Keys can be compared using |
Keys can be hashed using |
Constructors have optional extra parameters for the comparison object. |
Constructors have optional extra parameters for the initial minimum number of buckets, a hash function and an equality object. |
Keys |
Keys |
Member function |
No equivalent. Since the elements aren’t ordered |
|
|
|
|
Iterators, pointers and references to the container’s elements are never invalidated. |
Iterators can be invalidated by calls to insert or rehash. |
Iterators iterate through the container in the order defined by the comparison object. |
Iterators iterate through the container in an arbitrary order, that can change as elements are inserted, although equivalent elements are always adjacent. |
No equivalent |
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.) |
Can be compared using the |
Can be compared using the |
When inserting with a hint, implementations are permitted to ignore the hint. |
Operation | Associative Containers | Unordered Associative Containers |
---|---|---|
Construction of empty container |
constant |
O(n) where n is the minimum number of buckets. |
Construction of container from a range of N elements |
O(N log N), O(N) if the range is sorted with |
Average case O(N), worst case O(N2) |
Insert a single element |
logarithmic |
Average case constant, worst case linear |
Insert a single element with a hint |
Amortized constant if |
Average case constant, worst case linear (ie. the same as a normal insert). |
Inserting a range of N elements |
N log( |
Average case O(N), worst case O(N * |
Erase by key, |
O(log( |
Average case: O( |
Erase a single element by iterator |
Amortized constant |
Average case: O(1), Worst case: O( |
Erase a range of N elements |
O(log( |
Average case: O(N), Worst case: O( |
Clearing the container |
O( |
O( |
Find |
logarithmic |
Average case: O(1), Worst case: O( |
Count |
O(log( |
Average case: O(1), Worst case: O( |
|
logarithmic |
Average case: O( |
|
logarithmic |
n/a |