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 of vector与array,std :: sort使用模板类,模板函数或plain函数进行比较:

#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,您通常会传递const引用(以防万一它的复制成本更高).