无效排序中的运算符断言 [英] Invalid < operator assertion in sort

问题描述

我正在尝试实现一个简单的比较器，用于根据数组_vec"中的值对索引进行排序.我收到一条无效的 < 运算符"运行时错误消息.我不明白以下代码有什么问题:

I am trying to implement a simple comparator for sorting indices based on values in an array "_vec". I am getting an "invalid < operator" run-time error message. I fail to understand what is wrong with the following code:

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; 
    }
};

我正在使用以下函数调用:

I am using the following function call:

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

其中 inds 只是一个包含从 1 到 15(比如说)索引的数组，而 vals 是长度为 15 的数组，其中包含一些我想要计算其排序索引的值.总体目标是在 vals 中的两个(或更多)条目相等时随机化排序顺序.有什么帮助吗?

where inds is just an array containing indices from 1 to 15 (say) and vals is the array of length 15 with some values whose sorted indices I want to compute. The overall goal is to randomize the sort order when two (or more) entries in vals are equal. Any help?

推荐答案

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

std::sort() expects the comparison operation to be stable - if a particular result is returned when two items are compared, the comparison must return the same result if those items are compared again later. When you return a random value, obviously that's not necessarily going to hold.

C++03 25.3/4排序和相关操作"说:

C++03 25.3/4 "Sort and related operations" says:

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

If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations:

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

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

[Note: Under these conditions, it can be shown that

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

——结束注释]

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

And for clarification, Table 28 defines an equivalence relation:

== 是一个等价关系，即满足如下属性:

== is an equivalence relation, that is, it satisfies the following properties:

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

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

So your Compare() operation will not produce an equivalence relation.

获得断言比随机丢失数据更好.

It's kind of nice to get an assertion rather than losing data randomly.

当 _vec 中的两个(或多个)条目相等时，解决排序顺序随机化问题的一种方法是为这些索引组成一个随机值并跟踪这些随机值索引图 => 随机值之类的.只要确保您跟踪和使用这些随机值，以便 Compare() 的传递和等价属性成立.

One way to solve the problem of randomizing the sort order when two (or more) entries in _vec are equal is to make up a random value for those indexes and keep track of those random values in a map of index => random value or something. Just make sure that you keep track of and use those random values in such a way that the transitive and equivalence properties of Compare() hold.

这篇关于无效排序中的运算符断言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！