时间：2021-03-29 09:42:15 | 栏目：C代码 | 点击：次
前言
STL主要包含容器，迭代器，算法三块内容，用户可以对容器进行一系列的操作，比如遍历和计算，而STL提供的迭代器和容器完美地提供了这样的接口。其中std::vector是最常用的容器之一，vector是一个模板类，定义在命名空间namespace下，使用vector需要在包含相关头文件。今天主要讲解对vector的排序的使用。
sort类函数：
| 函数名 | 功能描述 |
|---|---|
| sort | 对给定区间所有元素进行排序 |
| stable_sort | 对给定区间所有元素进行稳定排序 |
| partial_sort | 对给定区间所有元素部分排序 |
| partial_sort_copy | 对给定区间复制并排序 |
| nth_element | 找出给定区间的某个位置对应的元素 |
| is_sorted | 判断一个区间是否已经排好序 |
| partition | 使得符合某个条件的元素放在前面 |
| stable_partition | 相对稳定的使得符合某个条件的元素放在前面 |
需要头文件<algorithm>
语法描述：sort（begin，end，cmp），cmp参数可以没有，如果没有默认非降序排序。
常见的排序算法有快速排序、冒泡排序、归并排序等。STL中sort函数的实现跟STL的版本有关，而往往sort函数是由多种排序算法混合而成的。
1. vector元素为内置数据类型
STL中sort函数的使用方法如下，默认对容器进行从小到大的排序。
#include <vector> // std::vector
#include <algorithm> // std::sort
int main(){
std::vector<int> vi{2, 0, 1, 8, 1, 2, 1, 5};
std::sort(vi.begin(), vi.end()); // 相当于 std::sort(vi.begin(), vi.end(), std::less<int>());
for (int i = 0; i < vi.size(); ++i) {
printf("%d ", vi[i]);
}
printf("\n");
// output: 0 1 1 1 2 2 5 8
当然也可以指定对容器进行从大到小的排序：
#include <vector> // std::vector
#include <algorithm> // std::sort
int main(){
std::vector<int> vi{2, 0, 1, 8, 1, 2, 1, 5};
std::sort(vi.begin(), vi.end(), std::greater<int>());
for (int i = 0; i < vi.size(); ++i) {
printf("%d ", vi[i]);
}
printf("\n");
// output: 8 5 2 2 1 1 1 0
2. vector元素为用户自定义数据类型
如果vector内的元素为用户自定义类型，并且用户想要按照自定义类型的某些组合特性进行排序。先来看看sort函数的定义：
template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
其中前两个参数为迭代器类型，第三个参数为比较函数。下面的例子中，类Character拥有两个属性，age_ 和 name_，这里为了简单起见，变量均为public。现在需要对一个元素类型为Character的vector进行按照Character的 age_ 从小打到进行排序。
class Character {
public:
Character(int n, string s) : age_(n), name_(s) {}
int age_;
string name_;
};
class Compare {
public:
bool operator() (Character* ca, Character* cb) {
return ca->age_ < cb->age_;
}
};
int main(){
vector<Character*> vc{new Character(1, "sasaki"), new Character(2, "nozomi"), new Character(1, "satchel"), new Character(6, "qingtian")};
sort(vc.begin(), vc.end(), Compare());
for (int i = 0; i < vc.size(); ++i) {
printf("%s ", vc[i]->name_.c_str());
}
return 0;
}// output: sasaki satchel nozomi qingtian
对于sort的第三个函数，用户可以自己定义任何类型的比较方式，但是需要满足 strict weak ordering 的条件：
X a; X b; Condition: Test Result a is equivalent to b: Compare(a, b) false Compare(b, a) false a is less than b Compare(a, b) true Compare(b, a) false b is less than a Compare(a, b) false Compare(b, a) true
上述例子中的 Compare 函数基于 Character 对象的 age_ 变量值进行比较。根据 strict weak ordering 的条件，对 vector 按照某种条件进行排序就比较好理解了。
对于 vector 的两个元素 a, b，如果 a 必须排在 b 前面，需要满足下面的条件：Compare(a, b) = true, Compare(b, a) = false; 如果满足 Compare(a, b) = false & Compare(b, a) = false，则说明两个元素是相等的；
拓展：对 vector 中的元素进行排序，使得 age_ 为 1 的元素排在前面，age_ != 1的元素排在后面；
分析：这种情况下 Character 被分为两类，age_ ==1 和 age_ != 1；对于任意两个 Character 对象 a, b：
1. 相等（a == b）：a->age_ == 1 && b->age_ ==1，或者 a->age_ != 1 && b->age_ != 1；
2. 小于（a < b）：a->age_ == 1 && b->age_ != 1；
class Compare {
public:
bool operator() (Character* ca, Character* cb) {
if (ca->age_ == 1 && cb->age_ == 1 ||
ca->age_ != 1 && cb->age_ != 1) return false;
return ca->age_ == 1;
}
};
完整的测试代码：
class Character {
public:
Character(int n, string s) : age_(n), name_(s) {}
int age_;
string name_;
};
class Compare {
public:
bool operator() (Character* ca, Character* cb) {
if (ca->age_ == 1 && cb->age_ == 1 ||
ca->age_ != 1 && cb->age_ != 1) return false;
return ca->age_ == 1;
}
};
int main() {
vector<Character*> vc{ new Character(1, "sasaki"), new Character(2, "nozomi"), new Character(1, "satchel"), new Character(6, "qingtian") };
sort(vc.begin(), vc.end(), Compare());
for (int i = 0; i < vc.size(); ++i) {
printf("%s ", vc[i]->name_.c_str());
}
return 0;
}// output: sasaki satchel nozomi qingtian
Reference:
1. std::sort
2. comparator
3. strict weak order
总结