C++, using custom function to sort an std::list

R00ts · 01-03-2005, 02:56 AM

From http://www.cppreference.com/cpplist_details.html#sort:

void sort( Comp compfunction );

The sort() function sorts the lists, optionally using compfunction as the comparison function to determine if an element is less than another.

I've spent the past half hour googling and trying to find more information about this compfunction, but I came up empty handed. Does anyone have an example of how I can write my own function for sorting a list? Here's a small snippet of what I'm storing in my list and what I want to sort it by:

Code:

class MObject {
  int row_position;
   ...
};

class Sprite : public MObject {
  int other_stuff;
  ...
}


class StaticObj : public MObject {
  int more_stuff;
  ...
}

class MapMode {
   std::list<MObject*> map_list;
   ...
};


int main() {
  MapMode my_map;
  // Push a bunch of Sprites and StaticObjs into map_list;

  my_map.map_list.sort( ?CompareFunctionHere? )
  return 0;
}

Do you get it? So basically I have a list of several different objects and I want to be able to sort the list based on one integer argument, their row position. I'm stumped here and I can't find anything about it in my C++ text (which has never failed me till now). Thanks for any help

Hivemind · 01-03-2005, 04:24 AM

Well, the C++ standard library comes with a number of sorting functions and there's one that takes a "binary predicate function". I'm not sure how you use with std::list, but say you were storing your objects in a std::vector, you could do:

Code:

#include <algorithm>
#include <iostream>
#include <vector>

class Row
{
public:
   Row(int row)
      :
      m_row(row) {}

   int get_row() const
   {
      return m_row;
   }
   
private:
   int m_row;
};

static void print_collection(const std::vector<Row>&);

bool less_wrt_row(const Row& lhs, const Row& rhs)
{
   return lhs.get_row() < rhs.get_row();
}

int
main()
{
   std::vector<Row> collection;

   collection.push_back(Row(39));
   collection.push_back(Row(3));
   collection.push_back(Row(202));
   collection.push_back(Row(1));

   std::cout << "Before sorting:" << std::endl;

   print_collection(collection);

   std::sort(collection.begin(), collection.end(), less_wrt_row);

   std::cout << "After sorting:" << std::endl;

   print_collection(collection);

   return 0;
}

static void
print_collection(const std::vector<Row>& collection)
{
   std::vector<Row>::const_iterator itr = collection.begin();

   while(itr != collection.end())
   {
      std::cout << itr->get_row() << std::endl;

      ++itr;
   }
}

Output:

Code:

$ ./foo.exe
Before sorting:
39
3
202
1
After sorting:
1
3
39
202

Using a binary predicate function is very nice if you have a class that should be sorted on different criteria at different times, simply select the proper predicate. If you *always* sort on row, you could define operator< for your class, and call the std::sort that does not take a predicate. There is also a stable_sort available to you should you need it.

Hope that helps

R00ts · 01-03-2005, 09:19 AM

Yeah I think that is what I'm after. I'll try out both the custom sort function and the operator overloading method and see how they do. Thanks!

Hivemind · 01-03-2005, 09:41 AM

I've done some more research, and it appears that the free-standing sort functions in the C++ standard library (those found in <algorithm> which I used in my example) requires random-access iterators to function.

std::list, due to its very nature, doesn't provide random access iterators.

That leaves you with two options:
Change to a different container (I used std::vector in my example) that supports random access iterators or use the built-in sort function in the list class.

There are two built-in sort functions in std::list. One that takes a binary predicate function to do the comparison and one that doesn't require a binary predicate function but requires that operator < to be defined for the type stored in the list.
So if you *always* sort by row, simply overload operator< in your base class and have it compare by row. But if you use several ways to sort the same collection create a predicate for each way (then you don't need to overload operator<).

Hope that clears things up for you