C++

---

时间轴

时间轴

2025-10-03

init

2025-10-12

add next_permutation 生成序列的全排列

2025-10-19

add string

本文介绍了C++编程语言中的核心基础知识，包括左值与右值的概念、引用类型（左值引用与右值引用）及其应用场景；详细说明了标准输入输出方法，如cin的使用规则、getline()函数读取含空格的字符串，以及输出函数的基本用法；同时讲解了sstream头文件中三个类（stringstream、istringstream、ostringstream）的功能与常用操作，包括字符串分割、数字解析和拼接等技巧。此外，文章总结了STL（标准模板库）中常用容器的使用方法：vector支持随机访问、动态扩容及多种遍历方式，并给出了各操作的时间复杂度；queue提供了先进先出的队列操作，所有操作均为O(1)复杂度；priority_queue默认实现大顶堆，支持自定义比较器构造小顶堆，并介绍了懒删除等高级技巧。整体内容面向C++初学者，涵盖语法要点、输入输出处理及STL容器实践，帮助读者快速掌握常用功能与注意事

---

语法

& 与 &&，左值与右值

• 左值 (Lvalue)

  • 有名字，可取地址。

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

  • 例子：

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

• 右值 (Rvalue)

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

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

  • 例子：

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

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

• 引用类型

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

示例：

int a = 5;
int &lref = a;   // 左值引用，a 是左值
int &&rref = 5;  // 右值引用，5 是右值

• 左值引用可以修改左值：

lref = 10; // a = 10

• 右值引用常用于移动语义：

vector<int> v1 = {1,2,3};
vector<int> v2 = std::move(v1); // 右值引用允许移动资源

输入输出

输入

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

• cin

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

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

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

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

• getline()

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

引入头文件

#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

举例：

分割字符串

#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

引用头文件

#include <vector>
using std::vector;

构造

// 空 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 异常

// 通过索引访问（不做边界检查）
int a = v[0];

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

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

修改元素

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();                   // 清空所有元素

遍历元素

// 索引遍历
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

引用头文件

#include <queue>
using std::queue;

构造

// 空队列
queue<int> q1;

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

访问队头队尾

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

入队出队

// 入队（尾部插入）
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()实现遍历

引用头文件

#include <queue>
using std::priority_queue;

构造

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

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

• 如果想要删除 priority_queue 中某一个元素，建议考虑能不能配合 unordered_map 实现懒删除(只有无效元素到堆顶了才删除，否则只做标记)

// 默认构造
priority_queue<int> pq1;
// 默认构造的全部参数
priority_queue<int,vector<int>,std::less<int>> pq_full;
// 拷贝构造
priority_queue<int> pq2(pq1);

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

访问堆顶

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

弹出堆顶元素

pq.pop();

自定义比较器

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

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

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

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

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

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()。

引用头文件

#include <stack>
using std::stack;

构造

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

入栈/出栈

stack<int> s;
// 入栈（push 到栈顶）
s.push(20);

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

访问栈顶元素

// 查看栈顶元素
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

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

unordered_map

// unordered_map
#include <unordered_map>
using std::unordered_map;

构造

map

// 空 map
map<int, string> m1;

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

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

unordered_map

// 空表
unordered_map<int, string> um1;

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

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

访问元素

map

map<int, string> m;

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

unordered_map

unordered_map<int, string> um;

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

插入，修改和元素

map

map<int, string> m;

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

unordered_map

unordered_map<int, string> um;

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

查找元素

map

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

unordered_map<int, string> um;

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

删除元素

map

map<int, string> m;

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

unordered_map

unordered_map<int, string> um;

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

遍历

map

map 是按 key 有序遍历的

map<int, string> m;

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

unordered_map

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

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

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

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

#include <set>
using std::set;

unordered_set

#include <unordered_set>
using std::unordered_set;

---

构造

set

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

unordered_set

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

---

插入和修改

set

set<int> s;

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

unordered_set

unordered_set<int> us;

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

---

查找元素

set

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

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

unordered_set

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

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

删除元素

set

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

unordered_set

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

遍历

set

按元素升序遍历

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

unordered_set

遍历顺序不固定

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

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

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 字符），很多实现会直接存放在对象内部的小缓冲区中，而不分配堆内存。

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

优点：

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

引用头文件

#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"

默认构造

string s1;
cout << s1.size(); // 0

• 易错点：空字符串的c_str()仍然有效，返回""。

---

拷贝构造

string s2("hello");
string s3(s2);
cout << s3; // "hello"

• 性能建议：大字符串尽量使用const string&传参，避免拷贝

---

移动构造（C++11+）

string s4(std::move(s2));

• 特性：s2的内容被移动，原对象为空
• 优势：避免拷贝内存，提高性能

