C++的STL(Standard Template Library,标准模板库)从广义上讲分为algorithm(算法)、container(容器)和iterator(迭代器)三类,包含了诸多在计算机科学领域里面所常用的基本数据结构和基本算法。
在C++标准里面,STL被组织为下面的13个头文件:< algorithm >、< deque >、< functional >、< iterator >、< vector >、< list >、< map >、< memory >、< numeric >、< queue >、< set >、< stack >、< utility >。
vector 向量容器
vector 向量容器是一种简单高效的容器,在尾端插入和删除元素,算法时间为$O(1)$,其他元素插入和删除时间为$O(n)$。vector可动态调整所占用的内存空间。
用数组访问vector元素的参考代码如下:
1 |
|
用迭代器访问vector的参考代码如下:
1 |
|
结构体容器参考代码如下:
1 |
|
deque双端队列容器
deque与vector很相似,不仅可以在尾部插入和删除元素,还可以在头部插入和删除元素,时间复杂度为$O(1)$,考虑到容器元素的内存分配策略和操作性能时,deque比vector有优势。
由于使用了Map管理以及块为单位进行内存分配,所以不易实现capacity和reverse函数(也不需要这种函数)。
参考程序如下:
1 |
|
list双向链表容器
list双向链表中任一位置的元素查找、插入、和删除都具有高效的常熟阶算法时间复杂度$O(1)$。
常用方法参考程序如下:
1 |
|
链表归并的参考代码如下所示:
1 |
|
set集合容器
set集合容器使用一种红黑树的平均二叉检索树,不会将重复键值插入,检索效率高($\log n $)。检索使用二叉树的中序遍历,因此可以将元素从小到大排列出来。
红黑树的节点结构如下表格所示:
颜色 | 左指针 | 父指针 | 右指针 | 数据 |
---|---|---|---|---|
红黑树的建立是一个复杂的过程,一般方法是每次插入一个新节点(黑色根节点除外),都着色为红色,然后再检查红黑树定义是否被破坏,否则要进行子树的左右旋转以作平衡处理。
参考代码如下:
1 |
|
set_intersection()
C++ STL 提供求交集的函数 set_intersection( ) 、求集合差的函数 set_difference( ) 和合并两个集合的函数 set_union( ) 。以 set_intersection( ) 为例,分析两端程序并简单记录其用法:
nums1:1,2,2,1
nums2:2,21
2
3
4
5
6
7vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
set<int> cod1(nums1.begin(),nums1.end());
set<int> cod2(nums2.begin(),nums2.end());
std::set_intersection(cod1.begin(),cod1.end(),cod2.begin(),cod2.end(),insert_iterator<vector<int>>(res,res.begin()));
return res; // res:2
}
1 | vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { |
首先传递的容器必须是排序的,set 容器中元素默认是排序的,而 vector 需要调用 sort 函数进行排序。其次 set_intersection( )中最后存放交集的容器的容量必须要足够大到能放下所有的元素,即函数只执行复制,不是插入!但是模板 insert_iterator 可以将复制转换为插入,可以解决该问题。
set_intersection( ) 不是 set 的方法,而是一个通用函数,而 set 函数必须要满足这些算法!使用 set 时,可以自动忽略重复的元素,而使用 vector 时可以保留重复的元素,即保留了‘个数’这一信息。
该函数的时间复杂度为线性复杂度,其实现为:
1 | template <class InputIterator1, class InputIterator2, class OutputIterator> |
multiset多重集合容器
multiset多重集合容器可将重复元素插入
参考代码如下:
1 |
|
map映照容器
map映照容器的元素数据是一个键值和一个映照数据组成的,键值与映照数据之间具有一一映照的关系。
map映照容器的数据结构是采用红黑树来实现的,插入键值的元素不允许重复,比较函数只对元素的键值进行比较,元素的各项数据可通过键值检索出来。
简单的参考程序如下:
1 |
|
又一个使用map映照容器的参考代码:
1 |
|
双一个使用map映照容器的参考代码:
1 |
|
结构体示例程序如下:
1 |
|
pair是一个模板类,你可以理解成一个仅存储两个元素的结构体,第一个是first,第二个是seconditerator指向map成员,map的每一个成员都是一个pair,只是将它的first作为红黑树的排序key。一个map中没有相同的key的元素,即没有两个pair的first相同。
map与set的区别是:map是处理带有键值的记录型元素数据的快速插入、删除和检索,而set是对单一数据的处理,map不允许重复的元素键插入,map与set都是泛型库对二叉树的一个泛化。
multimap 多重映照容器
multimap多重映照容器与map映照容器基本相同,唯独不同的是,multimap允许重复键值的存在,所以,multimap的元素的插入、删除、查找都与map不相同。
参考代码如下:
1 |
|
stack堆栈容器
堆栈容器是一个线性表,插入和删除只在线性表的一端进行。一端称为栈顶 (Stack Top);另一端称为栈底(Stack Bottom)。堆栈的元素插入称为入栈,元素的删除称为出栈。由于元素的入栈和出栈总在栈顶进行,因此,堆栈是一个后进先出(Last In First Out)的线性表结构,即LIFO表。
C++的STL的stack堆栈容器不设置最大容量,提供入栈、出栈、栈顶元素访问和判断是否为空的基本操作。
参考程序如下:
1 |
|
queue队列容器
queue队列容器是一个线性存储表,与后进先出的堆栈不同,元素的插入在线性表的一端进行,删除在另一端进行。从而构成了一个先进先出(First In First Out)表。插入一段称为队尾,删除一端称为队首。
C++的STL的queue队列容器提供基本操作。
参考程序如下:
1 |
|
priority_queue优先队列容器
优先队列是一种容器适配器,它的第一个元素(位于头部top)总是队列中最大的元素,这里的“最大”是指队列元素的严格弱序中的“最大”。严格弱序是一系列数或事物按照一定的比较关系”<”排列得出的序列,“<”可以是数学中进行数值比较的大于,也可以是小鱼,还可以是其他含义。
priority_queue优先队列容器使用堆排序算法,每次将最大值或最小值出列。时间复杂度为$\long n $。
创建一个优先队列的格式为priority_quque
T:队列中元素的数据类型。
Container:用于存储和访问队列队列元素的底层容器的类型。
Compare:比较关系,默认是数值上的小于关系,比如 1<2 , 6<7 , 此时队列中元素从队头到队尾由大到小排列,采用默认compare时此参数可以省去。当需要采用其他标准进行比较时需要额外定义这一比较方式。当满足比较关系“<”时,返回true,否则返回false。
参考代码如下:
1 |
|
另一个参考代码如下:
1 |
|
STL到底是好还是不好?我个人偏向于赞成用STL,同样是在战场别人有飞机加大炮,你为何还要坚持小米加步枪?