Map vs unordered_map in C++: Key Differences and Usage

In C++, map stores key-value pairs in sorted order using a balanced tree, while unordered_map stores them in no particular order using a hash table. map offers ordered traversal but slower lookups (O(log n)), whereas unordered_map provides faster average lookups (O(1)) but no order guarantee.

Quick Comparison

Here is a quick side-by-side comparison of map and unordered_map in C++.

Factor	map	unordered_map
Underlying Data Structure	Balanced binary search tree (usually Red-Black Tree)	Hash table
Order of Elements	Sorted by keys	No specific order
Average Lookup Time Complexity	O(log n)	O(1)
Worst-case Lookup Time Complexity	O(log n)	O(n)
Memory Usage	Generally less memory overhead	More memory overhead due to hashing
Use Case	When order matters or range queries needed	When fast access is priority and order doesn't matter

Key Differences

The map container stores elements in a sorted order based on the keys. It uses a balanced binary search tree internally, which keeps keys ordered and allows in-order traversal. This makes map ideal when you need to process elements in sorted order or perform range queries.

On the other hand, unordered_map uses a hash table to store elements. This means keys are not stored in any particular order, but lookup, insertion, and deletion operations are on average faster (constant time). However, in rare worst cases, these operations can degrade to linear time.

Memory usage also differs: unordered_map typically uses more memory because it stores hash buckets and handles collisions, while map uses less memory but has slower access times. Choosing between them depends on whether you need sorted data or faster access.

Code Comparison

Here is how you insert and print key-value pairs using map in C++.

cpp

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    myMap[3] = "Three";
    myMap[1] = "One";
    myMap[2] = "Two";

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

Output

1: One
2: Two
3: Three

unordered_map Equivalent

Here is the equivalent code using unordered_map. Notice the output order is not sorted.

cpp

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myUnorderedMap;
    myUnorderedMap[3] = "Three";
    myUnorderedMap[1] = "One";
    myUnorderedMap[2] = "Two";

    for (const auto& pair : myUnorderedMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

Output

3: Three
1: One
2: Two

When to Use Which

Choose map when you need your data sorted by keys or require ordered traversal and range queries. It is also better if you want predictable performance with guaranteed O(log n) operations.

Choose unordered_map when you want the fastest possible average lookup, insertion, and deletion times and do not care about the order of elements. It is ideal for quick key-based access where order is irrelevant.

Key Takeaways

Use map for sorted keys and ordered traversal with O(log n) access time.

Use unordered_map for faster average O(1) access without order guarantees.

map uses a balanced tree; unordered_map uses a hash table.

Memory overhead is generally higher for unordered_map due to hashing.

Pick based on whether order or speed is more important for your use case.