一.常用容器1.向量vector#includevector构造vector类型 arr(长度[初值])使用示例vectorint arr;//构造int数组 vectorint arr(100);//构造初始长为100的数组 vectorint arr(1001);//构造初始值为1初始长为100的数组 vectorvectorint arr(100,vectorint ());//构造行数100行不指定列数的二维数组 vectorvectorint arr(100,vectorint (1001));//构造行数100列数100初始值为1的二维数组尾接尾删.push_back():在vector尾接一个元素长度1.pop_back():删除vector尾部的元素长度-1获取长度.size():获取当前vector的长度清空.clear():清空vector判空.empty():判断是否为空空则返回1非空则返回0改变长度.resize(新长度[默认值])修改vector的长度一般情况下vector可替换掉普通数组除非卡常2.栈stack#includestack作用用法构造stack类型 stk进栈.push(元素)出栈.pop()取栈顶.top()注意栈不可访问内部元素,栈是先进后出3.队列queue#includequeue作用用法构造queue类型 queue进队.push(元素)出队.pop()取队首.front()取队尾.back()同样队列也不可以访问内部元素队列是先进先出4.优先队列priority_queue:#includequeue构造priority_queue类型容器比较器 pque类型要存储的数据类型容器储存数据的底层容器默认vector类型竞赛中保持默认即可比较器比较大小使用的比较器默认为小根堆priority_queueint pque;//小根堆 priority_queueint,vectorint,greaterint pque1;//大根堆小根堆值越小优先级越高函数对其进行的操作都优先返回小的元素大跟堆值越大优先级越高函数对其进行的操作都优先返回大的元素作用用法进堆.push(元素)出堆.pop()取堆顶.top()5.集合set#includeset集合的特性就是数学中的互异性、确定性同时集合是有序的存进集合中的元素会自动排序构造set类型比较器 名称比较器默认less类型setint st1; setint,greater st2;遍历set遍历有两种第一种是用迭代器进行遍历for(setint::iterator it st.begin();it ! st.end();it){ cout*itendl; }第二种是基于范围的循环for(auto ele : st){ couteleendl; }操作set的函数作用用法插入元素.insert()删除元素.erase()查找元素.find()判断元素是否存在.count()set在需要元素去重和维护顺序时需要优先使用注意set不存在下标索引set中的元素只读不可用迭代器计算下标6.映射map构造map键类型值类型比较器 mp比较器默认less类型mapint,int mp1; mapint,int,greaterint mp2;遍历map一共三种遍历方式第一种用迭代器进行遍历for(mapint,int::iterator it mp.begin();it !it.end();it){ coutit-first it-secondendl; }第二种也是基于范围循环for(auto pr : mp){ coutpr.first pr.secondendl; }第三种是结构化绑定范围内的循环for(auto [key,val]){ coutkey valendl; }操作函数作用用法查找元素.find()删除元素.erase()增/改/查元素[]判断元素是否存在.count()在需要统计字符串出现次数时推荐使用7.字符串string#includestring构造string(长度初值)stl里的字符串不像C语言里面的那么麻烦可以直接输入输出还有很多很方便的函数可以进行操作操作函数作用用法修改、查询指定下标字符[]判断是否相同字符串连接尾接字符串取子串.substr(起始下标子串长度)查找字符串.find(字符串起始下标)数值与字符串互转(C11):源目的函数int/long long/float/double/long doublestringto_string()stringintstoi()stringlogn longstoll()stringfloatstof()stringdoublestod()stringlong doublestold()尾接字符串一定要用.find()的实现是暴力实现时间复杂度是8.二元组pair#includeutility构造pair第一个值类型第二个值类型 prpairint,char pr {1,a};判同直接用运算符二.迭代器1.为何需要迭代器很多数据结构并不是线性的例如红黑树对于非线性数据结构下标是无意义的。无法使用下标来遍历整个数据结构。迭代器的作用就是定义某个数据结构的遍历方式通过迭代器的增减代表遍历到的位置通过迭代器便能成功遍历非线性结构了。例如set 的实现是红黑树我们是没法用下标来访问元素的。但是通过迭代器我们就能遍历 set 中的元素了for(setint::iterator it st.begin();it ! st.end();it){ cout*itendl; } 2.迭代器用法对于 vector 容器它的迭代器功能比较完整以它举例.begin()头迭代器.end()尾迭代器.rbegin()反向头迭代器.rend()反向尾迭代器迭代器整型将迭代器向后移动迭代器-整型将迭代器向前移动迭代器将迭代器向后移动 1 位迭代器--将迭代器向前移动 1 位迭代器-迭代器两个迭代器的距离prev(it)返回 it 的前一个迭代器next(it)返回 it 的后一个迭代器对于其他容器由于其结构特性上面的功能不一定都有注意.end()和.rend()指向的值是无意义的除了遍历和访问非必要不要使用迭代器三.常用算法1.swap()作用交换两个变量的值用法示例int a 4,b 5; swap(a,b);2.sort()作用使用快速排序给一个可迭代对象排序默认排序从小到大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 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)] }3.lower_bound()/upper_bound():在升序的元素中应用二分查找检索指定元素返回对应元素迭代器位置找不到则返回尾迭代器lower_bound():寻找第一个该元素的位置upper_bound():寻找第一个.该元素的位置返回的是迭代器如何转成下标索引呢减去头迭代器即可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 44.reverse():作用反转一个可迭代对象的元素顺序用法示例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, 15.max/min():返回最大值/最小值的数值在 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}); // 16.unique():作用消除数组的重复相邻元素数组长度不变但是有效数据缩短返回的是有效数据位置的结尾迭代器7.gcd/lcm()作用(C17返回最大公因数 / 最小公倍数8.数学函数作用示例||abs(-1.0)exp(2)lnxlog(3)pow(2,3)sqrt(2)ceil(2.1)floor(2.1)round(2.1)四.结语这篇文章是为了备考算法竞赛而准备的里面基本上都比较常用也希望能够帮到有需要的人