无效& lt;运算符断言 [英] 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的数组，其中包含一些我想计算其排序索引的值.总体目标是当val中的两个(或多个)条目相等时，将排序顺序随机化.有帮助吗?

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.

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