AnasAbbas's blog

Vector sorting Issue
By AnasAbbas, history, 4 years ago, In English

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

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Short answer: You should change:

cost(f)<=cost(s)

to

cost(f)<cost(s)
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you give me the long answer please ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +14 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Maybe this is helpful?

      EDIT: Sniped

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Jakube

      dpaleka

      thank you very much

      → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

→ Reply