C++ "std::map" vs "std::unordered_map"

Background

As I learning C++ in order to write native modules for JavaScript and Python, I need to find a replacement of the object datatype in JavaScript or the dict datatype in Python. Luckily, after doing some research, I found that C++ std library has already provided two containers that contains key-value pairs with unique keys, i.e. std::map and std::unordered_map. However, these two has significant difference in the underlaying implementation.

Difference

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare.
std::unordered_map is an associative container that contains key-value pairs with unique keys. Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key.

Comparison on time complexity and structure

	`std::map`	`std::unordered_map`
Search	$O(\log n)$	$O(1)$
Removal	$O(\log n)$	$O(1)$
Insertion	$O(\log n)$	$O(1)$
Insertion	$O(\log n)$	$O(1)$
Structure	Red-Black Tree	Hash Bucket

Tongze Wang

C++ "std::map" vs "std::unordered_map"

Background

Difference

References