6

我正在尝试实现一个简单的比较器，用于根据数组“_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 的数组，其中包含一些我想要计算其排序索引的值。总体目标是在 vals 中的两个（或更多）条目相等时随机化排序顺序。有什么帮助吗？

4

2 回答 2

7

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

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

如果我们将 equiv(a, b) 定义为 !comp(a, b) && !comp(b, a)，那么要求 comp 和 equiv 都是传递关系：

  • comp(a, b) && comp(b, c) 意味着 comp(a, c)
  • equiv(a, b) && equiv(b, c) 意味着 equiv(a, c)

[注：在这些条件下，可以证明

  • equiv 是等价关系
  • comp 在由 equiv 确定的等价类上引入明确定义的关系
  • 诱导关系是严格的全序。

——尾注]

为了澄清起见，表 28 定义了一个等价关系：

==是等价关系，即满足如下性质：

  • 对于所有 a，a == a。
  • 如果 a == b，则 b == a。

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

获得断言而不是随机丢失数据是一种不错的选择。

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

于 2012-09-23T02:40:40.410 回答
3

std::sort期望您的小于运算符提供传递关系，即当排序看到A < B为真并且B < C为真时，它暗示也A < C为真。

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

为相等的值返回 false 以解决此问题。

于 2012-09-23T02:41:46.393 回答