我有一个用我自己的 comp 函数声明的集合:
set<int, my_comp> my_set;
比较函数使用存储在别处的一些数据来决定哪个 int 更大。 如果所述数据发生变化，集合中元素的顺序也会发生变化。
set 是如何处理的？ 如果我知道一个 int 的相对位置可能已经改变，我是否必须删除并重新插入它？
详细信息:特别是，my_comp 使用整数作为索引来访问 vector 并比较 vector 中包含的值。所述值必然会发生变化。
最佳答案
不，对于 std::set 中的元素，严格的弱顺序不得更改，键必须被视为 const。
比较函数必须是strict weak ordering的模型:
A strict weak ordering has the following properties. For all x, y, and z in S,
- For all x, it is not the case that x < x (irreflexivity).
- For all x, y, if x < y then it is not the case that y < x (asymmetry).
- For all x, y, and z, if x < y and y < z then x < z (transitivity).
- For all x, y, and z, if x is incomparable with y, and y is incomparable with z, then x is incomparable with z (transitivity of incomparability).
更好的解决方案可能是排序的 std::vector，以及 std::sort(对其进行排序)、std::lower_bound(查找和插入元素)，std::inplace_merge(插入元素)。
关于C++ std::set 如何处理元素的动态排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19124732/