---

C 字符串构造

string s5("hello");
string s6("hello world", 5); // "hello"

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

---

重复字符构造

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

---

区间构造（迭代器）

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

---

initializer_list 构造（C++11+）

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

访问与赋值操作

下标访问operator[]

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

• 说明：

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

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

安全访问at()

char c = s.at(1); // 'e'
s.at(0) = 'H';    // "Hello"

• 说明：
  • 会进行范围检查，越界时抛std::out_of_range异常。

---

访问首尾字符

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');

性能建议

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

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标准库

#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()：

#include <algorithm>
#include <cctype>
using std::string;

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

}

::tolower里的::指的是全局作用域运算符，表示使用<cctype>中定义的全局tolower函数，避免与<locale>中的std::tolower（接受 locale 参数的重载版本）混淆。

字符串与数字的转换

字符串 → 整型转换函数表

函数	函数原型	参数说明	返回值说明	示例
stoi	int stoi(const string& str, size_t* pos = 0, int base = 10);	str: 输入字符串pos: 返回成功转换的字符数base: 进制（2~36）	转换后的int	stoi("123") → 123stoi("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")

---

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

函数	函数原型	参数说明	返回值说明	示例
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

字符串与流

引入头文件

#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

举例：

分割字符串

#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 的所有元素

引用头文件

// multiset
#include <set>
using std::multiset;

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

构造

multiset

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

multimap

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

插入元素

// multiset
ms.insert(2);
ms.insert(2); // 可以重复

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

查找元素

// 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;
}

删除元素

// 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);        // 删除单个迭代器指向的元素

遍历

// 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

引用头文件

#include <tuple>
using std::tuple;

构造

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

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

访问元素

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

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

int a = std::get<0>(tp);
int b = std::get<1>(tp);
int c = std::get<2>(tp);

• c++17 起可以用结构化绑定,这样更优雅些

auto [a, b, c] = tp;

• 也可以使用 std::tie

int a, b, c;
std::tie(a, b, std::ignore) = tp;

修改

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

获取长度

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

遍历

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

auto tp = make_tuple(1, 2.5, "hi");

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

algorithm

引用头文件

#include <algorithm>

sort

基本用法

#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>)

自定义比较器

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

基本用法

int a = 5, b = 10;

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

自定义比较器

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 及以上)

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 返回的迭代器

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

反转有序容器

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

find

• 顺序查找区间内第一个等于给定值的元素，返回迭代器。找不到返回end。

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

• 统计区间内某个值出现的次数

vector<int> v = {1,2,2,3,2};
int cnt = std::count(v.begin(), v.end(), 2); // cnt = 3

transform

// 单参数变换（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);

例子：

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

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

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

::tolower里的::指的是全局作用域运算符，表示使用<cctype>中定义的全局tolower函数，避免与<locale>中的std::tolower（接受 locale 参数的重载版本）混淆。

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

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

---

双参数变换

两个数组元素相加

#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
}

binary_search

• 对已排序序列执行二分查找，返回bool，判断是否存在

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 的位置

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)的迭代器对，区间包含所有等于给定值的元素

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

生成下一个字典序排列。若序列初始为字典序最小，循环调用直到返回 false 即可生成全排列

#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
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

• 也用于生成一个数组的所有长度为 m 的数字组合

#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
1 3
2 3
1 4
2 4
3 4

也可以使用 prev_permutation

#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)：填充整个区间为指定值

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)：生成连续整数序列

#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)：拷贝区间到另一容器

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)：交换元素

std::swap(a,b);
std::iter_swap(v.begin(), v.begin()+1);

• replace(begin,end,old_val,new_val)：替换区间内元素

std::replace(v.begin(), v.end(), 2, 5);

• remove(begin,end,val)/remove_if(begin,end,pred)：逻辑移除（需要配合erase）

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)：去除相邻重复元素

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)：区间求和（或自定义操作）

#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：判断区间元素是否满足条件

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)：区间遍历

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

引用头文件

#include <utility>

pair

引用头文件

#include <utility>
using std::pair;

构造

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

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

访问元素

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

std::move

std::move 其实是将参数 t 转换为一个右值引用类型，它本身不做任何资源拷贝或释放，也不调用构造函数和析构函数（实际移动操作由被调用的移动构造函数/移动赋值运算符完成）

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 为例：

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，但仍然是合法对象）

总结：以b = std::move(a)为例（此处为移动构造，b 为新对象）：

• b 接管 a 的内部指针（即 a 的资源转移给 b）
• a 被置于有效但未指定的状态（对 std::vector 而言，a 变为空，size()==0，仍是合法对象）
• a 析构时释放的是其当前持有的资源（此时已为空，不会重复释放）
• 不需要自己手动调用析构函数。