multiset, map and hash map complexity

Question

Hallo everybody,

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

• inserting entries
• accessing entries
• retrieving entries
• comparing entries

Answer 1

You can find this information in the SGI STL documentation: http://www.sgi.com/tech/stl/

Basically, both multiset and maps are sorted binary trees, so inserting/finding 1 out of N entries takes O(log N). See Sorted Assoc. Containers in the documentation.

Obviously, the big advantage of Hashmap is O(1) for inserting and finding entries.

Accessing it after found is O(1) for all structures. Comparison, what do you mean by that? Sounds like O(1) to me, after all were found.

Answer 2

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 this paper for an example.

Answer 3

cppreference.com is where I go for my c++ reference questions. They do a pretty good job of outlining the Big O notation for most of the functions you asked about above.

Answer 4

Thanks

everybody for your answers. U all the subject excellent.

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 this paper for an example. However:

@Adam could u or anybody else give some further explanation or tutorial link or other material besides the aforementioned paper concerning: Making the right choice of the hash function (for the hast map) Do I have to implement it on my own or are there more than one provided by stl from which I should choose?

Thanks everybody again in advance

P.S. @ypnos: ksipna :D