Map and Set in C++: Runnable STL Examples, Traps and Exercises

Both map and set keep entries ordered and reject duplicates, but they store different things. A map keeps a value behind each unique key, while a set keeps only unique values. Code can still compile and change state unexpectedly through map::operator[], or retain an old value when a duplicate insert fails. Five restock events (pen +3, book +2, pen +4, eraser +5, book +1) leave a map holding {book:3, eraser:5, pen:7} and a set holding just the three names.

Map and set in C++: the two-container mental model

std::map<Key, Value> is an ordered associative container of unique keys paired with mapped values. std::set<T> is an ordered associative container of unique values. With the default comparator, a map with keys "pen", "book" and "eraser" iterates as book, eraser, pen. A set built from 42, 18, 42, 31 stores 18, 31, 42.

Uniqueness is decided by the comparator, not by the number of insertion attempts. Search, insertion and key erasure meet logarithmic complexity requirements. Balanced trees are common implementations, but portable code should rely on the interface and its guarantees, not a particular tree layout.

Include <map> and <set>, then declare std::map<std::string, int> stock; or std::set<int> scores;. Both headers ship with the standard library, so nothing extra needs installing. For the wider language and data-structure route these containers sit inside, see Coding & DSA Courses for Placements.

std::map from zero: insert, update, find and iterate

One program produces four different outcomes:

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

int main() {
    std::map<std::string, int> stock{{"pen", 12}, {"book", 5}, {"eraser", 8}};

    stock["pen"] += 3;
    auto [bookIt, bookInserted] = stock.insert({"book", 9});
    stock.insert_or_assign("eraser", 10);
    stock["pencil"] += 7;

    std::cout << std::boolalpha << bookInserted << ' ' << bookIt->second << '\n';
    for (const auto& [name, quantity] : stock) {
        std::cout << name << '=' << quantity << '\n';
    }

    auto markerIt = stock.find("marker");
    if (markerIt == stock.end()) std::cout << "marker missing\n";
}

The exact output is:

false 5
book=5
eraser=10
pen=15
pencil=7
marker missing

insert does not overwrite the existing book. insert_or_assign changes eraser from 8 to 10. For missing pencil, operator[] first creates an int value of 0, then adds 7. find checks for marker without inserting it.

std::set from zero: deduplicate, erase and find a bound

#include <iostream>
#include <set>

int main() {
    std::set<int> scores{42, 18, 42, 31, 18, 27};
    auto [it35, inserted35] = scores.insert(35);
    auto [it31, inserted31] = scores.insert(31);
    auto erased = scores.erase(18);
    auto bound = scores.lower_bound(30);

    std::cout << std::boolalpha << inserted35 << ' ' << inserted31
              << ' ' << erased << '\n';
    std::cout << "lower_bound(30)=" << *bound << '\n';
    for (int score : scores)
        std::cout << (score == *scores.begin() ? "" : " ") << score;
    std::cout << '\n';
}

Its output is:

true false 1
lower_bound(30)=31
27 31 35 42

The constructor discards repeated 42 and 18. Inserting 35 succeeds, inserting existing 31 fails, and erase(18) removes one stored value. lower_bound(30) returns the first value not less than 30. A set has no mapped value or operator[]. Use a map for studentId -> score, a set for distinct student IDs, and a multiset when repeated values must remain separate.

Worked example: aggregate five restocks with a map and a set

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

int main() {
    std::vector<std::pair<std::string, int>> restocks{
        {"pen", 3}, {"book", 2}, {"pen", 4},
        {"eraser", 5}, {"book", 1}
    };
    std::map<std::string, int> units;
    std::set<std::string> products;

    for (const auto& [name, quantity] : restocks) {
        units[name] += quantity;
        products.insert(name);
    }

    int total = 0;
    for (const auto& [name, quantity] : units) {
        std::cout << name << " -> " << quantity << '\n';
        total += quantity;
    }
    std::cout << "distinct products: " << products.size() << '\n';
    std::cout << "total units: " << total << '\n';
}

Output: book -> 3, eraser -> 5, pen -> 7, distinct products: 3, total units: 15. Map values hold quantities, set entries hold names, and 3 + 5 + 7 = 15. The map and set produce that order themselves, and no sort call appears anywhere in the program.

Map vs set operations, complexity and unordered alternatives

map::operator[] is key access with possible insertion, not position-based indexing. Here, units.find("eraser") reaches 5, units.lower_bound("marker") reaches pen -> 7, and products.lower_bound("cable") reaches eraser. Default comparison is lexicographic, not insertion order.

unordered_map and unordered_set give average constant-time lookup, but their iteration order is unspecified and neither offers lower_bound, so the bound queries above are not available on them. Hashing MCQs: 12 Solved on Hash Functions (GATE) explains the hash-table reasoning behind that trade-off.

Map and set mistakes that silently change state or output

First, operator[] can mutate a map during a supposed lookup:

std::map<std::string, int> marks{{"Asha", 78}};
std::cout << marks["Ravi"] << ' ' << marks.size(); // 0 2

Use find for observation without insertion. Use at() when a missing key should be handled as an exception. Second, given std::map<int, std::string>{{2, "two"}}, insert({2, "deux"}) returns false and retains "two". Use assignment or insert_or_assign(2, "deux") to replace it. Map values need not be unique, so {1:"red", 2:"red"} is valid because the keys differ.

Finally, erase safely while iterating:

for (auto it = scores.begin(); it != scores.end(); ) {
    if (*it < 30) it = scores.erase(it);
    else ++it;
}

Starting from {18, 27, 31, 42}, the result is {31, 42}. Do not erase from the same set inside a range-based for loop. Choose multimap or multiset only when repeated equivalent keys or values belong in the data model.

How map and set are tested: output traces and exercises

Questions on these containers almost always ask you to predict a value: the iteration order, whether an insert took effect, the size left after duplicates, or which container a stated requirement needs. Work each of the following by hand before reading the answer.

1. Count banana with std::map<char, int>. The result is a:3 b:1 n:2, since keys iterate as a, b, n.

2. Start with std::set<int>{8, 3, 8, 5}, insert 2, erase 3, then find lower_bound(4). The final set is {2, 5, 8}, and the bound is 5.

3. Start with std::map<int, int>{{2, 20}, {1, 10}}, evaluate m[3], then set m[1] = 15. The first expression returns 0 and inserts key 3. Final iteration is 1:15 2:20 3:0, and size is 3.

Turn these traces into a repeatable routine with Coding Round Strategy for Placements, or work through them as part of the wider placement programme, Mera Placement Hoga.

Map or set in C++: the short version and next step

Use a map for unique key-to-value relationships and a set for unique values. Expect comparator order, not insertion order. Use find to observe without mutation. Choose unordered variants only when sorted traversal and bound queries are unnecessary.

For one last check, change the final restock to {"marker", 1}. The map becomes {book:2, eraser:5, marker:1, pen:7}. There are 4 distinct products, and the total remains 2 + 5 + 1 + 7 = 15. Continue with C++ Programming for a structured route through the rest of the language.