C++11 std::is_sorted 和 std::is_sorted_until 原理解析
原创
C++11 std::is_sorted 和 std::is_sorted_until 原理解析
原创
码事漫谈
发布于 2025-07-10 19:27:42
发布于 2025-07-10 19:27:42
1. 功能概述
- std::is_sorted：检查序列是否按升序（或自定义顺序）排列，返回布尔值。
- std::is_sorted_until：返回序列中第一个破坏排序的元素迭代器，若完全有序则返回尾迭代器。
2. 算法原理
2.1 std::is_sorted
- 核心逻辑：遍历序列，检查所有相邻元素对是否满足排序条件（默认前 <= 后）。
- 边界情况：空序列或单元素序列视为有序。
- 时间复杂度：O(n)，n为元素个数。
2.2 std::is_sorted_until
- 核心逻辑：遍历序列，找到第一个不满足排序条件的相邻元素对，返回后一个元素的迭代器。
- 时间复杂度：O(n)。
3. 简化源码实现
3.1 基于直接遍历的实现
// std::is_sorted 简化版（默认比较器）
template <typename ForwardIt>
bool is_sorted(ForwardIt first, ForwardIt last) {
if (first == last) return true; // 空序列
for (ForwardIt next_it = std::next(first); next_it != last; ++first, ++next_it) {
if (*next_it < *first) { // 发现逆序对
return false;
}
}
return true;
}
// std::is_sorted_until 简化版（默认比较器）
template <typename ForwardIt>
ForwardIt is_sorted_until(ForwardIt first, ForwardIt last) {
if (first == last) return last;
for (ForwardIt next_it = std::next(first); next_it != last; ++first, ++next_it) {
if (*next_it < *first) { // 发现逆序对，返回后一个元素迭代器
return next_it;
}
}
return last; // 完全有序
}3.2 基于 std::adjacent_find 的实现（标准库风格）
#include <algorithm> // for std::adjacent_find
// 利用 adjacent_find 查找逆序对
template <typename ForwardIt>
bool is_sorted(ForwardIt first, ForwardIt last) {
// adjacent_find 返回第一个满足 *it > *(it+1) 的 it
return std::adjacent_find(first, last, std::greater<>) == last;
}
template <typename ForwardIt>
ForwardIt is_sorted_until(ForwardIt first, ForwardIt last) {
auto it = std::adjacent_find(first, last, std::greater<>);
return (it == last) ? last : std::next(it);
}3.3 带自定义比较器的版本
// 自定义比较器版本（以降序为例）
template <typename ForwardIt, typename Compare>
bool is_sorted(ForwardIt first, ForwardIt last, Compare comp) {
if (first == last) return true;
for (ForwardIt next_it = std::next(first); next_it != last; ++first, ++next_it) {
if (comp(*next_it, *first)) { // 使用 comp 判断逆序
return false;
}
}
return true;
}
template <typename ForwardIt, typename Compare>
ForwardIt is_sorted_until(ForwardIt first, ForwardIt last, Compare comp) {
if (first == last) return last;
for (ForwardIt next_it = std::next(first); next_it != last; ++first, ++next_it) {
if (comp(*next_it, *first)) {
return next_it;
}
}
return last;
}4. 使用示例
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
// 基本用法
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {1, 3, 2, 4, 5};
std::cout << "v1 is sorted: " << std::boolalpha << std::is_sorted(v1.begin(), v1.end()) << "\n"; // true
std::cout << "v2 is sorted: " << std::is_sorted(v2.begin(), v2.end()) << "\n"; // false
auto it1 = std::is_sorted_until(v1.begin(), v1.end());
auto it2 = std::is_sorted_until(v2.begin(), v2.end());
std::cout << "v1 sorted until index: " << (it1 - v1.begin()) << "\n"; // 5（end）
std::cout << "v2 sorted until index: " << (it2 - v2.begin()) << "\n"; // 2（元素2的位置）
// 自定义比较器（降序检查）
std::vector<int> v3 = {5, 4, 3, 2, 1};
std::cout << "v3 is sorted descending: " << std::is_sorted(v3.begin(), v3.end(), std::greater<int>()) << "\n"; // true
return 0;
}5. 应用场景
- 验证排序结果正确性。
- 快速判断序列是否需要排序。
- 获取最长有序前缀长度（通过
std::distance(first, is_sorted_until(first, last))）。
6. 注意事项
- 迭代器类型：支持前向迭代器及以上（如双向迭代器、随机访问迭代器）。
- 自定义比较器：需满足严格弱序（Strict Weak Ordering）。
- 空序列处理：始终返回 true（is_sorted）或尾迭代器（is_sorted_until）。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号