语言的哪一部分禁止更改 std::set 的元素

Question

std::set 是一个排序的关联容器，可以快速查找其元素。键以排序的方式插入，并且一旦插入就不能修改键以保留该顺序。

考虑以下构建 int* 的 std::set 然后尝试破坏其元素排序的演示：

#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);
}

我得到的输出是：

表达式 values[1] = 0; 有效地间接改变了 set 的键之一。这打破了顺序，因此似乎也打破了 count。我认为这也会破坏 set 的大部分其他功能。

代码显然有问题。据我所知，它遵循所有语言规则，而且我似乎没有违反我能找到的比较功能或 set 的任何要求。但是 set 提供的保证仍然被打破，这意味着我一定错过了什么。

Answer 1

在C++17中，有[associative.reqmts]/3:

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

因此，您的代码存在 UB，因为它违反了此要求。

Answer 2

[不是很政治正确的言论：标准里面很多东西都没有写，甚至写的东西有时也是不正确的。缺的一定要补，比解析准确的词靠谱。]

所有关联容器（已排序或未排序）均基于公理化要求。

隐含的基础是所有predicates/functors上的公理都是数学的relations/functions，否则公理可能没有任何意义。 很明显，这些功能，如比较器，必须明确定义；这意味着容器中当前的元素已排序 。

但是如果你的容器是空的并且你改变它的排序函数也没关系。您还可以进行极坐标排序，根据角度对元素进行排序，使用任意截止值（定义为最小角度），并旋转该最小角度线，如果旋转没有越过容器中的元素。

语言的哪一部分禁止更改 std::set 的元素

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

c++

std

invariants

stdset

language-lawyer