6.25小学期CPP基础语法记录：反转、字符串查找、稳定sort

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’

📘 实战对比与举一反三