logo标签列表

C++集合：存储重复元素：关于<运算符感到困惑

c++setstd
3

我对C++还很新（但了解C），所以我可能会错过一些显而易见的东西。

简单来说：我使用一个std::set，其中存储元素两次，这绝对不是我想要的。

长话短说： 我定义了一个类Clique，并且需要将该类的元素存储在一个集合中，因此我为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排序（即每行的第一个成员），但实际情况并非如此。
然后，输出中有一些重复行（在上面的示例中未出现，但完整输出中存在）。考虑到它似乎对顺序感到困惑，我猜有重复行并不奇怪...
我猜答案可能是相当显而易见的，但我看不到它。任何帮助将不胜感激！
你使用哪个C++标准？解决方案的复杂度取决于此。 - Dmitry T.
您的比较器需要遵循等价关系，如此std::set参考中所指定的那样。 - Some programmer dude
顺便提一下，成员变量 int l; 没有被比较。 - Jarod42
4个回答
4
你的operator<有问题。考虑两个Clique:
c1 is {b = 0, e = 1, ...}
c2 is {b = 1, e = 0, ...}

你的代码将对和两种情况都返回。
很明显，在这种情况下，表现出奇怪的行为。
我会按照以下方式修复你的:
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 );
}
set的比较是错误的：（解引用end迭代器）。而operator < (const std::set<T>&, const std::set<T>&)就足够了。 - Jarod42
你说得对，会修复解引用。我不知道作者以这种方式定义operator<的目的，所以我不想改变行为。如果唯一的目标是将Clique存储在std::set中，那么它足够了（应该使用更易读和可维护的方式）。 - alexeykuzmin0
我简直不敢相信我写的比较方式有这么多缺陷！感谢您提出的改正建议！（事实上，我并不需要任何特定集合比较，我只是想要一个能为集合提供_任何_排序的函数，因此我不需要while循环，可以直接使用<）。 - chlorine
4

您的 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);
}
这个 operator< 的行为将与作者定义的不同。std::set::operator< 按字典顺序比较集合。 - alexeykuzmin0
1
@alexeykuzmin0：这也是 OP 尝试做的事情（除了大小检查）。据我所知，OP 只想要一个有效的运算符 < 以便在 std::set 中使用它。 - Jarod42
正是我所需要的，谢谢。我之所以引入集合比较，是因为我不确定 < 在集合中的作用，而在我的调试过程中，我有一段时间感到害怕它会比较集合的引用而不是内容。 - chlorine
@chlorine 我强烈建议你收藏这个网站：http://en.cppreference.com/w/cpp/container/set/operator_cmp 如果你对编写正确、惯用的代码感兴趣，那么你会发现它是非常有价值的。 - Richard Hodges
1
运算符operator<的定义应该是这样的，对于每一对元素'b'和'e'，关系b<e应该用来确定任何种类的关系。以下等式在此处适用: a>b <==> b<a a==b <==> !(a<b) && !(b<a) a>=b <==> `!(a<b)
等等。如果您使用多个字段来检查每个关系检查，则具有某种多维范围。将其制成平面范围只能通过以下方式完成:
  • 首先检查更重要的字段; 如果在此字段中值不相等，则立即返回结果
  • 否则 - 如果它们相等 - 按重要性顺序检查下一个字段，以此类推。
在集合中使用这种复杂的关系定义要求你做的事情实际上更加困难，因为你只需要说明一个元素是否小于另一个元素。所以在你的情况下，你将不得不自己检查相等性。你的过程会检查字段“下一个重要链”也会检查lhs.b > rhs.b。
是的，这是我感到羞愧的事情，因为我自己没有理解。谢谢你的解释！ :) - chlorine
1

运算符<必须提供严格弱序。即如果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 ;
};

我认为您会同意这是简洁、表达准确、符合习惯用语的。

我同意！:) 谢谢你详细的解释。:) - chlorine
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接