19 июля 2009

Sorting by several fields

Как вы сортируете по нескольким критериям?
struct foo
{
A a; B b; C c; D d;
X x; Y y;
};

// нужно отсортировать по a, затем по b, затем по c, ну а затем еще и по d
// по x и y сортировать не нужно
bool s(foo const &l, foo const &r)
{
if (l.a < r.a) return true;
if (l.a > r.a) return false;
if (l.b < r.b) return true;
if (l.b > r.b) return false;
if (l.c < r.c) return true;
if (l.c > r.c) return false;
return l.d < r.d;
}

std::vector<foo> f;
std::sort(f.begin(), f.end(), s);

Признаюсь, я примерно так раньше и сортировал. Хотя по сути-то [a,b,c,d] - это ж по-сути обычный кортеж, а для них уже есть готовые библиотеки. И операции сравнения кортежей там должны быть, в этих библиотеках. Нужно просто загнать l и r в кортежи (только для скорости - не в [A,B,C,D], а в [const&A,const&B,const&C,const&D]), и сравнить:
#include <boost/tuple/tuple_comparison.hpp>

bool s(foo const &l, foo const &r)
{
return boost::tie(l.a, l.b, l.c, l.d) < boost::tie(r.a, r.b, r.c, r.d);
}

5 комментариев:

Анонимный комментирует...

Правильнее и красивее было определить operator< для класса foo.
И не полениться сделать-таки конструктор(ы) :-)

Raider комментирует...

Смысл не в том, как назвать - s() или foo::operator<() - это зависит от конкретной задачи. Смысл в том, как его реализовать.

А конструкторы каким образом связаны с сортировкой?

Анонимный комментирует...

Если foo - не POD-структура и вы собираетесь ее сортировать, то нужен конструктор копирования, operator= и operator<. А вдруг, тип какого-нибудь из членов указатель? Желательно написать явные конструкторы.
Понятно, что вы хотели показать возможности boost::tuple, а я просто занудствую :-P

Анонимный комментирует...

первый вариант можно записать получше:
bool s(foo const &l, foo const &r)
{
if (l.a != r.a)
return l.a < r.a;
if (l.b != r.b)
return l.b < r.b;
if (l.c != r.c)
return l.c < r.c;
return l.d < r.d;
}

Анонимный комментирует...

Не делали сравнение по скорости обоих вариантов?