Read-Heavy Map Lookup: unordered_map vs. Sorted Vector + Binary Search

Question 14 / 51 • Correct so far: 0 (0 answered)

Snippet A

Unordered Map Lookup

std::size_t countFound(const std::unordered_map<int,std::string>& m,
                       const std::vector<int>& keys) {
    std::size_t found = 0;
    for (int k : keys)
        if (m.count(k)) ++found;
    return found;
}

std::size_t result = countFound(HASH_MAP, KEYS);
Snippet B

Sorted Vec Lookup

std::size_t countFound(const std::vector<std::pair<int,std::string>>& v,
                       const std::vector<int>& keys) {
    std::size_t found = 0;
    for (int k : keys) {
        auto it = std::lower_bound(
            v.begin(), v.end(), k,
            [](const std::pair<int, std::string>& entry, int key) {
                return entry.first < key;
            });
        if (it != v.end() && it->first == k) ++found;
    }
    return found;
}

std::size_t result = countFound(SORTED_VEC, KEYS);
Shared test data (shared-setup) 
constexpr int kMapSize = 32;
constexpr int kQueries = 65536;

static std::vector<std::pair<int,std::string>> makeSortedVec() {
    std::vector<std::pair<int,std::string>> v;
    v.reserve(kMapSize);
    for (int i = 0; i < kMapSize; ++i)
        v.push_back({i * 3, "val" + std::to_string(i)});
    std::sort(v.begin(), v.end());
    return v;
}

static std::unordered_map<int,std::string> makeHashMap() {
    std::unordered_map<int,std::string> m;
    m.reserve(kMapSize);
    for (int i = 0; i < kMapSize; ++i)
        m[i * 3] = "val" + std::to_string(i);
    return m;
}

static std::vector<int> makeKeys() {
    std::vector<int> ks;
    ks.reserve(kQueries);
    for (int i = 0; i < kQueries; ++i)
        ks.push_back((i % (kMapSize + 4)) * 3);
    return ks;
}

static const std::vector<std::pair<int,std::string>> SORTED_VEC = makeSortedVec();
static const std::unordered_map<int,std::string>     HASH_MAP   = makeHashMap();
static const std::vector<int>                        KEYS       = makeKeys();

Which snippet is faster?

Select the correct answer(s)