Using stable_sort() to sort doubles as ints

Question

Hello everyone,

I have a huge array of ints that I need to sort. The catch here is that each entry in the list has a number of other associated elements in it that need to follow that int around as it gets sorted. I've kind of solved this problem by changing the sorting to sort doubles instead of ints. I've tagged each number before it was sorted with a fractional part denoting that value's original location before the sort, thus allowing me to reference it's associated data and allowing me to efficiently rebuild the sorted list with all the associated elements.

My problem is that I want to sort the double values by ints using the function stable_sort().

I'm referring to this web page: http://www.cplusplus.com/reference/algorithm/stable%5Fsort/

However, since I'm a new programmer, i don't quite understand how they managed to get the sort by ints to work. What exactly am i supposed to put into that third argument to make the function work? (i know i can just copy and paste it and make it work, but i want to learn and understand this too).

Thanks,

-Faken

Edit: Please note that I'm a new programmer who has had no formal programming training. I'm learning as i go so please keep your explanations as simple and as rudimentary as possible.

In short, please treat me as if i have never seen c++ code before.

Answer 1

You need to pass the comparison function. Something like this:

bool intCompare(double first, double second)
{
    return static_cast<int>(first) < static_cast<int>(second);
}

int  main()
{

    std::vector<double> v;
    v.push_back(1.4);
    v.push_back(1.3); 
    v.push_back(2.1);
    v.push_back(1.5);

    std::stable_sort(v.begin(), v.end(), intCompare);



    return 0;
}

Inside the sort algorithm, to compare the values the comparison function passed by you is used. If you have a more complex data structure and want to sort on a particular attribute of the data structure then you can use this user-defined function to compare the values.

Answer 2

I believe you are talking about this function:

bool compare_as_ints (double i,double j)
{
  return (int(i)<int(j));
}

And the function call:

stable_sort (myvector.begin(), myvector.end(), compare_as_ints);

The function compare_as_ints is a normal function but this is being passed to the stable_sort as a function pointer. i.e., the address of the function is being passed which would be used by stable_sort internally to compare the values.

Look at this function pointer tutorial if you are unclear about this.

Answer 3

Since you say you're not familiar with vectors (you really should learn STL containers ASAP, though), I assume you're playing with arrays. Something along these lines:

int a[] = { 3, 1, 2 };
std::stable_sort(&a[0], &a[3]);

The third optional argument f of stable_sort is a function object - that is, anything which can be called like a function by following it with parentheses - f(a, b). A function (or rather a pointer to one) is a function object; other kinds include classes with overloaded operator(), but for your purposes a plain function would probably do.

Now you have your data type with int field on which you want to sort, and some additional data:

struct foo {
  int n;
  // data
  ...
};

foo a[] = { ... };

To sort this (or anything, really), stable_sort needs to have some way of comparing any two elements to see which one is greater. By default it simply uses operator < to compare; if the element type supports it directly, that is. Obviously, int does; it is also possible to overload operator< for your struct, and it will be picked up as well, but you asked about a different approach.

This is what the third argument is for - when it is provided, stable_sort calls it every time it needs to make a comparison, passing two elements as the arguments to the call. The called function (or function object, in general) must return true if first argument is less than second for the purpose of sorting, or false if it is greater or equal - in other words, it must work like operator < itself does (except that you define the way you want things to be compared). For foo, you just want to compare n, and leave the rest alone. So:

bool compare_foo_n(const foo& l, const foo& r) {
  return l.n < r.n;
}

And now you use it by passing the pointer to this function (represented simply by its name) to stable_sort:

std::stable_sort(&a[0], &a[3], compare_foo_n);