Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

confusion about using std::less and std::greater with std::sort

Tags:

c++

c

sorting

std

stl

In C, sort usually implements as in the following example:

#include <stdio.h>

void Sort( int* arr, int n, bool(*cmp)(int,int) )
{
    for( int i=0; i<n-1; i++ )
    {
        for( int j=i+1; j<n; j++ )
        {
            if( cmp(arr[i], arr[j]) )
                swap( arr[i], arr[j] );
        }
    }
}

int ascending( int a, int b ) { return a > b; }    // greater
int descending( int a, int b ) { return a < b; }   // less

void main()
{
    int arr[10] = { 1,3,5,7,9,2,4,6,8,10 };

    // ascending
    Sort( arr, 10, ascending );
    for( int i=0; i<10; i++ )
        printf( "%d ", arr[i] );

    printf( "\n" );


    // descending
    Sort( arr, 10, descending );
    for( int i=0; i<10; i++ )
        printf( "%d ", arr[i] );

    printf( "\n" );
}

So I wrote some source as in the following example, expecting same result:

#include <iostream>
#include <algorithm>    // for sort
#include <functional>   // for less & greater
using namespace std;

bool gt( int a, int b ) { return a > b; }   // greater
bool ls( int a, int b ) { return a < b; }   // less

void main()
{
    int x[10] = { 1,3,5,7,9,2,4,6,8,10 };

    // ascending but descending
    sort( x, x+10, gt );
    for( int i=0; i<10; i++ )
        cout << x[i] << " ";

    cout << endl;

    // descending but ascending
    sort( x, x+10, ls );
    for( int i=0; i<10; i++ )
        cout << x[i] << " ";

    cout << endl;


    greater<int> g; // a > b
    less<int> l;    // a < b

    // ascending but descending
    sort( x, x+10, g );
    for( int i=0; i<10; i++ )
        cout << x[i] << " ";

    cout << endl;

    // descending but ascending
    sort( x, x+10, l );
    for( int i=0; i<10; i++ )
        cout << x[i] << " ";

    cout << endl;
}

But my expectation was not correct.

Why does not sort in STL work like sort in C?

like image 636
user2063889 Avatar asked Feb 12 '13 08:02

user2063889


2 Answers

std::sort sorts in ascending order by default. In case you are looking for descending order, here's the trick:

int x[10] = { 1,3,5,7,9,2,4,6,8,10 };
std::vector<int> vec(x, x+10);          // construct std::vector object
std::sort(vec.rbegin(),vec.rend());     // sort it in reverse manner

This way, you explicitly say that std::sort should treat your array as its end is its beginning and vice versa, which results in your array being sorted in descending order. Here's the full example.


And in case you want to use std::less and std::greater, then it could look like this:

int x[10] = { 1,3,5,7,9,2,4,6,8,10 };
std::sort(x, x + 10, std::less<int>());     // for ascending order
std::sort(x, x + 10, std::greater<int>());  // for descending order

Full example with second solution is here.

like image 163
LihO Avatar answered Nov 10 '22 14:11

LihO


std::sort behaves like that because it's based on the idea of a strict weak ordering, which is (usually) defined in terms of the < operator.

As to your question; it currently seems to be "I wrote a C function that behaves differently to std::sort. Why is it different?". The answer is: because you wrote a different function!

like image 40
Oliver Charlesworth Avatar answered Nov 10 '22 13:11

Oliver Charlesworth