Есть ли поддержка в С++/STL для сортировки объектов по атрибуту?

Ответ 1

Общий адаптер для сравнения на основе атрибутов участника. Хотя это более подробно, первый раз, когда он повторно используется.

// Generic member less than
template <typename T, typename M, typename C>
struct member_lt_type 
{
   typedef M T::* member_ptr;
   member_lt_type( member_ptr p, C c ) : ptr(p), cmp(c) {}
   bool operator()( T const & lhs, T const & rhs ) const 
   {
      return cmp( lhs.*ptr, rhs.*ptr );
   }
   member_ptr ptr;
   C cmp;
};

// dereference adaptor
template <typename T, typename C>
struct dereferrer
{
   dereferrer( C cmp ) : cmp(cmp) {}
   bool operator()( T * lhs, T * rhs ) const {
      return cmp( *lhs, *rhs );
   }
   C cmp;
};

// syntactic sugar
template <typename T, typename M>
member_lt_type<T,M, std::less<M> > member_lt( M T::*ptr ) {
   return member_lt_type<T,M, std::less<M> >(ptr, std::less<M>() );
}

template <typename T, typename M, typename C>
member_lt_type<T,M,C> member_lt( M T::*ptr, C cmp ) {
   return member_lt_type<T,M,C>( ptr, cmp );
}

template <typename T, typename C>
dereferrer<T,C> deref( C cmp ) {
   return dereferrer<T,C>( cmp );
}

// usage:    
struct test { int x; }
int main() {
   std::vector<test> v;
   std::sort( v.begin(), v.end(), member_lt( &test::x ) );
   std::sort( v.begin(), v.end(), member_lt( &test::x, std::greater<int>() ) );

   std::vector<test*> vp;
   std::sort( v.begin(), v.end(), deref<test>( member_lt( &test::x ) ) );
}

Ответ 2

Вам не нужно создавать класс - просто напишите функцию:

#include <vector>
#include <algorithm>
using namespace std;

struct Person {
    int age;
    int getage() const {
        return age;
    }
};

bool cmp( const Person * a, const Person * b ) {
    return a->getage() < b->getage() ;
}

int main() {
    vector <Person*> v;
    sort( v.begin(), v.end(), cmp );
}

Ответ 3

На самом деле это не очень большой ответ, так как ответ на AraK отвечает на мой комментарий, что сортировка с помощью функции вместо функтора может быть медленнее. Здесь некоторый (по общему признанию, уродливый - слишком большой CnP) тестовый код, который сравнивает различную сортировку: qsort, std:: sort of vector vs. array и std:: sort с использованием класса шаблона, функции шаблона или простой функции для сравнения:

#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>

int compare(void const *a, void const *b) {
    if (*(int *)a > *(int *)b)
        return -1;
    if (*(int *)a == *(int *)b)
        return 0;
    return 1;
}

const int size = 200000;

typedef unsigned long ul;

void report(char const *title, clock_t ticks) { 
    printf("%s took %f seconds\n", title, ticks/(double)CLOCKS_PER_SEC);
}

void wait() { 
    while (clock() == clock())
        ;
}

template <class T>
struct cmp1 { 
    bool operator()(T const &a, T const &b) { 
        return a < b;
    }
};

template <class T>
bool cmp2(T const &a, T const &b) { 
    return a<b;
}

bool cmp3(int a, int b) { 
    return a<b;
}

int main(void) {
    static int array1[size];
    static int array2[size];

    srand(time(NULL));

    for (int i=0; i<size; i++) 
        array1[i] = rand();

    const int iterations = 100;

    clock_t total = 0;

    for (int i=0; i<iterations; i++) { 
        memcpy(array2, array1, sizeof(array1));
        wait();
        clock_t start = clock();
        qsort(array2, size, sizeof(array2[0]), compare);
        total += clock()-start;
    }
    report("qsort", total);

    total = 0;
    for (int i=0; i<iterations; i++) {
        memcpy(array2, array1, sizeof(array1));
        wait();
        clock_t start = clock();
        std::sort(array2, array2+size);
        total += clock()- start;
    }
    report("std::sort (array)", total);

    total = 0;
    for (int i=0; i<iterations; i++) {
        memcpy(array2, array1, sizeof(array1));
        wait();
        clock_t start = clock();
        std::sort(array2, array2+size, cmp1<int>());
        total += clock()- start;
    }
    report("std::sort (template class comparator)", total);

    total = 0;
    for (int i=0; i<iterations; i++) {
        memcpy(array2, array1, sizeof(array1));
        wait();
        clock_t start = clock();
        std::sort(array2, array2+size, cmp2<int>);
        total += clock()- start;
    }
    report("std::sort (template func comparator)", total);

    total = 0;
    for (int i=0; i<iterations; i++) {
        memcpy(array2, array1, sizeof(array1));
        wait();
        clock_t start = clock();
        std::sort(array2, array2+size, cmp3);
        total += clock()- start;
    }
    report("std::sort (func comparator)", total);

    total = 0;
    for (int i=0; i<iterations; i++) {
        std::vector<int> array3(array1, array1+size);
        wait();
        clock_t start = clock();
        std::sort(array3.begin(), array3.end());
        total += clock()-start;
    }
    report("std::sort (vector)", total);

    return 0;
} 

