使用动态数组错误进行排序

时间:2021-07-09 15:58:11

There are plenty of examples on how to use std::sort() with a std::vector. For my specific homework assignment, I'm not allowed to use an std::vector, so I instead want to use std::sort() on a dynamic array of custom objects.

关于如何使用std::sort()和std:::vector的例子有很多。对于特定的家庭作业,我不允许使用std::vector,所以我想在定制对象的动态数组上使用std::sort()。

Like so:

像这样:

int numberOfRoads = 100000;
Road* roads = new Road[numberOfRoads];
// Assume the comparator is defined correctly (<- this was the problem)
std::sort(roads, roads + numberOfRoads, SortRoadsComparator);

And here is the main compiler error I receive:

这是我收到的主要编译错误:

C:\Program Files (x86)\Microsoft Visual Studio 11.0\VC\include\algorithm(3781): error C2664: 'int (const void *,const void *)' : cannot convert parameter 1 from 'Road' to 'const void *'
1>          No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called

I receive this error about 20 times. What exactly is it requiring me to do?

我收到这个错误大约20次。到底需要我做什么?

SortRoadsComparator()

SortRoadsComparator()

int SortRoadsComparator(void const *v1, void const *v2)
{
    Road *a = (Road *)v1;
    Road *b = (Road *)v2;

    if (a->Length > b->Length) 
        return 1;

    else if (b->Length > a->Length) 
        return -1;

    else
    {
        // Non-determinism case
        if (a->Length == b->Length)
        {
            if ( (min(a->CityA, a->CityB) < min(b->CityA, b->CityB)) ||
                 (
                      (min(a->CityA, a->CityB) == min(b->CityA, b->CityB)) && max(a->CityA, a->CityB) < max(b->CityA, b->CityB)                                   
                 )
               )
            {
                return -1;
            }
            else
            {
                return 1;
            }
        }
        else
        {
            // Not expecting this
        }
    }
}

Solved by billz's comment.

解决billz的评论。

2 个解决方案

#1


2  

SortRoadsComparator function prototype should be:

SortRoadsComparator函数原型应该是:

bool SortRoadsComparator(Road const& v1, Road const& v2);

You should make sure SortRoadsComparator returns weak ordered Road.

你应该确保SortRoadsComparator返回弱有序的道路。

#2


3  

It requires you to pass proper comparator into std::sort. If you read std::sort documentation you can see that it requires following signature:

它要求您将适当的比较器传递到std::sort。如果您阅读std:::sort文档,您会发现它需要以下签名:

bool cmp(const Type1 &a, const Type2 &b);

and:

和:

The types Type1 and Type2 must be such that an object of type RandomIt can be dereferenced and then implicitly converted to both of them.

Type1和Type2的类型必须是随机类型的对象,可以取消引用,然后隐式地转换为这两个类型。

So in your case dereferenced "iterator" roads has type Road& and function could be something like:

所以在你的例子中,取消引用的"迭代器"道路有公路类型&函数可以是这样的:

bool cmp( const Road &a, const Road &b );

PS Looks like you are porting qsort code into C++. Though suggestion to make signature to:

PS看起来您正在将qsort代码移植到c++中。建议签字:

int cmp( const Road &a, const Road &b );

will compile, it is logically incorrect and would hide the fact that you need to change returned values in your function and slightly change the logic. In current implementation std::sort will most probably crash, but definatelly will not sort your sequence the way you expect it to.

将编译,它在逻辑上是不正确的,并将隐藏需要更改函数中返回的值并稍微更改逻辑的事实。在当前的实现中,std::sort很可能会崩溃,但是显然不会按照预期的方式对序列排序。

#1


2  

SortRoadsComparator function prototype should be:

SortRoadsComparator函数原型应该是:

bool SortRoadsComparator(Road const& v1, Road const& v2);

You should make sure SortRoadsComparator returns weak ordered Road.

你应该确保SortRoadsComparator返回弱有序的道路。

#2


3  

It requires you to pass proper comparator into std::sort. If you read std::sort documentation you can see that it requires following signature:

它要求您将适当的比较器传递到std::sort。如果您阅读std:::sort文档,您会发现它需要以下签名:

bool cmp(const Type1 &a, const Type2 &b);

and:

和:

The types Type1 and Type2 must be such that an object of type RandomIt can be dereferenced and then implicitly converted to both of them.

Type1和Type2的类型必须是随机类型的对象,可以取消引用,然后隐式地转换为这两个类型。

So in your case dereferenced "iterator" roads has type Road& and function could be something like:

所以在你的例子中,取消引用的"迭代器"道路有公路类型&函数可以是这样的:

bool cmp( const Road &a, const Road &b );

PS Looks like you are porting qsort code into C++. Though suggestion to make signature to:

PS看起来您正在将qsort代码移植到c++中。建议签字:

int cmp( const Road &a, const Road &b );

will compile, it is logically incorrect and would hide the fact that you need to change returned values in your function and slightly change the logic. In current implementation std::sort will most probably crash, but definatelly will not sort your sequence the way you expect it to.

将编译,它在逻辑上是不正确的,并将隐藏需要更改函数中返回的值并稍微更改逻辑的事实。在当前的实现中,std::sort很可能会崩溃,但是显然不会按照预期的方式对序列排序。