C++ set and map: Ordered Containers, Custom Keys and Bounds

You can use a vector, but a set rejects an insertion and you cannot see why. A map prints keys in a fixed order, then lower_bound appears to behave strangely after you add a custom comparator. The missing idea is that all these behaviours come from one ordering rule.

One student index makes ordering, comparator equivalence, bounds and duplicate handling visible. If the C++ syntax itself needs a refresh first, follow the C++ Tutorial complete learning path, then return to this example.

C++ set and map: one ordering model, two stored shapes

std::set<Key, Compare> stores unique keys in comparator order. std::map<Key, Value, Compare> stores unique keys paired with mutable mapped values, also in comparator order. Iteration follows that order, but neither container provides sequence-style positional indexing.

Search, single-element insertion and key-based erasure are logarithmic in the number of elements. Implementations commonly use balanced search trees, so binary-search-tree reasoning is useful intuition. The C++ interface does not promise a particular tree type or physical shape.

The decisive rule is equivalence. Two keys a and b are equivalent when:

!comp(a, b) && !comp(b, a)

They do not need to be identical in every field. If the comparator ignores a field, different objects can become the same container key.

Build an ordered set student index with a custom key

This complete example orders higher scores first, then smaller roll numbers for equal scores:

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

struct Student {
    int roll;
    std::string name;
    int score;
};

struct HigherScoreThenRoll {
    bool operator()(const Student& a, const Student& b) const {
        if (a.score != b.score) return a.score > b.score;
        return a.roll < b.roll;
    }
};

int main() {
    std::set<Student, HigherScoreThenRoll> index;

    auto [p1, inserted1] = index.insert({104, "Asha", 82});
    auto [p2, inserted2] = index.insert({101, "Ravi", 91});
    auto [p3, inserted3] = index.insert({107, "Meera", 82});
    auto [p4, inserted4] = index.insert({103, "Kabir", 76});
    auto [p5, inserted5] = index.insert({107, "Meera K.", 82});

    std::cout << std::boolalpha << inserted1 << ' ' << inserted2 << ' '
              << inserted3 << ' ' << inserted4 << ' ' << inserted5 << '\n';

    for (const Student& s : index) {
        std::cout << s.name << " (" << s.score << ", roll "
                  << s.roll << ")\n";
    }
}

The insertion flags are true true true true false. The fifth object has a different name, but its score 82 and roll 107 are comparator-equivalent to Meera's existing key. Rejection does not replace the stored element, so the name remains Meera.

Iteration produces:

Ravi (91, roll 101)
Asha (82, roll 104)
Meera (82, roll 107)
Kabir (76, roll 103)

Scores descend from 91 to 76. Within the score-82 group, rolls ascend from 104 to 107.

Read find and bounds in comparator order

Probe the set with Student{104, "ignored", 82}. find reaches the stored Asha record because the comparator does not inspect name. lower_bound also points to Asha. upper_bound points to Meera, so equal_range is the half-open range [Asha, Meera), containing only Asha.

Now try the absent key Student{105, "ignored", 82}. find returns end(). Both lower_bound and upper_bound point to Meera at score 82, roll 107.

The reliable definition is that lower_bound(k) returns the first element that does not come before k under the comparator. Trace the stored order first: 91/101, 82/104, 82/107, 76/103. The probe 82/105 belongs between 82/104 and 82/107, so the first stored element not before it is Meera. Ordinary ascending-integer intuition does not apply to a descending, two-field order.

Build a map with a composite student key

A map uses the same model, but associates each key with a value:

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

struct StudentKey {
    std::string branch;
    int roll;
};

struct ByBranchThenRoll {
    bool operator()(const StudentKey& a, const StudentKey& b) const {
        if (a.branch != b.branch) return a.branch < b.branch;
        return a.roll < b.roll;
    }
};

