无效<在排序

我想实现在一个阵列“_vec”排序基于价值指数的简单比较运营商断言。我收到一个“无效<运营商”的运行时错误消息。我不明白什么是错用下面的代码：无效<在排序

class Compare{ 
vector<int>& _vec; 
public: 
    Compare(vector<int>& vec) : _vec(vec) {} 
    bool operator()(size_t i, size_t j){ 
     if(_vec[i] != _vec[j]) 
     return _vec[i] < _vec[j]; 
     else 
     return (double)rand()/RAND_MAX < 0.5; 
    } 
};

我使用下面的函数调用：

sort(inds.begin(),inds.end(),Compare(vals));

其中INDS只是含指数从1到15的阵列（说）和vals是长度为15的数组，其中有些值的排序索引要计算。总体目标是在val中的两个（或更多）条目相等时随机排序。任何帮助？

来源

2012-09-23 archaic

你应该使用尾部下划线（或别的东西来区分这些）[而不是领先的下划线]（http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore -in-AC-标识符）。 –

@Brian：由于这些不是文件范围，并且下划线后面没有大写字母，因此只要不被保留就可以。尽管如此，这一领域引起了另一个命名约定可能会让一些人更快乐的混淆。 –

注意 - 如果'vals'的长度为15，那么'inds'最好包含[0..14]范围内的索引，而不是[1..15]。 –

std::sort()预计比较操作是稳定的 - 如果在比较两个项目时返回特定结果，则比较必须返回相同的结果，如果这些项目稍后再次进行比较。当你返回一个随机值时，显然这不一定成立。

C++ 03 25.3/4 “排序和相关操作” 说：

如果我们定义当量（A，B）作为补偿（A，B）& &补偿（二，一！），则要求是排版和当量两者可传递关系：

排版（A，b）& &排版（b，C）意味着排版（A，C）

当量（一， b）& &当量（B，C）意味着当量（A，C）

[注意：在这些条件下，它可以表明

当量是一个等价关系

排版诱导的阱由当量

感应关系确定等价类-defined关系是有严格的总次序。

末端音符]

而澄清，表28限定的等价关系：

==是一个等价关系，即，它满足以下属性：

对于所有A，A ==一。

如果== B，则b ==一。

所以你Compare()操作不会产生等价关系。

这是一种很好的得到一个断言，而不是随机丢失数据。

解决当_vec中的两个（或多个）条目相同时排序顺序随机化的问题的一种方法是为这些索引组成随机值，并在index =>映射中跟踪这些随机值。随机值或其他东西。只要确保您跟踪并使用那些随机值，以便Compare()的传递和等价属性成立。

来源

2012-09-23 02:40:40

谢谢迈克尔。我现在明白了问题所在。基于你的建议，我找到了一个解决方法：我现在将一个随机数（长度为15）的向量传递给Compare（），当两个值相等时，它用于打破平局。这样Compare（）的传递和等价属性就成立了。 – archaic

std::sort期待您低于运营商提供一个传递关系，即当某种看到A < B是真实的，B < C是真的，这意味着那是A < C也是如此。

在您的实现中，传递性规则不成立：当两个项目相等时，您随机地告诉排序其中一个大于另一个。这会触发调试断言。

对于相同的值返回false以解决此问题。

来源

2012-09-23 02:41:46 dasblinkenlight

可以使用standatd库提供的'std :: vector'的'operator <'来轻松实现。 – juanchopanza

回答

相关问题