C++ struct sorting

Question

• I have a vector of custom Struct that needs to be sorted on different criteria each time
• Implementing operator < will allow only one criteria
• But I want to be able to specify sorting criteria each time I call C++ standard sort.

How to do that?

• Please note it is better to be efficient in running time..

Thanks

Answer 1

You can define what comparison function to use in each run of the sort algorithm by using the third argument:

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

A simple example:

struct person {
   std::string name;
   int age;
};
bool sort_by_name( const person & lhs, const person & rhs )
{
   return lhs.name < rhs.name;
}
bool sort_by_age( const person & lhs, const person & rhs )
{
   return lhs.age < rhs.age;
}
int main() {
   std::vector<person> people;
   // fill in the vector
   std::sort( people.begin(), people.end(), sort_by_name );
   std::sort( people.begin(), people.end(), sort_by_age );
}

Answer 2

There are 2 versions of std::sort, the 2nd version accepts a comparison functor:

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
          StrictWeakOrdering comp);
//--------^^^^^^^^^^^^^^^^^^^^^^^

For example:

bool isLessThan(const MyStruct& first, const MyStruct& second) {
   if (first.name < second.name) return true;
   else if (first.name == second.name) {
      if (first.date > second.date) return true;
      // etc.
   }
   return false;
}

...

sort(v.begin(), v.end(), isLessThan);

See also http://www.cplusplus.com/reference/algorithm/sort/.

This variant still uses the same quicksort algorithm, so it's O(n log n) on average.

Answer 3

Just for completeness, here is a an example using c++0x lambda functions:

std::vector<Person> v;
std::sort(v.begin(), v.end(), [](Person a, Person b) { return a.name_ < b.name_; });
...
std::sort(v.begin(), v.end(), [](Person a, Person b) { return a.address_ < b.address_; });

Answer 4

Boost.Bind allows in simple cases to define a compare function inplace:

#include <iostream>
#include <algorithm>

#include <boost/foreach.hpp>
#include <boost/format.hpp>
#include <boost/bind.hpp>

#define P(a) do {                                                       \
    BOOST_FOREACH (Struct s, a)                                         \
      std::cout << boost::format("(%d %c) ") % s.i % s.c;               \
    std::cout << std::endl;                                             \
  } while(0)

namespace {
  struct Struct { int i; char c; };
}

int main() {
  using boost::bind;

  Struct a[] = { 1, 'z', 2, 'a' }; P(a);
  const int N = sizeof(a) / sizeof(*a);

  std::sort(a, a + N, bind(&Struct::i, _1) > bind(&Struct::i, _2));  P(a);
  std::sort(a, a + N, bind(&Struct::c, _1) > bind(&Struct::c, _2));  P(a);
}

Output:

(1 z) (2 a) 
(2 a) (1 z) 
(1 z) (2 a)