时间轴

2025-10-03

init

2025-10-12

add next_permutation 生成序列的全排列

2025-10-19

add string

语法

& 与 &&，左值与右值

  • 左值 (Lvalue)

    • 有名字，可取地址。

    • 可以出现在赋值符号左边。

    • 例子：

      1
      2
      3
      int x = 5; // x 是左值
      x = 10;    // 可以赋值
      int* p = &x; // 可以取地址

  • 右值 (Rvalue)

    • 临时对象或字面量，没有名字，不能取地址。

    • 通常出现在赋值符号右边。

    • 例子：

      1
      2
      int y = x + 2; // x+2 是右值
      int z = 42;    // 42 是右值

    注意：右值可以绑定到 右值引用 (&&)。

  • 引用类型

引用 含义
T& 左值引用（只能绑定到左值）
T&& 右值引用（只能绑定到右值）

示例：

1
2
3
int a = 5;
int &lref = a;   // 左值引用，a 是左值
int &&rref = 5;  // 右值引用，5 是右值
  • 左值引用可以修改左值：
1
lref = 10; // a = 10
  • 右值引用常用于移动语义：
1
2
vector<int> v1 = {1,2,3};
vector<int> v2 = std::move(v1); // 右值引用允许移动资源

输入输出

输入

首先，在C++语言中，要使用标准的输入，需要包含头文件< iostream >

  • cin

cin是C++中， 标准的输入流对象，下面列出cin的两个用法，单独读入，和批量读入，cin的原理，简单来讲，是有一个缓冲区，我们键盘输入的数据，会先存到缓冲区中，用cin可以从缓冲区中读取数据。

注意1：cin可以连续从键盘读入数据

注意2：cin以空格、tab、换行符作为分隔符

注意3：cin从第一个非空格字符开始读取，直到遇到分隔符结束读取

  • getline()
1
2
istream& getline (char* s, streamsize n );
istream& getline (char* s, streamsize n, char delim );

从cin的注意中，也可以看出，当我们要求读取的字符串中间存在空格的时候，cin会读取不全整个字符串，这个时候，可以采用getline()函数来解决。

注意1：使用getline()函数的时候，需要包含头文件<string>

注意2：getline()函数会读取一行，读取的字符串包括空格，遇到换行符结束

  • getchar()

该函数会从缓存区中读出一个字符，经常被用于判断是否换行

输出

同样的，在C++语言中，要使用标准的输出，也需要包含头文件<iostream>

输出这边，主要介绍一个函数，就是用的最多的cout，需要注意的是，如果输出endl对象的时候，会输出一个换行符，类似\n。

sstream

引入头文件

1
2
3
4
#include <sstream>
using std::stringstream;
using std::istringstream;
using std::ostringstream;

三个类

类名 作用 场景
stringstream 读写都支持 通用
istringstream 只读输入流 解析字符串
ostringstream 只写输出流 构造字符串

常用操作：

函数 作用 示例
str() 获取/设置内部字符串 ss.str("123 456")
clear() 清空流状态 必须在重复使用时调用
operator>> 提取数据（按空白分割） ss >> x;
operator<< 插入数据 ss << 42;
getline() 按行读取 getline(ss, s)
good() fail() 检查流状态 判断解析是否成功

注意重复使用时必须调用clear

举例：

分割字符串

1
2
3
4
5
6
7
8
9
#include <sstream>
using std::stringstream;

string s = "apple banana orange";
stringstream ss(s);
string word;
while (ss >> word) {
    cout << word << endl;
}
用途 方法 示例 说明 易错点
空白分词 ss >> word ss >> w1 >> w2 按空格、换行、制表符切分 遇到逗号等非空白不会分割
自定义分隔符 getline(ss, word, ',') getline(ss, word, ','); 按 , 切分 必须用 getline，>> 无法自定义分隔符
解析数字 ss >> num int x; ss >> x; 字符串数字 → int/double 非数字会使流失败，需检查 ss.fail()
拼接字符串 oss << val oss << "ID=" << 5; 高效构造动态字符串 输出结束后 oss.str() 才能获取完整内容

STL

vector

引用头文件

1
2
#include <vector>
using std::vector;

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 空 vector
vector<int> v1;

// 指定大小，默认初始化为0
vector<int> v2(5);  // 5个元素，每个为0

// 指定大小和初始值
vector<int> v3(5, 42);  // 5个元素，每个为42

// 通过 initializer_list
vector<int> v4 = {1, 2, 3, 4};

// 复制另一个 vector
vector<int> v5(v4);

// 从数组构造
int arr[] = {10, 20, 30};
vector<int> v6(arr, arr + 3);

访问元素

  • 返回的是元素的引用

  • 带边界检查的访问如果越界会抛出 std::out_of_range 异常

1
2
3
4
5
6
7
8
9
// 通过索引访问（不做边界检查）
int a = v[0];

// 通过 at() 访问（带边界检查）
int b = v.at(1);

// 访问首尾元素
int first = v.front();
int last = v.back();

修改元素

1
2
3
4
5
6
v[2] = 10;     // 修改索引2的值
v.push_back(5); // 在末尾插入元素
v.pop_back();   // 删除末尾元素
v.insert(v.begin() + 1, 20); // 在索引1位置插入20
v.erase(v.begin() + 2);      // 删除索引2的元素
v.clear();                   // 清空所有元素

遍历元素

1
2
3
4
5
6
7
8
9
10
11
// 索引遍历
for (size_t i = 0; i < v.size(); ++i)
    std::cout << v[i] << " ";

// 迭代器遍历
for (auto it = v.begin(); it != v.end(); ++it)
    std::cout << *it << " ";

// 范围 for（C++11+）
for (auto &x : v)
    std::cout << x << " ";

时间复杂度

操作 时间复杂度 说明
v[i] O(1) 随机访问
v.at(i) O(1) 随机访问，带边界检查
push_back(x) O(1) 摊销 平均常数时间，偶尔扩容 O(n)
pop_back() O(1) 删除末尾元素
insert(v.begin() + i, x) O(n) 插入到中间，平均移动 n/2 个元素
erase(v.begin() + i) O(n) 删除中间元素，平均移动 n/2 个元素
front() / back() O(1) 访问首尾元素
size() / empty() O(1) 获取大小/是否为空
clear() O(n) 清空元素（析构调用）
sort(v.begin(), v.end()) O(n log n) 使用 STL 算法排序

