第 2 章 · 01 C++ 基础(对应 docs/lang/)

第 2 章 · 01 C++ 基础(对应 docs/lang/)

本节定位:对应 OI Wiki docs/lang/。难度:入门。前置依赖:第 1 章(会用这份地图)。

⚠️ 注意:竞赛几乎只用 C++。虽然 OI Wiki 也讲了 Python(docs/lang/python.md)和 Java(docs/lang/java.md),但竞赛性能与 STL 支持上 C++ 占绝对优势,不要在语言选择上浪费时间,直接 C++。

知识地图

为什么选 C++

算法竞赛主流语言是 C++,原因有三:

1. 性能:C++ 编译为原生机器码,常数因子小,同等算法比 Python/Java 快一到两个数量级,在 1 秒时限内能多撑过一个 log。
2. STL 强大:vector / set / map / priority_queue / sort / lower_bound / __builtin_* 等开箱即用,竞赛题几乎都靠 STL 起手。
3. 社区与评测友好:所有主流 OJ 都把 C++ 作为首选语言,题解、模板几乎全是 C++。OI Wiki 的代码示例也以 C++ 为主。

docs/lang/ 页面地图

OI Wiki 的 docs/lang/ 目录覆盖 C++ 从入门到进阶的全部语法,按学习顺序排列:

语言基础

• docs/lang/helloworld.md:第一个程序,认识 C++ 源程序框架。
• docs/lang/basic.md:C++ 语法基础总览。
• docs/lang/var.md:变量与数据类型(int/long long/double/char)。
• docs/lang/op.md:运算符(算术/关系/逻辑/位运算)。
• docs/lang/branch.md:分支结构(if/switch)。
• docs/lang/loop.md:循环结构(for/while/do-while)。
• docs/lang/array.md:数组。
• docs/lang/struct.md:结构体。
• docs/lang/func.md:函数与参数传递。
• docs/lang/optimizations.md:常数优化(竞赛向,必读)。

进阶语法

• docs/lang/pointer.md:指针。
• docs/lang/reference.md:引用(&,函数参数常用)。
• docs/lang/class.md:面向对象(OOP,类与对象)。
• docs/lang/struct.md + docs/lang/union.md + docs/lang/new.md:结构体/联合体/动态内存。
• docs/lang/namespace.md:命名空间。
• docs/lang/lambda.md:Lambda 表达式(STL 算法回调常用)。
• docs/lang/op-overload.md:运算符重载(自定义排序时用到)。

STL

• docs/lang/csl/:这是 STL 子目录,放容器与迭代器的详细页面。包括 vector / string / set / map / queue / stack / priority_queue / deque / bitset 等。
• docs/lang/pb-ds/:Policy-Based Data Structures,扩展数据结构(tree 红黑树 / rope 串 / hash_table),省选级才用,初学可跳过。

算法库
竞赛最常用的 <algorithm> 库函数(sort / lower_bound / upper_bound / unique / max / min / nth_element / next_permutation / __gcd / reverse / fill 等)散落在各页,主要在 docs/lang/basic.md 和 STL 相关页提及。docs/basic/stl-sort.md 专门讲 sort。

其中几个高频"冷门好用"函数值得专门记住:

• nth_element:O(n) 求第 k 小(把第 k 大放到位置 k,左侧都比它小)。
• unique:配合 sort 去重(排序后把相邻重复元素放后面,返回去重后尾地址)。经典套路 int n = unique(a, a+n) - a;。
• __builtin_popcount / __builtin_ctz / __builtin_clz:位运算计数(1 的个数、末尾/前导 0 个数),状压 DP 必备。
• next_permutation:生成下一个排列,全排列暴力用。

输入输出

• docs/lang/io.md(在 docs/contest/ 下):输入输出优化,竞赛必备的"快读快写"。
• docs/lang/file-op.md:文件操作(交互题、对拍用)。

学习建议

必须掌握的"三大容器 + 两大算法 + 快读写"

如果时间有限,先吃透这几样:

1. vector:动态数组,竞赛最常用容器。掌握 push_back / size / [] / clear / resize / 迭代器遍历。
2. set:有序集合(基于红黑树),自动去重排序。掌握 insert / erase / find / lower_bound / count。
3. map:有序映射(键值对)。掌握 [] / insert / erase / find / 遍历。注意 [] 会自动插入默认值。
4. sort:万能排序,掌握自定义比较函数(函数指针或 Lambda)。
5. lower_bound / upper_bound:二分查找,配合 vector 或数组使用,前提是已排序。
6. 快读快写:scanf / printf 比 cin / cout 快;数据量极大时用自定义 read() 读整数(见 docs/contest/io.md)。

进阶一点,这两个也要早学:

7. bitset:压缩位存储,32/64 倍省空间,状压和优化常数神器(docs/lang/csl/ 里有)。例如 bitset<1000> 只用 128 字节,而不是 1000 字节数组。
8. struct + 运算符重载:自定义类型排序时,重载 < 运算符比写比较函数更优雅(docs/lang/op-overload.md)。

struct Node{ int v, w; bool operator<(const Node&o) const { return w<o.w; } };
​

💡 学习提示:STL 容器的复杂度要记牢(如 set 的 lower_bound 是 O(log n),但 vector 上的 lower_bound 也是 O(log n);而 set 不支持随机访问,不能用全局 lower_bound)。这些细节 Wiki 页面都标了,务必看。

顺序建议

按 helloworld.md → basic.md → var.md → op.md → branch.md → loop.md → array.md → func.md 的顺序读,这是 Wiki 自带 docs/contest/roadmap.md 推荐的路径。语法基础过完再进 STL(csl/ 目录)。OOP(class.md)和指针(pointer.md)竞赛中用得不多,理解即可,不必深抠。

💡 学习提示:语言学习不要"过度准备"。掌握基础语法 + STL 三大容器后,就可以开始刷题,在题目中遇到不懂的语法再回查 Wiki。在题目里学的语法比单纯看书记得牢。判断"可以开始刷题"的标准:能独立写出"读入 n 个数、排序、输出"这种入门题。

常见误区

⚠️ 注意:以下三个错误初学者几乎必犯:

1. 忘了 #include:用 cin/cout 没 #include <iostream>,用 sort 没 #include <algorithm>,用 vector 没 #include <vector>。竞赛时图省事可以 #include <bits/stdc++.h>(万能头,但非标准,部分评测机不支持)。
2. 没开 O2 优化:本地编译加 -O2,很多评测机默认开 O2。不开 O2 你的程序可能慢一倍,影响常数。
3. cin / cout 没解除同步:ios::sync_with_stdio(false); cin.tie(0); 这两行能大幅提速 cin/cout。但用了之后不要和 scanf/printf 混用。
4. long long 溢出:int 范围约 2e9,乘法或大数求和务必开 long long。这是 NOIp 最经典的爆零原因。
5. 数组越界 / 没初始化:全局数组默认 0,局部数组是垃圾值。多测题务必每轮清空。

本节要点

1. 竞赛只用 C++(性能 + STL + 社区),不要纠结语言选择。
2. docs/lang/ 按学习顺序排:语法基础(helloworld/basic/var/op/branch/loop/array/func)→ STL(csl/)→ 进阶(class/pointer/lambda)。
3. 必须掌握三大容器(vector/set/map)+ 两大算法(sort/lower_bound)+ 快读快写。
4. STL 容器的复杂度要记牢,set 不能用全局 lower_bound。
5. 三大坑:忘 include、没开 O2、cin/cout 没解除同步;外加 long long 溢出和多测不清空。