C++ 集：存储重复项：对 < 运算符感到困惑

Question

我对 C++ 很陌生（但了解 C 的使用方式）所以我可能遗漏了一些明显的东西。

TLDR：我使用 std::set 存储元素两次，这绝对不是我想要的。

长话短说：我已经定义了一个 class Clique，我需要将这个 class 的元素存储在一个集合中，所以我已经为 Clique 定义了 < 运算符：

class Clique{
public :
  int b;
  int e;
  int l;
  std::set<int> X;

  bool operator <( const Clique &rhs ) const
  {
    if( b < rhs.b)
      return true;
    if( e < rhs.e)
      return true;
    if( X.size() < rhs.X.size() )
      return true;
    std::set<int>::iterator itX = X.begin();
    std::set<int>::iterator itrhs = rhs.X.begin();
    // both sets have same size, need only to check end for one of them                                                                                                                                            
    while( (*itX == *itrhs) && ( itX != X.end() ) ){
      ++itX;
      ++itrhs;
    }
    if( itX == X.end() ){
      //both sets are equal                                                                                                                                                                                        
      return false;
    }
    else
      return ( *itX < *itrhs );
  }

  void print_clique(FILE *F) const ;
};

（我不确定集合比较是如何完成的，所以我写了一个例程，先按大小比较它们，然后逐个元素进行比较）。

现在我想将 Clique 元素存储在一个集合中，这就是问题出现的地方。我的 std::set (1) 似乎没有按照我定义的顺序存储 Clique 元素； (2) 存储同一个 Clique

的多个副本

我写了一个函数来打印一组 Clique：

void print_cliqueset(std::set<Clique> mySet){
  int setsize = 0;

  std::set<Clique>::iterator it = mySet.begin();
  Clique cur_c = *it;
  Clique prev_c = *it;
  while( it != mySet.end() ){
  //  for( std::set<Clique>::iterator it = mySet.begin(); it != mySet.end(); ++it ){                                                                                                                               
    it->print_clique(stdout);
    setsize ++;
    ++it;
    if( it != mySet.end() ){
      cur_c = *it;
      assert ( prev_c < cur_c);
      gassert( prev_c.b <= cur_c.b );
    prev_c = *it;
    }
  }

  assert( setsize == mySet.size() );
}

我的功能比需要的更复杂，但我想确保我了解发生了什么。

这是打印此类集合的典型输出：每个 Clique 都有一行，我先打印 b，然后打印 e，然后是集合 X 中的元素。

6829 9716 1 2 3 5 8 9 10 
6792 9687 1 2 3 7 8 9 10 
606 6531 1 2 3 5 6 7 8 9 
6829 9687 1 2 3 5 7 8 9 10 
410 9951 2 6 
484 9805 1 2 4 6 
494 9805 2 4 6 10 
506 9805 1 2 5 6 
484 9821 1 2 4 
484 9871 2 3 4 6 
506 9821 1 2 5 
484 9802 1 2 3 4 6 
486 9805 1 2 4 6 9 
486 9802 1 2 3 4 6 9 
507 9802 1 2 3 4 6 9 10 
502 9802 1 2 3 4 6 10 
506 9802 1 2 3 5 6 
507 9806 1 2 4 9 10 
507 9805 1 2 5 6 9 
527 9806 1 2 5 9 10

正如我们所见，派系根本没有按照我定义（或想要定义）的顺序排序。它们应该首先按成员 b 排序（这是每行的第一个），而根本不是这样。

然后我在输出中有一些重复的行（没有出现在上面的示例中，但出现在完整的输出中）。我想我有重复的事实并不奇怪，因为它似乎对顺序感到困惑......

我想答案很明显，但我看不到。如有任何帮助，我们将不胜感激！

Answer 1

你的 operator< 坏了。考虑两个 Cliques:

c1 is {b = 0, e = 1, ...}
c2 is {b = 1, e = 0, ...}

对于 c1 < c2 和 c2 < c1，您的代码将 return true。

显然，在这种情况下 std::set 表现出奇怪的行为。

我会按以下方式修复您的 operator<：

bool operator <( const Clique &rhs ) const
{
    if( b != rhs.b)
        return b < rhs.b;
    if( e != rhs.e)
        return e < rhs.e;
    if( X.size() != rhs.X.size() )
        return X.size() < rhs.X.size();
    std::set<int>::iterator itX = X.begin();
    std::set<int>::iterator itrhs = rhs.X.begin();
    // both sets have same size, need only to check end for one of them
    while((itX != X.end()) && (itX == *itrhs)){
        ++itX;
        ++itrhs;
    }
    if( itX == X.end() ){
    //both sets are equal
        return false;
    }
    else
        return ( *itX < *itrhs );
}

Answer 2

您的 bool operator <( const Clique &rhs ) const 是错误的，因为它不遵守严格的顺序。

可能只是：

bool operator <(const Clique& rhs) const
{
    return std::tie(b, e, X) < std::tie(rhs.b, rhs.e, rhs.X);
}

Answer 3

operator< 的定义应该是这样的，对于每对元素 'b' 和 'e' 应该使用关系 b < e 来确定 any种关系。以下等效项在这里生效：

a > b <==> b < a

a == b <==> !(a < b) && !(b < a)

a >= b <==> `!(a < b)

等等。如果您为每个关系检查使用多个字段进行检查，那么您就有了一种多维范围。只能通过这种方式从中得出一个平坦的范围：

首先检查更重要的字段；如果此字段中的值不相等，您 return 立即得到结果
否则 - 如果它们相等 - 你检查重要性顺序中的下一个字段等等。

在集合中使用这种复杂关系定义的要求实际上让事情变得更难了，因为您要做的就是说明一个元素是否小于另一个元素。因此，在您的情况下，您必须自己检查内部的 equality 。您的程序检查字段 "next in significance chain" also if lhs.b > rhs.b.

Answer 4

运算符 < 必须提供严格的弱排序。 IE。如果 x < y 那么 !(y < x) 和 !(y == x).

在Clique的情况下，要求好像是元素b,e,X按字典序比较

表示这一点的惯用方法是根据 operator<:

进行所有比较

#include <set>

class Clique{
public :
    int b;
    int e;
    int l;
    std::set<int> X;

    bool operator <( const Clique &r ) const
    {
        auto const& l = *this;

        if (l.b < r.b) return true;
        if (r.b < l.b) return false;

        if (l.e < r.e) return true;
        if (r.e < l.e) return false;

        if (l.X < r.X) return true;
        if (r.X < l.X) return false;

        return false;
    }

    void print_clique(FILE *F) const ;
};

是的，std::set 在密钥类型提供时确实提供了 operator<。

另一种写法，正如 Jarod 所暗示的那样：

#include <set>
#include <tuple>

class Clique{
public :
    int b;
    int e;
    int l;
    std::set<int> X;

    bool operator <( const Clique &r ) const
    {
        auto const& l = *this;
        return std::tie(l.b, l.e, l.X) < std::tie(r.b, r.e, r.X);
    }

    void print_clique(FILE *F) const ;
};

我想你会同意的是简洁、表达、正确和地道。

C++ 集：存储重复项：对 < 运算符感到困惑

C++ set: storing duplicates: confused about < operator

c++

std

set