queue

引用头文件

1
2
#include <queue>
using std::queue;

构造

1
2
3
4
5
// 空队列
queue<int> q1;

// 拷贝构造
queue<int> q2(q1);

访问队头队尾

1
2
3
// 查看队首/队尾元素
int front_val = q.front();
int back_val  = q.back();

入队出队

1
2
3
4
5
6
// 入队（尾部插入）
q.push(10);
q.push(20);

// 出队（头部删除）
q.pop();

时间复杂度

操作 时间复杂度
push() O(1)
pop() O(1)
front() O(1)
back() O(1)
empty() O(1)
size() O(1)

priority_queue

  • 优先队列，内部默认使用大顶堆

  • 出队时总是弹出队列中 最大的元素（默认大顶堆）。

  • 可以自定义比较器实现 小顶堆。

priority_queue 没有迭代器，只能利用 pop()和 top()实现遍历

引用头文件

1
2
#include <queue>
using std::priority_queue;

构造

priority_queue 的泛型参数中第一个是存储元素的类型，第二个是存储元素的容器，默认为 vector，第三个是元素的比较器

注意 priority_queue 除了能弹出堆顶外，不支持直接修改或删除堆中某一个元素

  • 如果想要删除 priority_queue 中某一个元素，建议考虑能不能配合 unordered_map 实现懒删除(只有无效元素到堆顶了才删除，否则只做标记)
1
2
3
4
5
6
7
8
9
10
11
// 默认构造
priority_queue<int> pq1;
// 默认构造的全部参数
priority_queue<int,vector<int>,std::less<int>>;
// 拷贝构造
priority_queue<int> pq2(pq1);

// 从容器构造
#include <vector>
std::vector<int> v = {1, 3, 2};
priority_queue<int> pq3(v.begin(), v.end()); // 默认最大堆

访问堆顶

1
2
priority_queue<int> pq;
int top_val = pq.top(); // 20

弹出堆顶元素

1
pq.pop();

自定义比较器

方法 1：使用 std::greater实现小顶堆

1
priority_queue<int, vector<int>, std::greater<int>> min_pq;

方法 2：自定义结构体/lambda

1
2
3
4
struct cmp {
    bool operator()(int a, int b) { return a > b; } // 最小值优先
};
priority_queue<int, vector<int>, cmp> pq_custom;

方法 3：如果是结构体，直接重载<运算符

1
2
3
4
5
6
7
8
9
10
11
struct Person {
    string name;
    int age;

    // 重载 < 运算符
    bool operator<(const Person& other) const {
        return age < other.age;  // 默认大顶堆，年龄大的优先
    }
};

priority_queue<Person> pq;

时间复杂度

操作 平均复杂度
push O(log n)
pop O(log n)
top O(1)
size O(1)
empty O(1)

stack

栈，先进后出

stack 没有迭代器，不能用 for 循环直接遍历。遍历只能通过 top() + pop()。

引用头文件

1
2
#include <stack>
using std::stack;

构造

1
2
stack<int> s1;          // 空栈
stack<int> s2(s1);      // 拷贝构造

入栈/出栈

1
2
3
4
5
6
stack<int> s;
// 入栈（push 到栈顶）
s.push(20);

// 出栈（pop 栈顶元素）
s.pop();

访问栈顶元素

1
2
// 查看栈顶元素
int top_val = s.top();  // 栈顶元素

时间复杂度

操作 平均复杂度
push O(1)
pop O(1)
top O(1)
size O(1)
empty O(1)

map, unordered_map

  • map

    • map 是 有序关联容器，底层通常用 红黑树 实现。

    • 每个元素是 key-value 对，key 唯一，自动按 key 排序。

    • 适合需要 按键顺序访问 的场景。

  • unordered_map

    • unordered_map 是 哈希表，无序存储 key-value。
    • 查找、插入和删除平均时间复杂度为 O(1)。
    • 适合快速查找，不关心顺序。

    GCC 的 unordered_map 自 C++11 起有一个优化：

    • 当某个桶内链表长度超过一定阈值（通常是 8）时，链表会转为红黑树。
    • 这样可以防止 最坏情况哈希冲突导致的 O(n) 复杂度，把查找复杂度从 O(n) 降到 O(log n)。
    • 也就是：链表 → 红黑树，而不是整个哈希表退化为红黑树。

引用头文件

map

1
2
3
// map
#include <map>
using std::map;

unordered_map

1
2
3
// unordered_map
#include <unordered_map>
using std::unordered_map;

构造

map

1
2
3
4
5
6
7
8
// 空 map
map<int, string> m1;

// 拷贝构造
map<int, string> m2(m1);

// 初始化列表
map<int, string> m3 = {{1, "one"}, {2, "two"}};

unordered_map

1
2
3
4
5
6
7
8
// 空表
unordered_map<int, string> um1;

// 拷贝构造
unordered_map<int, string> um2(um1);

// 初始化列表
unordered_map<int, string> um3 = {{1,"one"}, {2,"two"}};

访问元素

map

1
2
3
4
5
map<int, string> m;

// 访问元素
string s = m[1];       // key 必须存在，否则会创建默认值

unordered_map

1
2
3
4
unordered_map<int, string> um;

// 访问元素
string s = m[1];       // key 必须存在，否则会创建默认值

插入，修改和元素

map

1
2
3
4
5
6
map<int, string> m;

// 插入元素
m.insert({3, "three"});
m[1] = "one";     // 插入或修改
m[2] = "two";

unorder_map

1
2
3
4
5
6
unordered_map<int, string> um;

// 插入
um.insert({3, "three"});
um[1] = "one";
um[2] = "two";

查找元素

map

1
2
3
4
5
6
map<int, string> m;

bool hasKey = um.count(2); // 0 或 1

auto it = m.find(2);   // 返回迭代器，找不到返回 m.end()
bool hasKey = um.count(2); // 0 或 1

