Back to all concepts
Intermediate 12 min

Unordered Containers

Master hash-based unordered_set and unordered_map for O(1) average-case performance when order doesn't matter

Discover unordered containers that trade sorted order for blazing-fast O(1) average-case performance using hash tables.

A Simple Example 

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <string>

int main() {
    // unordered_set - unique elements, NO sorting
    std::unordered_set<int> numbers{5, 2, 8, 2, 1, 9};

    std::cout << "Unordered set (no guaranteed order): ";
    for (int num : numbers) {
        std::cout << num << " ";  // Order is unpredictable!
    }
    std::cout << "\n";

    // Fast O(1) average lookup
    if (numbers.find(8) != numbers.end()) {
        std::cout << "Found 8 in O(1) average time!" << "\n";
    }

    // unordered_map - key-value pairs, NO sorting
    std::unordered_map<std::string, int> scores{
        {"Alice", 95},
        {"Bob", 87},
        {"Charlie", 92}
    };

    // O(1) average access
    std::cout << "Alice's score: " << scores["Alice"] << "\n";

    // Insertion is O(1) average
    scores["Diana"] = 88;

    std::cout << "\nAll scores (no guaranteed order):" << "\n";
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << "\n";
    }

    return 0;
}

Breaking It Down

Hash Tables - The Secret Behind Speed

  • What it is: Array-based structure where hash function maps keys to indices
  • O(1) average-case insertion, deletion, and lookup
  • No ordering - elements arranged by hash value, not natural order
  • Use when: Speed matters more than order

unordered_set vs set

  • unordered_set: O(1) average operations, no order guarantee
  • set: O(log n) operations, sorted order maintained
  • unordered_set uses more memory for hash table
  • Remember: Choose based on whether you need speed or order

unordered_map vs map

  • unordered_map: O(1) average for find/insert, no key ordering
  • map: O(log n) for operations, keys always sorted
  • unordered_map is faster for large datasets when order doesn't matter
  • Remember: Can't use lower_bound/upper_bound on unordered_map

Hash Collisions and Worst Case

  • What it is: When different keys hash to same index
  • Worst case: O(n) when all keys collide (rare with good hash function)
  • Good hash functions distribute keys evenly
  • Remember: Average case O(1) is what matters in practice

Why This Matters

  • Unordered containers trade sorted order for speed.
  • When you need fast lookups and don't care about order, unordered_map and unordered_set provide O(1) average performance instead of O(log n).
  • This can be the difference between a responsive application and one that feels sluggish with large datasets.

Critical Insight

Hash tables are like a library where books are placed based on the first letter of their title - you can find any book instantly by going to the right section (O(1)), but you can't efficiently browse all books in alphabetical order.

Ordered containers (set/map) are like a sorted shelf - finding takes longer (O(log n)) but you can browse in order.

Choose based on what you need: speed or order!

Best Practices

Default to unordered containers for lookups: When you only need fast find/insert/delete and don't need order, use unordered versions.

Use ordered containers when order matters: If you need sorted iteration or range queries, use set/map.

Reserve capacity for known sizes: Call reserve() if you know the size upfront to avoid rehashing.

Understand hash requirements: Custom types need a hash function to be used in unordered containers.

Common Mistakes

Expecting order: Unordered containers don't maintain any order. Iteration order is unpredictable and can change.

Using with non-hashable types: Custom types need a hash function and equality operator to work with unordered containers.

Iterator invalidation: Rehashing (when load factor exceeds threshold) invalidates all iterators.

Debug Challenge

This code needs the fastest possible lookups and doesn't care about order. Click the highlighted line to optimize:

1 #include <iostream>
2 #include <set>
3
4 int main() {
5 std::set<int> cache{1, 2, 3};
6 // Need fastest lookups, order doesn't matter
7 return 0;
8 }

Quick Quiz

  1. What's the average time complexity of unordered_map::find()?
O(1)
O(log n)
O(n)
  1. When should you use map instead of unordered_map?
When you need elements sorted by key or range operations
When you need O(1) lookup
When you want to save memory

Practice Playground

Time to try out what you just learned! Play with the example code below, experiment by making changes and running the code to deepen your understanding.

Lesson Progress

  • Fix This Code
  • Quick Quiz
  • Practice Playground - run once