wannbegood's blog

Compartors in C++
By wannbegood, history, 4 years ago, In English 
#include <bits/stdc++.h>

using namespace std;

bool comp(const int &a , const int&b)
{
    return ((a > 0 and b > 0) ? true : ((a == 0) ? false : true));
}


int32_t main()
{
    vector <int> a = {1 , 0 , 0 , 3 , 12};
    sort(a.begin() , a.end() , comp);
    for(int &x : a)
        cout << x << ", " ;
    cout << endl;
    return 0;
}

The aim is to move all the zeroes to the back keeping the relative order of all other non-zero elements intact. I thought the comparator would do the job as it changes the relative order of two elements a and b if a is equal to 0 and not in any other case, and print the final output as :

0, 0, 1, 3, 12,

However, it printed this :

12, 3, 1, 0, 0,

Why is the comparator failing?

THIS REALLY HELPED : Custom Comparators

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

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

The comparator function in stl:sort requires strict weak ordering. Your comparator causes UB while sorting. Read more here — Geothermal's comment.

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

Looks like you need std::stable_partition

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

read this blog https://codeforces.me/blog/entry/70237

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

    Thanks, that blog was not of much use but I found a link to a good resource in the comments which certainly helped. :).

    Find it here.

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

Auto comment: topic has been updated by wannbegood (previous revision, new revision, compare).

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

There is no need for a custom comparator. The Standard Library already has a function to move all elements that are not equal to a certain value to the front: std::remove. However, it does not necessarily move the "bad" values to the end. So the end of the range is in an undefined state. To overcome this, you can use std::fill. Here is an example.

→ Reply