unordered_map

1
2
3
4
unordered_map<int, string> um;

auto it = um.find(2);  // 返回迭代器，找不到返回 um.end()
bool hasKey = um.count(2); // 0 或 1

删除元素

map

1
2
3
4
5
map<int, string> m;

// 删除元素
m.erase(1);            // 根据 key 删除
m.erase(m.begin());    // 根据迭代器删除

unordered_map

1
2
3
4
5
unordered_map<int, string> um;

// 删除
um.erase(1);
m.erase(um.begin());    // 根据迭代器删除

遍历

map

map 是按 key 有序遍历的

1
2
3
4
5
map<int, string> m;

for (auto &[key, value] : m) {
    cout << key << " -> " << value << endl;
}

unordered_map

注意：unordered_map 是无序的，遍历顺序不固定。

1
2
3
for (auto &[key, value] : um) {
    cout << key << " -> " << value << endl;
}

自定义比较器（仅 map 支持）

1
map<int, string, std::greater<int>> m; // 按 key 降序

时间复杂度

map

操作 平均复杂度
插入/删除 O(log n)
查找 O(log n)
遍历 O(n)
访问元素 O(log n)

unordered_map

操作 平均复杂度 最坏复杂度
插入 O(1) O(n)
查找 O(1) O(n)
删除 O(1) O(n)
遍历 O(n) O(n)

set, unordered_set

  • set
    • set 是 有序集合，底层通常用 红黑树 实现。
    • 存储 唯一元素，自动按元素大小排序。
    • 适合需要 有序访问和快速查找唯一元素 的场景。
  • unordered_set
    • unordered_set 是 哈希表集合，无序存储唯一元素。
    • 平均查找、插入和删除复杂度为 O(1)。
    • 适合快速查找，不关心顺序。

      GCC 的 unordered_set 同样支持 链表长度超过阈值时桶内树化，避免最坏情况 O(n)。

引用头文件

set

1
2
#include <set>
using std::set;

unordered_set

1
2
#include <unordered_set>
using std::unordered_set;

构造

set

1
2
3
set<int> s1;               // 空集合
set<int> s2(s1);           // 拷贝构造
set<int> s3 = {1, 2, 3};   // 初始化列表

unordered_set

1
2
3
unordered_set<int> us1;              // 空集合
unordered_set<int> us2(us1);         // 拷贝构造
unordered_set<int> us3 = {1, 2, 3};  // 初始化列表

插入和修改

set

1
2
3
4
5
set<int> s;

s.insert(10);  // 插入元素
s.insert(20);
s.insert(10);  // 重复元素不会插入

unordered_set

1
2
3
4
5
unordered_set<int> us;

us.insert(10);
us.insert(20);
us.insert(10);  // 重复元素不会插入

查找元素

set

1
2
3
4
set<int> s = {1,2,3};

auto it = s.find(2);   // 返回迭代器，找不到返回 s.end()
bool exists = s.count(2); // 返回 0 或 1

unordered_set

1
2
3
4
unordered_set<int> us = {1,2,3};

auto it = us.find(2);   // 返回迭代器，找不到返回 us.end()
bool exists = us.count(2); // 返回 0 或 1

删除元素

set

1
2
s.erase(2);        // 根据元素值删除
s.erase(s.begin()); // 根据迭代器删除

unordered_set

1
2
us.erase(2);
us.erase(us.begin());

遍历

set

按元素升序遍历

1
2
3
for (auto &val : s) {
    cout << val << " ";
}

unordered_set

遍历顺序不固定

1
2
3
for (auto &val : us) {
    cout << val << " ";
}

自定义比较器（仅 set 支持）

1
set<int, std::greater<int>> s; // 按降序排列

时间复杂度

set

操作 平均复杂度
插入/删除 O(log n)
查找 O(log n)
遍历 O(n)

unordered_set

操作 平均复杂度 最坏复杂度
插入 O(1) O(n)
查找 O(1) O(n)
删除 O(1) O(n)
遍历 O(n) O(n)

string

绝大多数现代 C++ 编译器（如 GCC/Clang/MSVC）中的 std::string 实现类似：

  • 内部使用动态数组存储字符
  • 结尾自动维护 '\0'（兼容 C-string）
  • 每个 string 还维护 size 和 capacity

字符串扩容通常按照指数方式增长（如 2 倍），以减少反复申请内存。

小字符串优化（SSO - Small String Optimization）

SSO 是 std::string 的核心性能优化技术。

目的：减少堆内存分配，加快小字符串操作

当字符串长度较短（通常 ≤ 15 字符），很多实现会直接存放在对象内部的小缓冲区中，而不分配堆内存。

1
string s = "hello";  // 很可能不分配堆内存（SSO）

优点：

  • 避免频繁 new/delete
  • 提高性能
  • 减少内存碎片

引用头文件

1
2
#include <string>
using std::string;

构造

构造方式 原型 说明 示例
默认构造 string() 创建空字符串 string s1; // ""
拷贝构造 string(const string& str) 拷贝已有字符串 string s2(s1);
移动构造 string(string&& str) 移动已有字符串（C++11 后） string s3(std::move(s1));
C 字符串 string(const char* s) 从以 \0 结尾的 C 字符串构造 string s4("hello");
C 字符串 + 长度 string(const char* s, size_t n) 只取前 n 个字符 string s5("hello world", 5); // "hello"
重复字符 string(size_t n, char c) 创建 n 个相同字符组成的字符串 string s6(4, 'a'); // "aaaa"
区间构造 template<class InputIt> string(InputIt first, InputIt last) 用迭代器区间初始化 vector<char> v{'x','y','z'}; string s7(v.begin(), v.end());
initializer_list string(std::initializer_list<char> ilist) 用列表初始化字符（C++11） string s8({'a','b','c'}); // "abc"

默认构造

1
2
string s1;
cout << s1.size(); // 0
  • 易错点：空字符串的 c_str() 仍然有效，返回 ""。

拷贝构造

1
2
3
string s2("hello");
string s3(s2);
cout << s3; // "hello"
  • 性能建议：大字符串尽量使用 const string& 传参，避免拷贝

