HOWTO · C++
在 C++ 中对向量进行排序
本文介绍如何在 C++ 中对向量进行排序
本页内容
在 C++ 中对 std::vector 排序时，调用 std::sort，并传入向量的 begin() 和 end() 迭代器。默认情况下，元素按 operator< 排序。若类型采用其他排序规则，可传入比较器，由它判断第一个参数是否应排在第二个参数之前。
使用 std::sort 对向量排序
std::sort 会重新排列半开区间中的元素：从第一个迭代器指向的位置开始，到最后一个迭代器指向的位置为止，但不包含后者。std::vector 提供此算法所需的随机访问迭代器。使用 std::sort 需要包含 <algorithm>；示例还包含用于输出的 <iostream> 和用于容器的 <vector>。如果不传入比较器参数，算法会采用元素类型的默认排序规则，通常由 operator< 表示。
运行此示例，输出按升序排列的数值：
本节中的代码以及显示的标签或输出仍为英文。
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{8, 3, 6, 1, 5};
std::sort(values.begin(), values.end());
for (std::size_t index = 0; index < values.size(); ++index) {
if (index != 0) {
std::cout << ' ';
}
std::cout << values[index];
}
std::cout << '\n';
}
1 3 5 6 8
对整个向量排序时，使用相同的迭代器范围；若只需排序其中一部分，则传入界定该部分的迭代器。范围必须有效，且不包含最后一个迭代器。对于数字，以及已定义所需排序规则的类型，默认排序方式很实用。对于记录类型，可以通过比较器明确指定要比较的字段。
使用 lambda 比较器对记录排序
lambda 可以将简短的比较规则放在使用它的排序操作旁边。本例按 Task 记录的 priority 字段排序。比较器接收两条记录；如果第一条应排在第二条之前，就返回 true。参数使用 const 引用，因为比较时无需修改记录。
运行此示例；代码和输出中的任务名称保持英文，输出按优先级升序列出任务：
本节中的代码以及显示的标签或输出仍为英文。
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Task {
std::string name;
int priority;
};
int main() {
std::vector<Task> tasks{{"write", 3}, {"review", 1}, {"build", 2}};
std::sort(tasks.begin(), tasks.end(),
[](const Task& left, const Task& right) {
return left.priority < right.priority;
});
for (const Task& task : tasks) {
std::cout << task.name << ':' << task.priority << '\n';
}
}
review:1
build:2
write:3
比较规则必须满足严格弱序：行为一致，并且任何元素都不能排在自身之前。用 < 比较整数型字段会按优先级升序排列。调换操作数就会改变排序方向。如果再次调用 std::sort 并传入不同的比较器，该次调用会按新规则重新排列当前范围；连续调用不会将各次的比较键合并成多字段排序。若需要依据多个条件排序，应在一个比较器中表达完整规则。
使用具名比较器复用排序规则
如果同一规则会在多处使用，可以为它命名。带有 const 调用运算符的函数对象和 lambda 一样，可以传给 std::sort。本例按任务名称排序，因此需要此规则的地方都可以复用该比较器。
运行此示例；代码和输出中的任务名称保持英文，输出按名称排序：
本节中的代码以及显示的标签或输出仍为英文。
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Task {
std::string name;
int priority;
};
struct ByName {
bool operator()(const Task& left, const Task& right) const {
return left.name < right.name;
}
};
int main() {
std::vector<Task> tasks{{"write", 3}, {"review", 1}, {"build", 2}};
std::sort(tasks.begin(), tasks.end(), ByName{});
for (const Task& task : tasks) {
std::cout << task.name << ':' << task.priority << '\n';
}
}
build:2
review:1
write:3
如果具名比较器的逻辑值得用一个描述性名称来表达，或需要供多次排序调用共享，那么使用具名比较器会很方便。排序规则应与数据相符；只读比较时，参数应使用 const 引用。若只是一次性比较某个字段，通常直接使用 lambda 更简洁。无论采用哪种形式，顺序都由比较器决定；只有未提供比较器时，才使用默认的 operator<。
