c++ - 在 std::set 中使用 operator != 作为 operator < 是否安全？

Question

我有一个包含一些成员的结构，并且我有一个实现的 operator== 。在 operator== 的帮助下实现 operator< 是否安全？我想在一个集合中使用这个结构，并且我想检查这个结构是否是唯一的。

struct Data
{
  std::string str1;
  std::string str2;
  std::string str3;
  std::string str4;

  bool operator==(const Data& rhs)
  {
    if (str1 == rhs.str1
     && str2 == rhs.str2
     && str3 == rhs.str3
     && str4 == rhs.str4
       )
      return true;
    else
      return false;
  }

  // Is this ok??
  bool operator<(const Data& rhs)
  {
    return !this->operator==(rhs);
  }
}

那么当我将这个结构插入到 std::set 时会发生什么？

score 9 · Accepted Answer

不，这很不安全。实现它的最简单方法是通过std::tie.

#include <tuple>
struct Data
{
  std::string str1;
  std::string str2;
  std::string str3;
  std::string str4;

  bool operator<(const Data& rhs) const // you forgot a const
  {
      return 
      std::tie(str1, str2, str3, str4) < 
      std::tie(rhs.str1, rhs.str2, rhs.str3, rhs.str4);
  }
}

score 6 · Accepted Answer

不，那不安全。您定义的方式<，a < b并且b < a将同时为真。

那么当我将这个结构插入到 std::set 时会发生什么？

该行为是未定义的，因此任何事情都是允许的，并且在不同的实现中可能会有所不同。

score 3 · Accepted Answer

好吧，您的代码表明 if A!=B，这意味着A<B这绝对是错误的，因为它也可以是A>B。

您将必须以与使用相同的方式实现您的>和运算符，这意味着通过逐个比较对象。由您决定如何根据其成员来确定是“更多”还是“更少” 。<operator==AB

如果您使用任何标准库容器中的操作符，您将获得 UB。

score 2 · Accepted Answer

你需要用operator<自己的术语来定义。你不能operator<根据来实现operator==，尽管你可以做相反的事情。

考虑这个真值表中的悖论：

"a" < "b" : TRUE
"b" < "a" : TRUE

如果您的实现operator<产生了上述悖论，如果您按照以下方式实现它，operator==那么您没有正确实现严格的弱排序。你实施的是一团糟。

您需要确定哪些成员字符串优先于其他字符串，然后按从最重要到最不重要的顺序在它们之间进行比较。

例如，如果字符串的优先级是，从最重要到最不重要：

str1
str2
str3
str4

...然后这会产生以下算法operator<：

bool operator<(const Data& rhs) const
{
  if( str1 < rhs.str1 )
    return true;
  if( rhs.str1 < str1 )
    return false;
  if( str2 < rhs.str2 )
    return true;
  if( rhs.str2 < str2 )
    return false;
  if( str3 < rhs.str3 )
    return true;
  if( rhs.str3 < str3 )
    return false;
  if( str4 < rhs.str4 )
    return true;
  if( rhs.str4 < str4 )
    return false;

  return false;
}

使用它，您可以选择operator==根据operator<. 您假设这样做的时间复杂度固有的低效率，但是：

bool operator==(const Data& rhs) const
{
  return !operator<(rhs) && !rhs.operator<(*this);
}

c++ - 在 std::set 中使用 operator != 作为 operator < 是否安全？

4 回答 4

Related

Reference