移动构造（C++11+）

1
string s4(std::move(s2));
  • 特性：s2 的内容被移动，原对象为空
  • 优势：避免拷贝内存，提高性能

C 字符串构造

1
2
string s5("hello");
string s6("hello world", 5); // "hello"
  • 使用场景：从字面量或 C 风格数组初始化
  • 性能建议：如果长度已知，用第二个参数避免多余扫描
  • 易错点：传入非 \0 结尾字符串时，必须指明长度

重复字符构造

1
string s7(5, 'x'); // "xxxxx"

区间构造（迭代器）

1
2
vector<char> v{'a','b','c'};
string s8(v.begin(), v.end()); // "abc"

initializer_list 构造（C++11+）

1
string s9({'x','y','z'}); // "xyz"

访问与赋值操作

下标访问 operator[]

1
2
3
string s = "hello";
char c = s[1]; // 'e'
s[0] = 'H';    // "Hello"

  • 说明：

    • 不进行边界检查，访问越界会导致未定义行为。

    • 移动构造或扩容后，指向原字符的指针或引用可能失效。

安全访问 at()

1
2
char c = s.at(1); // 'e'
s.at(0) = 'H';    // "Hello"
  • 说明：
    • 会进行范围检查，越界时抛 std::out_of_range 异常。

访问首尾字符

1
2
3
4
5
char f = s.front(); // 'H'
char b = s.back();  // 'o'

s.front() = 'h';
s.back()  = '!';    // "hello!"
  • 说明：
    • 当字符串为空时调用 front() 或 back() 是未定义行为。
  • 易错点：
    • 空字符串访问会触发 UB（未定义行为）。

字符串赋值 assign()

assign() 是 std::string 赋值的多用途函数，重载丰富：

原型 说明 示例
string& assign(const string& str) 拷贝另一个字符串 s.assign(s2);
string& assign(string&& str) 移动另一个字符串 s.assign(std::move(s2));
string& assign(const string& str, size_t pos, size_t count) 从 str 的子串赋值 s.assign(s2, 1, 3); // 取 s2[1..3]
string& assign(const char* s) C 字符串赋值 s.assign("world");
string& assign(const char* s, size_t n) 前 n 个字符赋值 s.assign("hello world", 5); // "hello"
string& assign(size_t n, char c) 重复字符赋值 s.assign(4, 'x'); // "xxxx"
template<class InputIt> string& assign(InputIt first, InputIt last) 区间赋值 vector<char> v{'a','b'}; s.assign(v.begin(), v.end());
string& assign(initializer_list<char> il) 列表赋值（C++11+） s.assign({'x','y','z'}); // "xyz"

修改操作

追加append

原型 说明 示例
string& append(const string& str) 追加整个字符串 s.append(s2);
string& append(const string& str, size_t pos, size_t count) 追加 str 的子串 s.append(s2, 1, 3);
string& append(const char* s) 追加 C 字符串 s.append("world");
string& append(const char* s, size_t n) 追加 C 字符串前 n 个字符 s.append("hello world", 5); // "hello"
string& append(size_t n, char c) 追加 n 个相同字符 s.append(3, '!'); // "!!!"
template<class InputIt> string& append(InputIt first, InputIt last) 追加区间 vector<char> v{'a','b'}; s.append(v.begin(), v.end());
string& push_back(char c) 追加单个字符 s.push_back('x');

性能建议

优化拼接操作 —— 默认拼接效率低

1
2
string s;
s.reserve(1000);  // 建议预留空间减少扩容
  • 频繁修改时建议用 std::ostringstream 或 std::string_view

插入insert

原型 说明 示例
string& insert(size_t pos, const string& str) 在 pos 插入整个字符串 s.insert(2, s2);
string& insert(size_t pos, const string& str, size_t subpos, size_t count) 插入 str 子串 s.insert(1, s2, 0, 2);
string& insert(size_t pos, const char* s) 插入 C 字符串 s.insert(0, "Hi");
string& insert(size_t pos, const char* s, size_t n) 插入 C 字符串前 n 个字符 s.insert(0, "Hello World", 5);
string& insert(size_t pos, size_t n, char c) 插入 n 个相同字符 s.insert(3, 4, '*');
iterator insert(const_iterator p, char c) 插入单字符 s.insert(s.begin()+1, 'x');
template<class InputIt> void insert(const_iterator p, InputIt first, InputIt last) 插入区间 s.insert(s.begin(), v.begin(), v.end());

删除erase

原型 说明 示例
string& erase(size_t pos = 0, size_t count = npos) 从 pos 开始删除 count 个字符 s.erase(2,3);
iterator erase(const_iterator p) 删除迭代器指向字符 s.erase(s.begin()+1);
iterator erase(const_iterator first, const_iterator last) 删除区间 s.erase(s.begin(), s.begin()+3);

替换replace

原型 说明 示例
string& replace(size_t pos, size_t count, const string& str) 替换 pos 起 count 个字符为 str s.replace(0,2,"Hi");
string& replace(size_t pos, size_t count, const string& str, size_t subpos, size_t subcount) 替换为 str 子串 s.replace(0,2,s2,1,2);
string& replace(size_t pos, size_t count, const char* s) 替换为 C 字符串 s.replace(0,2,"OK");
string& replace(size_t pos, size_t count, const char* s, size_t n) 替换为 C 字符串前 n 个字符 s.replace(0,2,"Hello World",5);
string& replace(size_t pos, size_t count, size_t n, char c) 替换为 n 个相同字符 s.replace(0,2,3,'*');
iterator replace(const_iterator first, const_iterator last, InputIt first2, InputIt last2) 替换迭代器区间 s.replace(s.begin(), s.begin()+2,v.begin(),v.end());

查找操作

