c++:c++与算法(需要有C语言，数据结构基础)
·
1.食用须知
本文需要有c语言，数据结构基础。重归纳重使用，本文以简洁为主，可能并不全但在算法中比较重要的都有涉及。完整STL库查询地址https://legacy.cplusplus.com/
c++中兼容c的语法。
2.预备知识
1.范围for
范围for是在c++11中引入，他可以比较方便的遍历容器或其他可迭代对象中的元素。（string vector）
#include<iostream> //基础库
using namespace std; //为避免命名冲突c++中引入了命名空间
//命名空间在写算法题中建议展开
int main() {
int a[] = { 1,2,3,4 };
for (auto e : a)
cout << e << endl;
}
/*
for (auto e : a)类似于python中for e in a
auto为自动变量可以自动识别变量类别，在变量类型不明确时不可用。
例：
auto a; //错误auto无法推导a的类型
auto a=10；//之前a的类型为整型
*/
/*
cout << e << endl;
cout用于输出，他可以自动推断类型。所以无论e是什么基本类型都可以输出
<<流插入运算符用于插入数据
endl相当于'\n'
*/
//例：
/*
int main() {
int a=0;
float b=0;
char c='c';
cout<<a<<' '<<b<<' '<<c<<endl;
}
//输出0 0 c
*/
//同样的也有用于输入的cin，用法与cout类似
/*
int main() {
int a=0,b=0;
cin>>a>>b;
}
//<<流提取运算符用于将输入的数据提取出来
*/
3.string类
string是标准库（std 命名空间）提供的用于处理字符串的类，定义在 <string> 头文件中。
他使用new（底层是malloc）在对上开辟空间，并对其进行空间管理，他可以自动扩容免去手动扩容的繁杂。
1.初始化：
注：非红字部分不掌握对使用无影响
string() | 默认构造函数，创建空字符串 | string s;（s 为空字符串） |
string(const string& str) | 拷贝构造函数，用另一个字符串初始化 | string s1("hello"); string s2(s1);（s2 是 s1 的副本） |
string(const char* cstr) | 用 C 风格字符串（char*）初始化 | string s("hello");（s 包含 "hello"） |
string(const char* cstr, size_t n) | 用 C 风格字符串的前 n 个字符初始化 | string s("hello world", 5);（s 为 "hello"） |
string(size_t n, char c) | 用 n 个重复的字符 c 初始化 | string s(5, 'a');（s 为 "aaaaa"） |
string(initializer_list<char> ilist) | 用初始化列表初始化（C++11 及以上） | string s{'h', 'e', 'l', 'l', 'o'};（s 为 "hello"） |
#include <iostream>
#include <string>
using namespace std;
int main() {
// 1. 默认构造函数：创建空字符串
string s1;
cout << "1. 默认构造函数: ";
if (s1.empty()) {
cout << "s1 是空字符串（长度: " << s1.size() << "）" << endl;
}
//重点 2. 拷贝构造函数：用另一个字符串初始化
string s11("hello");
string s2(s1); // 拷贝s1_copy的值
cout << "2. 拷贝构造函数: s1 = \"" << s11
<< "\", s2 = \"" << s2 << "\"" << endl;
// 3. 用C风格字符串（char*）初始化
const char* c_style_str = "hello";
string s3(c_style_str);
cout << "3. C风格字符串初始化: s3 = \"" << s3 << "\"" << endl;
// 4. 用C风格字符串的前n个字符初始化
string s4("hello world", 5); // 取前5个字符
cout << "4. C风格字符串前n个字符: s4 = \"" << s4 << "\"" << endl;
// 5. 用n个重复的字符c初始化
string s5(5, 'a'); // 5个'a'字符
cout << "5. n个重复字符: s5 = \"" << s5 << "\"" << endl;
//重点 6. 用初始化列表初始化（C++11及以上）
string s6{ 'h', 'e', 'l', 'l', 'o' };
cout << "6. 初始化列表: s6 = \"" << s6 << "\"" << endl;
return 0;
}
//可以将string理解为可以接受多种初始化方式的的结构体
2.增删查改
| 增加 | += | 在字符串末尾追加内容（字符串 / 字符） | s += "gh"; | "abcdefgh" |
append() | 追加字符串、字符序列或重复字符 | s.append(2, 'x'); | "abcdefxx" | |
insert(pos, str) | 在指定位置 pos 插入字符串 str | s.insert(3, "123"); | "abc123def" | |
push_back(c) | 在末尾添加单个字符 | s.push_back('z'); | "abcdefz" | |
| 删除 | erase(pos, len) | 从位置 pos 开始删除 len 个字符（len 省略时删除到末尾） | s.erase(3, 2); | "abcef" |
clear() | 清空字符串所有内容（长度变为 0） | s.clear(); | ""（空字符串） | |
pop_back() | 删除末尾最后一个字符 | s.pop_back(); | "abcde" | |
| 查询 | find(str) | 从开头查找子串 str，返回首次出现位置（未找到返回 string::npos） | s.find("cd"); | 2（索引位置） |
rfind(str) | 从末尾查找子串 str，返回最后出现位置 | "ababa".rfind("aba"); | 2 | |
substr(pos, len) | 从位置 pos 截取 len 个字符（len 省略时取到末尾） | s.substr(2, 3); | "cde" | |
at(pos) / [pos] | 获取位置 pos 的字符（at() 越界抛异常，[] 不检查） | s.at(1); / s[1]; | 'b' | |
| 修改 | replace(pos, len, str) | 从位置 pos 开始，替换 len 个字符为 str | s.replace(2, 2, "XY"); | "abXYef" |
operator= | 整体赋值替换字符串 | s = "new str"; | "new str" | |
[pos] / at(pos) | 修改指定位置的字符 | s[0] = 'A'; | "Abcdef" | |
assign(str, pos, len) | 用子串重新赋值（从 str 的 pos 位置取 len 个字符） | s.assign("xyz123", 3, 3); | "123" |
一般增删查改都是用索引[]完成与数组使用基本一致
#include <iostream>
#include <string>
using namespace std;
int main() {
string s = {"xingheng"};
//append(str, pos) 表示从字符串 str 的 pos 位置开始，将剩余所有字符追加到当前字符串末尾。
s.append("xi", 2);//xinghengxi
cout << s << endl;
//push_back只能插入单个字符
s.push_back('a'); //xinghengxia
cout << s << endl;
s.erase(2, 1); //xighengxia
cout << s << endl;
s[0] = 'v'; //修改第一个字符
cout << s << endl;
}
| 获取长度 | size() | 返回字符串当前包含的字符数（与 length() 功能相同） | string s = "hello"; s.size(); | 5 |
length() | 同 size()，历史遗留的命名（早期为与 C 风格字符串兼容） | s.length(); | 5 | |
| 容量管理 | capacity() | 返回当前分配的内存可容纳的字符数（不包含终止符），可能大于实际长度 | string s(5, 'a'); s.capacity(); | 通常为 5（编译器可能优化） |
reserve(n) | 预分配至少可容纳 n 个字符的内存空间（不改变实际内容，避免频繁扩容） | s.reserve(10); s.capacity(); | 至少为 10 | |
shrink_to_fit() | 缩减容量以匹配实际长度（C++11 及以上，可能不被所有编译器支持） | s.shrink_to_fit(); s.capacity(); | 与 size() 相等（5） | |
| 判空与清空 | empty() | 判断字符串是否为空（长度为 0 时返回 true） | string s; s.empty(); | true |
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
// empty()：判断是否为空
cout << "s是否为空？" << (s.empty() ? "是" : "否") << endl; // 是
// size()：获取长度
s = "abc";
cout << "s的长度：" << s.size() << endl; // 3
// reserve(n)：预留容量
s.reserve(10); // 提前预留10个字符的空间
cout << "预留后容量：" << s.capacity() << endl; // 至少10
cout << "预留后长度：" << s.size() << endl; // 仍为3（长度不变）
return 0;
}
注：size(),empty()，在所有容器中均存在
4.vector
定义：vector<元素类型> 容器名称;
vector可以储存所有的数据类型，但一个vector只能储存一种类型。
#include <iostream>
#include <string>
#include<vector> //头文件 使用vector时需包含
using namespace std;
int main() {
vector<int>v1(1);//定义一个整型的vector只能用来储存整型，储存其他类型会报错
vector<char*>v2;//定义一个整型的vector只能用来储存char*类型，储存其他类型会报错
}
注：vector与string方法高度相似可选择跳过
1.初始化
vector() | 默认构造函数，创建空容器 | vector<int> v; | 空容器（size=0，capacity=0） |
vector(size_t n) | 创建包含 n 个元素的容器，元素值为默认初始化（int 为 0，自定义类型调用默认构造） | vector<int> v(3); | 包含 3 个元素：[0, 0, 0] |
vector(size_t n, const T& val) | 创建包含 n 个元素的容器，每个元素值均为 val | vector<int> v(5, 8); | 包含 5 个元素：[8, 8, 8, 8, 8] |
vector(const vector& other) | 拷贝构造函数，复制另一个 vector 的所有元素 | vector<int> v1 = {1,2,3}; vector<int> v2(v1); | v2 与 v1 相同：[1, 2, 3] |
vector(InputIt first, InputIt last) | 范围构造，用迭代器区间 [first, last) 内的元素初始化 | vector<int> v1 = {1,2,3,4,5}; vector<int> v2(v1.begin()+1, v1.end()-1); | v2 包含 [2, 3, 4] |
vector(initializer_list<T> ilist) | 初始化列表构造（C++11 及以上），用列表中的元素初始化 | vector<int> v = {10, 20, 30}; |
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 1. 初始化列表构造
vector<int> v1 = {1, 2, 3};
cout << "初始化列表: ";
for (int n : v1) cout << n << " "; // 1 2 3
cout << endl;
// 2. 拷贝构造
vector<int> v2(v1); // 复制v1
cout << "拷贝构造: ";
for (int n : v2) cout << n << " "; // 1 2 3
cout << endl;
return 0;
}
2.增删查改
| 增加 | push_back(val) | 在容器末尾添加元素 val | v.push_back(40); | {10,20,30,40} |
insert(pos, val) | 在迭代器 pos 指向的位置插入元素 val | v.insert(v.begin()+1, 15); | {10,15,20,30} | |
insert(pos, n, val) | 在迭代器 pos 位置插入 n 个重复元素 val | v.insert(v.end(), 2, 50); | {10,20,30,50,50} | |
| 删除 | pop_back() | 删除容器末尾的元素 | v.pop_back(); | {10,20} |
erase(pos) | 删除迭代器 pos 指向的元素 | v.erase(v.begin()+1); | {10,30} | |
clear() | 清空容器中所有元素（size 变为 0，capacity 不变） | v.clear(); | {}（空容器） | |
| 查询 | operator[]（v[i]） | 通过索引 i 访问元素（无越界检查） | cout << v[1]; | 输出 20 |
at(i) | 通过索引 i 访问元素（越界抛 out_of_range 异常） | cout << v.at(2); | 输出 30 | |
front() | 访问容器的第一个元素 | cout << v.front(); | 输出 10 | |
back() | 访问容器的最后一个元素 | cout << v.back(); | 输出 30 | |
| 修改 | operator[]（v[i] = val） | 通过索引 i 修改元素值（无越界检查） | v[0] = 100; | {100,20,30} |
at(i) = val | 通过索引 i 修改元素值（越界抛异常） | v.at(1) = 200; | {10,200,30} | |
assign(n, val) | 清空容器并赋值 n 个 val 元素 | v.assign(3, 5); | {5,5,5} |
#include <iostream>
#include <vector>
using namespace std;
// 打印vector内容的辅助函数
void printVector(const vector<int>& v, const string& msg) {
cout << msg << ": ";
for (int num : v) {//范围for
cout << num << " ";
}
cout << endl;
}
int main() {
// 初始化vector
vector<int> v = {10, 20, 30};
printVector(v, "初始vector");
// 1. push_back(val)：末尾添加元素
v.push_back(40);
printVector(v, "push_back(40)后"); // 10 20 30 40
// 4. operator[] (v[i])：访问和修改元素
cout << "v[2] 的值：" << v[2] << endl; // 访问索引2的元素（20）
v[3] = 300; // 修改索引3的元素
printVector(v, "v[3] = 300后"); // 10 15 20 300 40 50 50
// 5. pop_back()：删除末尾元素
v.pop_back();
printVector(v, "pop_back()后"); // 10 15 20 300 40 50
printVector(v, "erase(v.begin()+4)后"); // 10 15 20 300 50
// 8. clear()：清空所有元素
v.clear();
printVector(v, "clear()后"); // 空vector
cout << "是否为空：" << (v.empty() ? "是" : "否") << endl; // 是
return 0;
}常用获取及容量管理函数与string一直在此不再赘述。
5.list
定义：list<元素类型> 容器名称;
list可以储存所有的数据类型，但一个list只能储存一种类型。他的底层是链表
注：list为链表，效率低于vector，且空间占用较大不推荐使用，但是再有大量的添加删除操作时可以使用,迭代器部分可以重点观看，list不支持[]！！！
1.初始化
list<T>() | 默认构造，创建空链表 | list<int> lst; | 空链表（size=0） |
list<T>(size_t n, const T& val = T()) | 创建含 n 个元素的链表，元素值均为 val（未指定则默认初始化） | list<int> lst(3, 8); | {8, 8, 8} |
list<T>(InputIt first, InputIt last) | 范围构造，用迭代器区间 [first, last) 内的元素初始化 | vector<int> vec={1,2,3}; list<int> lst(vec.begin(), vec.end()-1); | {1, 2} |
list<T>(const list<T>& other) | 拷贝构造，复制另一个 list 的所有元素 | list<int> lst1={10,20}; list<int> lst2(lst1); | {10, 20} |
2.
#include <iostream>
#include<list>
using namespace std;
int main() {
list<int >l1 = { 1, 2, 3, 4 };
/*
begin()用于获取容器的首个元素，在所有容器中都适用
类似的有end()获取容器结尾后一个位置，通常用作结束标志
rbegin() 获取容器开始的前一个位置，通常用作结束标志
rend()用于获取容器的最后一个元素
*/
auto iterator = l1.begin();
for (; iterator != l1.end(); iterator++) {
cout << *iterator; //*iterator（底层为指针）可以获得它指向的值
}
}2.增删查改
| 增加 | push_back(val) | 在链表末尾添加元素 val | lst.push_back(40); | {10,20,30,40} |
push_front(val) | 在链表头部添加元素 val | lst.push_front(5); | {5,10,20,30} | |
insert(pos, val) | 在迭代器 pos 指向的位置插入元素 val | auto it = ++lst.begin(); lst.insert(it, 15); | {10,15,20,30} | |
insert(pos, n, val) | 在迭代器 pos 位置插入 n 个重复元素 val | lst.insert(lst.end(), 2, 50); | {10,20,30,50,50} | |
insert(pos, first, last) | 在迭代器 pos 位置插入另一个容器 [first, last) 区间的元素 | list<int> a={5,6}; lst.insert(lst.begin(), a.begin(), a.end()); | {5,6,10,20,30} | |
| 删除 | pop_back() | 删除链表末尾的元素 | lst.pop_back(); | {10,20} |
pop_front() | 删除链表头部的元素 | lst.pop_front(); | {20,30} | |
erase(pos) | 删除迭代器 pos 指向的元素 | auto it = ++lst.begin(); lst.erase(it); | {10,30} | |
erase(first, last) | 删除迭代器区间 [first, last) 内的所有元素 | lst.erase(lst.begin(), ++lst.begin()); | {20,30} | |
clear() | 清空链表中所有元素（size 变为 0） | lst.clear(); | {}（空链表） | |
| 查询 | front() | 访问链表的第一个元素（返回引用） | cout << lst.front(); | 输出 10 |
back() | 访问链表的最后一个元素（返回引用） | cout << lst.back(); | 输出 30 | |
| 迭代器遍历 | 通过迭代器遍历所有元素（支持双向遍历，不支持随机访问） | for (auto it = lst.begin(); it != lst.end(); ++it) { ... } | 遍历 10,20,30 | |
| 修改 | front() = val | 修改第一个元素的值 | lst.front() = 100; | {100,20,30} |
back() = val | 修改最后一个元素的值 | lst.back() = 300; | {10,20,300} | |
| 迭代器修改 | 通过迭代器找到元素后修改 | auto it = lst.begin(); ++it; *it = 200; | {10,200,30} | |
assign(n, val) | 清空链表并赋值 n 个 val 元素 | lst.assign(3, 5); | {5,5,5} | |
assign(first, last) | 清空链表并赋值另一个容器 [first, last) 区间的元素 | list<int> b={1,2}; lst.assign(b.begin(), b.end()); | {1,2} |
6.栈与队列（高频）
stack:具有先进后出的特性
queue:具有先进先出的特性
priority_queue（优先级队列）:优先级驱动（每次弹出优先级最高元素）底层为堆可以自动调整，默认情况为大堆，用于取最大。
将元素 val 加入栈/队列/堆中 | 栈是 “先进后出” 结构，新元素始终在栈/队列/堆 顶 | ||
pop() | 弹出栈/队列/堆顶元素（无返回值） | 需先通过 empty() 判断栈/队列/堆非空，否则操作未定义（可能崩溃） | |
top() | 返回栈顶元素的引用（可修改，若为 const stack 则只读） | 仅能访问栈/队列/堆 顶，不支持随机访问 | |
empty() | 判断是否为空，返回 bool 值（空为 true，非空为 false） | 常用于弹出 / 访问前的合法性检查 | |
|
| 返回元素的个数，类型为 size_t | 无 |
#include <iostream>
#include <stack> //栈所需头文件
#include <queue> //优先级队列和队列所需头文件
using namespace std;
int main() {
// 栈：先进后出
stack<int> s;
s.push(1), s.push(2), s.push(3);
cout << "栈顶: " << s.top() << " 大小: " << s.size() << endl; // 3 3
s.pop(); //注意使用完后弹出
cout << "出栈后栈顶: " << s.top() << endl; // 2
// 队列：先进先出
queue<int> q;
q.push(1), q.push(2), q.push(3);
cout << "队头: " << q.front() << " 大小: " << q.size() << endl; // 1 3
q.pop(); //注意使用完后弹出
cout << "出队后队头: " << q.front() << endl; // 2
// 优先队列（大根堆）：取最大
priority_queue<int> pq;
pq.push(3), pq.push(1), pq.push(2);
cout << "大根堆顶: " << pq.top() << endl; // 3
pq.pop(); //注意使用完后弹出
cout << "出堆后堆顶: " << pq.top() << endl; // 2
// 小根堆：取最小
priority_queue<int, vector<int>, greater<int>> min_pq;
min_pq.push(3), min_pq.push(1), min_pq.push(2);
cout << "小根堆顶: " << min_pq.top() << endl; // 1
}
7.map和set
| 容器类型 | 核心特性 | 底层结构 | 关键方法（增删查） | 适用场景 |
|---|---|---|---|---|
| map | 1. 存储 <key, value> 键值对2. key 唯一，不允许重复3. 按 key 自动排序（默认升序） | 红黑树（平衡二叉搜索树） | - 增：insert({key, val})/emplace(key, val)- 删：erase(key)/erase(迭代器)- 查：find(key)（返回迭代器）/count(key)（判断存在） | 需键值映射且 key 唯一、需有序的场景（如学生 ID - 成绩映射、排序的配置表） |
| set | 1. 仅存储 key（key 即 value）2. key 唯一，不允许重复3. 按 key 自动排序（默认升序） | 红黑树 | - 增：insert(key)/emplace(key)- 删：erase(key)/erase(迭代器)- 查：find(key)/count(key) | 需去重且有序的场景（如排序的 ID 列表、去重的成绩集合） |
| unordered_set | 1. 仅存储 key，key 唯一2. 无序（不排序）3. 基于哈希表，查询效率高（平均 O (1)） | 哈希表 | 同 set（增删查方法一致） | 需快速去重、无需排序的场景（如判断元素是否存在、去重统计） |
| unordered_map | 1. 存储 <key, value> 键值对2. key 唯一3. 无序4. 基于哈希表，查询效率高（平均 O (1)） | 哈希表 | 同 map（增删查方法一致，支持 [] 访问 value：umap[key] = val） | 需快速键值映射、无需排序的场景（如缓存、计数统计） |
| multimap | 1. 存储 <key, value> 键值对2. key 可重复（允许多个相同 key）3. 按 key 自动排序 | 红黑树 | - 增：同 map（可插入重复 key）- 删：erase(key)（删除所有相同 key 的键值对）- 查：equal_range(key)（返回重复 key 的迭代器区间） | 需键值映射且 key 可重复、需有序的场景（如一个关键词对应多个内容、按时间排序的日志） |
| multiset | 1. 仅存储 key2. key 可重复3. 按 key 自动排序 | 红黑树 | - 增：同 set（可插入重复 key）- 删：erase(key)（删除所有相同 key）- 查：equal_range(key)（返回重复 key 区间） | 需保留重复元素且有序的场景（如带重复的成绩排序、统计元素出现次数） |
#include <iostream>
#include <map> // map, multimap
#include <set> // set, multiset
#include <unordered_set>// unordered_set
#include <unordered_map>// unordered_map
using namespace std;
int main() {
// 1. map（键值对，key唯一，有序）
map<int, string> m;
m.insert({1, "one"});
m[2] = "two"; // map支持[]访问
cout << "map[1] = " << m[1] << endl; // 输出：one
if (m.find(2) != m.end()) {
cout << "map中存在key=2" << endl;
}
// 2. set（仅key，key唯一，有序）
set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);
cout << "set元素（自动排序）：";
for (int val : s) cout << val << " "; // 输出：1 2 3
cout << endl;
// 3. unordered_set（仅key，key唯一，无序，哈希实现）
unordered_set<int> us;
us.insert(3);
us.insert(1);
us.insert(2);
cout << "unordered_set元素（无序）：";
for (int val : us) cout << val << " "; // 输出顺序不确定（如3 1 2）
cout << endl;
// 4. unordered_map（键值对，key唯一，无序，哈希实现）
unordered_map<int, string> um;
um.insert({1, "one"});
um[2] = "two"; // 支持[]访问
cout << "unordered_map[2] = " << um[2] << endl; // 输出：two
// 5. multimap（键值对，key可重复，有序）
multimap<int, string> mm;
mm.insert({1, "a"});
mm.insert({1, "b"}); // 允许重复key
cout << "multimap中key=1的元素数：" << mm.count(1) << endl; // 输出：2
auto range = mm.equal_range(1); // 获取重复key的区间
for (auto it = range.first; it != range.second; ++it) {
cout << it->second << " "; // 输出：a b
}
cout << endl;
// 6. multiset（仅key，key可重复，有序）
multiset<int> ms;
ms.insert(2);
ms.insert(1);
ms.insert(2); // 允许重复key
cout << "multiset元素（有序+重复）：";
for (int val : ms) cout << val << " "; // 输出：1 2 2
cout << endl;
}
8.常用函数
1.排序
sort
#include <iostream>
#include <vector>
#include <algorithm> // 包含ranges::sort
#include <ranges> // 包含范围相关工具
using namespace std;
int main() {
std::vector<int> nums = { 3, 1, 4, 1, 5, 9 };
//ranges::sort(nums); // 无需传递begin()和end()，c++20标准使用前需确认支持该标准
sort(nums.begin(), nums.end());//不支持c++20标准时可用
std::cout << "升序排序结果：";
for (int n : nums) {
std::cout << n << " "; // 输出：1 1 3 4 5 9
}
std::cout << "\n";
// 2. 自定义比较：降序排序
std::vector<int> nums2 = { 3, 1, 4, 1, 5, 9 };
//ranges::sort(nums2, std::greater<int>()); // 传递比较函数
sort(nums2.begin(), nums2.end(), greater<int>());
std::cout << "降序排序结果：";
for (int n : nums2) {
std::cout << n << " "; // 输出：9 5 4 3 1 1
}
std::cout << "\n";
// 3. 对容器的子范围排序
std::vector<int> nums3 = { 3, 1, 4, 1, 5, 9 };
// 排序从索引1到4的元素（左闭右开）
sort(nums3.begin() + 1, nums3.begin() + 5);
std::cout << "子范围排序结果：";
for (int n : nums3) {
std::cout << n << " "; // 输出：3 1 1 4 5 9
}
std::cout << "\n";
return 0;
}
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
18
0- 0
已为社区贡献4条内容
所有评论(0)