关于c++中stl库的sort模板的理解

今天浮于表面的研究了以下STL库中sort方法，从新思考了以下sort方法中穿回调函数应该怎么用数学方法理解

先来看一下形式

default (1)	
template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)	
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

下面是具体代码

// sort algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobject;

int main () {
  int myints[] = {32,71,12,45,26,80,53,33};
  std::vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33

  // using default comparison (operator <):
  std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // using object as comp
  std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ‘ ‘ << *it;
  std::cout << ‘\n‘;

  return 0;
}

从上面的代码中可以看出传入的回调函数是一个bool返回值的，具体的细节我不清楚，源码的阅读理解会在后续展开，但是就从快速使用上来说，如何理解这个回调函数的意义？先来看看c++官网是如何解释的：*Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.（返回的值指示作为第一个参数传递的元素是否在其定义的特定严格弱顺序中位于第二个参数之前）
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.
其中重要的一句话是：
返回的值指示作为第一个参数传递的元素是否在其定义的特定严格弱顺序中位于第二个参数之前
我可以理解为这个回调函数其实是一个数学条件，我理解为sort是按照如此这般的方法去规范自己排序的依据，并且对所有的元素都应该是遵守这个依据的，如果两个元素比较的时候没有遵守这个依据，就交换位置

如何用数学语言去描述呢？

我比较喜欢用数学的方法去描述，这样更简单且方便理解一点。这个回调函数其实可以描述成一个数学表达式：?i,j，其中i!=j，都有 bool comp（i,j）== true
而对整个sort函数运行结构的数学描述则是：在数组num中，i∈num，j∈num，i!=j，?i,j，都有 bool comp（i,j）== true

总结

当用数学描述出来后会发现，相当的好理解，也好记忆了（也可能是我自己个人的感受），以后的算法设计也可以按照这种想法来：先提出数学表达式，以此为目的，设计出符合自己目的的算法来。从这里我也理解出，算法其实是实现目的的手段，而正真的难点是如何抽象你所需要实现的东西，当你抽象出来后，算法的复用性可大大增加，否则会增加很多工作量。算法是服务与人类的，算法本身不美，美的是背后的思想，和伟大的人。

关于c++中stl库的sort模板的理解

原文：https://www.cnblogs.com/initlist/p/14158645.html