函数原型 说明 示例
size_t find(const string& str, size_t pos=0) const 从 pos 开始查找子串首次出现位置 s.find("world"); // 6
size_t find(const char* s, size_t pos=0) const 从 pos 开始查找 C 字符串 s.find("lo"); // 3
size_t find(const char* s, size_t pos, size_t n) const 查找 C 字符串前 n 个字符 s.find("hello world", 0, 5); // 查找 "hello"
size_t find(char c, size_t pos=0) const 查找字符首次出现位置 s.find('o'); // 4
size_t rfind(const string& str, size_t pos=npos) const 从右向左查找子串 s.rfind("lo");
size_t rfind(char c, size_t pos=npos) const 从右向左查找字符 s.rfind('o');
size_t find_first_of(const string& chars, size_t pos=0) const 查找任意指定字符集合首次出现 s.find_first_of("aeiou");
size_t find_last_of(const string& chars, size_t pos=npos) const 查找任意字符集合最后一次出现 s.find_last_of("aeiou");
size_t find_first_not_of(const string& chars, size_t pos=0) const 查找第一个不属于字符集合的位置 s.find_first_not_of("aeiou");
size_t find_last_not_of(const string& chars, size_t pos=npos) const 查找最后一个不属于字符集合的位置 s.find_last_not_of("aeiou");

字符串比较

函数原型 说明 示例 性能
int compare(const string& str) const 比较整个字符串与 str s.compare("hello"); O(min(n, m))
int compare(size_t pos, size_t count, const string& str) const 比较子串 [pos, pos+count) 与 str s.compare(0,2,"he"); O(count)
int compare(size_t pos, size_t count, const string& str, size_t subpos, size_t subcount) const 比较 s 子串与 str 子串 s.compare(0,2,s2,1,2); O(subcount)
int compare(const char* s) const 与 C 字符串比较 s.compare("hello"); O(n)
int compare(size_t pos, size_t count, const char* s) const 比较子串与 C 字符串 s.compare(0,2,"he"); O(count)
int compare(size_t pos, size_t count, const char* s, size_t n) const 比较子串与 C 字符串前 n 个字符 s.compare(0,2,"hello",2); // "he" O(n)

返回值：

  • 返回值小于0 s<str,

  • 返回值等于0 s==str,

  • 返回值大于0 s>str

也可以用运算符比较

运算符 功能 示例 返回类型 比较方式
== 判断是否相等 s == "hello" bool 大小写敏感 & 按字符逐一比较
!= 判断是否不相等 s != t bool 同上
< 按字典序小于 "abc" < "abd" bool 按 ASCII/Unicode 比较
<= 小于等于 "abc" <= "abc" bool 同上
> 按字典序大于 "dog" > "cat" bool 同上
>= 大于等于 "hi" >= "ha" bool 同上

子串

函数原型 说明 示例 返回值 注意 性能
string substr(size_t pos = 0, size_t count = npos) const 从位置 pos 开始，截取长度为 count 的子串 s.substr(2, 4) 返回新 string pos > size() 抛异常 会产生新字符串拷贝，注意性能

字符检查与大小写转换

需要引入c标准库

1
#include <cctype>

常用字符判断函数

函数 作用 示例
isalnum(c) 是否为字母或数字 'A','z','3'
isalpha(c) 是否为字母 'A','b'
isdigit(c) 是否为数字 '0'~'9'
islower(c) 是否为小写字母 'a'
isupper(c) 是否为大写字母 'Z'
isspace(c) 是否为空白字符（空格/换行/制表） ' ','\n','\t'
ispunct(c) 是否为标点符号 ',' '.' '!'
isxdigit(c) 是否为十六进制数字 '0'~'9','a'~'f'
isprint(c) 是否为可打印字符 普通字符
iscntrl(c) 是否控制字符 '\n' '\r'

大小写转换函数

函数 说明 示例
tolower(c) 字符转小写 tolower('A') → 'a'
toupper(c) 字符转大写 toupper('b') → 'B'

这两个函数只作用于单个字符，要处理字符串需要配合 transform()：

1
2
3
4
5
6
7
8
9
#include <algorithm>
#include <cctype>
using std::string;

int main(){
    string s = "HeLLo";
	std::transform(s.begin(), s.end(), s.begin(), ::tolower);  // s = "hello"

}

::tolower 里的 :: 指的是全局作用域运算符，表示用 全局的 tolower 函数，避免与某些类成员同名造成歧义。

字符串与数字的转换

字符串 → 整型转换函数表

函数 函数原型 参数说明 返回值说明 示例
stoi int stoi(const string& str, size_t* pos = 0, int base = 10); str: 输入字符串 pos: 返回成功转换的字符数 base: 进制（2~36） 转换后的 int stoi("123") → 123 stoi("1A", nullptr, 16) → 26
stol long stol(const string& str, size_t* pos = 0, int base = 10); 同上 转换为 long stol("99999") → 99999L
stoll long long stoll(const string& str, size_t* pos = 0, int base = 10); 同上 转换为 long long stoll("1234567890123")
stoi (C字符串) int stoi(const char* str, size_t* pos = 0, int base = 10); str: C风格字符串 转换为 int stoi("42") → 42

字符串 → 浮点型转换函数表

函数 函数原型 参数说明 返回值说明 示例
stof float stof(const string& str, size_t* pos = 0); str: 字符串 pos: 返回解析字符长度 转为 float stof("3.14") → 3.14f
stod double stod(const string& str, size_t* pos = 0); 同上 转为 double stod("2.71828")
stold long double stold(const string& str, size_t* pos = 0); 同上 转为 long double stold("1.6180339887")

数字 → 字符串转换 (to_string)

函数 函数原型 参数说明 返回值说明 示例
to_string string to_string(int value); value: 数字 返回转换后的字符串 to_string(42) → "42"
to_string string to_string(double value); 同上 浮点转字符串 to_string(3.14) → "3.140000"
to_string string to_string(long long value); 同上 支持长整型 to_string(1234567890123)

返回值与异常总结

情况 行为
输入不是数字 抛出 std::invalid_argument
数字超出范围 抛出 std::out_of_range
自动去除前导空格 ✅ 支持 " 123"
支持符号 ✅ "-42" " +88"
支持部分解析 ✅ "123abc" → 123

字符串与流

引入头文件

1
2
3
4
#include <sstream>
using std::stringstream;
using std::istringstream;
using std::ostringstream;

三个类

类名 作用 场景
stringstream 读写都支持 通用
istringstream 只读输入流 解析字符串
ostringstream 只写输出流 构造字符串

