向std::set比较类传递更多数据的方法

Question

我有一个带有Compare类的std::set，该类需要额外的参数来比较键。这个可变的参数是在运行时确定的，我将它打包到集合的键中，以便让它可以被Compare访问。

然而，这个参数在逻辑上属于集合而不是键，因此这个解决方案看起来很笨拙，并且重复了所有键上的相同值。

有没有一种优雅的方法来向Compare类传递附加参数？（我最初考虑了set::value_comp，但它返回按值比较的对象，而我需要一个引用）。

谢谢。

- jackhab

Answer 1

std::set的定义如下：

template <
      class Key, 
       class Traits=less<Key>, 
       class Allocator=allocator<Key> 
>
class set

因此，Traits 应该是您的比较运算符，但如果看一下构造函数，您会再次看到它：

explicit set(
   const Traits& _Comp
);

所以只需将您的实例传递给构造函数即可。（请注意，这是通过复制完成的）

- Dewfy

---

这个答案是正确的，但我觉得有点难理解。为了澄清：你需要创建一个带有额外参数的比较对象，然后将该对象传递给std::set构造函数。不要尝试在集合构建之后修改参数。 - Mark Ransom

@Mark Ransom - 没有银弹，如果排序规则改变，则必须重新构建整个集合。如果参数不影响排序顺序，则可以通过引用或指针将其传递给 Traits。 - Dewfy

除了将其复制到新集合中，没有重建集合的方法，因此我坚持我的说法。比较对象在给定相同输入集时必须始终返回相同的值，否则集合可能会出现故障。 - Mark Ransom

@Mark Ransom - 是的，你不能重建set，只能进行复制。好吧，总是有两种方法：你能把你的比较规则分成两部分：（1）不可变的（2）取决于参数。然后你可以重建（通过擦除和临时复制到另一个集合中）仅在应用std::set::equal_range（规则1）返回的范围内的集合的一部分。之后，你可以使用特殊的set::insert - 用于排序。结果你得到O(ln(n))的复杂度。 - Dewfy

马克·兰索姆 - 谢谢，伙计们！现在我明白了，我陷入死锁的真正原因是因为我正在重复使用具有可变比较参数的相同集合成员。我应该做的是在调整Compare对象内部的比较参数后，在动态创建集合。 @马克·兰索姆 - 没有故障，因为我在重新使用具有不同参数的集合之前清空了它。我这样做是因为我更喜欢重用成员而不是动态分配。 - jackhab