keywords: C++, Time Complexity, Vector, Set and Map

Time complexity of find() in std::map

std::map and std::set are implemented by compiler vendors using highly balanced binary search trees (e.g. red-black tree, AVL tree).

As correctly pointed out by David, find would take O(log n) time, where n is the number of elements in the container.

But that’s with primitive data types like int, long, char, double etc., not with strings.

If std:string, lets say of size ’m’, is used as key, traversing the height of the balanced binary search tree will require log n comparisons of the given key with an entry of the tree.

When std::string is the key of the std::map or std::set, find and insert operations will cost O(m log n), where m is the length of given string that needs to be found.

Quoted From:
Time complexity of find() in std::map?
https://stackoverflow.com/questions/9961742/time-complexity-of-find-in-stdmap

Time complexity of find() in std::vector, std::map and std::unordered_map

The time complexity to find an element in `std::vector` by linear search is O(N). It is O(log N) for `std::map` and O(1) for `std::unordered_map`. However, the complexity notation ignores constant factors. Different containers have various traversal overheads to find an element. For example, node branching during tree traversals in std::set and hashing complexity in std::unordered_set are considered constant overheads in complexity. On the other hand, although the complexity of std::vector is linear, the memory addresses of elements in std::vector are contiguous, which means it is faster to access elements in order.

Quoted From:
Searching: vector, set and unordered_set
https://medium.com/@gx578007/searching-vector-set-and-unordered-set-6649d1aa7752

Reference

Searching: vector, set and unordered_set
https://medium.com/@gx578007/searching-vector-set-and-unordered-set-6649d1aa7752

Time complexity
https://en.wikipedia.org/wiki/Time_complexity

File:Comparison computational complexity.svg
https://en.wikipedia.org/wiki/File:Comparison_computational_complexity.svg

Perhaps this is what the stories meant when they called somebody heartsick. Your heart and your stomach and your whole insides felt empty and hollow and aching. ― Gabriel García Márquez