STL 主要包含容器, 迭代器, 算法三块内容, 用户可以对容器进行一系列的操作, 比如遍历和计算, 而 STL 提供的迭代器和容器完美地提供了这样的接口. 其中 std::vector 是最常用的容器之一, vector 是一个模板类, 定义在命名空间 namespace 下, 使用 vector 需要在包含相关头文件. 今天主要讲解对 vector 的排序的使用.
常见的排序算法有快速排序, 冒泡排序, 归并排序等. 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 https://en.cppreference.com/w/cpp/algorithm/sort
- 2. comparator
- 3. strict weak order
来源: https://www.cnblogs.com/satchel/p/10123420.html