Standard Library Sort and User Defined Types

Standard library sort and user defined types

It is possible to use standard function if your type implements "bool operator < (...) const" and a copy constructor (compiler-generated or custom).

struct MyType {
    int a;
    int b;
    bool operator < (const MyType& other) const {
        ... // a meaningful implementation for your type
    }
    // Copy constructor (unless it's a POD type).
    MyType(const MyType &other)
        : a(other.a), b(other.b) { }
    // Some other form of construction apart from copy constructor.
    MyType()
        : a(0), b(0) { }
};

Alternatively, you can pass an ordering function (or a functor) as a third argument to sort() instead of implementing operator "<".

bool type_is_less(const MyType& t1, const MyType& t2) { ... }
...
std::sort(c.begin(), c.end(), type_is_less);

This is useful in the following situations:

1. you don't want to implement operator "<" for whatever reason,
2. you need to sort a container of built-in or pointer types for which you can't overload operators.
3. you wish to sort the sequence using different orderings. ex: sometimes you want a struct with first/last name members sorted by first name, other times by last name. two different functions (or functors) make such options trivial.

why does std::sort not require the user to specify the templated types?

or is it being automatically deduced...?

Yes.

When a template parameter is used for a function parameter, the template argument can be deduced from the argument passed to the function. So, in this case RandomIt is deduced from the arguments data.begin() and data.end().

Explain the working of compare predicate of standard library sort function C++?

While refering to standard is fine, understanding it can sometimes be quite hard...

Trying in simpler words:

If you want to sort elements, you need some kind of order relation that defines which of two elements shall come first ("be the smaller one"). Some data types come with a natural order, such as integral numbers, for instance: -12 < -10 - 0 - 10 < 12. std::sort (without comparison parameter) uses this natural order to sort elements ascending.

The third parameter gives you the possibility to tell std::sort explicitly how this order shall be defined, imagine the following:

std::vector v({12, 7, 10});
std::sort(v.begin(), v.end(), [](int x, int y){return x > y;});

Looks unnatural, doesn't it? std::sort interprets the comparison as "less", but we implemented a "greater"! By doing so, the greater values then (as considered being "smaller") are sorted in front of smaller ones (considered being "greater"), so we have achieved sorting in descending order...

So the comparison parameter passed to std::sort is used to either sort differently to what the natural order would be or to define explicitly an order for data types where such order does not exist.

Side note: The order relation does not necessarily have to be a total order; however, equivalent elements then can be sorted in arbitrary order (you could, though, use std::stable_sort instead to at least preserve their relative order before sorting):

int a[12, 7, 10, 7];
std::vector<int*> v({&a[0], &a[1], &a[2], &a[3]});
std::sort(v.begin(), v.end(), [](int* x, int* y) { return *x < *y; });
// v[2] == &a[2]
// v[3] == &a[1]
// BUT:
// v[0] == &a[1] && v[1] == &a[3] || v[0] == &a[3] && v[1] == &a[1]

Sorting a vector of custom objects

A simple example using std::sort

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}
};

struct less_than_key
{
    inline bool operator() (const MyStruct& struct1, const MyStruct& struct2)
    {
        return (struct1.key < struct2.key);
    }
};

std::vector < MyStruct > vec;

vec.push_back(MyStruct(4, "test"));
vec.push_back(MyStruct(3, "a"));
vec.push_back(MyStruct(2, "is"));
vec.push_back(MyStruct(1, "this"));

std::sort(vec.begin(), vec.end(), less_than_key());

---

Edit: As Kirill V. Lyadvinsky pointed out, instead of supplying a sort predicate, you can implement the operator< for MyStruct:

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator < (const MyStruct& str) const
    {
        return (key < str.key);
    }
};

Using this method means you can simply sort the vector as follows:

std::sort(vec.begin(), vec.end());

Edit2: As Kappa suggests you can also sort the vector in the descending order by overloading a > operator and changing call of sort a bit:

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator > (const MyStruct& str) const
    {
        return (key > str.key);
    }
};

And you should call sort as:

std::sort(vec.begin(), vec.end(),greater<MyStruct>());

Sort function from standard library gives an error using an iterator

Ok let's sort things out one by one.

First about your error message. Your vector stores pointers and keep in mind that a->b is equivalent to (*a).b, so open_list.begin()->h_value equals to open_list.front().h_value, and a pointer clearly doesn't have member variable. To refer to the member variable, you need to write (*open_list.begin())->h_value. Furthermore, dereferencing .end() gives you undefined behaviour immediately. To access the last element of std::vector, use .back() instead of *(you_vector.end()). (Remember to check the vector is not empty beforehand! Otherwise you will step into undefined behaviour again :) )

Secondly your idea about how to use std::sort is wrong. To sort a range of elements by a "standard" you chose, the first two parameters of sort provide the information about the range, and the third parameter is your "standard", so it must be a "callable", and it takes two parameters and tell std::sort whether the first parameter should be sorted before the second. As a result, to sort v in descending order, you need to call std::sort in the following way:

std::sort(v.begin(), v.end(), [](int a,int b)->bool{ return a > b;});

Here, the third parameter is a lambda expression, if you don't know what the hell it is, google helps you. (FYI callable may not necessarily be a lambda expression, it may also be a function or a functor (a.k.a. function object) but I personally think lambda is the clearest one here.)

I will not give you the statement needed for sorting your open_list, you can use it to check whether you have figured out how the things work or not. Enjoy learning.

Any stable sorting function in standard C libraries?

Standard C library provides qsort() that can be used for sorting an array. As the name suggests, the function uses QuickSort algorithm to sort the given array. Following is prototype of qsort()

void qsort (void* base, size_t num, size_t size, 
            int (*comparator)(const void*,const void*));

The key point about qsort() is comparator function comparator. The comparator function takes two arguments and contains logic to decide their relative order in sorted output. The idea is to provide flexibility so that qsort() can be used for any type (including user defined types) and can be used to obtain any desired order (increasing, decreasing or any other).

The comparator function takes two pointers as arguments (both type-casted to const void*) and defines the order of the elements by returning (in a stable and transitive manner).

Still if you get any doubt fell free to ask.

How do I sort a CArray of a user defined type?

std::sort() should work:

CArray<int> arrayOfInts;
arrayOfInts.Add(7);
arrayOfInts.Add(114);
arrayOfInts.Add(3);
std::sort(arrayOfInts.GetData(), arrayOfInts.GetData()+arrayOfInts.GetSize());

This uses the pointer to the first element in the array as the start iterator, and the pointer to one past the last element as the last iterator (should never be dereferenced anyway, so all's well). You could also pass in a custom predicate if the array contained more interesting data:

struct Foo
{
  int val;
  double priority;
};

bool FooPred(const Foo& first, const Foo& second)
{
   if ( first.val < second.val )
      return true;
   if ( first.val > second.val )
      return false;
   return first.priority < second.priority;
}

//... 

   CArray<Foo> bar;
   std::sort(bar.GetData(), bar.GetData()+bar.GetSize(), FooPred);

Oh - and don't use CArray.

How to sort a very large vector of user defined type

struct mycomp
{
     bool operator() (const Palet& p1, const Palet& p2)
    {
        return (p1.Aantal < p2.Aantal); //Change the operator as required
    }
};

std::sort(MyContainer.begin(), MyContainer.end() , mycomp());

---

Related Topics