C++/STL 是否支持按属性对对象进行排序？

Question

我想知道STL是否支持这一点：

假设我有一个像这样的类：

class Person
{
public:
  int getAge() const;
  double getIncome() const;
  ..
  ..
};

和一个向量：

vector<Person*> people;

我想按人们的年龄对向量进行排序： 我知道我可以通过以下方式做到这一点：

class AgeCmp
{
public:
   bool operator() ( const Person* p1, const Person* p2 ) const
   {
     return p1->getAge() < p2->getAge();
   }
};
sort( people.begin(), people.end(), AgeCmp() );

有没有更简洁的方法来做到这一点？仅仅因为我想根据“属性”进行排序就必须定义整个类似乎有点过分了。也许是这样的？

sort( people.begin(), people.end(), cmpfn<Person,Person::getAge>() );

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

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

Answer 3

这本身并不是一个真正的答案，而是对 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;
} 

使用 cl /O2b2 /GL sortbench3.cpp 与 VC++ 9/VS 2008 进行编译，我得到：

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，您几乎肯定会按值传递，而对于泛型 T，您通常会按 const 传递参考（以防万一复制成本更高）。

Answer 4

如果您只想根据一件事对人员进行排序（或者如果您在大多数情况下想要使用一个合理的默认值），请覆盖 operator< People 类按此属性排序。如果没有显式比较器，STL 排序函数（以及任何隐式使用排序的函数，如集合和映射）将使用 operator<。

当您想要按 operator< 以外的其他方式进行排序时，您所描述的方式是从当前版本的 C++ 开始执行此操作的唯一方法（尽管比较器可以只是常规函数；它并不不必是函子）。 C++0x 标准将允许 lambda 函数。

如果您不愿意等待 C++0x，另一种方法是使用 boost::lambda。

Answer 5

从 C++20 开始，您可以使用投影直接执行此操作。投影可以应用于范围内的每个元素以进行排序：

#include <algorithm>
#include <vector>

std::vector<Person> persons;
std::ranges::sort(persons, {}, &Person::getAge);

std::vector<Person*> personPtrs;
std::ranges::sort(personPtrs, {}, &Person::getAge);

Answer 6

我看到 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() 可能是个好主意，但随后就无法通过继承 binary_function 来定义 argument_types - 这是可能不是一个很大的损失，因为无论如何都很难在需要的地方使用它，例如，无论如何都无法否定比较函子。

Answer 7

尽管我喜欢模板的想法，但这些答案都非常冗长！只需使用 lambda 函数，事情就变得简单多了！

你可以用这个：

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

Answer 8

我只是根据 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;
}

Answer 9

您可以只有一个全局函数，也可以有一个静态函数。这些全局或静态函数中的每一个都与一个属性进行比较。无需上课。保存论文进行比较的一种方法是使用 boost bind，但绑定仅适用于查找所有类或将所有类与某些绑定参数进行比较。跨多个元素存储数据是创建函子的唯一原因。

编辑：另请参阅 boost lambda 函数，但它们仅适用于简单函数。