c++ - 具有基于身份的相等性的有序关联容器

Question

我正在写一个模板函数，带有模板参数 X .在该函数中，我想创建 std::set<std::pair<int, X>>这样:

• 该集合中的对象按该对的第一个 ( int) 字段排序(我不关心关系是如何被打破的)
• 我可以添加多个具有相同 .first 的对象给定的，只要自己.second不相同

如果我知道模板参数 X总是有 <定义，最基本的std::set<std::pair<int, X> (使用默认比较器)会工作得很好。不幸的是，我不能对 X 做任何假设。 .

我想“作弊”并为 X 使用基于指针的比较领域:

template <typename X>
struct DistCmp {
    bool operator()(const std::pair<int, X>& lhs, const std::pair<int, X>& rhs) const {
        return lhs.first < rhs.first || lhs.first == rhs.first && &lhs.second < &rhs.second;
    }
};

template <typename X>
void f() {
    std::set<std::pair<int, X>, DistCmp<X>> s{};
    // ...
}

(毕竟，我真的不在乎如何比较 .second，只要不对不同的对象进行同等比较即可。)

不幸的是，我认为这是不正确的。部分原因是引用自 C++ 标准 here (这表明指针比较通常是未指定的，因此我不能依赖它们对于不同的对象是不相等的)。在某种程度上，我只是觉得它很可疑/hacky。

这个问题是否有任何干净/便携的解决方案？

更新:

我想到的一种方法是使用 ==用于比较指针而不是 < .但是，这不好，因为它会导致 pair<1, x> < pair<1, y> && pair<1, y> < pair<1, x>成为true .这违反了strict weak ordering的要求并可能导致stuff to break .

Answer 1

简短回答:使用 std::multiset 并回避整​​个问题 - multiset 允许多个键，所以只比较对的第一个元素。

请注意，如果您想在您的 map 中禁止 X 的相同值，您必须向 X 添加要求，因此它至少是 EqualityComparable。否则，您甚至无法检测到 X 的值何时相同以及何时不同。

更长的答案:您的代码不会产生您希望的结果。考虑添加新对 <0, x> 以映射到 <0, x>。 std::map 将尝试使用 <0, x> 的临时拷贝来查找 <0, x> 的存在。它将使用 x 的地址(临时的!)，它会将 false 与 map 中的所有内容进行比较，std::map 将根据 x 的地址(临时的!)找到要插入的位置。然后它会复制 x，从而改变地址并可能破坏它自己的顺序。