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

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）。