从C到C++：STL核心知识点记录

一、C++ 对 C 的语法增强

1.1 输入输出提速

Q:为什么需要提速？ A:因为默认情况下,C++为了和C统一cin/cout和scanf/printf安全混用，会进行同步，这将带来额外开销。ios::sync_with_stdio(false);就是关闭这个同步，让C++流独立运行，速度大幅提升。因此，加速后也不能同scanf/printf混用。

cin/cout 基础用法：比 scanf/printf 更简洁，支持类型自动推断

加速关键语句：

cpp

ios::sync_with_stdio(false);  // 解除C++与C标准流同步
cin.tie(0);                   // 解除 cin 与 cout 的绑定

cin.tie(0)的作用：默认情况下，cin在读入前会刷新cout的缓冲区，以保证你之前输出的提示语能被看到。这个功能对于交互来说非常重要，但是对于纯读入大量数据的竞赛题来说，这也是不必要的性能损耗。tie(0)解绑后，cin和cout各自独立，速度更快。

注意：加速后不可与 scanf/printf 混用（补充，puts/getchar等C风格输入输出都不行，否则会导致输入输出顺序混乱和其他错误）

1.2 引用（Reference）

本质：变量的别名，与原始变量共享内存地址
函数参数传递：void func(int& x) 避免拷贝，提升效率
与指针区别：引用必须初始化，不能为空，不能重新绑定

e.g.1

void swap_c(int* a, int* b) { // C风格，用指针
    int t = *a; *a = *b; *b = t;
}
void swap_cpp(int& a, int& b) { // C++风格，用引用
    int t = a; a = b; b = t;
}
int main() {
    int x = 1, y = 2;
    swap_cpp(x, y); // 调用时更简洁，像传值一样
    // swap_c(&x, &y); // C需要传地址
}

e.g.2 在for循环中的应用（Deepseek告诉我这很关键）

vector<int> v = {1, 2, 3};
for (int& x : v) { // x是v中每个元素的引用
    x *= 2; // 直接修改原容器中的元素
}
// v 现在是 {2, 4, 6}
// 如果写成 for (int x : v)，则修改的只是临时拷贝

1.3 函数重载（Overload）

规则：函数名相同，参数类型或数量不同

底层原理：C++编译器通过名字修饰（Name Mangling），将函数名和参数类型等信息编码成一个唯一的内部名字，从而区分同名函数。 C语言没有这个机制。

应用场景：简化同名功能函数（如不同数据类型的排序）

注意:返回值类型不同不能构成重载

二、标准模板库（STL）核心组件

2.1 容器（Containers）

vector（动态数组）

头文件：#include <vector>
特性：动态扩容的连续内存数组

核心方法：

cpp

vector<int> v;           // 声明
v.push_back(x);          // 尾部插入
v.pop_back();            // 尾部删除
v.size();                // 元素数量
v.clear();               // 清空
v.resize(n);             // 调整大小
v[i];                    // 随机访问（不检查越界）?
v.at(i);                 // 随机访问（检查越界）  ?

应用场景：替代C静态数组，存储邻接表

其他使用方法：

预分配空间，避免频繁扩容（性能关键）

cpp

vector<int> v;
v.reverse(100000); //预留10万个int空间，但size仍为0
//之后push_back在容器用尽前不会触发重新分配和拷贝

构造方式

cpp

vector<int> v1(10,5); //10个元素，每个初始化为5
vector<int> v2={1,2,3,4,5}; //列表初始化，C++11
vector<int> v3(v2.begin()+1,v2.end()-1); //用迭代器范围构造，v3={2,3,4}

emplace_backvspush_backemplace_back直接在容器尾部构造元素，省去一次临时对象的拷贝或移动，对于非基本类型的对象效率更高。（什么叫“非基本类型”？）

cpp

vector<pair<int,string>> v;//pair是什么意思？
v.push_back(make_pair(1,"hello")); //需要构造临时pair
v.emplace_back(1,"hello"); //直接根据参数(1,"hello")在容器内构造pair，更高效

string（字符串）详细笔记

头文件：#include <string>
特性：动态字符序列，支持丰富操作

核心方法：

cpp

string s = "Hello";
s += " World";           // 拼接
s.find("ello");          // 查找子串 （具体用法？）
s.substr(pos, len);      // 获取子串 （？）
s.length();              // 字符串长度 （返回值？）
s.c_str();               // 转换为C风格字符串 （什么时候需要用？）

