Same-named find, different identity: define the key equivalence relation first

First write clearly what the set considers the same

The publisher Item 44 comparison of member algorithms reminds us not to look only at function names. This example restricts numbers to non-negative integers and buckets by tens: 12 and 18 belong to the same bucket. The comparator compares only the result of division by 10, so the set considers them equivalent, i.e. both directions of comparison are false. The set keeps only one representative per equivalence class and does not automatically convert the representative into the query value.

This modeling suits businesses that keep only one representative per group. If every record actually needs to exist, you cannot pretend this set is ordinary deduplication; use a multiset, or a map from bucket number to a set of records. Data-structure choice must follow the true identity definition.

Member lookup and linear search answer different questions

After inserting 12 into the set, member find(18) can return the node that holds 12, because it asks whether a key equivalent to 18 exists. std::find walks the elements and performs integer equality comparison, so it will not consider 12 equal to 18. Different results are entirely legal; it is not that some algorithm missed an element.

Ordered-set member lookup can also use the internal structure, with logarithmic complexity; generic find is linear search. This lesson only asserts observable results, not red-black tree shape or exact comparison counts, which are implementation details. If the business needs exact equality, that should be expressed explicitly; do not change the meaning of the query just for speed.

Strictness is only the starting point, not the full requirement

Item 21 stresses that comparison of equal values must be false, so <= cannot be the ordering relation here. Reverse order should compare whether the later key is less than the earlier key, not negate the original comparison result. Negation would also treat equal values as ordered, breaking the contract.

Strict weak ordering also requires transitivity, and that the incomparability relation form consistent equivalence classes. This example naturally satisfies those conditions via ordinary < on integer bucket numbers. Do not infer from a few assertions that an arbitrary comparator is already correct; finite examples are for observation, and full guarantees come from the definition. Modern ranges algorithms will not automatically prove these semantic properties for you either.

Pitfalls

• When the comparator treats different objects as equivalent, set will reject the second equivalent key; this is independent of whether operator== holds.
• Do not change external state that the comparator depends on while the key is still in the container, or the existing order may become invalid.

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

#include <algorithm>
#include <cassert>
#include <set>

struct ByBucket {
    bool operator()(int left, int right) const noexcept {
        return left / 10 < right / 10;
    }
};

int main() {
    std::set<int, ByBucket> representatives{12, 31};
    const auto equivalent = representatives.find(18);
    assert(equivalent != representatives.end());
    assert(*equivalent == 12);
    assert(std::find(representatives.begin(), representatives.end(), 18)
           == representatives.end());
    const auto inserted = representatives.insert(19);
    assert(!inserted.second);
    assert(representatives.size() == 2);
    assert(!ByBucket{}(12, 12));
    assert(!ByBucket{}(12, 18));
    assert(!ByBucket{}(18, 12));
}

Compile locally

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

Expected result

Expected: exit 0, no output; every assert holds.

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

If buckets must be ordered descending while intra-bucket equivalence is preserved, how should the comparator be modified?

Check the sources

• Effective STL Item 44 — full publisher excerpt
• Effective STL Item 21 — full publisher excerpt
• C++ draft [associative.reqmts] — key equivalence

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