0%

Cpp Standard Library Review

cpp standard library review:

Map vs Unordered Map

Similar:

both map and unordered map are mapping an object with a key. The key is unique. Take this as the idea of hash table.

Diff:

From their name, we can tell that objects in unordered map is allocated without order. On the contravase, object in the map has order.

The core diffferent in this property is in their implementation. Map is implemented by binary search tree but unordered map is implemented by bucket list. Therefore, insert, delete and find operations are slightly different.

Unordered map:

Internal use a hash function to allocate object into bucket. So we will hit into hash collision situation in the worst case.

In Average case: Find O(1), Insert O(1), Delete O(1)

In Worst case: Find O(n), Insert O(n), Delete O(n)

However, there is possible trigger rehash in container. Rehash is when object new bucket number is larger than current bucket count. Container decide to “resize” the bucket for more efficient hashing. In this case, bucket size may change, and ALL objects will relocate. This can takes time.

In case of rehash,
Average case: linear in container size.
Worst case: quadratic in container size. ??? why

Map:

Internal map is a binary search tree structure. So we can use key as sorting comparisor to manage object. So everything is exactly a BST.

Find O(logn), Insert O(log n), Delete O(log n)

Set and Unordered Set are exactly case.