reverse函数

在 C++ 中，reverse 是一个非常常用的 STL 算法，用于就地反转序列中的元素顺序。它定义在 <algorithm> 头文件中。

🧩 函数定义

template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);

参数说明：
- first：反转范围的起始迭代器（包含）。
- last：反转范围的终止迭代器（不包含）。
返回值：
- 无（void），它是就地修改，直接在原容器上改变顺序。
迭代器要求：
- 必须是双向迭代器（如 vector, list, deque 都支持；forward_list 不支持）。

示例

1. 反转 `vector<int>`

#include <iostream>
#include <vector>
#include <algorithm> // for reverse

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::reverse(v.begin(), v.end());

    for (int i : v) std::cout << i << " ";
    return 0;
}

输出：

5 4 3 2 1

2. 反转 `string`（也支持，因为 `string::iterator` 是双向的）

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    std::string s = "abcdef";
    std::reverse(s.begin(), s.end());
    std::cout << s;  // 输出: fedcba
    return 0;
}

3. 局部反转

cpp复制编辑std::vector<int> v = {10, 20, 30, 40, 50, 60};
// 只反转中间部分 [1, 4)
std::reverse(v.begin() + 1, v.begin() + 4);  // -> 10, 40, 30, 20, 50, 60

reverse 的底层实现原理

使用的是双向迭代器，通过交换 front 和 back 元素来实现反转。

伪代码：

while (first != last && first != --last) {
    swap(*first, *last);
    ++first;
}

时间复杂度与空间复杂度

时间复杂度： O(n)
空间复杂度： O(1)（原地操作，不使用额外空间）

举一反三

std::reverse_copy(first, last, dest)：把反转结果复制到另一个位置，不影响原数据。

std::vector<int> v = {1,2,3,4,5};
std::vector<int> res(5);
std::reverse_copy(v.begin(), v.end(), res.begin());  // res = 5,4,3,2,1

如果你想自己实现一个 reverse 函数，可以练习写模板函数操作双向迭代器。

string::find函数

C++ 中的 string::find 是处理字符串查找的核心函数，常用于查找某个子串或字符第一次出现的位置。下面我们详细分析它的用法、变体、返回值，再拓展介绍其他常见的字符串查找函数，比如 rfind、find_first_of、find_last_of、find_first_not_of 等。

一、`string::find` 基本用法

size_t find(const string& str, size_t pos = 0) const;
size_t find(const char* s, size_t pos = 0) const;
size_t find(const char* s, size_t pos, size_t n) const;
size_t find(char c, size_t pos = 0) const;

参数说明：

str / s / c: 要查找的目标字符串/字符。
pos: 从原字符串的哪个位置开始查找（默认为 0）。

返回值：

成功：返回目标第一次出现的位置（类型为 size_t）。
失败：返回 string::npos（一个极大的无符号整数，表示未找到）。

示例一：查找子串

std::string s = "hello world";
size_t pos = s.find("world"); // 返回 6

示例二：查找字符

std::string s = "abcabc";
size_t pos = s.find('b');  // 返回 1，第一个 b 的位置

示例三：未找到

std::string s = "hello";
size_t pos = s.find("abc");
if (pos == std::string::npos)
    std::cout << "not found";

示例四：从指定位置开始查找

std::string s = "abcabc";
size_t pos = s.find('b', 2);  // 返回 4，跳过前面的 b

二、其他查找方法汇总

1️⃣ `rfind`：从右往左找（返回最后一次出现的位置）

std::string s = "abcabc";
size_t pos = s.rfind('b');  // 返回 4

2️⃣ `find_first_of`：查找任一字符第一次出现的位置

std::string s = "hello world";
size_t pos = s.find_first_of("aeiou");  // 返回 1，‘e’是第一个元音

3️⃣ `find_last_of`：查找任一字符最后一次出现的位置

std::string s = "abcabc";
size_t pos = s.find_last_of("ab");  // 返回 4，‘b’在位置4最后出现

4️⃣ `find_first_not_of`：找第一个不是指定字符集的字符

std::string s = "aaaabc";
size_t pos = s.find_first_not_of('a');  // 返回 4，‘b’不是 ‘a’

5️⃣ `find_last_not_of`：找最后一个不是指定字符集的字符

std::string s = "abcddd";
size_t pos = s.find_last_not_of('d');  // 返回 2，‘c’不是 ‘d’

实战对比与举一反三

函数名	含义	查找方向	典型用途
`find`	第一次出现	左→右	查找特定子串或字符
`rfind`	最后一次出现	右→左	查找最后一个位置
`find_first_of`	第一次出现（任一）	左→右	查找多个候选字符之一
`find_last_of`	最后一次出现（任一）	右→左
`find_first_not_of`	第一个不是指定字符	左→右	忽略前缀空格等
`find_last_not_of`	最后一个不是指定字符	右→左	忽略后缀空格等

