1

我试图运行下面的代码。我发现输出存在差异。我了解比较器功能中使用的排序机制存在问题。我基本上要寻找的是：1）Set如何在内部存储数据。2）如何解决此问题或将数据复制到不同集合的最佳方法。3）排序究竟是如何产生这个问题的。

#include <iostream>
#include <set>
using namespace std;
struct Comparator {
  bool operator()( const int& a, const int& b ) {
    if( a <= b ) 
      return true;
    else
      return false;
  }
};
int main()
{
  set< int, Comparator > customSet;
  for( unsigned k = 0, index = 2; k < 10; ++k ) {
    customSet.insert( index );
  }

  set< int, Comparator >::iterator iter = customSet.begin();
  for(; iter != customSet.end(); ++iter ) {
    cout<<*iter<<endl;
  }

  cout<<"---------------------------------"<<endl;
  set< int, Comparator > tempCustomSet ;//= customSet;
  tempCustomSet.insert( customSet.begin(), customSet.end() );

  iter = tempCustomSet.begin();
  for(; iter != tempCustomSet.end(); ++iter ) {
    cout<<*iter<<endl;
  }

  return 0;
}
4

4 回答 4

2

有关. _ _ std::set实现不应该与您有关（它们可能因平台而异），因为接口和复杂性保证对标准来说是最重要的。典型的实现是使用red-black-trees。

您需要Comparator使用operator<而不是operator<=. 原因是如果评估为（即两者都不严格小于另一个） ，std::set则将认为元素等效。!Comparator(a, b) && !Comparator(b, a)true

但是有了<=，你就有a <= a等于true，所以!(a<=a) && !(a<=a)给出false了相等的元素。而<你有a < a等于false所以!(a<a) && !(a<a)给true。

做事的权利是：

struct Comparator 
{
    bool operator()(int const& lhs, int const& rhs) const 
    {
        return lhs < rhs; 
    }
};

这将保证相等的元素被认为是等价的。请注意，这在Effective STL中详细讨论，“第 19 项。理解相等和等价之间的区别”。

于 2013-01-29T12:42:46.350 回答
2

问题很可能是因为您的比较没有实现严格的弱排序。集合上的内部排序机制依赖于此。您可以通过将比较更改为小于来获得 SWO：

struct Comparator {
  bool operator()( const int& a, const int& b ) const {
    return ( a < b ); 
  }
};

另一方面，std::set默认情况下将使用此比较标准，因此您无需指定它。

我对这个问题的回答中有一些相关信息（以及无数其他 SO 问题）。

于 2013-01-29T12:46:12.423 回答
2

1）Set如何在内部存储数据

唯一的要求是元素是：

  • 根据比较器排序，以便在迭代集合时出现在if Comp(a,b)、 then之前；ab
  • 独特的，因此没有不同的元素同时Comp(a,b)适用Comp(b,a)。

并且操作满足一定的复杂性要求。

在实践中，它们通常存储在二叉搜索树中；但这对用户来说并不重要。

2）如何解决此问题或将数据复制到不同集合的最佳方法

为了满足要求，比较器必须是严格的弱排序，like <，这样Comp(a,a)总是假的，而不是非严格排序的 like <=。由于<是默认设置，这意味着您根本不需要自定义比较器。

3）排序究竟是如何产生这个问题的

请注意，您的第一个循环是插入值2十次；我不确定这是否是故意的。

给定所需的严格排序，insert(b)可能会通过查找第一个为 false的元素a来查找插入点；Comp(a,b)即b不应该出现的第一个元素。然后它将通过检查来检查唯一性Comp(b,a)。如果两者都为假，则表明这两个值是等价的，所以b不会被插入。

由于您的比较不严格，因此此唯一性测试可能会失败；所以你最终可能会得到一个重复的条目。或者可能发生其他事情 - 行为未定义。

于 2013-01-29T13:05:16.020 回答
0

在两种情况下，您会得到不同的输出，因为您是inserting in different ways. 在案例 1 中，您将元素 2 插入十次。在这种情况下，当您在第一次之后插入整数 2 时，Comparator()将调用您的函数来决定插入的位置。在另一种情况下，您正在插入一个范围。在这里，被调用函数接受第一个参数 i,ecustomSet.begin()并与另一个参数 i,e 进行检查customSet.end()，如果这两个不相等，则只插入一个元素，否则将不会插入元素。

于 2014-05-26T09:18:15.577 回答