set and map in STL

The Ordered Associative Container Model

std::set and std::map are ordered associative containers. They retrieve data by a key and maintain iteration order through a comparison object. Default std::less<Key> normally gives ascending order.

Core search, insertion and erasure operations are logarithmic. The standard specifies behavior and complexity, not a mandatory red-black-tree implementation.

std::set: Unique Ordered Values

#include <set>

std::set<int> roll_numbers{104, 101, 104, 103};

for (int roll : roll_numbers) {
    std::cout << roll << ' ';
}

The duplicate 104 is not inserted, and iteration follows key order. Inspect the insertion result:

auto [position, inserted] = roll_numbers.insert(102);
if (inserted) {
    std::cout << "Added " << *position;
}

A set iterator provides const access to the key because changing a key in place could break the ordering invariant. To change a key, erase the old element and insert the new one. Since C++17, node handles can support carefully controlled extraction and reinsertion.

Use multiset when repeated equivalent values are part of the model, such as all marks including duplicates. Do not use a set merely as a convenient duplicate remover if the original order must remain significant.

std::map: Unique Keys with Values

#include <map>
#include <string>

std::map<std::string, int> marks{
    {"Sara", 91}, {"Aman", 78}
};

marks.insert_or_assign("Aman", 83);
marks.try_emplace("Kabir", 84);

for (const auto& [name, mark] : marks) {
    std::cout << name << ':' << mark << ' ';
}

insert_or_assign inserts a missing key or replaces its mapped value. try_emplace inserts only when the key is absent and can avoid constructing a mapped object unnecessarily. Plain insert does not replace an existing key.

The key is const through the iterator; the mapped value is modifiable:

for (auto& [name, mark] : marks) {
    mark += 2;       // allowed
    // name = "X";  // not allowed: key is const
}

Lookup, Access and Range Queries

if (auto it = marks.find("Sara"); it != marks.end()) {
    std::cout << it->second;
}

if (!marks.contains("Riya")) { // C++20
    std::cout << "Not found";
}

Comparators, Equivalence and Custom Keys

The comparison must impose a strict weak ordering. Two keys are equivalent when neither compares before the other; this equivalence is not necessarily identical to operator==.

struct ByLengthThenText {
    bool operator()(const std::string& a,
                    const std::string& b) const {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b;
    }
};

std::set<std::string, ByLengthThenText> words;

Do not use <=, a random result, current time or mutable external state. The comparator must remain consistent while keys are stored.

For a custom record key, define a stable comparator over the fields that form identity. C++20 transparent comparators such as std::less<> can permit heterogeneous lookup without constructing a temporary key when the involved comparisons are supported.

std::map<std::string, int, std::less<>> scores;
// scores.find(std::string_view{"Sara"}); // heterogeneous lookup

Insertion, Erasure and Iterator Safety

marks.emplace("Riya", 86);
marks.erase("Aman");

for (auto it = marks.begin(); it != marks.end(); ) {
    if (it->second < 40) it = marks.erase(it);
    else ++it;
}

• Insertion and emplacement do not invalidate existing iterators or references.
• Erasure invalidates only iterators and references to erased elements.
• erase(iterator) returns the following iterator, enabling a safe erase loop.
• Do not dereference end() or reuse an erased iterator.

A good position hint can make insertion more efficient, but a wrong hint does not change correctness. Bulk-load sorted data only after measuring; clear code is the first priority.

Unlike unordered_map, map supplies key order and logarithmic worst-case operations. Unordered containers offer average constant lookup but no sorted iteration and can have linear worst cases.

Complete Word-Frequency Lab with Output

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

int main() {
    const std::vector<std::string> words{
        "code", "learn", "code", "cpp", "learn", "code"
    };

    std::set<std::string> unique_words;
    std::map<std::string, int> frequency;
    for (const std::string& word : words) {
        unique_words.insert(word);
        ++frequency[word]; // insertion with zero is intentional
    }

    std::cout << "Unique:";
    for (const auto& word : unique_words) std::cout << ' ' << word;
    std::cout << "\nFrequency:\n";
    for (const auto& [word, count] : frequency) {
        std::cout << word << '=' << count << '\n';
    }
}

Here operator[] is appropriate: a missing word should begin with an integer value of zero before incrementing. Both containers iterate in lexical key order.

Common Mistakes, Practice and Review

Practice: build a phone book, word counter, unique roll-number register, score range query with lower_bound, and a custom key for year/roll number. Test empty data, missing keys, duplicate insertion and erasure during traversal.

1. Is the data a set or key-value relation?
2. Are keys unique or repeatable?
3. Is comparator equivalence correct?
4. Can lookup accidentally insert?
5. Is the required order explicit?
6. Are erased handles discarded?

Authoritative References

• C++ Working Draft: set and multiset
• C++ Working Draft: map and multimap
• C++ Working Draft: Associative Container Requirements

Ordering, key equivalence, complexity and iterator rules were checked against the current working draft. Review STL architecture for the full container decision table.