189 8069 5689
前言
创新互联是一家网站设计公司，集创意、互联网应用、软件技术为一体的创意网站建设服务商，主营产品：响应式网站设计、品牌网站建设、全网营销推广。我们专注企业品牌在网站中的整体树立，网络互动的体验，以及在手机等移动端的优质呈现。成都做网站、网站设计、移动互联产品、网络运营、VI设计、云产品.运维为核心业务。为用户提供一站式解决方案，我们深知市场的竞争激烈，认真对待每位客户，为客户提供赏析悦目的作品，网站的价值服务。
STL主要包含容器，迭代器，算法三块内容，用户可以对容器进行一系列的操作，比如遍历和计算，而STL提供的迭代器和容器完美地提供了这样的接口。其中std::vector是最常用的容器之一，vector是一个模板类，定义在命名空间namespace下，使用vector需要在包含相关头文件。今天主要讲解对vector的排序的使用。
sort类函数：
| 函数名 | 功能描述 |
|---|---|
| sort | 对给定区间所有元素进行排序 |
| stable_sort | 对给定区间所有元素进行稳定排序 |
| partial_sort | 对给定区间所有元素部分排序 |
| partial_sort_copy | 对给定区间复制并排序 |
| nth_element | 找出给定区间的某个位置对应的元素 |
| is_sorted | 判断一个区间是否已经排好序 |
| partition | 使得符合某个条件的元素放在前面 |
| stable_partition | 相对稳定的使得符合某个条件的元素放在前面 |
需要头文件
语法描述：sort（begin，end，cmp），cmp参数可以没有，如果没有默认非降序排序。
常见的排序算法有快速排序、冒泡排序、归并排序等。STL中sort函数的实现跟STL的版本有关，而往往sort函数是由多种排序算法混合而成的。
1. vector元素为内置数据类型
STL中sort函数的使用方法如下，默认对容器进行从小到大的排序。
#include// std::vector #include // std::sort int main(){ std::vector vi{2, 0, 1, 8, 1, 2, 1, 5}; std::sort(vi.begin(), vi.end()); // 相当于 std::sort(vi.begin(), vi.end(), std::less ()); for (int i = 0; i < vi.size(); ++i) { printf("%d ", vi[i]); } printf("\n"); // output: 0 1 1 1 2 2 5 8
当然也可以指定对容器进行从大到小的排序：
#include// std::vector #include // std::sort int main(){ std::vector vi{2, 0, 1, 8, 1, 2, 1, 5}; std::sort(vi.begin(), vi.end(), std::greater ()); 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函数的定义：
templatevoid 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 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 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
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对创新互联的支持。