c++ - std::map 不删除自定义对象的重复项

Question

全部。

因此，我创建了一个 Comparable 基类(一种 Java)，它负责在 C++ 中重载比较运算符。在这里:

template <class T>
class Comparable {
public:
  bool operator== (const T& rhs) const { return this->compare(rhs) == 0; }
  bool operator!= (const T& rhs) const { return !(*this == rhs); }
  bool operator<  (const T& rhs) const { return this->compare(rhs) < 0; }
  bool operator<= (const T& rhs) const { return (*this == rhs) || (*this < rhs); }
  bool operator>  (const T& rhs) const { return this->compare(rhs) > 0; }
  bool operator>= (const T& rhs) const { return (*this == rhs) || (*this > rhs); }
protected:
  virtual int compare (const T& rhs) const = 0;
};

子类对象既有ID，也有数据需要作为排序的key。我已经实现了每个对象，以便具有相同 ID 的对象返回 0，如果它们的 ID 不同，则它们根据它们的数据进行排序。这是一个例子:

int Foo::compare(const Foo& rhs) const
{
    if (_id == rhs._id)
        return 0;
    // _value is integer data; comparison should sort on this
    if (_value == rhs._value)
    {
        // OK, same data, now sort on ID's
        return _id.compare(rhs._id);
    }
    // Sort on value
    return _value - rhs._value;
}

到目前为止，我认为还不错。

但是，当我尝试将 Foo 对象存储在 std::set 容器中时，该集合不会消除重复项。也就是说，其中仍然会有包含相同 ID 的对象，即使这应该被视为相等。

有人知道发生了什么事吗？

编辑:关于为什么这样设计代码有很多问题。

我需要满足两个条件:

1. 无论值如何，具有相同 ID 的对象都必须被视为“相同”对象。
2. 不具有相同 ID 的对象必须根据它们的值进行排序(该值是什么取决于对象的类型)。

这是因为创建这些对象的数据来自未经验证的来源。如果该来源提供具有相同 ID 但不同值的数据，则为无效数据。

编辑 2:关于 std::map 的严格弱排序。假设您有两个 Foo 对象，A 和 B。

如果他们的 ID 相同，则 A < B 为假，B < A 为假。 如果它们的 ID 不相等，则 A < B 为真或假取决于它们的值，而 B < A 与 A < B 相反。

这不应该满足严格的排序规则吗？

无论如何，如果 std::set 使用小于运算符(默认情况下)，它不应该按设计工作吗？

编辑 3:std::set，而不是 std::map。我真是太蠢了。抱歉。

Answer 1

std::map不通过 operator== 确定重复项.它使用 operator< ¹，因为它无论如何都需要使用它来确定顺序。你的operator<被打破。它需要执行 strict weak ordering .

您的比较失败的方式在于以下属性(称为传递性)。对于 3 个对象，如果 A < B和 B < C , 那么一定是 A < C .

所以，考虑三个对象，A , B和 C . A.id != B.id ，但是A.value < B.value , 所以 A < B .现在，C.id == B.id (因此 C.id != A.id )，但是 C.value < A.value .所以C < A , 和 A < B .因此，C应该是 < B .但事实并非如此，因为 C.id == B.id .

一种方法是定义您的 compare像这样的功能:

int Foo::compare(const Foo& rhs) const
{
    if (_id < rhs._id)
        return -1;
    if (rhs._id < _id)
        return 1;

    return _value - rhs._value;
}

如果您不能使用它，并且找不到其他方法来强制执行正确的排序，那么您根本无法将您的对象用作 std::map 中的键。 .

<子>1。如果 rhs 不小于 lhs，并且 lhs 不小于 rhs，则暗示它们相等。您还可以提供替代仿函数，只要它也强制执行严格的弱排序。