极客教程

Appearance

共 806 字预计阅读约 3 分钟

sort / find 等算法库 ​

更新时间：2026-08-27。本文是 languages/cpp/ 主题入门层第 39 篇（存量 stl-containers 拆解迁入）。std::sort、std::find、std::count 这些算法只认迭代器、不认容器：同一套 sort 能排 vector、deque、array，还能配自定义比较器。这是 STL 三件套（容器+迭代器+算法）的最后一块。

本文要回答的问题 ​

  • 算法库怎么做到"与容器无关"？
  • 排序怎么用？自定义比较器怎么写？
  • 常用算法有哪些？各自什么复杂度？

一、算法只认迭代器 ​

cpp
#include <algorithm>
#include <vector>

std::vector<int> v = {5, 2, 8, 1};

std::sort(v.begin(), v.end());              // 排序
auto it = std::find(v.begin(), v.end(), 8); // 查找
int n = std::count(v.begin(), v.end(), 1);  // 计数
bool any = std::any_of(v.begin(), v.end(),  [](int x){ return x < 0; });  // 判断

算法接收迭代器范围 [begin, end)，对"是什么容器"一无所知——vector、deque、array 全都能用。这就是容器与算法的解耦：你想换容器，算法代码一行不用改。

注意范围是左闭右开 [begin, end)：end 指向最后一个元素的"后一个位置"，不含它自己。这是 STL 的统一约定，写循环边界时心里要有这个数。

二、排序与自定义比较器 ​

默认升序：

cpp
std::sort(v.begin(), v.end());          // 升序
std::sort(v.begin(), v.end(), std::greater<int>());   // 降序

自定义结构体排序——给 sort 第三个参数传比较器（比较函数或 lambda，第 49 篇系统讲 lambda）：

cpp
struct Student { std::string name; int score; };

std::vector<Student> students = {{"alice", 95}, {"bob", 88}, {"carol", 92}};

std::sort(students.begin(), students.end(),
          [](const Student& a, const Student& b) {
              return a.score > b.score;   // 按分数降序
          });

比较器返回"a 是否排在 b 前面"。这比 C 的 qsort 舒服太多——C 要写 int (*cmp)(const void*, const void*) 还得手动 *(const Student**)a 转类型，C++ 的 lambda 直接写成员访问。

三、find / count / 其他常用算法 ​

cpp
std::vector<int> v = {3, 1, 4, 1, 5, 9};

auto it = std::find(v.begin(), v.end(), 4);    // 找 4，返回迭代器
if (it != v.end()) { /* 找到了，*it == 4 */ }

int ones = std::count(v.begin(), v.end(), 1);   // 1 出现 2 次

std::sort(v.begin(), v.end());                  // 排序后：
std::binary_search(v.begin(), v.end(), 5);      // 二分查找 O(log n)（要求已排序）

std::min_element(v.begin(), v.end());           // 最小元素位置
std::max_element(v.begin(), v.end());           // 最大元素位置
std::accumulate(v.begin(), v.end(), 0);         // 求和（<numeric>）
std::reverse(v.begin(), v.end());               // 反转
算法作用复杂度
sort排序O(n log n)
find线性查找O(n)
binary_search二分查找（需已排序）O(log n)
count计数O(n)
min/max_element找最值O(n)
accumulate求和/累积O(n)
reverse反转O(n)
any_of/all_of条件判断O(n)

四、二分查找的前提：先排序 ​

cpp
std::sort(v.begin(), v.end());      // 先排序！
bool ok = std::binary_search(v.begin(), v.end(), 5);

binary_search 要求容器已排序，否则结果是未定义的（不会报错，但可能找不到）。配套姿势：大数据量多次查找 → 一次 sort + 多次 binary_search/lower_bound，比每次都 find 快得多。这和 C 的 qsort + bsearch 组合一脉相承。

五、和 C 对比 ​

对比项CC++
排序qsort + void* 比较函数std::sort + lambda
查找bsearch / 手写循环find / binary_search
类型安全void* 无检查模板全类型检查
容器无关每种结构一套迭代器通用
性能差不多模板内联常更快

qsort 的 void* 回调既慢又不安全（编译期零检查），std::sort 是模板，比较逻辑编译期内联——同样 O(n log n)，C++ 版本通常更快。

六、与本站主线衔接 ​

  • 排序算法的原理与复杂度，见 排序算法；
  • 算法与 lambda 的配合，见 lambda 入门；
  • 迭代器是这一切的基础，回看 迭代器与范围 for；
  • 下一篇：stack / queue / priority_queue——容器适配器。

一句话总结 ​

std::sort、find、count 等算法只认迭代器不认容器，[begin, end) 左闭右开，同一套算法全容器通用；自定义排序给第三个参数传 lambda 比较器（返回"a 是否排 b 前"）；binary_search 必须配合 sort 使用；对比 C 的 qsort/bsearch，模板算法类型安全且常常更快。

上一篇：迭代器与范围 for　下一篇：stack / queue / priority_queue