C ++ struct sorting

Question

• У меня есть вектор пользовательской структуры, который нужно каждый раз сортировать по разным критериям
• Реализующий оператор <допускает только один критерий </li>
• Но я хочу указывать критерии сортировки каждый раз, когда вызываю стандартную сортировку C ++.

Как это сделать?

• Обратите внимание, что лучше быть эффективным во время выполнения ..

Спасибо

Answer 1

Вы можете определить, какую функцию сравнения использовать при каждом запуске алгоритма сортировки, используя третий аргумент:

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

Простой пример:

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

Существует 2 версии std::sort, вторая версия принимает функтор сравнения:

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

Например:

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);

См. Также http://www.cplusplus.com/reference/algorithm/sort/.

В этом варианте все еще используется тот же алгоритм быстрой сортировки, поэтому в среднем это O (n log n).

Answer 3

Просто для полноты, вот пример использования лямбда-функций c ++ 0x:

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

Существует две версии std :: sort , первая просто берет итераторы и использует оператор объекта StrictWeakOrdering в качестве компартмента.Объект компаратора (или функция) должен вызываться с двумя параметрами, где каждый параметр имеет указанный тип, и он должен возвращать значение true, если первый параметр меньше, чем второй параметр.Например:

bool mycomparator(const T& a, const T&b); // return true if a < b

ИЛИ

class MyComparator
{
    public:
         bool operator()(const T& a, const T& b)const; // return true if a < b
};

Answer 5

Boost.Bind позволяет в простых случаях определять функцию сравнения на месте:

#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);
}

Выход:

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