Step 4 of 6

unordered_map

std::unordered_map has the same interface as std::map ([], find, contains, insert, erase), but it's built on a hash table instead of a tree. The trade:

When you don't care about order, unordered_map is usually faster. The classic use is remembering what you've seen so you don't have to search again.

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

// Index of the first repeated word, or -1.
int first_repeat(const std::vector<std::string>& words) {
    std::unordered_map<std::string, int> first_seen;   // word -> index where it appeared
    for (int i = 0; i < (int)words.size(); i++) {
        auto it = first_seen.find(words[i]);
        if (it != first_seen.end()) {
            std::cout << "'" << words[i] << "' first seen at " << it->second << "\n";
            return i;
        }
        first_seen[words[i]] = i;
    }
    return -1;
}

int main() {
    std::cout << first_repeat({"red", "green", "blue", "green", "red"}) << "\n";
    std::cout << first_repeat({"a", "b", "c"}) << "\n";
}

'green' first seen at 1
3
-1

Why this is fast

The naive way to find a repeat compares every pair of words: about n * n / 2 comparisons. With a hash map, each word is checked and stored once, so the whole scan is O(n). Trading a little memory for a lot of speed is one of the most important ideas in algorithms, and the "one pass with a hash map" pattern solves a huge number of interview problems.

The order of the check matters

Notice the loop looks up first, then inserts. If it inserted first, every word would immediately "find itself". The same care applies to your exercise: check for the partner before storing the current element, so an element is never paired with itself.

Your turn: write std::pair<int, int> two_sum(const std::vector<int>& v, int target) that returns the indexes {i, j} (with i < j) of two numbers adding up to target, or {-1, -1}. Do it in one pass: for each element, check whether target - v[j] was seen before.

Previous: std::set Next: pair and tuple