1.常用容器1.1向量vector构造vector类型 arr(长度, [初值])常用的一维和二维数组构造示例高维也是一样的就是会有点长vectorint arr; // 构造int数组 vectorint arr(100); // 构造初始长100的int数组 vectorint arr(100, 1); // 构造初始长100的int数组初值为1 vectorvectorint mat(100, vectorint ()); // 构造初始100行不指定列数的二维数组 vectorvectorint mat(100, vectorint (666, -1)) // 构造初始100行初始666列的二维数组初值为-1尾接 尾删push_back(元素)在 vector 尾接一个元素数组长度 1pop_back()删除 vector 尾部的一个元素数组长度// init: arr [] arr.push_back(1); // after: arr [1] arr.push_back(2); // after: arr [1, 2] arr.pop_back(); // after: arr [1] arr.pop_back(); // after: arr []获取长度.size()清空.clear()判空.empty()如果是空返回true反之返回false.改变长度.resize(新长度, [默认值])修改 vector 的长度如果是缩短则删除多余的值如果是扩大且指定了默认值则新元素均为默认值旧元素不变1.2 栈 stack1.2.1 常用方法作用用法示例构造stack类型 stkstackint stk;进栈.push(元素)stk.push(1);出栈.pop()stk.pop();取栈顶.top()int a stk.top();判空.empty()stack.empty()true;查看大小.size()stack.size()1.2.2注意事项不可访问内部元素下面都是错误用法for (int i 0; i stk.size(); i) cout stk[i] endl; for (auto ele : stk) cout stk endl;1.3 队列 queue1.3.1 常用方法作用用法示例构造queue类型 quequeueint que;进队.push(元素)que.push(1);出队.pop()que.pop();取队首.front()int a que.front();取队尾.back()int a que.back();判空.empty()que.empty()true;查看大小.size()que.size()1.3.2注意事项不可访问内部元素下面都是错误用法for (int i 0; i que.size(); i) cout que[i] endl; for (auto ele : que) cout ele endl;1.4 优先队列 priority_queue(堆)1.4.1构造priority_queue类型, 容器, 比较器 pque类型要储存的数据类型容器储存数据的底层容器默认为vector类型竞赛中保持默认即可比较器比较大小使用的比较器默认为less类型可自定义priority_queueint pque1; // 储存int的大顶堆 priority_queueint, vectorint, greaterint pque2; // 储存int的小顶堆对于需要自定义比较器的情况涉及一些初学时容易看迷糊的语法重载小括号运算符 / lambda 表达式在此就不展开讲了。如果想要了解可以查阅 cppreference 中的代码示例。其他作用用法示例进堆.push(元素)que.push(1);出堆.pop()que.pop();取堆顶.top()int a que.top();查看大小 / 判空略略1.4.2 适用情形持续维护元素的有序性每次向队列插入大小不定的元素或者每次从队列里取出大小最小/最大的元素1.4.3 注意事项仅堆顶可读只可访问堆顶其他元素都无法读取到。下面是错误用法cout pque[1] endl;所有元素不可写堆中所有元素是不可修改的。下面是错误用法pque[1] 2; pque.top() 1;如果你恰好要修改的是堆顶元素那么是可以完成的int tp pque.top(); pque.pop(); pque.push(tp 1);1.5 集合set集合三要素解释setmultisetunordered_set确定性一个元素要么在集合中要么不在✔✔✔互异性一个元素仅可以在集合中出现一次✔❌任意次✔无序性集合中的元素是没有顺序的❌从小到大❌从小到大✔1.5.1 常用方法构造set类型, 比较器 st类型要储存的数据类型比较器比较大小使用的比较器默认为less类型可自定义setint st1; // 储存int的集合从小到大 setint, greaterint st2; // 储存int的集合从大到小对于需要自定义比较器的情况涉及一些初学时容易看迷糊的语法重载小括号运算符 / lambda 表达式在此就不展开讲了。遍历可使用迭代器进行遍历for (setint::iterator it st.begin(); it ! st.end(); it) cout *it endl;基于范围的循环C 11for (auto ele : st) cout ele endl;其他作用用法示例插入元素.insert(元素)st.insert(1);删除元素.erase(元素)st.erase(2);查找元素.find(元素)auto it st.find(1);判断元素是否存在.count(元素)st.count(3);查看大小 / 清空 / 判空略略增删查时间复杂度均为 (log⁡)1.5.2 适用情形元素去重[1,1,3,2,4,4]→[1,2,3,4]维护顺序[1,5,3,7,9]→[1,3,5,7,9]元素是否出现过元素大小 [−1018,1018]元素数量 106vis 数组无法实现通过 set 可以完成。1.5.3 注意事项不存在下标索引set 虽说可遍历但仅可使用迭代器进行遍历它不存在下标这一概念无法通过下标访问到数据。下面是错误用法cout st[0] endl;元素只读set 的迭代器取到的元素是只读的因为是 const 迭代器不可修改其值。如果要改需要先 erase 再 insert.下面是错误用法cout *st.begin() endl; // 正确。可读。 *st.begin() 1; // 错误不可写不可用迭代器计算下标set 的迭代器不能像 vector 一样相减得到下标。下面是错误用法auto it st.find(2); // 正确返回2所在位置的迭代器。 int idx it - st.begin(); // 错误不可相减得到下标。1.6 映射map提供对数时间的有序键值对结构。底层原理是红黑树。性质解释mapmultimapunordered_map互异性一个键仅可以在映射中出现一次✔❌任意次✔无序性键是没有顺序的❌从小到大❌从小到大✔1.6.1 常用方法构造map键类型, 值类型, 比较器 mp键类型要储存键的数据类型值类型要储存值的数据类型比较器键比较大小使用的比较器默认为less类型可自定义mapint, int mp1; // int-int 的映射键从小到大 mapint, int, greaterint st2; // int-int 的映射键从大到小对于需要自定义比较器的情况涉及一些初学时容易看迷糊的语法重载小括号运算符 / lambda 表达式在此就不展开讲了。遍历可使用迭代器进行遍历for (mapint, int::iterator it mp.begin(); it ! mp.end(); it) cout it-first it-second endl;基于范围的循环C 11for (auto pr : mp) cout pr.first pr.second endl;结构化绑定 基于范围的循环C17for (auto [key, val] : mp) cout key val endl;其他作用用法示例增 / 改 / 查元素中括号mp[1] 2;查元素返回迭代器.find(元素)auto it mp.find(1);删除元素.erase(元素)mp.erase(2);判断元素是否存在.count(元素)mp.count(3);查看大小 / 清空 / 判空略略1.6.2 适用情形需要维护映射的场景可以使用输入若干字符串统计每种字符串的出现次数。(mapstring, int mp)1.6.3 注意事项中括号访问时默认值如果使用中括号访问 map 时对应的键不存在那么会新增这个键并且值为默认值因此中括号会影响键的存在性。mapchar, int mp; cout mp.count(a) endl; // 0 mp[a]; // 即使什么都没做此时mp[a]0已经插入了 cout mp.count(a) endl; // 1 cout mp[a] endl; // 0不可用迭代器计算下标map 的迭代器不能像 vector 一样相减得到下标。下面是错误用法auto it mp.find(a); // 正确返回2所在位置的迭代器。 int idx it - mp.begin(); // 错误不可相减得到下标。1.7 字符串 string构造构造函数string(长度, 初值)string s1; // 构造字符串为空 string s2 awa!; // 构造字符串并赋值awa! string s3(10, 6); // 构造字符串通过构造函数构造为6666666666输入输出Cstring s; cin s; cout s;Cstring s; char buf[100]; scanf(%s, buf); s buf; printf(%s, s.c_str());其他作用用法示例修改、查询指定下标字符[]s[1] a;是否相同if (s1 s2) ...字符串连接string s s1 s2;尾接字符串s awa;取子串.substr(起始下标, 子串长度)string sub s.substr(2, 10);查找字符串.find(字符串, 起始下标)int pos s.find(awa);数值与字符串互转C11源目的函数int / long long / float / double / long doublestringto_string()stringintstoi()stringlong longstoll()stringfloatstof()stringdoublestod()stringlong doublestold()1.7.2 适用情形非常好用建议直接把字符数组扔了赶快投入 string 的怀抱。1.7.3 注意事项尾接字符串一定要用string 的 运算符将会在原字符串原地尾接字符串。而 了再 赋值会先生成一个临时变量在复制给 string.通常字符串长度可以很长如果使用 字符串很容易就 TLE 了。// 优化前: 15139ms string s; for (int i 0; i 5e5; i) s s a; // 优化后: 1ms (计时器显示0) string s; for (int i 0; i 5e5; i) s a;2.迭代器2.1 迭代器是什么对于一个 vector我们可以用下标遍历for (int i 0; i a.size(); i) cout a[i] endl;我们同时也可以用迭代器来遍历for (vectorint::iterator it a.begin(); it ! a.end(); it) cout *it endl;a.begin()是一个迭代器指向的是第一个元素a.end()是一个迭代器指向的是最后一个元素再后面一位上述迭代器具有自增运算符自增则迭代器向下一个元素移动迭代器与指针相似如果对它使用解引用运算符即*it就能取到对应值了2.2 为何需要迭代器很多数据结构并不是线性的例如红黑树对于非线性数据结构下标是无意义的。无法使用下标来遍历整个数据结构。迭代器的作用就是定义某个数据结构的遍历方式通过迭代器的增减代表遍历到的位置通过迭代器便能成功遍历非线性结构了。例如set 的实现是红黑树我们是没法用下标来访问元素的。但是通过迭代器我们就能遍历 set 中的元素了for (setint::iterator it st.begin(); it ! st.end(); it) cout *it endl;2.3 迭代器用法对于 vector 容器它的迭代器功能比较完整以它举例.begin()头迭代器.end()尾迭代器.rbegin()反向头迭代器.rend()反向尾迭代器迭代器整型将迭代器向后移动迭代器-整型将迭代器向前移动迭代器将迭代器向后移动 1 位迭代器--将迭代器向前移动 1 位迭代器-迭代器两个迭代器的距离prev(it)返回 it 的前一个迭代器next(it)返回 it 的后一个迭代器对于其他容器由于其结构特性上面的功能不一定都有例如 set 的迭代器是不能相减求距离的2.4 常见问题.end()和.rend()指向的位置是无意义的值对于一个长度为 10 的数组for (int i 0; i 10; i)第 10 位是不可访问的对于一个长度为 10 的容器for (auto it a.begin(); it ! a.end(); it).end 是不可访问的不同容器的迭代器功能可能不一样迭代器细化的话有正向、反向、双向每个容器的迭代器支持的运算符也可能不同因此不同容器的迭代器细节很有可能是不一样的。删除操作时需要警惕为什么 3 没删掉vectorint a{1, 2, 3, 4}; for (auto it a.begin(); it ! a.end(); it) if (*it 2 || *it 3) a.erase(it); // a [1, 3, 4]为啥 RE 了vectorint a{1, 2, 3, 4}; for (auto it a.begin(); it ! a.end(); it) if (*it 4) a.erase(it);建议如无必要别用迭代器操作容器。遍历与访问没关系3. 常用算法4.2swap()交换两个变量的值用法示例template class T void swap( T a, T b );int a 0, b 1; swap(a, b); // now a 1, b 0 int arr[10] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; swap(arr[4], arr[6]); // now arr {0, 1, 2, 3, 6, 5, 4, 7, 8, 9}注意事项这个 swap 参数是引用的不需要像 C 语言一样取地址。4.3sort()使用快速排序给一个可迭代对象排序用法示例template class RandomIt, class Compare void sort( RandomIt first, RandomIt last, Compare comp );默认排序从小到大vectorint arr{1, 9, 1, 9, 8, 1, 0}; sort(arr.begin(), arr.end()); // arr [0, 1, 1, 1, 8, 9, 9]如果要从大到小则需要传比较器进去。vectorint arr{1, 9, 1, 9, 8, 1, 0}; sort(arr.begin(), arr.end(), greaterint()); // arr [9, 9, 8, 1, 1, 1, 0]如果需要完成特殊比较则需要手写比较器。比较器函数返回值是 bool 类型传参是需要比较的两个元素。记我们定义的该比较操作为 ⋆若 ⋆则比较器函数应当返回true若 ⋆̸则比较器函数应当返回false注意如果 比较器函数必须返回falsebool cmp(pairint, int a, pairint, int b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; } int main() { vectorpairint, int arr{{1, 9}, {2, 9}, {8, 1}, {0, 0}}; sort(arr.begin(), arr.end(), cmp); // arr [(0, 0), (8, 1), (2, 9), (1, 9)] }4.4lower_bound()/upper_bound()在已升序排序的元素中应用二分查找检索指定元素返回对应元素迭代器位置。找不到则返回尾迭代器。lower_bound(): 寻找 ≥ 的第一个元素的位置upper_bound(): 寻找 的第一个元素的位置怎么找 ≤ / 的第一个元素呢 的第一个元素的前一个元素如果有便是 ≤ 的第一个元素≥ 的第一个元素的前一个元素如果有便是 的第一个元素返回的是迭代器如何转成下标索引呢减去头迭代器即可。用法示例template class ForwardIt, class T ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T value );vectorint arr{0, 1, 1, 1, 8, 9, 9}; vectorint::iterator it lower_bound(arr.begin(), arr.end(), 7); int idx it - arr.begin(); // idx 4我们通常写成一行vectorint arr{0, 1, 1, 1, 8, 9, 9}; idx lower_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4 idx lower_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 4 idx upper_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4 idx upper_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 54.5reverse()反转一个可迭代对象的元素顺序用法示例template class BidirIt void reverse( BidirIt first, BidirIt last );vectorint arr(10); iota(arr.begin(), arr.end(), 1); // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 reverse(arr.begin(), arr.end()); // 10, 9, 8, 7, 6, 5, 4, 3, 2, 14.6max()/min()返回最大值 / 最小值的数值用法示例int mx max(1, 2); // 2 int mn min(1, 2); // 1在 C11 之后可以使用列表构造语法传入一个列表这样就能一次性给多个元素找最大值而不用套娃了// Before C11 int mx max(max(1, 2), max(3, 4)); // 4 int mn min(min(1, 2), min(3, 4)); // 1 // After C11 int mx max({1, 2, 3, 4}); // 4 int mn min({1, 2, 3, 4}); // 14.7unique()消除数组的重复相邻元素数组长度不变但是有效数据缩短返回的是有效数据位置的结尾迭代器。例如[1,1,4,5,1,4]→[1,4,5,1,4,?―]下划线位置为返回的迭代器指向。template class ForwardIt ForwardIt unique( ForwardIt first, ForwardIt last );用法示例单独使用 unique 并不能达成去重效果因为它只消除相邻的重复元素。但是如果序列有序那么它就能去重了。但是它去重后序列尾部会产生一些无效数据[1,1,2,4,4,4,5]→[1,2,4,5,?―,?,?]为了删掉这些无效数据我们需要结合 erase.最终给 vector 去重的写法便是vectorint arr{1, 2, 1, 4, 5, 4, 4}; sort(arr.begin(), arr.end()); arr.erase(unique(arr.begin(), arr.end()), arr.end());4.8 数学函数所有函数参数均支持int/long long/float/double/long double公式示例f(x)|x|abs(-1.0)f(x) e^xexp(2)f(x)lnxlog(3)f(x,y) x^ypow(2, 3)f(x)√xsqrt(2)向上取整ceil(2.1)向下取整floor(2.1)去掉小数round(2.1)4.9gcd()/lcm()C17返回最大公因数 / 最小公倍数int x gcd(8, 12); // 4 int y lcm(8, 12); // 24如果不是 C17但是是 GNU 编译器g那么可以用内置函数__gcd().当然gcd/lcm函数也挺好写直接写也行欧几里得算法int gcd(int a, int b) { if (!b) return a; return gcd(b, a % b); } int lcm(int a, int b) { return a / gcd(a, b) * b; }