Maps and Sets

A map stores key–value pairs and finds a value by its key — a phone book, word counts, settings. A set stores unique values. C++ offers ordered versions (std::map, std::set) that keep keys sorted, and hash-based ones (std::unordered_map, std::unordered_set) that are usually faster.

std::map

C++

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> stock{{"apples", 30}, {"bananas", 24}};
    stock["cherries"] = 200;          // insert or overwrite
    stock["apples"] += 10;            // update

    std::cout << "apples: " << stock["apples"] << '\n';
    std::cout << stock.size() << " products\n";
    for (const auto& [fruit, count] : stock) {     // always in key order
        std::cout << fruit << " = " << count << '\n';
    }
}

Output

apples: 40
3 products
apples = 40
bananas = 24
cherries = 200

Iterating a std::map visits keys in sorted order. Each element is a std::pair of key and value, which the structured binding unpacks.

Looking up safely

m[key] inserts a default value if the key is missing — handy for counting, a bug when you only wanted to look. To look without inserting, use contains, find or at:

C++

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, double> prices{{"tea", 2.5}, {"coffee", 3.2}};

    std::cout << std::boolalpha << prices.contains("juice") << '\n';   // C++20

    if (auto it = prices.find("coffee"); it != prices.end()) {
        std::cout << "coffee costs " << it->second << '\n';
    }

    double unknown = prices["juice"];           // oops: inserts juice = 0
    std::cout << unknown << ", size now " << prices.size() << '\n';

    prices.erase("juice");
    std::cout << "size after erase " << prices.size() << '\n';
}

Output

false
coffee costs 3.2
0, size now 3
size after erase 2

at(key) throws std::out_of_range if the key is missing.

Counting words

C++

#include <iostream>
#include <map>
#include <sstream>
#include <string>

int main() {
    std::istringstream text{"the cat sat on the mat the end"};
    std::map<std::string, int> counts;
    std::string word;
    while (text >> word) ++counts[word];      // missing words start at 0
    for (const auto& [w, n] : counts) std::cout << w << ':' << n << ' ';
    std::cout << '\n';
}

Output

cat:1 end:1 mat:1 on:1 sat:1 the:3

std::set

A set keeps one copy of each value, in sorted order:

C++

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> tags{"cpp", "tutorial", "cpp", "beginner"};
    tags.insert("tutorial");                  // already there: ignored
    auto [it, inserted] = tags.insert("stl");
    std::cout << std::boolalpha << "stl inserted: " << inserted << '\n';
    for (const auto& t : tags) std::cout << t << ' ';
    std::cout << "\nhas beginner? " << tags.contains("beginner") << '\n';
}

Output

stl inserted: true
beginner cpp stl tutorial
has beginner? true

Unordered containers

std::unordered_map and std::unordered_set use a hash table: lookups take constant time on average instead of growing with the size, but iteration order is unspecified — it can differ between compilers and even between runs. Sort the results when you need a stable order:

C++

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

int main() {
    std::unordered_map<std::string, int> visits;
    for (std::string page : {"/home", "/about", "/home", "/blog", "/home", "/blog"}) {
        ++visits[page];
    }
    std::cout << visits["/home"] << " visits to /home\n";

    std::vector<std::pair<std::string, int>> sorted(visits.begin(), visits.end());
    std::sort(sorted.begin(), sorted.end(), [](const auto& a, const auto& b) { return a.second > b.second; });
    for (const auto& [page, n] : sorted) std::cout << page << ' ' << n << '\n';
}

Output

3 visits to /home
/home 3
/blog 2
/about 1

Which to choose

Container	Lookup	Order	Key requirements
`std::map` / `std::set`	O(log n)	Sorted by key	`<` comparison
`std::unordered_map` / `unordered_set`	O(1) average	Unspecified	Hash function and `==`
`std::multimap` / `multiset`	O(log n)	Sorted; duplicate keys allowed	`<`

Use unordered_map by default for lookups by key; use map when you need sorted iteration or range queries ("all keys between A and F"). For a handful of items, a std::vector searched linearly is often fastest of all.

Custom keys

Any type with < works as a std::map key — including structs with a defaulted <=> (lesson 20):

C++

#include <compare>
#include <iostream>
#include <map>
#include <string>

struct Seat {
    int row;
    char letter;
    auto operator<=>(const Seat&) const = default;
};

int main() {
    std::map<Seat, std::string> bookings{{{12, 'C'}, "Ana"}, {{3, 'A'}, "Ben"}, {{12, 'A'}, "Chloe"}};
    for (const auto& [seat, name] : bookings) {
        std::cout << seat.row << seat.letter << ": " << name << '\n';
    }
}

Output

3A: Ben
12A: Chloe
12C: Ana

Try it yourself

Group words by their first letter using a std::map<char, std::vector<std::string>>.

#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> words{"banana", "apple", "blueberry", "cherry", "avocado", "cranberry"};
    std::map<char, std::vector<std::string>> groups;
    for (const auto& w : words) groups[w[0]].push_back(w);
    for (const auto& [letter, list] : groups) {
        std::cout << letter << ':';
        for (const auto& w : list) std::cout << ' ' << w;
        std::cout << '\n';
    }
}

Edit the code, copy it into main.cpp, then compile and run it with c++ -std=c++20 -Wall main.cpp -o main && ./main. How to set up a C++ compiler

Output

a: apple avocado
b: banana blueberry
c: cherry cranberry

PreviousStructs & Enums NextMore Containers