[C++ Primer] C++中sort对类对象进行排序 - c++编程基础

使用C++进行编程时，常常需要对处理对象进行排序，因此C++中提供了sort范型算法。

1 sort的原型

template 
  
   
  void sort (RandomAccessIterator first, RandomAccessIterator last);

template 
   
     void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

上面是两个范型算法的模板。

第一个函数有两个参数，分别是随机访问迭代器first和last，它默认使用迭代器引用的operator<进行排序。

第二个函数有三个参数，前两个和第一个一样，第三个参数是一个Compare，也就是说它使用comp对迭代器引用的对象进行排序。

comp是一个二元函数，它接受前两个参数指定范围内的两个元素，它的返回值可以转换为bool类型，这个函数不改变迭代器引用的对象，而且，它可以是函数指针和函数对象。

需要注意的是，这两个排序函数不是稳定的，稳定的排序可以看看stable_sort。

2 一个对整数进行排序的简单例子

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int cmp_func(int a, int b) { if(a > b) return true; return false; } void print_res(int x) { cout << x << " "; } int main(int argc, char *argv[]) { int arr[] = {6, 4, 8, 2, 1}; int len = sizeof(arr) / sizeof(arr[0]); vector
     
       ivec(arr, arr + len); sort(ivec.begin(), ivec.end()); for_each(ivec.begin(), ivec.end(), print_res); cout << endl; sort(ivec.begin(), ivec.end(), cmp_func); for_each(ivec.begin(), ivec.end(), print_res); cout << endl; return 0; }

上面是一个使用sort的简单例子，定义了一个比较函数cmp_func，当a > b时，返回真，否则返回假。

主函数中先调用了两个形参的函数，然后调用了三个形参的函数。

第一个默认使用operator<排序，因此结果是1 2 4 6 8 。

第二个使用给定的cmp_func函数排序，因此结果是8 6 4 2 1。

3 使用sort对类对象进行排序

3.1 使用自定义的比较函数

#include 
  
   
#include 
   
     #include 
    
      using namespace std; struct Test{ int val; Test(int x) : val(x) { } }; bool nonmem_cmp(const Test &t1, const Test &t2) { if(t1.val > t2.val) return true; return false; } void print_res(Test t) { cout << t.val << " "; } int main(int argc, char *argv[]) { vector
     
       ivec; ivec.push_back(Test(6)); ivec.push_back(Test(4)); ivec.push_back(Test(8)); ivec.push_back(Test(2)); ivec.push_back(Test(1)); sort(ivec.begin(), ivec.end(), nonmem_cmp); for_each(ivec.begin(), ivec.end(), print_res); cout << endl; return 0; }

上例中定义了一个nonmem_cmp函数，然后在第二个版本的sort函数中的第三个参数指定为nonmem_cmp函数，就能够对迭代器引用区间的元素用nonmem_cmp函数进行排序。相当简单吧？

3.2 重载operator<操作符

#include 
  
   
#include 
   
     #include 
    
      using namespace std; struct Test{ int val; Test(int x) : val(x) { } bool operator<(const Test &t) const { if(val < t.val) return true; return false; } }; bool operator<(const Test &t1, const Test &t2) { if(t1.val < t2.val) return true; return false; } void print_res(Test t) { cout << t.val << " "; } int main(int argc, char *argv[]) { vector
     
       ivec; ivec.push_back(Test(6)); ivec.push_back(Test(4)); ivec.push_back(Test(8)); ivec.push_back(Test(2)); ivec.push_back(Test(1)); sort(ivec.begin(), ivec.end()); for_each(ivec.begin(), ivec.end(), print_res); cout << endl; return 0; }

上面的代码用两种方式为Test类定义了operator<，当然，要想代码正确运行，只能有一种方式：成员函数或者非成员函数。此时，就能够用sort的第一个版本对迭代器引用区间的元素进行排序，此时使用operator<进行。上面的结果就是：1 2 4 6 8。

3.3 使用自定义的函数对象

什么是函数对象？就是定义了函数调用操作符()的类的对象。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; struct Test { int val; Test(int x) : val(x) { } }; class Cmp { public: int val; bool operator()(const Test &t1, const Test &t2) { if(t1.val < t2.val) return true; return false; } }; void print_res(Test t) { cout << t.val << " "; } int main(int argc, char *argv[]) { vector
     
       ivec; ivec.push_back(Test(6)); ivec.push_back(Test(4)); ivec.push_back(Test(8)); ivec.push_back(Test(2)); ivec.push_back(Test(1)); sort(ivec.begin(), ivec.end(), Cmp()); for_each(ivec.begin(), ivec.end(), print_res); cout << endl; return 0; }

上面的代码定义了类Test，只定义了类成员变量和构造函数。

然后定义了一个类Cmp，它定义了operator()，因此Cmp的对象就是函数对象，它的对象可以当作函数一样使用。

在Cmp的operator()中，有两个Test类类型的参数，它们进行比较得到布尔值。

在主函数中，使用sort的第二个版本，而且第三个参数用的是默认构造函数构造的一个Cmp临时对象。

假设Cmp()创建的临时变量是compare，即Cmp compare，sort(ivec.begin(), ivec.end(), compare)，在比较两个Test类对象时，会调用compare(t1, t2)，由于我们为Cmp定义了operator()操作符，而且参数就是两个Test类对象，因此，该函数可以正常工作。

3.4 对中的类模板进行派生创建函数对象

在中定义了多种模板，这里使用二元函数模板。

template 
  
   
  struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
  };

以上是二元函数结构体的模板定义，它只定义了三个参数，分别是二元函数的两个操作数和返回值。

在使用中我们需要对上面的类进行派生，添加operator()，然后就可以使用函数对象了。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; struct Test { int val; Test(int x) : val(x) { } }; class Cmp : public binary_function
      
        { public: bool operator()(const Test &t1, const Test &t2) { if(t1.val < t2.val) return true; return false; } }; void print_res(Test t) { cout << t.val << " "; } int main(int argc, char *argv[]) { vector
       
         ivec; ivec.push_back(Test(6)); ivec.push_

[C++ Primer] C++中sort对类对象进行排序(一)