...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Table 29.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 29.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(N^{2}) 
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 