CODEWITHSUNDEEP
c++g++
user3288177
user3288177

Reputation: 499

What is the time complexity of std::map

What is the time complexity of std::map? And will it degenerate in the worst case? Or it is decide by the implementation, we can't know it?

Upvotes: 25

Views: 88089

Answers (4)

user2485710
user2485710

Reputation: 9801

This depends on the implementation, you can't associate a complexity of any kind to std::map just by looking at the language specs.

Usually an std::map is implemented as a Red-Black Tree and you can find all info about the Big-O properties of this kind of containers here.

Notably there are less popular alternatives to the standard libraries shipped with popular compilers such as msvc or gcc, that implements this kind of containers with B-trees, this leads to lower memory usage due to the fact that a B-tree usually occupy less memory that an RB-tree.

For example click here.

Upvotes: 4

Jerry Coffin
Jerry Coffin

Reputation: 490148

Lookups are proportional to log(N). In a typical case (implementation as a red-black tree) the number of comparisons can be up to twice Log2N.

Insertions are normally proportional to Log2N as well--but there's a special provision made for when you're inserting a number of items that are already in order1. In this case, you can specify a "hint" for where an insertion is going to take place. When that hint is correct, each insertion is (amortized) O(1) instead of O(Log N), so inserting a range of items in sorted order is linear instead of N log(N). The hint you specify is an iterator to the position just after the item to be inserted.

For example, if you have a number of items in a file in sorted order, and you want to insert them into the map, you can specify your_map.end() as the "hint", and building the map will have O(N) complexity instead of O(N Log N) complexity.

1. Technically, this applies anytime you insert items, not just when you're inserting them in order--but by far the most common case where you have a reasonable "hint" available is when you're inserting items in order.

Upvotes: 37

ak_2050
ak_2050

Reputation: 159

if you're asking about the lookup time compexity for std::map then that would be O(log(n)) since the stl implemented the std::map library as a Tree (binary tree) datastructure.

More information here: http://www.cplusplus.com/reference/map/map/

Here is also the commonly used std::unordered_map, which would be your hashmap (no ordering hence) with a O(1) look up speed, however, using more memory than the Tree per the design of the data structure.

Upvotes: 4

Jörg Beyer
Jörg Beyer

Reputation: 3671

Usually the time complexity is specified for operations. In your case the lookup and insert seems relevant.

See http://www.sgi.com/tech/stl/complexity.html for the guaranteed complexties of the STL containers. And this http://www.sgi.com/tech/stl/AssociativeContainer.html on the Associative Containers.

Another source is found here:

the lookup of std::map is log(number of elements in the map).

Upvotes: 4

Related Questions