其他：

与C字符串的互换：

cpp

char cstr[]="Hello";
string cppstr=cstr;
const char* p=cppstr.cstr(); //C++转C，用于需要C字符串参数的函数（如printf）

流式操作

cpp

string s;
int a;
getline(cin,s); //读取整行（包括空格）
stringstream ss(s); //字符串流
while (ss>>a) { //可以像cin一样从字符串中提取数据
  cout<<a<<endl;
}

下面两个感觉和高中技术学的Python里面字典和集合的概念很像（有点忘了，没选技术🙃）

map（映射）

头文件：#include <map>
特性：键值对集合，基于红黑树实现，自动按键排序 (什么是红黑树？)

核心方法：

cpp

map<string, int> mp;
mp["apple"] = 5;         // 插入/修改
mp.count("apple");       // 查找键是否存在 ？
mp.find("apple");        // 返回迭代器    ？
mp.erase("apple");       // 删除
mp.size();               // 元素数量

时间复杂度：插入、查找、删除 O(log n)
应用场景：统计频率、建立映射关系

set（集合）

头文件：#include <set>
特性：有序不重复集合，基于红黑树实现

核心方法：

cpp

set<int> s;
s.insert(10);            // 插入
s.count(10);             // 判断元素是否存在
s.erase(10);             // 删除
s.lower_bound(x);        // 返回首个不小于x的迭代器 ？
s.upper_bound(x);        // 返回首个大于x的迭代器   ？

`unordered_map`/`unordered_set` （哈希表）

为什么重要：map/set基于红黑树(O(log n))。而unordered_map/unordered_set基于哈希表，平均O(1)的查找、插入，在不要求键有序的场景下，性能远胜于map/set.
头文件#include <unordered_map>,#include <unordered_set>
用法：与map/set几乎一致，但没有lower_bound/upper_bound这类有序操作
竞赛建议：除非题目需要有序键，否则优先使用unordered_map/unordered_set

queue（队列） & stack（栈）

头文件：#include <queue>、#include <stack>

队列核心方法：

cpp

queue<int> q;
q.push(x);               // 入队
q.pop();                 // 出队（不返回值）
q.front();               // 队首元素
q.empty();               // 判断空

栈核心方法：

cpp

stack<int> st;
st.push(x);              // 入栈
st.pop();                // 出栈
st.top();                // 栈顶元素

2.2 算法（Algorithms）

sort（排序）

头文件：#include <algorithm>

核心用法：

cpp

vector<int> v = {5, 3, 8, 1};
sort(v.begin(), v.end());                // 升序排序
sort(v.begin(), v.end(), greater<int>()); // 降序排序（greater<int>是什么）

自定义比较函数：

cpp

bool cmp(int a, int b) { return a > b; }
sort(v.begin(), v.end(), cmp);

补充：对`sort`的深入：自定义复杂比较

对结构体/类排序

cpp

struct Node{
  int x,y;
};
bool cmp(const Node& a, const Node& b) {
  if (a.x != b.x) return a.x<b.x; //先按x升序
  return a.y>b.y; //x相同，按y降序
}
vector<Node> nodes;
sort(nodes.begin(),nodes.end(),cmp);

Lambda表达式（C++11，更简洁）

cpp

sort(nodes.begin(),nodes.end(),[](const Node& a, const Node& b){
  return a.x<b.x;
});

lower_bound & upper_bound（二分查找）

前提：必须在有序序列上使用

核心用法：

cpp

vector<int> v = {1, 3, 5, 7, 9};
auto pos = lower_bound(v.begin(), v.end(), 5) - v.begin();  // 第一个≥5的位置
auto pos2 = upper_bound(v.begin(), v.end(), 5) - v.begin(); // 第一个>5的位置

auto是什么？

其他实用算法

unique去重：通常与sort联用，删除相邻重复元素，返回去重后的尾后迭代器。

cpp

vector<int> v = {1,2,2,3,3,3,4};
sort(v.begin(),v.end()); //必须先排序
auto last = unique(v.begin(),v.end()); //last指向去重后的逻辑末尾
v.erase(last,v.end()); //删除尾部重复元素，v={1,2,3,4}

next_permutation全排列：

cpp

vector<int> v={1,2,3};
do {
  //处理当前排列，如123，132，213，...
} while (next_permutation(v.begin(),v.end()));

2.3 实用组件

