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

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

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Short answer: You should change:

cost(f)<=cost(s)

to

cost(f)<cost(s)
→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you give me the long answer please ?

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← 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.

      → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Maybe this is helpful?

      EDIT: Sniped

      → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Jakube

      dpaleka

      thank you very much

      → Ответить
»
7 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить