当前位置：首页 > news >正文

C++11 std::is_sorted 和 std::is_sorted_until 原理解析

news 2025/7/21 4:00:10

文章目录

- 1. 功能概述
- 2. 算法原理
- - 2.1 std::is_sorted
  - 2.2 std::is_sorted_until
- 3. 简化源码实现
- - 3.1 基于直接遍历的实现
  - 3.2 基于 std::adjacent_find 的实现（标准库风格）
  - 3.3 带自定义比较器的版本
- 4. 使用示例
- 5. 应用场景
- 6. 注意事项

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) 的 itreturn 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"; // truestd::cout << "v2 is sorted: " << std::is_sorted(v2.begin(), v2.end()) << "\n"; // falseauto 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"; // truereturn 0;
}