🧠 延伸：用 find 实现字符串替换

std::string s = "abcabc";
std::string from = "ab", to = "XY";

size_t pos = 0;
while ((pos = s.find(from, pos)) != std::string::npos) {
    s.replace(pos, from.length(), to);
    pos += to.length(); // 避免死循环
}
// s 变为 "XYcXYc"

计数排序的巧妙用法

【问题描述】

       定义一个字符串的无序度为所有位置后面的字母比该位置的字母小的总数之和。比如"DAABEC''这个字符串的无序度是5，因为D后面有4个位置比它小（AABC），E后面有1个比它小（C），其它位置后面没有比自己小的。" AACEDGG "的无序度为1（E后面有一个D比它小）。" ZWQM "的无序度为6，每个位置后面所有的字母都比它小。
       现在你的任务是给定一些字符串（只由大写字母组成），把他们按照无序度从小到大排序，如果无序度一样，那么就按照输入的相对顺序排序。

【输入形式】

     单组测试数据。
     第一行有两个整数n(0 < n <= 50)和m (0 < m <= 100)，分别表示输入的字符串的长度和字符串的个数。
     接下来m行，每一行包含一个长度为n的字符串，只由大写字母组成。
【输出形式】

    输出m行，表示排序之后的字符串。
【样例输入】

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
【样例输出】

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

面对形如求逆序数的题目，常用的方法有：

暴力法（省略）
归并排序
树状数组
线段树

但对于只包含大写字母的情况，我们可以用O(n)时间复杂度的算法：

使用计数数组的方法

思路是从右向左遍历字符串，维护一个计数数组记录已经遇到的每个字符的数量：

// 以O(n)时间复杂度计算字符串无序度
int cal(string a){
    int cnt[26] = {0}, ans = 0;
    for(int i = n - 1; i >= 0; --i){
        int num = a[i] - 'A';
        ++cnt[num];
        for(int j = num - 1; j >= 0; --j){
            ans += cnt[j];
        }
    }
    return ans;
}

原理解释

从右向左遍历字符串，这样我们处理每个字符时，它后面的字符已经被处理过
对于每个位置i，我们统计在位置i后面出现的、比字符s[i]小的所有字符的数量
使用计数数组count记录已处理的每个字符的出现次数
对于当前字符s[i]，统计比它小的所有字符(A到s[i]-1)的出现次数之和，这就是该位置对无序度的贡献

这个方法的时间复杂度是O(n)，因为外层循环n次，内层循环最多26次（大写字母数量固定），所以总体是O(26n) = O(n)。

完整解决方案

计数排序思路

#include <bits/stdc++.h>
using namespace std;

int n, m;
int cal(string a){
    int cnt[26] = {0}, ans = 0;
    for(int i = n - 1; i >= 0; --i){
        int num = a[i] - 'A';
        ++cnt[num];
        for(int j = num - 1; j >= 0; --j){
            ans += cnt[j];
        }
    }
    return ans;
}

int main(){
    cin >> n >> m;
    vector<pair<string, int>> strs(m);
    for(int i = 0; i < m; ++i){
        cin >> strs[i].first;
        strs[i].second = cal(strs[i].first);
    }
    stable_sort(strs.begin(), strs.end(), 
                [](pair<string, int> a, pair<string, int> b){
        return a.second < b.second;
    });
    for(int i = 0; i < m; ++i){
        cout << strs[i].first << endl;
    }
}

归并算法

// 使用归并排序计算无序度
int mergeCount = 0; // 全局变量记录逆序对数量

void merge(vector<char>& arr, int left, int mid, int right) {
    vector<char> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            // 当右半部分元素小于左半部分时，构成逆序对
            temp[k++] = arr[j++];
            mergeCount += (mid - i + 1); // 计算逆序对
        }
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    for (i = left, k = 0; i <= right; i++, k++) {
        arr[i] = temp[k];
    }
}

void mergeSort(vector<char>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

// 计算字符串无序度
int calculateDisorder(const string& s) {
    // 需要重新组织数据结构来适应我们的问题
    vector<pair<char, int>> charWithPos;
    for (int i = 0; i < s.length(); i++) {
        charWithPos.push_back({s[i], i});
    }
    
    // 结果...
}

树状数组

class BIT {
private:
    vector<int> tree;
    int n;
    
    int lowbit(int x) {
        return x & (-x);
    }
    
public:
    BIT(int size) : n(size), tree(size + 1, 0) {}
    
    void update(int idx, int val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += lowbit(idx);
        }
    }
    
    int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= lowbit(idx);
        }
        return sum;
    }
};