int main() {
    std::map<StudentKey, int, ByBranchThenRoll> marks;

    auto [a, inserted1] = marks.emplace(StudentKey{"CSE", 42}, 86);
    auto [b, inserted2] = marks.emplace(StudentKey{"ECE", 7}, 78);
    auto [c, inserted3] = marks.emplace(StudentKey{"CSE", 19}, 91);
    auto [d, inserted4] = marks.emplace(StudentKey{"CSE", 42}, 99);
    auto [e, inserted5] = marks.insert_or_assign(StudentKey{"CSE", 42}, 99);

    std::cout << std::boolalpha << inserted4 << ' ' << inserted5 << '\n';
    for (const auto& [key, value] : marks) {
        std::cout << key.branch << '-' << key.roll << " -> " << value << '\n';
    }

    std::cout << "ME-12 -> " << marks[StudentKey{"ME", 12}] << '\n';
}

The second emplace for CSE-42 reports false and leaves 86 unchanged. insert_or_assign also reports false, meaning the key was not newly inserted, but it changes the mapped value to 99. The three-entry iteration is CSE-19 -> 91, CSE-42 -> 99, ECE-7 -> 78.

Map keys are immutable through ordinary iterators, while mapped values are mutable. The final operator[] expression deliberately inserts ME-12 -> 0 because the key is absent and int is value-initialised. Prefer find, contains or at when accidental insertion would be a bug.

Write a strict weak ordering that remains valid

A valid comparator needs four practical checks:

1. comp(x, x) must be false.

2. If comp(a, b) is true, comp(b, a) must be false.

3. The ordering must be transitive.

4. If a is equivalent to b and b is equivalent to c, a must be equivalent to c.

That is why descending order uses a.score > b.score, not a.score >= b.score. With >=, an equal object would compare before itself.

Every field that defines identity must appear in the comparator. In the set above, {101, "Ravi", 95} and {101, "Ravi", 91} are different keys because score is compared before roll. If roll alone defines a student, compare only rolls or use a map keyed by roll. Data identity and display order are not automatically the same.

Do not make a comparator depend on mutable external state, and do not change ordering fields while an element is stored. Set elements and map keys cannot be edited through ordinary iterators because an in-place key change could break the ordering invariant. Extract and reinsert when a key truly must change.

Choose the container from the required operation

Use set for unique ordered values and map for unique ordered key-value records. Choose multiset or multimap when comparator-equivalent duplicates must coexist; their equal_range can contain several elements.

Hash-based unordered_set and unordered_map fit cases where sorted traversal and ordered bounds are unnecessary. There is no blanket winner. A collection built once and searched many times may also suit a sorted vector, which gives compact storage and binary search but makes middle insertion expensive. Sorting Algorithms: Complexity and Comparison helps separate the one-time sorting cost from later search costs.

How coding tests and interviews probe custom comparators

Common tasks ask you to predict iteration order, decide whether insertion succeeds, identify the iterator returned by a bound, or spot a comparator that violates strict weak ordering. These are all traces of the same rule.

Try the 60-second drill on the set. Write 91/101, 82/104, 82/107, 76/103; test equivalence for 82/107; then place 82/105 between 82/104 and 82/107. The answers are: the fifth insertion is rejected, find(82/105) == end(), and lower_bound(82/105) points to Meera at 82/107.

For first-use operations and standard-key exercises, use Map and Set in C++: Runnable STL Examples, Traps and Exercises. Custom-key questions add comparator equivalence, ordered bounds and strict weak ordering.

C++ set and map: the short version and next step

Keep five rules:

• The comparator controls traversal.

• Comparator equivalence controls uniqueness.

• Bounds follow comparator order.

• map::emplace does not overwrite an equivalent key.

• The comparator must remain a strict weak ordering for the container's lifetime.

Compile both examples. Then change the set comparator to roll-only and predict what survives before running it. The second roll 107 record is still rejected, and {101, "Ravi", 95} now collides with the existing roll-101 record because score no longer participates in key identity.

For a structured C++ route, continue with Coding for Placements: C, C++, Java and Python. You can also browse the wider Coding & DSA courses, then return to the examples and practise predicting the result before letting the compiler confirm it.