前言
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函数的使用方法如下，默认对容器进行从小到大的排序。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <vector> // std::vector#include <algorithm> // std::sortint 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 |
当然也可以指定对容器进行从大到小的排序：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <vector> // std::vector#include <algorithm> // std::sortint 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函数的定义：
|
1
2
|
template <class RandomAccessIterator, class Compare>void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
其中前两个参数为迭代器类型，第三个参数为比较函数。下面的例子中，类Character拥有两个属性，age_ 和 name_，这里为了简单起见，变量均为public。现在需要对一个元素类型为Character的vector进行按照Character的 age_ 从小打到进行排序。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
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 的条件：
|
1
2
3
4
5
6
7
8
9
|
X a;X b;Condition: Test Resulta is equivalent to b: Compare(a, b) false Compare(b, a) falsea is less than b Compare(a, b) true Compare(b, a) falseb 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；
|
1
2
3
4
5
6
7
8
|
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; }}; |
完整的测试代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对服务器之家的支持。
原文链接：https://www.cnblogs.com/satchel/p/10123420.html
