CODEWITHSUNDEEP
c++language-lawyerstdstdsetinvariants
François Andrieux
François Andrieux

Reputation: 29022

Which part of the language forbids changing elements of an std::set

An std::set is a sorted associative container that offers fast lookup of it's elements. Keys are inserted in a sorted fashion and keys can't be modified once inserted to preserve that order.

Consider the following demonstration that constructs an std::set of int* and then tries to break it's elements' sorting : 

#include <iostream>
#include <set>

int values[] = { 50, 40, 30, 20, 10 };

// Comparator that sorts by pointed value
struct comparator {
    bool operator()(const int* left, const int* right) const {
        return *left < *right;
    }
};

using my_set_t = std::set<int*, comparator>;

// Checks if each of the elements of `values` are in the set
void output(const my_set_t & foo)
{
    for (auto & x : values) {
        std::cout << x << ' ' << foo.count(&x) << '\n';
    }
    std::cout << std::endl;
}

int main()
{
    // Insert the address of each element of `values` into the set
    my_set_t foo;
    for (auto & x : values) {
        foo.emplace(&x);
    }

    output(foo);
    // Changing `values[1]` to zero should break the sorting of the set
    values[1] = 0;
    output(foo);
}

The output I got was : 

50 1
40 1
30 1
20 1
10 1

50 1
0 0
30 0
20 0
10 0

The expression values[1] = 0; effectively alters one of the set's keys indirectly. This breaks the ordering and consequently seems to also break count. I assume this would also break most of the set's other functionalities.

There is obviously something wrong with the code. As far as I can tell it follows all language rules and I doesn't seem to violate any requirement that I could find for the compare function or set. But the guaranties provided by set are nonetheless broken, meaning I must have missed something.

Upvotes: 1

Views: 134

Answers (2)

curiousguy
curiousguy

Reputation: 8288

[Not very politically correct remark: Many things are unwritten in the standard, and even written things are sometimes incorrect. You have to make up for the missing parts, it's more reliable than parsing exact words.]

All associative containers (sorted or not sorted) are based on axiomatic requirements.

The implicit basis is that all the predicates/functors on which there are axioms are mathematical relations/functions, or the axioms wouldn't possibly mean anything. So obviously these functions, like comparators, must be well defined; it means that elements currently in a container are ordered.

But it doesn't matter if your container is empty and you change its ordering function. You can also have a polar ordering where you order elements according to the angle, with an arbitrary cutoff (minimal angle by definition), and rotate that minimum angle line, if the rotation doesn't pass over elements in the container.

Upvotes: -1

Brian Bi
Brian Bi

Reputation: 119382

In C++17, there is [associative.reqmts]/3:

... For any two keys k1 and k2 in the same container, calling comp(k1, k2) shall always return the same value.

Thus, your code has UB because it violates this requirement.

Upvotes: 5

Related Questions