Компилируя это с помощью VС++ 9/VS 2008 с помощью cl /O2b2 /GL sortbench3.cpp, я получаю:

qsort took 3.393000 seconds
std::sort (array) took 1.724000 seconds
std::sort (template class comparator) took 1.725000 seconds
std::sort (template func comparator) took 2.725000 seconds
std::sort (func comparator) took 2.505000 seconds
std::sort (vector) took 1.721000 seconds

Я считаю, что эти падения довольно чисто в три группы: используя сортировку с сопоставлением по умолчанию, и используя класс шаблона, созданный самым быстрым кодом. Использование функции или функции шаблона заметно медленнее. Использование qsort (как ни удивительно, для некоторых) является самым медленным из всех, примерно на 2: 1.

Разница между cmp2 и cmp3, по-видимому, полностью связана с прохождением по ссылке или значением - если вы меняете cmp2, ​​чтобы принимать свои аргументы по значению, его скорость точно соответствует cmp3 (по крайней мере, в моем тестировании). Разница в том, что если вы знаете, что тип будет int, вы почти наверняка пройдете по значению, тогда как для generic T вы обычно будете передавать по ссылке const (на всякий случай это что-то более дорогое для копирования).

Ответ 4

Если есть только одна вещь, которую вам когда-либо захочется сортировать людей по (или если есть разумный по умолчанию, который вы собираетесь использовать большую часть времени), переопределите operator< для People класс для сортировки по этому атрибуту. Без явного компаратора функции сортировки STL (и все, что делает неявное использование порядка, например множеств и карт), будет использовать operator<.

Если вы хотите сортировать что-то отличное от operator<, способ, которым вы описываете, является единственным способом сделать это с текущей версией С++ (хотя компаратор может быть просто регулярной функцией, он не имеет быть функтором). Стандарт С++ 0x сделает это менее подробным, если лямбда-функции.

Если вы не хотите ждать С++ 0x, альтернативой является использование boost:: lambda.

Ответ 5

Я вижу, что dribeas уже опубликовал эту идею, но так как я уже написал ее, вот как вы напишете общий компаратор для использования функций getter.

#include <functional>

template <class Object, class ResultType>
class CompareAttributeT: public std::binary_function<const Object*, const Object*, bool>
{
    typedef ResultType (Object::*Getter)() const;
    Getter getter;
public:
    CompareAttributeT(Getter method): getter(method) {}
    bool operator()(const Object* lhv, const Object* rhv) const
    {
        return (lhv->*getter)() < (rhv->*getter)();
    }
};

template <class Object, class ResultType>
CompareAttributeT<Object, ResultType> CompareAttribute(ResultType (Object::*getter)() const)
{
    return CompareAttributeT<Object, ResultType>(getter);
}

Использование:

std::sort(people.begin(), people.end(), CompareAttribute(&Person::getAge));

Я думаю, что было бы неплохо перегрузить operator() для не указателей, но тогда нельзя было бы набирать аргумент_types путем наследования от binary_function - это, вероятно, не большая потеря, так как было бы трудно используйте его там, где это необходимо в любом случае, например, в любом случае нельзя просто скрыть функтор сравнения.

Ответ 6

Эти ответы все действительно многословны, хотя мне нравится идея шаблона! Просто используйте лямбда-функции, это делает вещи намного проще!

Вы можете просто использовать это:

sort( people.begin(), people.end(), []( Person a, Person b ){ return a.age < b.age; } );

Ответ 7

У вас может быть только глобальная функция или статическая функция. Каждая из этих глобальных или статических функций сравнивается с атрибутом. Не нужно создавать класс. Один из способов удержания папелетов для сравнения - использовать boost bind, но bind полезен только для поиска всех классов или сравнения всех классов с некоторым связанным параметром. Хранение данных по нескольким элементам является единственной причиной для создания функтора.

Редактирование: также см. boost lambda functions, но они применимы только для простых функций.

Ответ 8

Я просто попробовал это на основе идей UncleBens и Дэвида-Родригеса-дрибеа.

Это, похоже, работает (как есть) с моим текущим компилятором. g++ 3.2.3. Пожалуйста, дайте мне знать, если он работает с другими компиляторами.

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

using namespace std;

class Person
{
public:
    Person( int _age )
        :age(_age)
    {
    }
    int getAge() const { return age; }
private:
    int age;
};

template <typename T, typename ResType>
class get_lt_type
{
    ResType (T::*getter) () const;
public:
    get_lt_type(ResType (T::*method) () const ):getter(method) {}
    bool operator() ( const T* pT1, const T* pT2 ) const
    {
        return (pT1->*getter)() < (pT2->*getter)();
    }
};

template <typename T, typename ResType>
get_lt_type<T,ResType> get_lt( ResType (T::*getter) () const ) {
    return get_lt_type<T, ResType>( getter );
}

int main() {
    vector<Person*> people;
    people.push_back( new Person( 54 ) );
    people.push_back( new Person( 4 ) );
    people.push_back( new Person( 14 ) );

    sort( people.begin(), people.end(), get_lt( &Person::getAge) );

    for ( size_t i = 0; i < people.size(); ++i )
    {
        cout << people[i]->getAge() << endl;
    }
    // yes leaking Persons
    return 0;
}