STL

时间：2020-02-03 21:27:12 阅读：70 评论：0 收藏：0 [点我收藏+]

$STL$

容器：可容纳各种数据类型的通用数据结构，是类模板

可以用于存放各种类型的数据(基本类型的变量，对象等)的数据结构，都是类模版,分为三种:

? 1，顺序容器容器并非排序的，元素插入的位置同元素的值无关,

$vector,deque$ 元素在内存连续存放.随机存取任何元素都能在常数时间完成($deque$劣于$vector$)。在尾端增删元素具有较佳的性能(大部分情况下是常数时间).

$list$ 双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。

? 2.关联容器：元素是排序的，插入任何元素，都按相应的排序规则来确定其位置，在查找时具有很好性能,通常以平衡二叉树方式实现，插入和检索的时间都是 $O(log(N))$

$set$(不重集）,$multiset$（可重集）,$map,multimap,unordered\_set,unordered\_map(O(1)查询O(1)插入O(1)删除?$

? 3.容器适配器 $stack,queue,priority\_queue$

顺序容器和关联容器中都有的成员函数

$begin$ 返回指向容器中第一个元素的迭代器

$end$ 返回指向容器中最后一个元素后面的位置的迭代器

$rbegin$ 返回指向容器中最后一个元素的迭代器

$rend$ 返回指向容器中第一个元素前面的位置的迭代器

$erase$ 从容器中删除一个或几个元素

$clear$ 从容器中删除所有元素释放所有内存：$s=set<int>()$

顺序容器的常用成员函数

$front $:返回容器中第一个元素的引用

$back$ : 返回容器中最后一个元素的引用

$push\_back$ : 在容器末尾增加新元素

$pop\_back$ : 删除容器末尾的元素

$erase$ :删除迭代器指向的元素(可能会使该迭代器失效)，或删除一个区间，返回被删除元素后面的那个元素的迭代器

迭代器：可用于依次存取容器中元素，类似于指针;用于指向顺序容器和关联容器中的元素

非$const$迭代器：可修改，$const$迭代器：只能访问，不可修改

定义一个容器类的迭代器的方法可以是:

容器类名$::iterator$ 变量名;

或:

容器类名$::const_iterator $变量名;

例如：$set<int>::iterator\ it;$

访问一个迭代器指向的元素:

*迭代器变量名

例如$*it$

迭代器上可以执行 $++$ 操作, 以使其指向容器中的下一个元素。
如果迭代器到达了容器中的最后一个元素的后面，此时再使用它，就会出错，类似于使用$NULL$或未初始化的指针一样。

双向迭代器 $set/,map/$

若$p$和$p1$都是双向迭代器，则可对$p、p1$可进行以下操作:

$++p, p++ $使$p$指向容器中下一个元素

$--p, p-- $使$p$指向容器中上一个元素

$*p$ 取$p$指向的元素

$p=p1 $赋值

$p == p1 , p!= p1 $判断是否相等、不等

随机访问迭代器：$vector,deque,list$

若$p$和$p1$都是随机访问迭代器，则可对$p、p1$可进行以下操作:

双向迭代器的所有操作

$p += i $将$p$向后移动$i$个元素

$p -= i $将$p$向前移动$i$个元素

$p + i $值为: 指向$ p $后面的第$i$个元素的迭代器

$p - i $值为: 指向$ p$ 前面的第$i$个元素的迭代器 $ p[i]$ 值为: $p$后面的第$i$个元素的引用

$p < p1, p <= p1, p > p1, p>= p1$

$p – p1 : p1$和$p$之间的元素个数