# [Algorithms]Time Complexity of Vector, Set and Map

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`