How do i sort objects?

Question

I've created a class and created an array of objects under that class and filled it all up with data. Now i want to sort the entire array by a specific member of that class, how do I do this using the stable_sort() function?

Edit: Ok, i have this right now,

class sortContiner 
{
public:
    double position;
    int key;
    double offsetXposition;
    double offsetYposition;
    int origXposition;
    int origYposition;
};

I've declared the array like this:

sortContiner * sortList = new sortContiner [length];

Now i want want to sort it by the sortList .position member using stable_sort() like this:

stable_sort(sortList, sortList + length, ????);

What is the comparator function supposed to look like?

Answer 1

I see there are already a couple of solutions, but since I typed mine already, I want to post it anyway. This is a little working solution to give you an idea:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib> 
using namespace std;    //i know :-/


//A very useless class
class myClass{          
private:
  int value;
public:
  myClass(int val){value = val;}
  int getValue(){return value;}
};

//a function which defines how to compare my objects
bool myComparsion (myClass m ,myClass n)
{
    return (m.getValue()<n.getValue());
}

int main(){

  vector<myClass> myvector;
  vector<myClass>::iterator it;

  //Filling up the vector with my objects which are initialized with random numbers
  for (int n=0;n<10;++n)
    myvector.push_back(*(new myClass(rand()%100)));

  //looking at my vector 
  cout<<"Before:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout<< " "<<it->getValue();
  cout << endl;     

  //sorting the vector and looking again      
  stable_sort (myvector.begin(), myvector.end(), myComparsion);    //this is where the magic happens
  cout<<"After:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << it->getValue();
  cout << endl;

  //...

  }

The output should be something like this

Before: 83 86 77 15 93 35 86 92 49 21
After: 15 21 35 49 77 83 86 86 92 93

Answer 2

Here's the declaration of stable_sort():

template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, 
                 StrictWeakOrdering comp);

You have to use the second overload and provide you own comparison functor. Something along the lines:

class obj; // your type
struct obj_cmp
{
  bool operator()( const obj& lhs, const obj& rhs ) const
  {
     return lhs.member_ < rhs.member_;
  } 
};

It could also be a free function - anything that you can apply () to, like:

bool obj_cmp_func( const obj& lhs, const obj& rhs )
{
  return lhs.member_ < rhs.member_;
} 

Then you sorting statement would be:

obj array[X]; // X is a compile-time constant
// populate array
std::stable_sort( array, array + X, obj_cmp());
// or with the function
std::stable_sort( array, array + X, obj_cmp_func );

Note that objects of your type have to freely copyable. Look here for details.

Answer 3

You need iterators into your array and some sorting criterion. Let's start with the iterators:

You will need a begin iterator and an end iterator. The begin iterator needs to point to the first element, the end iterator needs to point behind the last element. Pointers are perfect iterators. An array is implicitly convertible into a pointer to its first element, so you have a begin iterator. Add the number of elements in the array to it and you have an end iterator. The number of elements in the array can be obtained by dividing the size (number of bytes) of the array by the size of a single element. Putting it all together:

foo array[10];
const std::size_t array_size = sizeof(array)/sizeof(array[0]);
const int* array_begin = array; // implicit conversion
const int* array_end = begin + array_size;

Now you need something for the algorithm to decide which of two given objects of your class is the smaller one. An easy way to do this would be by overloading operator< for your class:

bool operator<(const foo& lhs, const foo& rhs)
{
  // compares using foo's bar
  return lhs.get_bar() < rhs.get_bar();
}

Now you can sort your array:

std::stable_sort( array_begin, array_end );

If the sorting criterion isn't as fix (say, sometimes you want to sort based on foo's bar data, sometimes based on its wrgly data), you can pass different sorting criteria to the sort algorithm as an optional third parameter. Sorting criteria should be function-like entities. That can be functions or function objects. The latter provide inlining, which is why they are usually better. Here's both:

bool compare_by_bar(const food& lhs, const foo& rhs)
{
  return lhs.get_bar() < rhs.get_bar();
}

struct wrgly_comparator {
  bool operator()(const food& lhs, const foo& rhs) const
  {
    return lhs.get_wrgly() < rhs.get_wrgly();
  }
};

This is how you use them:

std::stable_sort( array_begin, array_end, compare_by_bar );
wrgly_comparator wc;
std::stable_sort( array_begin, array_end, wc );

You can also create the comparator on the fly:

std::stable_sort( array_begin, array_end, wrgly_comparator() );

Edit: Here's a few more hints based on your expanded question:

sortContainer * sortList = new sortContiner [length]; will create a dynamic array on the heap. In C++, there is no garbage collection and you are responsible for cleaning up on the heap after yourself (in this case by invoking delete[] sortList;). This is notoriously hard to do for novices and error-prone even for seasoned programmers. There's a very good chance that what you want is an automatic array: sortContainer sortList[length]; on the stack.

The identifier sortContainer tells me that the thing is a container. However, it's the type of the items to be put into the container. Be more careful by picking identifiers. Proper naming goes a long way towards readable and maintainable code.

Answer 4

As a complement to the other answers: The predicate can be created on the fly with boost (or tr1) bind. For example, to sort by the "key" member:

std::stable_sort(sortList, sortList + length,
  boost::bind(&sortContiner::key, _1) < boost::bind(&sortContiner::key, _2)
);

Answer 5

You can put the objects in container ( say, std::vector) and write a functor and use the same in stable_sort.

class Functor
{
    public:
        bool operator() (const Data& info1, const Data& info2)
        {
            return info1.AnyMemberOfData>info2.AnyMemberOfData;
        }
};

std::stable_sort(aVector.begin(), aVector.end(),functor);

Edit: Using arrays ( as @sbi and @wrang-wrang suggested):

Data anArray[10];
//Fill anArray
std::stable_sort(anArray, anArray + 10,functor);

OR write operator < for your class and straight way call stable_sort

Answer 6

You can something like this: The code is self explanatory:

class A
{
public:
    A() : m_a(0), m_b(0)
    {
    }
    void setA(int n)
    {
        m_a = n;
    }
    void setB(int n)
    {
        m_b = n;
    }

    int getA() const
    {
        return m_a;
    }


    int getB() const
    {
        return m_b;
    }


private:
    int m_a;
    int m_b;
};

bool compareA(const A& first, const A& second)
{
    return first.getA() < second.getA();
}

bool compareB(const A& first, const A& second)
{
    return first.getB() < second.getB();
}


int _tmain(int argc, _TCHAR* argv[])
{
    A a[10];
    for(int i = 10; i >= 0; --i)
    {
        a[i].setA(i);
        a[i].setB(i);
    }

    //Sort on variable m_a
    std::stable_sort(a, a + 10, compareA);

    //Sort on variable m_b
    std::stable_sort(a, a + 10, compareB);
}

Answer 7

You must write your own predicate and pass it to the standard algorithm.