c++ - C++ std::set 如何处理元素的动态排序

Question

我有一个用我自己的 comp 函数声明的集合：

set<int, my_comp> my_set;

比较函数使用存储在其他地方的一些数据来决定哪个 int 更大。如果所述数据改变，则集合元素的顺序也会改变。

set如何处理呢？如果我知道一个 int 的相对位置可能已经改变，我是否必须删除并重新插入它？

详细信息：特别是，my_comp 使用整数作为索引来访问向量并比较向量中包含的值。所述值必然会改变。

Answer 1

不，严格的弱顺序不能改变 a 中的元素std::set，键必须被视为const。

比较函数必须是严格弱排序的模型：

严格的弱排序具有以下属性。对于 S 中的所有x、y和z ，

• 对于所有x，情况并非x < x（非自反性）。
• 对于所有x，y，如果x < y则不是y < x（不对称）。
• 对于所有x、y和 z，如果x < y和y < z则x < z（传递性）。
• 对于所有x、y和z，如果x与y不可比，并且y与z不可比，则x与z不可 比（不可比性的传递性）。

更好的解决方案可能是 sorted std::vector，以及std::sort（对其进行排序）、std::lower_bound（查找和插入元素）、std::inplace_merge（插入元素）。