常用操作：

函数 作用 示例
str() 获取/设置内部字符串 ss.str("123 456")
clear() 清空流状态 必须在重复使用时调用
operator>> 提取数据（按空白分割） ss >> x;
operator<< 插入数据 ss << 42;
getline() 按行读取 getline(ss, s)
good() fail() 检查流状态 判断解析是否成功

注意重复使用时必须调用clear

举例：

分割字符串

1
2
3
4
5
6
7
8
9
10
#include <sstream>
using std::stringstream;


string s = "apple banana orange";
stringstream ss(s);
string word;
while (ss >> word) {
    cout << word << endl;
}
用途 方法 示例 说明 易错点
空白分词 ss >> word ss >> w1 >> w2 按空格、换行、制表符切分 遇到逗号等非空白不会分割
自定义分隔符 getline(ss, word, ',') getline(ss, word, ','); 按 , 切分 必须用 getline，>> 无法自定义分隔符
解析数字 ss >> num int x; ss >> x; 字符串数字 → int/double 非数字会使流失败，需检查 ss.fail()
拼接字符串 oss << val oss << "ID=" << 5; 高效构造动态字符串 输出结束后 oss.str() 才能获取完整内容

multiset/multimap

multiset

  • 元素 可重复，自动按 key 排序
  • 底层通常使用 红黑树
  • 不支持通过下标访问，只能用迭代器
  • 适合需要 快速查找和按顺序遍历重复元素

multimap<K,V>

  • key 可重复，按 key 排序
  • 底层通常使用 红黑树
  • 可以通过 equal_range 查找某个 key 的所有元素

引用头文件

1
2
3
4
5
6
7
// multiset
#include <set>
using std::multiset;

// multimap
#include <map>
using std::multimap;

构造

multiset

1
2
3
multiset<int> ms;            // 空 multiset
multiset<int> ms2(ms);        // 拷贝构造
multiset<int> ms3 = {1,2,2,3}; // 初始化列表

multimap

1
2
3
multimap<int,string> mm;            // 空 multimap
multimap<int,string> mm2(mm);       // 拷贝构造
multimap<int,string> mm3 = {{1,"a"},{2,"b"},{2,"c"}}; // 初始化列表

插入元素

1
2
3
4
5
6
7
// multiset
ms.insert(2);
ms.insert(2); // 可以重复

// multimap
mm.insert({2,"b"});
mm.insert({2,"c"}); // key 可以重复

查找元素

1
2
3
4
5
6
7
8
9
// multiset
auto it = ms.find(2);       // 返回第一个 2 的迭代器
size_t cnt = ms.count(2);   // 2 出现的次数

// multimap
auto range = mm.equal_range(2); // 返回 key=2 的元素区间 [first, second)
for(auto it = range.first; it != range.second; ++it) {
    cout << it->first << " -> " << it->second << endl;
}

删除元素

1
2
3
4
5
6
7
8
9
// multiset
ms.erase(2);          // 删除所有值为 2 的元素
auto it = ms.find(2);
ms.erase(it);         // 删除单个迭代器指向的元素

// multimap
mm.erase(2);          // 删除所有 key=2 的元素
auto it2 = mm.find(2);
mm.erase(it2);        // 删除单个迭代器指向的元素

遍历

1
2
3
4
5
6
7
8
9
10
// multiset
for(auto &x : ms) {
    cout << x << " ";
}
cout << endl;

// multimap
for(auto &[key,value] : mm) {
    cout << key << " -> " << value << endl;
}

时间复杂度

操作 multiset / multimap
插入 O(log n)
查找 O(log n)
删除 O(log n)
遍历 O(n)

tuple

引用头文件

1
2
#include <tuple>
using std::tuple;

构造

1
2
3
4

tuple<int,int,int> tp ={1,2,3};

auto tp2 = std::make_tuple(1, 2.5, "hi"); // 自动推断类型

访问元素

  • 不能像 pair 一样访问，使用 std::get<0>(tuple)

    注意，这里 get要求 index 是常量，编译期可知的常量，因此不能利用它来遍历

1
2
3
int a = std::get<0>(tp);
int b = std::get<1>(tp);
int c = std::get<2>(tp);
  • c++17 起可以用结构化绑定,这样更优雅些
1
auto [a, b, c] = tuple;
  • 也可以使用 std::tie
1
2
int a, b, c;
std::tie(a, b, std::ignore) = tp;

修改

1
std::get<1>(t) = 6;

获取长度

1
2
// tuple 长度
constexpr size_t n = std::tuple_size<decltype(tp)>::value; // n=3

遍历

不常用，使用结构化绑定 + fold 表达式

1
2
3
4
5
6
7
auto tp = make_tuple(1, 2.5, "hi");

// fold expression 遍历
std::apply([](auto&&... args) {
    ((cout << args << " "), ...);
}, tp);

algorithm

引用头文件

1
#include <algorithm>

sort

基本用法

1
2
3
4
5
6
#include <functional> // std::greater<int>
vector<int> v={3,2,4};
// 按非递减顺序排序（升序）
std::sort(v.begin(), v.end());
// 按非递增顺序排序（降序）
std::sort(v.begin(), v.end(),std::greater<int>)

自定义比较器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Person {
    string name;
    int age;
};

vector<Person> people = {{"Alice", 25}, {"Bob", 30}, {"Carol", 20}};

// 按年龄升序
std::sort(people.begin(), people.end(), [](const Person &a, const Person &b){
    return a.age < b.age;
});

// 按年龄降序
std::sort(people.begin(), people.end(), [](const Person &a, const Person &b){
    return a.age > b.age;
});

std::sort 的标准要求是 稳定性不保证，如果需要稳定排序请使用 std::stable_sort

  • 稳定排序：如果两个元素相等，排序前它们的相对顺序在排序后保持不变。
  • 不稳定排序：相等元素的相对顺序在排序后可能被打乱。

min, max

基本用法

1
2
3
4
int a = 5, b = 10;

int mi = std::min(a, b); // mi = 5
int ma = std::max(a, b); // ma = 10

