STL自定义排序函数：sort()函数；priority_queue，set，map等容器排序函数

1、sort()函数自定义排序：

1.1、sort()模板原型：
1.1.1、默认模板：利用<比较，升序排列

template <class_Randlt> // 模板参数为迭代器类型
void sort(_Randlt first, _RandIt last); // 参数为起止随机访问迭代器

前提是a、b (_Randlt迭代器指向的对象) 必须可比较大小。元素比较大小是用<进行的，如果表达式a<b的值为 true，则 a 排在 b 前面。

• a，b为值对象：可直接比较大小

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
// 默认sort模板，使用<排序
std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

• a，b为class/struct对象：类中或类外必须重载<比较函数

class A
{
public:
    int v1;
    int v2;
    A(int n) : v1(n), v2(0) {}
    // 方式1：
    bool operator < (const A & a1) const
	{  //重载为 A 的 const 成员函数，重载为非 const 成员函数在某些编译器上会出错
	   return v1 < a1.v1;
	}
};
// 方式2：
bool operator < (const A & a1, const A & a2) 
{  // 类外重载，调用<比较函数时会先在本文件内查找匹配的函数，没有才调用全局空间的<函数
    return a1.v1 < a2.v1;
}

// 默认sort模板，但元素自定义了比较函数
A a2[5] = { 13, 12, 9, 8, 16 };
std::sort (a2, a2+5);           // 8, 9, 12, 13, 16

1.1.2、自定义排序模板：

template <class_Randlt, class Pred>
void sort(_Randlt first, _RandIt last, Pred op); // 多了一个比较函数指针或对象

通过表达式op(a, b)对元素 a、b 比较大小，其中Pred op可以是一个函数指针或一个函数对象，如果该表达式的值为 true，则 a 比 b 小。

• Pred op为函数指针：函数返回值必须为bool量

bool GreaterA(const A & a1, const A & a2)
{  //v值大的元素作为较小的数
    return a1.v1 > a2.v1;
}
std::sort (a2, a2+5, GreaterA);           // 16, 13, 12, 9, 8  按v1的值从大到小排序

• Pred op为函数对象：类成员函数返回值必须为bool量

struct LessA  // 自定义排序对象,struct换成class也可以
{
    bool operator() (const A & a1, const A & a2)
    {  //v的个位数小的元素就作为较小的数
        return (a1.v1) < (a2.v1);
    }
}LessA_1; // LessA为对象类型，LessA_1为对象
std::sort (a2, a2+5, LessA_1);           // 8, 9, 12, 13, 16  按v1的值从小到大排序
std::sort (a2, a2+5, LessA());           // 8, 9, 12, 13, 16  按v1的值从小到大排序
以上两行结果是一样的，下面一行是先调用了LessA类构造函数构造处函数对象后作为参数使用

STL中定义了一些函数对象类模板，都位于头文件 functional 中。例如，greater 模板的源代码如下：

template <class T>
struct greater
{
    bool operator()(const T& x, const T& y) const{
        return x > y;
    }
};
int a[4] = {3, 5, 34, 8};
sort( a, a+4, greater<int>() );

1.2、函数对象详细介绍：
如果一个类将()运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象。函数对象是一个对象，但是使用的形式看起来像函数调用，实际上也执行了函数调用，因而得名。
推荐学习：C++函数对象及在sort()函数中应用详解

class CAverage // 函数对象类
{
public:
    double operator()(int a1, int a2, int a3)
    {  //重载()运算符
        return (double)(a1 + a2 + a3) / 3;
    }
};

CAverage average // 函数对象
cout << average(3, 2, 3); // 像函数一样调用函数对象

2、set、map、priority_queue容器自定义排序函数：
2.1、set容器原型：

template < class T,                        // 键/值类型
           class Compare = less<T>,        // 比较函数/对象
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

2.1.1、默认排序方式：利用<比较，升序排列

int myints[] = { 4,2,7,1,9 };
set<int> mySet(myints, myints + 5);    // 1, 2, 4, 7, 9 默认升序排序

前提是a、b必须可比较大小。元素比较大小是用<进行的，如果表达式a<b的值为 true，则 a 排在 b 前面。
2.1.2、自定义比较函数：
自定义比较函数，可以当参数为结构体时，指定比较的成员变量。

• Compare为函数指针：函数返回值必须为bool量 复杂不推荐

bool fncomp(int lhs, int rhs) { return lhs<rhs; } // 比较函数
int myints[] = { 4,2,7,1,9 };
set<int, bool(*)(int, int)> mySet(fncomp);  // 变量声明方式，较复杂
sixth.insert(4);
sixth.insert(2);
sixth.insert(7);
sixth.insert(1);
sixth.insert(9); // 1, 2, 4, 7, 9 升序排序

• Compare为函数对象类型：类成员函数返回值必须为bool量 简单，推荐

struct classcomp { // 比较函数对象
	bool operator() (const int& lhs, const int& rhs) const
	{
		return lhs<rhs;
	}
};
int myints[] = { 4,2,7,1,9 };
set<int, classcomp> mySet(myints, myints + 5);    // 1, 2, 4, 7, 9 默认升序排序

2.2、map容器原型：默认也是升序
map使用键进行排序，与set类似，均常用函数对象类型作比较。
在map基础上无法实现按值排序，只能将其转换到其他容器进行。

struct classcomp {
	bool operator() (const char& lhs, const char& rhs) const
	{
		return lhs<rhs;
	}
};
std::map<char, int, classcomp> first;
first['a'] = 60;
first['c'] = 30;
first['b'] = 50;
first['d'] = 70; // a, b, c, d 根据键排序
std::map<int, int, std::greater<int>> mi; // 利用函数对象类模板实现降序排序

2.2.2、map实现按值排序：
将map的键值对放入vector中，利用sort自定义排序。

bool cmp(const pair<string,int> &p1, const pair<string,int> &p2) {
    return p1.second > p2.second; // 按值排序
}

vector<pair<string,int> > vpr;
for(map<string,int>::iterator it = mp.begin(); it != mp.end(); it++){
    vpr.push_back(make_pair(it->first,it->second);
}
sort(vpr.begin(),vpr.end(),cmp);

2.3、priority_queue容器原型：

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

T：元素的类型。别名为成员类型priority_queue :: value_type。
Container：存储元素的内部基础容器对象的类型，其value_type应为T，别名为成员类型priority_queue :: container_type。
2.3.1、默认排序方式：升序

int myints[] = { 10,60,50,20 };
std::priority_queue<int> second(myints, myints + 4); // 10, 20, 50, 60

2.3.2、自定义比较函数：

class mycomparison
{
public:
	bool operator() (const int& lhs, const int&rhs) const
	{
		return (lhs<rhs);
	}
};
std::priority_queue<int, std::vector<int>, std::greater<int> > 
	third(myints, myints + 4); // 60, 50, 20, 10
std::priority_queue<int, std::vector<int>, mycomparison> // 10, 20, 50, 60

由于模板参数必须顺序赋值，不能调过中间的基本容器参数，所以需要有std::vector<int>,部分。

总结：

1、所有容器、sort()函数默认都是升序排列。
2、可以使用函数指针与函数对象方法进行自定义排序。
3、priority_queue自定义比较函数时需要多家一个基本容器参数vector。