map and set: ordered association and the comparator contract

The standard promises order, not a particular tree

set stores keys and map stores keys with values. Ordinary versions allow each equivalent key only once; the multi versions allow duplicates. Iteration order follows the comparator. Lookup and ordinary single-element insertion have logarithmic complexity. Erasure by iterator has amortized constant complexity; erasure by key also includes the cost of lookup and of how many elements are removed.

A red-black tree is a common implementation, not a data structure the standard names. Complexity also does not turn one string comparison into a constant cost: a long shared prefix can make the comparison itself expensive. When you need range queries, ordered traversal, or a clear logarithmic lookup bound, ordered associative containers match the job better than a hash table that relies on average-constant lookup.

Comparison equivalence and business equality must line up

Keys a and b are equivalent when !comp(a,b) && !comp(b,a): neither sorts before the other. That need not satisfy a == b. The example compares only Record::id, so a second insert with the same id and a different label still fails. If the business requires the same id with different labels to coexist, the label must join the ordering key, or you must choose a container that allows equivalent keys.

The comparator must form a strict weak ordering: nothing is less than itself, the before-relation is transitive, and comparison equivalence is transitive. <= is not a legal substitute. External configuration the comparator depends on must not change the ordering while elements are stored. Likewise, a key's ordering fields must not change by casting away const or through a mutable indirect object.

Lookup should not insert by accident

map::operator[] inserts a value-initialized mapped value when the key is missing, so existence checks should use find. Use at when a missing key should report an error. A map element has type pair<const Key,T>: you may modify second and must not modify first in place. A set iterator likewise must not modify the key.

Insertion keeps existing iterators and references valid. Erasure invalidates only handles to the erased element. Prefer the member lower_bound for boundary queries; it can use the container structure for logarithmic lookup. Generic std::lower_bound has a logarithmic comparison count, but on these bidirectional iterators it may still pay a linear number of increments. A range result must still be checked against end before dereference.

Pitfalls

• Uniqueness in a set is comparator equivalence, not equality of every field. Comparing only one field can merge records on purpose or by accident.
• Using map[key] to test whether a key exists mutates the container. Use find, or in C++20 use contains.

Minimum C++11 · complete program · Download .cpp

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

struct Record { int id; std::string label; };
struct ById {
    bool operator()(const Record& a, const Record& b) const {
        return a.id < b.id;
    }
};

int main() {
    std::set<Record, ById> records;
    auto first = records.insert(Record{7, "original"});
    auto duplicate = records.insert(Record{7, "replacement"});
    assert(first.second && !duplicate.second);
    assert(duplicate.first->label == "original");

    std::map<int, std::string> names{{10, "ten"}, {30, "thirty"}};
    auto saved = names.find(10);
    names.emplace(20, "twenty");
    assert(saved->second == "ten");
    auto boundary = names.lower_bound(15);
    assert(boundary != names.end() && boundary->first == 20);
    auto missing = names.find(99);
    assert(missing == names.end() && names.size() == 3);
    std::cout << duplicate.first->label << ' ' << boundary->second << '\n';
}

Compile locally

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread stl-ordered.cpp -o example && ./example

Expected result

original twenty

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

In a map<int,int>, you need the sum of values whose keys lie in [20,40). How should you locate and traverse them? State the complexity.

Check the sources

• Working draft [associative.reqmts]: comparison equivalence, ordered lookup, and stability
• Working draft [alg.binary.search]: comparison count versus increment count

Drafts and official chapters change. The version mark is only the example’s minimum.