自定义比较器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Person {
    std::string name;
    int age;
};

Person p1{"Alice", 25}, p2{"Bob", 30};

// 返回年龄小的
auto youngest = std::min(p1, p2, [](const Person &x, const Person &y){
    return x.age < y.age;
});

auto oldest = std::max(p1, p2, [](const Person &x, const Person &y){
    return x.age < y.age;
});

可接受 initializer_list (C++11 及以上)

1
2
int x = std::min({3, 1, 4, 2}); // x = 1
int y = std::max({3, 1, 4, 2}); // y = 4

min_element/max_element

min_element 和 max_element 返回的迭代器

1
2
3
4
vector<int> v= {1,2,4,8};
// 查找最小/最大值
int mn = *std::min_element(v.begin(), v.end());
int mx = *std::max_element(v.begin(), v.end());

reverse

反转有序容器

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

find

  • 顺序查找区间内第一个等于给定值的元素，返回迭代器。找不到返回 end。
1
2
3
4
5
vector<int> v = {1, 3, 5, 7};
auto it = std::find(v.begin(), v.end(), 5); // it 指向 5
if(it != v.end()) {
    cout << "Found: " << *it << endl;
}

count

  • 统计区间内某个值出现的次数
1
2
vector<int> v = {1,2,2,3,2};
int cnt = std::count(v.begin(), v.end(), 2); // cnt = 3

transform

1
2
3
4
5
6
7
8
9
// 单参数变换（Unary Operation）
template<class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first, InputIt last, OutputIt d_first, UnaryOperation unary_op);

// 双参数变换（Binary Operation）
template<class InputIt1, class InputIt2, class OutputIt, class BinaryOperation>
OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2,
                   OutputIt d_first, BinaryOperation binary_op);

例子：

1
std::transform(s.begin(), s.end(), s.begin(), ::tolower);

使用的是 单参数版本（Unary Operation），意思是：

  • 输入区间：[s.begin(), s.end())
  • 输出区间起始：s.begin()（原地修改字符串）
  • 对每个字符应用操作：::tolower

::tolower 里的 :: 指的是全局作用域运算符，表示用 全局的 tolower 函数，避免与某些类成员同名造成歧义。

也可以不使用 tolower，传你自己的处理逻辑：

1
2
3
transform(s.begin(), s.end(), s.begin(), [](char c) {
    return c >= 'a' && c <= 'z' ? c - 32 : c;
});

双参数变换

两个数组元素相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> a = {1, 2, 3, 4};
    vector<int> b = {10, 20, 30, 40};
    vector<int> result(a.size());

    // result[i] = a[i] + b[i]
    transform(a.begin(), a.end(), b.begin(), result.begin(),
              [](int x, int y) { return x + y; });

    for (int x : result) cout << x << " ";  // 输出：11 22 33 44
}

  • 对已排序序列执行二分查找，返回 bool，判断是否存在
1
2
3
vector<int> v = {1,3,5,7};
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 5); // true

lower_bound/upper_bound

  • 返回迭代器，要求序列已排序
  • lower_bound(begin,end,val)：返回第一个 >= val 的位置
  • upper_bound(begin,end,val)：返回第一个 > val 的位置
1
2
3
4
5
6
vector<int> v = {1,2,2,3,5};
auto lb = std::lower_bound(v.begin(), v.end(), 2); // 指向第一个 2
auto ub = std::upper_bound(v.begin(), v.end(), 2); // 指向 3

int distance = std::distance(std::lower_bound(vec.begin(), vec.end(), startTime),
                         std::upper_bound(vec.begin(), vec.end(), endTime));

equal_range

  • 返回 [lower_bound, upper_bound) 的迭代器对，区间包含所有等于给定值的元素
1
2
3
4
auto range = std::equal_range(v.begin(), v.end(), 2);
for(auto it = range.first; it != range.second; ++it) {
    cout << *it << " "; // 输出所有 2
}

next_permutation/prev_permutation

生成下一个字典序排列，可以用于生成一个序列的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // v是字典序列最小
    std::vector<int> v = {1, 2, 3};

    do {
        for (int x : v) std::cout << x << " ";
        std::cout << "\n";
    } while (std::next_permutation(v.begin(), v.end()));
}

输出：

1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
  • 也用于生成一个数组的所有长度为 m 的数字组合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4};
    int m = 2;
    int n = vec.size();

    // 初始化标记数组
    std::vector<int> select(n, 0);
    std::fill(select.end() - m, select.end(), 1); // 后 m 个为 1

    do {
        // 根据 select 生成组合
        for (int i = 0; i < n; ++i) {
            if (select[i]) std::cout << vec[i] << " ";
        }
        std::cout << "\n";
    } while (std::next_permutation(select.begin(), select.end()));
}

输出

1
2
3
4
5
6
1 2
1 3
2 3
1 4
2 4
3 4

也可以使用 prev_permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4};
    int m = 2; // 组合长度
    int n = vec.size();

    // 1. 创建选择标记数组
    std::vector<int> select(n, 0);
    std::fill(select.begin(), select.begin() + m, 1); // 前 m 个选中

    std::vector<std::vector<int>> result;

    // 2. 用 prev_permutation 生成所有组合
    do {
        std::vector<int> combo;
        for (int i = 0; i < n; ++i) {
            if (select[i]) combo.push_back(vec[i]);
        }
        result.push_back(combo);
    } while (std::prev_permutation(select.begin(), select.end()));

    // 输出
    for (auto& c : result) {
        for (auto x : c) std::cout << x << " ";
        std::cout << "\n";
    }
}

fill

  • fill(begin,end,val)：填充整个区间为指定值
1
2
3
4
5
6
vector<int> v(5);
std::fill(v.begin(), v.end(), 7); // v = {7,7,7,7,7}


std::vector<int> select(n, 0);
std::fill(select.begin(), select.begin() + m, 1);

iota

  • iota(begin,end,start)：生成连续整数序列
1
2
3
#include <numeric>
vector<int> v(5);
std::iota(v.begin(), v.end(), 10); // v = {10,11,12,13,14}

copy / swap / replace / remove / remove_if

  • copy(begin,end,out_it)：拷贝区间到另一容器
