2023年7月30日发(作者：)

史上最全的各种C++STL容器全解析史上最全的C++ STL 容器⼤礼包为什么C++⽐C更受⼈欢迎呢？除了C++ 的编译令⼈感到更舒适，C++的标准模板库（STL）也占了很重要的原因。当你还在⽤⼿⼿写快排、⼿写⼆叉堆，挑了半天挑不出⽑病的时候，C++党⼀⼿STL轻松AC，想不嫉妒都难。所以这篇随笔就带⼤家⾛进博⼤精深的C++STL，系统讲解各种STL容器及其⽤法、作⽤。在学习STL的时候认真体会STL语法及功能，提升⾃⼰在算法竞赛及程序设计中解题、码代码的能⼒。话不多说，现在开始：浅谈C++ STL vector 容器本篇随笔简单介绍⼀下C++STL中vector容器的使⽤⽅法和常见的使⽤技巧。vector容器是C++STL的⼀种⽐较基本的容器。我们在学习这个容器的时候，不仅要学到这个容器具体的使⽤⽅法，更要从中体会C++STL的概念。vector容器的概念vector在英⽂中是⽮量的意思。如果学过⾼中数学必修四的平⾯向量或者⾼中物理必修⼀的第⼀节课对其会有⼀个直观的认识。但是在STL中，vector和物理、⼏何等东西没有任何关系。我们知道，⼀个数组必须要有固定的长度，在开⼀个数组的时候，这个长度也就被静态地确定下来了。但是vector却是数组的“加强版”，对于⼀组数据来讲，你往vector⾥存多少数据，vector的长度就有多⼤。也就是说，我们可以将其理解为⼀个“变长数组”。事实上，vector的实现⽅式是基于倍增思想的：假如vector的实际长度为n，m为vector当前的最⼤长度，那么在加⼊⼀个元素的时候，先看⼀下，假如当前的n=m，则再动态申请⼀个2m⼤⼩的内存。反之，在删除的时候，如果ngefrac{m}{2}，则再释放⼀半的内存。vector容器的声明vector容器存放在模板库：#include⾥，使⽤前需要先开这个库。vector容器的声明遵循C++STL的⼀般声明原则：容器类型<变量类型> 名称例：#includevector vec;vector vec;vector > vec;vector vec;struct node{...};vector容器的使⽤⽅法vector容器的使⽤⽅法⼤致如下表所⽰：⽤法(),()作⽤返回vector的⾸、尾迭代器从vector末尾加⼊⼀个元素返回vector当前的长度（⼤⼩）从vector末尾删除⼀个元素返回vector是否为空，1为空、0不为空清空(),()返回vector的⾸、尾元素_back()()_back()()()除了上⾯说过的那些之外，我们的vector容器是⽀持随机访问的，即可以像数组⼀样⽤[,,]来取值。请记住，不是所有的STL容器都有这个性质！在STL的学习过程中，⼀定要清楚各个容器之间的异同！浅谈C++ STL queue 容器本篇随笔简单介绍⼀下C++STL中queue容器的使⽤⽅法和常见的使⽤技巧。queue容器是C++STL的⼀种⽐较基本的容器。我们在学习这个容器的时候，不仅要学到这个容器具体的使⽤⽅法，更要从中体会C++STL的概念。queue容器的概念queue在英⽂中是队列的意思。队列是⼀种基本的数据结构。⽽C++STL中的队列就是把这种数据结构模板化了。我们可以在脑中想象买票时⼈们站的排队队列。我们发现，在⼀个队列中，只可以从队⾸离开，从队尾进来（没有插队，想啥呢）。即⼀个先进先出的数据结构。上图理解：queue容器的声明queue容器存放在模板库：#include⾥，使⽤前需要先开这个库。queue容器的声明遵循C++STL的⼀般声明原则：容器类型<变量类型> 名称例：#includequeue q;queue q;queue > q;queue q;struct node{...};queue容器的使⽤⽅法queue容器的使⽤⽅法⼤致如下表所⽰：⽤法()()()()作⽤从queue末尾加⼊⼀个元素返回queue当前的长度（⼤⼩）从queue末尾删除⼀个元素返回queue是否为空，1为空、0不为空(),()返回queue的⾸、尾元素注意，虽然vector和queue是两种最基本的STL容器，但请记住它们两个不是完全⼀样的。就从使⽤⽅法来讲：queue不⽀持随机访问，即不能像数组⼀样地任意取值。并且，queue并不⽀持全部的vector的内置函数。⽐如queue不可以⽤clear()函数清空，清空queue必须⼀个⼀个弹出。同样，queue也并不⽀持遍历，⽆论是数组型遍历还是迭代器型遍历统统不⽀持，所以没有begin(),end();函数，使⽤的时候⼀定要清楚异同！浅谈C++ STL stack 容器本篇随笔简单介绍⼀下C++STL中stack容器的使⽤⽅法和常见的使⽤技巧。stack容器的概念stack在英⽂中是栈的意思。栈是⼀种基本的数据结构。⽽C++STL中的栈就是把这种数据结构模板化了。栈的⽰意图如下：这是⼀个先进后出的数据结构。这⾮常重要！！事实上，stack容器并不是⼀种标准的数据结构，它其实是⼀个容器适配器，⾥⾯还可以存其他的STL容器。但那种使⽤⽅法过于⾼深⽽且不是很常⽤，所以在此不与介绍。请有兴趣的读者⾃⾏查询资料。stack容器的声明stack容器存放在模板库：#include⾥，使⽤前需要先开这个库。stack容器的声明遵循C++STL的⼀般声明原则：容器类型<变量类型> 名称例：#includestack st;stack st;stack > st;stack st;struct node{...};stack容器的使⽤⽅法stack容器的使⽤⽅法⼤致如下表所⽰：⽤法()()()()作⽤返回stack的栈顶元素从stack栈顶加⼊⼀个元素返回stack当前的长度（⼤⼩）从stack栈顶弹出⼀个元素()返回stack是否为空，1为空、0不为空浅谈C++ STL string容器本篇随笔简单讲解⼀下C++STL中string容器的使⽤⽅法及技巧。string容器的概念其实string并不是STL的⼀种容器，但是由于它的使⽤⽅法等等和STL容器很像，所以就把它当作STL容器⼀样介绍。其实string容器就是个字符串，这通过它的英⽂译名就能看得出来。但是对于字符串以及字符串的相关操作，可能读者还是对普通的C/C++的#include，#include库更熟悉⼀些。我丝毫不否认这些传统字符操作的经典性和实⽤性，但是由于它们函数定义的局限，有些时候对于⼀些特殊的读⼊、输出、遍历等要求，它的操作并不如string容器好⽤。⽐如，要求读⼊⼀群中间可能带空格的字符串，如果⽤传统⽅式进⾏读⼊，可能就会很⿇烦，但是如果使⽤string的话，⼀个读⼊函数就可以完全搞定。string容器的使⽤⽅法及与传统字符读⼊的对⽐⼀张图解决问题。详解C++ STL priority_queue 容器本篇随笔简单介绍⼀下C++STL中priority_queue容器的使⽤⽅法和常见的使⽤技巧。priority_queue容器的概念priority_queue在英⽂中是优先队列的意思。队列是⼀种基本的数据结构。其实现的基本⽰意图如下所⽰：⽽C++STL中的优先队列就是在这个队列的基础上，把其中的元素加以排序。其内部实现是⼀个⼆叉堆。所以优先队列其实就是把堆模板化，将所有⼊队的元素排成具有单调性的⼀队，⽅便我们调⽤。priority_queue容器的声明priority_queue容器存放在模板库：#include⾥，使⽤前需要先开这个库。这⾥需要注意的是，优先队列的声明与⼀般STL模板的声明⽅式并不⼀样。事实上，我认为其是C++STL中最难声明的⼀个容器。⼤根堆声明⽅式：⼤根堆就是把⼤的元素放在堆顶的堆。优先队列默认实现的就是⼤根堆，所以⼤根堆的声明不需要任何花花肠⼦，直接按C++STL的声明规则声明即可。#includepriority_queue q;priority_queue q;priority_queue > q;C++中的int,string等类型可以直接⽐较⼤⼩，所以不⽤我们多操⼼，优先队列⾃然会帮我们实现。但是如果是我们⾃⼰定义的结构体，就需要进⾏重载运算符了。关于重载运算符的讲解，请参考这篇博客：⼩根堆声明⽅式⼤根堆是把⼤的元素放堆顶，⼩根堆就是把⼩的元素放到堆顶。实现⼩根堆有两种⽅式：第⼀种是⽐较巧妙的，因为优先队列默认实现的是⼤根堆，所以我们可以把元素取反放进去，因为负数的绝对值越⼩越⼤，那么绝对值较⼩的元素就会被放在前⾯，我们在取出的时候再取个反，就瞒天过海地⽤⼤根堆实现了⼩根堆。第⼆种：⼩根堆有⾃⼰的声明⽅式，我们记住即可（我也说不明⽩道理）：priority_queue,greater >q;注意，当我们声明的时候碰到两个"<"或者">"放在⼀起的时候，⼀定要记得在中间加⼀个空格。这样编译器才不会把两个连在⼀起的符号判断成位运算的左移/右移。priority_queue容器的使⽤⽅法priority_queue容器的使⽤⽅法⼤致如下表所⽰：⽤法()()()()作⽤返回priority_queue的⾸元素向priority_queue中加⼊⼀个元素返回priority_queue当前的长度（⼤⼩）从priority_queue末尾删除⼀个元素()返回priority_queue是否为空，1为空、0不为空注意：priority_queue取出队⾸元素是使⽤top，⽽不是front，这点⼀定要注意！！浅谈C++ STL deque 容器本篇随笔简单介绍⼀下C++STL中deque容器的使⽤⽅法及常见使⽤技巧。deque容器的概念deque的意义是：双端队列。队列是我们常⽤⽽且必须需要掌握的数据结构。C++STL中的确有模拟队列的模板：#include中的queue和priority_queue。队列的性质是先进先出，即从队尾⼊队，从队⾸出队。⽽deque的特点则是双端进出，即处于双端队列中的元素既可以从队⾸进/出队，也可以从队尾进/出队。即：deque是⼀个⽀持在两端⾼效插⼊、删除元素的线性容器。deque模板存储在C++STL的#include中。deque容器的使⽤⽅法因为deque容器真的和queue容器⼤体相同，其使⽤⽅式也⼤体⼀致。下⾯把deque容器的使⽤⽅式以列表的⽅式放在下⾯：⽤法(),()作⽤返回deque的⾸、尾迭代器从队尾⼊队⼀个元素从队头⼊队⼀个元素从队尾出队⼀个元素从队头出队⼀个元素清空队列(),()返回deque的⾸、尾元素_back()_front()_back()_front()()除了这些⽤法之外，deque⽐queue更优秀的⼀个性质是它⽀持随机访问，即可以像数组下标⼀样取出其中的⼀个元素。即：q[i]。deque的⼀些⽤途由于本蒟蒻⽔平有限，暂时想不出deque应⽤的⼀些实例。但有⼀点是肯定的：deque容器可以被应⽤到SPFA算法的SLF优化。其具体应⽤⽅式可见这篇博客：详解C++ STL set 容器本篇随笔简单介绍⼀下C++STL中set容器的使⽤⽅法及常见使⽤技巧。set容器的概念和性质set在英⽂中的意义是：集合。set容器也的确“⼈如其名”，实现了这个集合的功⽤。⾼中数学必修⼀集合那章（⾼⼀以下的⼩伙伴不⽤慌，不讲数学只讲概念），关于集合的性质，给出了三个概念：⽆序性、互异性、确定性。那么，set容器的功⽤就是维护⼀个集合，其中的元素满⾜互异性。我们可以将其理解为⼀个数组。这个数组的元素是两两不同的。这个两两不同是指，如果这个set容器中已经包含了⼀个元素i，那么⽆论我们后续再往⾥假如多少个i，这个set中还是只有⼀个元素i，⽽不会出现⼀堆i的情况。这就为我们提供了很多⽅便。但是，需要额外说明的是，刚刚说集合是有⽆序性的，但是set中的元素是默认排好序（按升序排列）的。（稍微说⼀句，set容器⾃动有序和快速添加、删除的性质是由其内部实现：红⿊树（平衡树的⼀种）。这个东西过于⾼深我不会，所以不予过多介绍，有兴趣的⼩伙伴可以⾃⾏浏览相关内容。）set容器的声明set容器的声明和⼤部分C++STL容器⼀样，都是：容器名<变量类型> 名称的结构。前提需要开#include库。如：#includeset s;set s;set > s;set s;struct node{...};set容器的使⽤其实，C++STL容器的使⽤⽅式都是差不多的。我们完全可以举⼀反三地去类⽐。与bitset重定义了许多奇形怪状新的函数之外，其他都是⼤致相同的。所以笔者在此不再做幼稚的介绍，⼤家都是竞赛狗，应该都能⾃⼰看明⽩。();empty()函数返回当前集合是否为空，是返回1，否则返回();size()函数返回当前集合的元素个数。();clear()函数清空当前集合。(),();begin()函数和end()函数返回集合的⾸尾迭代器。注意是迭代器。我们可以把迭代器理解为数组的下标。但其实迭代器是⼀种指针。这⾥需要注意的是，由于计算机区间“前闭后开”的结构，begin()函数返回的指针指向的的确是集合的第⼀个元素。但end()返回的指针却指向了集合最后⼀个元素后⾯⼀个元素。(k);insert(k)函数表⽰向集合中加⼊元素k。(k);erase(k)函数表⽰删除集合中元素k。这也反映了set容器的强⼤之处，指哪打哪，说删谁就删谁，完全省略了遍历、查找、复制、还原等繁琐操作。更不⽤像链表那种数据结构那么毒瘤。直接⼀个函数，⽤O(logn)的复杂度解决问题。(k);find(k)函数返回集合中指向元素k的迭代器。如果不存在这个元素，就返回()，这个性质可以⽤来判断集合中有没有这个元素。其他好⽤的函数下⾯介绍⼀些不是很常⽤，但是很好⽤的set容器的内置函数_bound(),_bound();熟悉algorithm库和⼆分、离散化的⼩伙伴会对这两个函数⽐较熟悉。其实这两个函数⽐较常⽤。但是对于set集合来讲就不是很常⽤。其中lower_bound返回集合中第⼀个⼤于等于关键字的元素。upper_bound返回集合中第⼀个严格⼤于关键字的元素。_range();这个东西是真的不常⽤...可能是我太菜了。这个东西返回⼀个pair（内置⼆元组），分别表⽰第⼀个⼤于等于关键字的元素，第⼀个严格⼤于关键字的元素，也就是把前⾯的两个函数和在⼀起。如果有⼀个元素找不到的话，就会返回()。详解C++ STL multiset 容器本篇随笔简单介绍⼀下C++STL中multiset容器的使⽤⽅法及常见使⽤技巧。multiset容器的概念和性质set在英⽂中的意义是：集合。⽽multi-前缀则表⽰：多重的。所以multiset容器就叫做：有序多重集合。multiset的很多性质和使⽤⽅式和set容器差不了多少。⽽multiset容器在概念上与set容器不同的地⽅就是：set的元素互不相同，⽽multiset的元素可以允许相同。所以，关于⼀些multiset容器和set容器的相同点，本篇博客就不加以赘述了。需要学习的⼩伙伴推荐进⼊本蒟蒻的这篇博客：与set容器不太⼀样的地⽅：(k);erase(k)函数在set容器中表⽰删除集合中元素k。但在multiset容器中表⽰删除所有等于k的元素。时间复杂度变成了O(tot+logn)，其中tot表⽰要删除的元素的个数。那么，会存在⼀种情况，我只想删除这些元素中的⼀个元素，怎么办呢？可以妙⽤⼀下：if((it=(a))!=()) (it);if中的条件语句表⽰定义了⼀个指向⼀个a元素迭代器，如果这个迭代器不等于()，就说明这个元素的确存在，就可以直接删除这个迭代器指向的元素了。(k);count(k)函数返回集合中元素k的个数。set容器中并不存在这种操作。这是multiset独有的。C++ STL bitset 容器详解本篇随笔讲解C++STL中bitset容器的⽤法及常见使⽤技巧。bitset容器概论bitset容器其实就是个01串。可以被看作是⼀个bool数组。它⽐bool数组更优秀的优点是：节约空间，节约时间，⽀持基本的位运算。在bitset容器中，8位占⼀个字节，相⽐于bool数组4位⼀个字节的空间利⽤率要⾼很多。同时，n位的bitset在执⾏⼀次位运算的复杂度可以被看作是n/32，这都是bool数组所没有的优秀性质。bitset容器包含在C++⾃带的bitset库中。#includebitset容器的声明因为bitset容器就是装01串的，所以不⽤在< >中装数据类型，这和⼀般的STL容器不太⼀样。< >中装01串的位数。如：（声明⼀个10^5位的bitset）bitset<100000> s;对bitset容器的⼀些操作1、常⽤的操作函数和其他的STL容器⼀样，对bitset的很多操作也是由⾃带函数来实现的。下⾯，我们来介绍⼀下bitset的⼀些常⽤函数及其使⽤⽅法。count()函数count，数数的意思。它的作⽤是数出1的个数。即()返回s中有多少个();any()/none()函数any，任何的意思。none，啥也没有的意思。这两个函数是在检查bitset容器中全0的情况。如果，bitset中全都为0，那么()返回false，()返回true。反之，假如bitset中⾄少有⼀个1，即哪怕有⼀个1，那么()返回true，()返回();();set()函数set()函数的作⽤是把bitset全部置为1.特别地，set()函数⾥⾯可以传参数。set(u,v)的意思是把bitset中的第u位变成v,vin 0/1。();(u,v);reset()函数与set()函数相对地，reset()函数将bitset的所有位置为0。⽽reset()函数只传⼀个参数，表⽰把这⼀位改成0。();(k);flip()函数flip()函数与前两个函数不同，它的作⽤是将整个bitset容器按位取反。同上，其传进的参数表⽰把其中⼀位取反。();(k);2、位运算操作在bitset中的实现bitset的作⽤就是帮助我们⽅便地实现位运算的相关操作。它当然⽀持位运算的⼀些操作内容。我们在编写程序的时候对数进⾏的⼆进制运算均可以⽤在bitset函数上。⽐如：~：按位取反&：按位与|：按位或^：按位异或<< >>：左/右移==/！=：⽐较两个bitset是否相等。关于位运算的相关知识，不懂的⼩伙伴请戳这⾥：另外，bitset容器还⽀持直接取值和直接赋值的操作：具体操作⽅式如下：s[3]=1;s[5]=0;这⾥要注意：在bitset容器中，最低位为0。这与我们的数组实现仍然有区别。bitset容器的实际应⽤bitset可以⾼效率地对01串，01矩阵等等只含0/1的题⽬进⾏处理。其中⽀持的许多操作对我们处理数据⾮常有帮助。如果碰到⼀道0/1题，使⽤bitset或许是不错的选择。详解C++ STL map 容器本篇随笔简单讲解⼀下C++STL中的map容器的使⽤⽅法和使⽤技巧。map容器的概念map的英语释义是“地图”，但map容器可和地图没什么关系。map是“映射容器”，其存储的两个变量构成了⼀个键值到元素的映射关系。⽐如下图：我们可以根据键值快速地找到这个映射出的数据。map容器的内部实现是⼀棵红⿊树（平衡树的⼀种），因为⽐较复杂⽽且与理解并⽆多⼤关系，所以不予介绍，有兴趣的读者可以⾃⼰查阅相关的资料。map容器的声明map容器存在于STL模板库#include