int calculateDisorder(const string& s) {
    int n = s.length();
    int disorder = 0;
    
    // 创建离散化映射(A-Z -> 1-26)
    map<char, int> charToIdx;
    for (char c = 'A'; c <= 'Z'; c++) {
        charToIdx[c] = c - 'A' + 1;
    }
    
    BIT bit(26); // 26个大写字母
    
    // 从右向左遍历
    for (int i = n - 1; i >= 0; i--) {
        int idx = charToIdx[s[i]];
        // 查询比当前字符小的所有字符的出现次数
        disorder += bit.query(idx - 1);
        // 更新当前字符的出现次数
        bit.update(idx, 1);
    }
    
    return disorder;
}

线段树

class SegmentTree {
private:
    vector<int> tree;
    int n;
    
public:
    SegmentTree(int size) : n(size) {
        tree.resize(4 * n, 0);
    }
    
    void update(int node, int start, int end, int idx) {
        if (start == end) {
            tree[node]++;
            return;
        }
        
        int mid = (start + end) / 2;
        if (idx <= mid) {
            update(2 * node, start, mid, idx);
        } else {
            update(2 * node + 1, mid + 1, end, idx);
        }
        
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
    int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0;
        }
        
        if (l <= start && end <= r) {
            return tree[node];
        }
        
        int mid = (start + end) / 2;
        int leftSum = query(2 * node, start, mid, l, r);
        int rightSum = query(2 * node + 1, mid + 1, end, l, r);
        
        return leftSum + rightSum;
    }
};

稳定的`sort` —— `stable_sort`用法详解

我们来系统讲解 std::stable_sort：不仅要理解它的功能和用法，还要深入分析它为什么叫“稳定排序”（stable）以及它背后的算法原理。

🧩 一、`std::stable_sort` 概述

#include <algorithm>

template <class RandomIt>
void stable_sort(RandomIt first, RandomIt last);

template <class RandomIt, class Compare>
void stable_sort(RandomIt first, RandomIt last, Compare comp);

作用：对 [first, last) 区间的元素进行稳定排序。
特点：排序后，相等元素的原始相对顺序保持不变。
迭代器要求：必须是随机访问迭代器（如 vector, deque, 原始数组等）。

二、稳定排序的含义

稳定性定义：

如果在排序前，两个元素 A 和 B 相等（A == B），并且 A 在 B 前面；排序后，A 仍然在 B 前面 → 这种排序叫做 稳定排序（stable sort）。

举个例子更直观：

struct Item {
    int key;
    char tag; // 附加标记，用于区分原始顺序
};

vector<Item> items = {
    {2, 'a'},
    {1, 'b'},
    {2, 'c'},
    {1, 'd'}
};

std::stable_sort(items.begin(), items.end(), [](Item a, Item b) {
    return a.key < b.key;
});

排序后结果：

{1, 'b'}, {1, 'd'}, {2, 'a'}, {2, 'c'}

注意：虽然 1 和 2 都出现了多次，但其原始相对顺序被保留。

️ 三、和 `std::sort` 的区别

特性	`std::sort`	`std::stable_sort`
是否稳定	否	是
时间复杂度	最优 `O(n log n)`	最优 `O(n log^2 n)`
空间复杂度	原地排序 `O(1)`	需要额外空间 `O(n)`
使用算法	快速排序/混合排序	通常是归并排序

🧠 四、为什么 `stable_sort` 是稳定的？

原因：底层是归并排序

std::stable_sort 通常使用 优化版归并排序（Merge Sort） 实现，因为归并排序天然稳定。

稳定的原因核心在于“合并过程不打乱相等元素的原始顺序”：

在归并两个有序子序列时，如果出现：

Left[i] == Right[j]

稳定排序会优先选择左边的元素（原先靠前）进入结果，确保相对顺序不变。

所以：即使 operator< 或自定义比较函数 comp 不区分相等元素，稳定排序也不会打乱原始顺序。

五、使用示例

示例一：默认比较

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> v = {5, 3, 4, 3, 2};
    std::stable_sort(v.begin(), v.end());

    for (int x : v) std::cout << x << " ";
    return 0;
}
// 输出：2 3 3 4 5

示例二：结构体排序（强调稳定性）

#include <iostream>
#include <vector>
#include <algorithm>

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

int main() {
    std::vector<Student> students = {
        {90, "Alice"},
        {85, "Bob"},
        {90, "Charlie"},
        {85, "David"}
    };

    std::stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        return a.score < b.score;
    });

    for (const auto& s : students)
        std::cout << s.score << " " << s.name << "\n";
    return 0;
}

输出：