C / C++ / 系统课时
用 sort 给容器数据排序
用 sort 给容器数据排序
当 vector 中的数据需要按大小重新排列时,不必自己编写冒泡排序等循环。标准库的 std::sort 可以直接处理一段迭代器范围,并原地改变元素顺序。本节用一个完整示例掌握它最常见的写法,并理解 [begin, end) 范围的含义。
学习目标
- 使用
std::sort对vector元素进行升序排序 - 理解算法参数中的起始迭代器和结束迭代器
- 知道排序会直接修改原容器中的元素顺序
sort 接收的是迭代器范围
std::sort 定义在 <algorithm> 中。最常见的调用形式是 std::sort(first, last),它处理从 first 开始、到 last 之前结束的范围,也就是左闭右开的 [first, last)。
对于 vector,begin() 指向第一个元素,end() 指向最后一个元素之后的位置,因此 std::sort(values.begin(), values.end()) 正好覆盖整个容器。
对 vector 进行升序排序
下面的程序先保存一组乱序整数,再使用 std::sort 排序。默认比较规则会让较小的值排在前面。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{5, 2, 4, 1, 3};
// 排序范围覆盖 vector 中的全部元素。
std::sort(values.begin(), values.end());
for (int value : values) {
std::cout << value << ' ';
}
std::cout << '\n';
return 0;
}预期输出
1 2 3 4 5 std::sort 不会创建一个新的已排序容器,而是直接重新排列 values 中原有的元素。执行完成后,再读取 values,得到的就是排序后的顺序。
范围决定哪些元素参加排序
算法与具体容器解耦的重要原因,是它接收迭代器而不是整个 vector。只要提供合法范围,就可以只排序一部分元素。例如 values.begin() + 1 到 values.end() 表示跳过第一个元素,对后面的元素排序。
范围必须满足起点和终点来自同一个有效序列,并且终点能够从起点向后到达。对于 vector,std::sort 可以工作,是因为它的迭代器支持随机访问;并不是所有容器都能直接使用这个算法。
什么时候使用 sort
当数据已经存放在 vector、array 等支持随机访问迭代器的序列中,并且允许改变元素原有顺序时,std::sort 是最直接的选择。核心写法可以记成:选择一段 [first, last) 范围,让算法在这段范围内原地重新排列元素。