1
2
3
vector<int> src = {1,2,3};
vector<int> dst(3);
std::copy(src.begin(), src.end(), dst.begin());
  • swap(a,b) / iter_swap(it1,it2)：交换元素
1
2
std::swap(a,b);
std::iter_swap(v.begin(), v.begin()+1);
  • replace(begin,end,old_val,new_val)：替换区间内元素
1
std::replace(v.begin(), v.end(), 2, 5);
  • remove(begin,end,val) / remove_if(begin,end,pred)：逻辑移除（需要配合 erase）
1
2
v.erase(std::remove(v.begin(), v.end(), 5), v.end());
v.erase(std::remove_if(v.begin(), v.end(), [](int x){ return x%2==0; }), v.end());

set operations（集合操作）

  • 序列必须 已排序
  • merge(a,b,out)：合并两个已排序序列
  • set_union(a,b,out)：并集
  • set_intersection(a,b,out)：交集
  • set_difference(a,b,out)：差集
  • unique(begin,end)：去除相邻重复元素
1
2
3
4
5
6
7
8
vector<int> a = {1,2,2,3};
vector<int> b = {2,3,4};
vector<int> out;

std::set_union(a.begin(),a.end(),b.begin(),b.end(),std::back_inserter(out));
// out = {1,2,2,3,4}

a.erase(std::unique(a.begin(),a.end()), a.end()); // 去重 a = {1,2,3}

使用std::unique必须要求元素是已经有序的

accumulate / all_of / any_of / none_of / for_each

  • accumulate(begin,end,init)：区间求和（或自定义操作）
1
2
3
#include <numeric>
vector<int> v = {1,2,3};
int sum = std::accumulate(v.begin(), v.end(), 0); // sum = 6
  • all_of(begin,end,pred) / any_of / none_of：判断区间元素是否满足条件
1
2
bool all_even = std::all_of(v.begin(), v.end(), [](int x){ return x%2==0; });
bool any_even = std::any_of(v.begin(), v.end(), [](int x){ return x%2==0; });
  • for_each(begin,end,f)：区间遍历
1
std::for_each(v.begin(), v.end(), [](int &x){ x++; });

时间复杂度

算法 功能 时间复杂度 示例代码
sort 排序（不稳定） O(n log n) std::sort(v.begin(), v.end());
stable_sort 稳定排序 O(n log² n) 最坏，平均 O(n log n) std::stable_sort(v.begin(), v.end());
min / max 两数取最小/最大 O(1) std::min(a,b); std::max(a,b);
min_element / max_element 区间最小/最大元素迭代器 O(n) *std::min_element(v.begin(), v.end());
reverse 反转区间 O(n) std::reverse(v.begin(), v.end());
find 顺序查找 O(n) auto it = std::find(v.begin(),v.end(),5);
count 统计出现次数 O(n) std::count(v.begin(),v.end(),2);
binary_search 是否存在（二分，需有序） O(log n) std::binary_search(v.begin(),v.end(),5);
lower_bound 第一个 >= val（二分） O(log n) auto it=std::lower_bound(v.begin(),v.end(),2);
upper_bound 第一个 > val（二分） O(log n) auto it=std::upper_bound(v.begin(),v.end(),2);
equal_range 返回等于 val 的区间 O(log n) auto r=std::equal_range(v.begin(),v.end(),2);
fill 区间赋值 O(n) std::fill(v.begin(), v.end(), 7);
iota 连续赋值（需 <numeric>） O(n) std::iota(v.begin(),v.end(),10);
copy 拷贝区间 O(n) std::copy(src.begin(),src.end(),dst.begin());
swap / iter_swap 交换元素 O(1) std::swap(a,b);
replace 替换指定值 O(n) std::replace(v.begin(),v.end(),2,5);
remove / remove_if 逻辑删除（需 erase） O(n) v.erase(std::remove(v.begin(),v.end(),5),v.end());
unique 去除相邻重复（逻辑删除） O(n) v.erase(std::unique(v.begin(),v.end()),v.end());
set_union 并集（需有序） O(n+m) std::set_union(a.begin(),a.end(),b.begin(),b.end(),back_inserter(out));
set_intersection 交集（需有序） O(n+m) std::set_intersection(...);
set_difference 差集（需有序） O(n+m) std::set_difference(...);
merge 合并两个有序序列 O(n+m) std::merge(a.begin(),a.end(),b.begin(),b.end(),out.begin());
accumulate 区间累加（需 <numeric>） O(n) int sum=std::accumulate(v.begin(),v.end(),0);
all_of / any_of / none_of 区间条件判断 O(n) std::all_of(v.begin(),v.end(),[](int x){return x%2==0;});
for_each 遍历执行函数 O(n) std::for_each(v.begin(),v.end(),[](int &x){x++;});

utility

引用头文件

1
#include <utility>

pair

引用头文件

1
2
#include <utility>
using std::pair;

构造

1
2
3
pair<int,int> p = {1,2};

auto p = std::make_pair(1, 2); // 自动推断类型

访问元素

1
2
int a = p.first;
int b = p.second;

std::move

std::move 其实是将参数 t 转换为一个右值引用类型，不会拷贝内存，不会释放资源，不会调用构造函数和析构函数

1
2
3
4
template <typename T>
typename std::remove_reference<T>::type&& move(T&& t) noexcept {
    return static_cast<typename std::remove_reference<T>::type&&>(t);
}

以 std::vector 为例：

1
2
std::vector<int> a = {1, 2, 3};
std::vector<int> b = std::move(a);

这里：std::move(a) 把 a 变成右值引用。编译器会选择 vector 的移动构造函数，而不是拷贝构造。移动构造函数做的事：

  • 把 a 的内部指针直接“偷走”，交给 b。
  • 把 a 的指针设为空，避免析构时释放同一块内存。

所以最后：b 持有 {1,2,3} 的数据。a 变成空的（size()==0，但仍然是合法对象）

总结：
nums1 = std::move(vec);

  • 旧内容自动释放（移动赋值内部完成）
  • 新内容接管
  • vec 变空不需要自己手动调用析构函数。