Vector sorting Issue

Блог пользователя AnasAbbas

Автор AnasAbbas, история, 6 лет назад, По-английски

hello everyone

i'm trying to sort a vector using an explicit compare function

why does this simple code gives me Runtime Error sometimes and sometime Time Limit Exceeded

https://ideone.com/MpRvD9

AnasAbbas
6 лет назад
7

Комментарии (7)

Написать комментарий?

VLamarca

6 лет назад, # |

Short answer: You should change:

cost(f)<=cost(s)

cost(f)<cost(s)

→ Ответить

AnasAbbas

6 лет назад, # ^ |

can you give me the long answer please ?

→ Ответить

Jakube

6 лет назад, # ^ |

← Rev. 2 →

+14

Here are the requirements for a Compare function: cppreference Basically the compare function needs to define a strict weak ordering. If your compare function returns true, you're telling the sort function that the first value has to appear before the second element. So if cost(f) == cost(s), then the program thinks that the value f has to appear before s, and also s has to appear before f (because cost(s) == cost(f)). So it doesn't know what to do and gives a runtime error.

→ Ответить

dpaleka

6 лет назад, # ^ |

← Rev. 2 →

Maybe this is helpful?

EDIT: Sniped

→ Ответить

AnasAbbas

6 лет назад, # ^ |

Jakube

dpaleka

thank you very much

→ Ответить

CodingKnight

6 лет назад, # |

← Rev. 4 →

I have just tried to compile and run your code using GNU C++17 Custom Invocation in CF

#include<bits/stdc++.h>
 
using namespace std;
 
int cost(int in)
{
    return in;
}

bool comp( const int f, const int s )
{
    return cost(f) <= cost(s);
}

int main()
{
    auto x = vector<int>( 100000, 0 );
    
    sort( x.begin(), x.end(), comp );
    
    cout << "Done" << endl;
}

The following is the program output:

Done

=====

Used: 2839 ms, 3660 KB

The following is the program output after replacing the <= operator with < operator in the comp function.

Done

=====

Used: 15 ms, 3680 KB

→ Ответить