pair（数据对）

头文件：#include <utility> 或 <algorithm>
特性：将两个值组合为单一对象

核心用法：

cpp

pair<int, string> p = {1, "apple"};
p.first;                 // 访问第一个元素
p.second;                // 访问第二个元素

默认排序：按 first 排序，相同时按 second 排序

auto 关键字

用途：类型自动推断，简化迭代器声明

典型用法：

cpp

for(auto it = v.begin(); it != v.end(); ++it)
for(const auto& x : v)   // 范围for循环

C数组 → vector：获得动态大小和安全管理
C字符串 → string：获得丰富字符串操作方法
手动查找/统计 → map/set：获得 O(log n) 复杂度操作
手写排序/二分 → sort/lower_bound：获得标准化高效实现

Iterator 迭代器

三、关键转换思维

是什么：一种智能指针，用于遍历和访问容器中的元素，是算法（如sort）和容器之间的桥梁。
核心类型：
- begin()：指向第一个元素
- end：指向最后一个元素的下一个位置（“尾后”，不是最后一个元素！）。
失效问题（重要陷阱！）：在修改容器（如vector插入删除）时，原有的迭代器可能失效，不要保存旧的迭代器。

cpp

vector<int> v={1,2,3,4};
auto it = v.begin()+2; //it指向3
v.insert(v.begin(),0); //在头部插入，可能导致内存重新分配
//此时it可能已经失效！再使用*it是未定义行为

四、性能注意事项

大量数据输入：使用 ios::sync_with_stdio(false); 加速
容器传参：使用引用避免拷贝，如 void func(const vector<int>& v)
查找操作：优先使用 map/set 而非线性查找
内存释放：局部 STL 容器会在作用域结束时自动释放

五、其他

#include <bits/stdc++.h>：这是一个“万能头文件”，包含了竞赛中绝大多数需要的标准库。在ICPC等允许的环境下使用可以极大节省编码时间，但不利于工程学习。
使用 endl 换行：endl 会输出换行符并立即刷新缓冲区，在大量输出时非常慢。竞赛中多用 '\n'。
cpp
```
cout << "Hello" << '\n'; // 快
cout << "World" << endl; // 慢（除非需要即时输出，如调试）
```
vector 的 = 是深拷贝：vector<int> v2 = v1; 会复制所有元素，时间复杂度O(n)。如果不想拷贝，请用引用。
map 的下标访问 [] 的危险性：mp[key] 如果 key 不存在，会自动插入一个默认值（如int是0）。如果你只想检查是否存在，应该先用 count() 或 find()。
ios::sync_with_stdio(false) 的位置：必须放在所有输入输出操作之前，通常是 main 函数的第一句。

此笔记为从C语言过渡到竞赛C++的核心知识点摘要，侧重STL在算法竞赛中的实际应用。

从C到C++：STL核心知识点记录 ​

一、C++ 对 C 的语法增强 ​

1.1 输入输出提速 ​

1.2 引用（Reference） ​

1.3 函数重载（Overload） ​

二、标准模板库（STL）核心组件 ​

2.1 容器（Containers） ​

vector（动态数组） ​

string（字符串）详细笔记 ​

map（映射） ​

set（集合） ​

unordered_map/unordered_set （哈希表） ​

queue（队列） & stack（栈） ​

2.2 算法（Algorithms） ​

sort（排序） ​

补充：对sort的深入：自定义复杂比较 ​

lower_bound & upper_bound（二分查找） ​

其他实用算法 ​

2.3 实用组件 ​

pair（数据对） ​

auto 关键字 ​

Iterator 迭代器 ​

三、关键转换思维 ​

四、性能注意事项 ​

五、其他 ​

从C到C++：STL核心知识点记录

一、C++ 对 C 的语法增强

1.1 输入输出提速

1.2 引用（Reference）

1.3 函数重载（Overload）

二、标准模板库（STL）核心组件

2.1 容器（Containers）

vector（动态数组）

string（字符串）详细笔记

map（映射）

set（集合）

`unordered_map`/`unordered_set` （哈希表）

queue（队列） & stack（栈）

2.2 算法（Algorithms）

sort（排序）

补充：对`sort`的深入：自定义复杂比较

lower_bound & upper_bound（二分查找）

其他实用算法

2.3 实用组件

pair（数据对）

auto 关键字

Iterator 迭代器

三、关键转换思维

四、性能注意事项

五、其他