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

Это не столько ответ сам по себе, сколько ответ на ответ AraK на мой комментарий о том, что сортировка с помощью функции вместо функтора может быть медленнее. Вот некоторый (правда, уродливый - слишком много CnP) тестовый код, который сравнивает различные сортировки: qsort, std :: sort вектора и массива и 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;
} 

Компилируя это с VC ++ 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

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

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

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

#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 () для не-указателей, но тогда нельзя было бы typedef the argument_types путем наследования от binary_function ] - что, вероятно, не является большой потерей, так как в любом случае было бы трудно использовать его там, где они нужны, например, все равно нельзя было отрицать функтор сравнения.

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

Изменить: также см. Лямбда-функции повышения, но они применимы только для простых функций.

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

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

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

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

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

Я только что попробовал это на основе идей UncleBens и david-rodriguez-dribeas.

Похоже, это работает (как есть) с моим текущим компилятором. 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;
}