CODEWITHSUNDEEP
c++sortingcomparator
zengweitotty
zengweitotty

Reputation: 3

Sort/stable_sort custom compare function cause some strange issues

I have very basic experience of custom function for sort/stable_sort API.
Below is the source code I am running under Windows Visual Studio 2017.
Please help analyze what is the problem, do I miss anything or what is the theory behind? Thanks for the help

// 10_3_1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX_INPUT_NO    (10u)

typedef bool(* sort_func_t)(const int input_a, const int input_b);

bool is_shorter(const int input_a, const int input_b)
{
#if 0
    //this portion will show the iteration overlap
    if (input_a > input_b)
        return false;
    else
        return true;
#else
    //both below works
    //return input_a < input_b;
    return input_a > input_b;

#endif
}

void elimDups(vector<int> &dat, sort_func_t func)
{
    vector<int>::iterator temp = dat.begin();
    std::stable_sort(dat.begin(), dat.end(), func);
    //sort(dat.begin(), dat.end());

    temp = unique(dat.begin(), dat.end());
    dat.erase(temp, dat.end());
}

void print_vec(vector<int> &dat)
{
    vector<int>::const_iterator index = dat.cbegin();
    int i = 0;
    for (; index < dat.cend(); index++)
    {
        cout << "dat[" << i << "] = " << dat.at(i++) << endl;
    }
}

int main()
{
    vector<int> a;
    int ia[MAX_INPUT_NO] = {0, 1, 2, 1, 2, 3, 1, 2, 4, 5};
    a.assign(ia, ia + MAX_INPUT_NO);
    print_vec(a);
    elimDups(a, is_shorter);
    print_vec(a);

    getchar();
    return 0;
}

But the problem I face when I play with if-else portion, it gives me the invalid comparator assert error.

  1. If I define the custom function like below use the if-else pattern, it works fine.
bool is_shorter(const int input_a, const int input_b)
{
#if 1
    //this portion will show the iteration overlap
    if (input_a > input_b)
        return true;
    else
        return false;
#else
    //below works
    return input_a > input_b;
#endif
}

Below is the result I get.

expect result from item 1

  1. If I define the custom comparator function like below, it also uses the if-else pattern, it will fail with "Invalid comparator" Error.
bool is_shorter(const int input_a, const int input_b)
{
#if 1
    //this portion will show the iteration overlap
    if (input_a > input_b)
        return false;
    else
        return true;
#else
    //below works
    return input_a > input_b;
#endif
}

Below is the error message I get:

error message from visual studio 2017

  1. But if I just use return, then it works fine for both direction.
bool is_shorter(const int input_a, const int input_b)
{
#if 0
    //this portion will show the iteration overlap
    if (input_a > input_b)
        return false;
    else
        return true;
#else
    //both below works
    //return input_a < input_b;
    return input_a > input_b;

#endif
}

Upvotes: 0

Views: 376

Answers (1)

Slava
Slava

Reputation: 44268

This code:

if (input_a > input_b)
    return false;
else
    return true;

is convoluted way to say:

return !(input_a > input_b);

and negation of greater then is less or equal:

return input_a <= input_b; // logically same as before

The problem is you cannot use less or equal relation for sorting as it does not provide strict weak ordering the algorithm requires. You can use less though:

return input_a < input_b;

or greater then as you used in your code when it works.

Upvotes: 1

Related Questions