Which Map and Set Variants Fit Which Job?

Which map and set variants fit which job comes down to one question: do you need the elements in a defined order, and does the cost of that order matter? The ordered containers — [[std::map]], [[std::set]], [[std::multimap]] — keep their elements sorted using a tree and give you logarithmic lookup. The unordered ones — [[std::unordered_map]], [[std::unordered_set]] — use a hash table and give you average constant-time lookup with no ordering at all.

The four containers

• std::map — unique keys mapped to values, kept sorted by key.
• std::multimap — the same, but several keys may share a value.
• std::set — unique elements, kept sorted.
• std::multiset — sorted elements that may repeat.
• std::unordered_map — unique keys mapped to values, in no particular order.
• std::unordered_set — unique elements, in no particular order.

The ordered versions are built on a balanced tree. The unordered versions are built on a hash table.

A map associates keys with values

A std::map stores key-value pairs, sorted by key, with lookup in logarithmic time.

#include 
#include 
#include 

int main() {
    std::map weights = {
        {"p-003", 12},
        {"p-001", 4},
        {"p-002", 30}
    };

    weights["p-004"] = 8;

    for (const auto& entry : weights) {
        std::cout << entry.first << " -> " << entry.second << '\n';
    }

    std::cout << "p-002 weight: " << weights["p-002"] << '\n';
    std::cout << "count: " << weights.size() << '\n';
    return 0;
}

The output shows the entries in key order regardless of the order they were inserted:

p-001 -> 4
p-002 -> 30
p-003 -> 12
p-004 -> 8
p-002 weight: 30
count: 4

Note that operator[] on a map creates the key with a default value if it is missing. That is convenient and occasionally surprising.

A set holds unique elements

A std::set stores elements with no duplicates and keeps them sorted.

#include 
#include 
#include 

int main() {
    std::set zones = {"north", "south", "north", "east"};

    std::cout << "size: " << zones.size() << '\n';
    for (const std::string& zone : zones) {
        std::cout << zone << ' ';
    }
    std::cout << '\n';

    std::cout << "has north: " << (zones.count("north") > 0) << '\n';
    std::cout << "has west:  " << (zones.count("west") > 0) << '\n';
    return 0;
}

The output shows the duplicate removed and the elements sorted:

size: 3
east north south 
has north: 1
has west:  0

.count() on a set returns 0 or 1, which makes it a convenient membership test.

The unordered variants

The unordered containers make no promises about the order of the elements, but they are usually faster for large collections because a hash lookup avoids the pointer chasing of a tree.

#include 
#include 
#include 

int main() {
    std::unordered_map weights = {
        {"p-003", 12},
        {"p-001", 4},
        {"p-002", 30}
    };

    std::cout << "p-002 weight: " << weights["p-002"] << '\n';
    std::cout << "count: " << weights.size() << '\n';

    std::cout << "bucket count: " << weights.bucket_count() << '\n';
    return 0;
}

The output shows the same lookup behaviour with no ordering:

p-002 weight: 30
count: 3
bucket count: 13

The .bucket_count() reveals the internal structure: the hash table has that many buckets, and elements are distributed among them by hash value.

Ordered or unordered

The decision comes down to three questions.

Do you need the elements in order? If you iterate and need sorted output, or you need .lower_bound() and .upper_bound() to find a range, you need an ordered container.

Is the key type hashable? The unordered containers require a hash function. The standard library provides one for every built-in type and for std::string, but a user-defined type needs its own std::hash specialisation.

How big is the collection? For a handful of elements the difference does not matter. For hundreds of thousands, the unordered containers usually win.

| | std::map | std::unordered_map | |---|---|---| | Order | sorted by key | unspecified | | Lookup | logarithmic | average constant | | Insertion | logarithmic | average constant | | Iterators | stay valid on insert | invalidated by rehash | | Memory | one node per element | buckets plus nodes |

Finding ranges in an ordered map

The ordered containers support range queries, which is the reason to choose them when you need them.

#include 
#include 
#include 

int main() {
    std::map orders = {
        {100, "alpha"}, {200, "bravo"}, {300, "charlie"}, {400, "delta"}
    };

    auto first = orders.lower_bound(200);
    auto last = orders.upper_bound(400);

    std::cout << "between 200 and 400:\n";
    for (auto it = first; it != last; ++it) {
        std::cout << "  " << it->first << " -> " << it->second << '\n';
    }
    return 0;
}

The output shows the two entries in the half-open range:

between 200 and 400:
  200 -> bravo
  300 -> charlie
  400 -> delta

Choosing the right container

• Lookup by key, no ordering needed — std::unordered_map.
• Lookup by key, and you need the entries sorted — std::map.
• Membership test, no ordering needed — std::unordered_set.
• Membership test, and you need the elements sorted or the minimum and maximum — std::set.
• Several values for the same key — std::multimap or std::unordered_multimap.
• A sorted range query — std::map with .lower_bound() and .upper_bound().

Quick reference

• std::map and std::set keep elements sorted; lookup is logarithmic.
• std::unordered_map and std::unordered_set use hashing; lookup is average constant.
• Ordered containers give you range queries; unordered ones do not.
• The unordered containers need a hash function, which user-defined types must provide.
• .count() on a set is a membership test.
• Rehashing invalidates iterators into an unordered container.

Try it yourself: store a set of parcel records in a [[std::map]] keyed by identifier, then look one up and print its weight. Next, convert it to an [[std::unordered_map]] and time a thousand lookups in each. Finally, use [[.lower_bound()]] and [[.upper_bound()]] on the ordered map to list every parcel whose identifier starts with a given letter.