<p>I would like to know the complexity in Big O notation of the STL multiset, map and hash map classes when:</p>

<ul>
<li>inserting entries</li>
<li>accessing entries</li>
<li>retrieving entries</li>
<li>comparing entries</li>
</ul>

map, set, multimap, and multiset
These are implemented using a
red-black tree
, a type of
balanced binary search tree
.  They have the following asymptotic run times:
Insertion: O(log n)
Lookup: O(log n)
Deletion: O(log n)
hash_map, hash_set, hash_multimap, and hash_multiset
These are implemented using
hash tables
.  They have the following runtimes:
Insertion: O(1) expected, O(n) worst case
Lookup: O(1) expected, O(n) worst case
Deletion: O(1) expected, O(n) worst case
If you use a proper hash function, you'll almost never see the worst case behavior, but it is something to keep in mind — see
Denial of Service via Algorithmic Complexity Attacks
by Crosby and Wallach for an example of that.