...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Table 24.4. Interface differences.
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. Pointers and references to the container's elements are never invalidated. |
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 |
Local iterators can be used to iterate through individual buckets. (I don't think that the order of local iterators and iterators are required to have any correspondence.) |
Can be compared using the |
No comparison operators are defined in the standard, although implementations
might extend the containers to support |
|
When inserting with a hint, implementations are permitted to ignore the hint. |
|
The containers' hash or predicate function can throw exceptions from
|
Table 24.5. Complexity Guarantees
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 t elements inserted right after hint, logarithmic otherwise |
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 |