从根本上说,STL是一些“容器”的集合,这些“容器”有list, vector,set,map等,STL也是算法和其它一些组件的集合。STL提供了类型安全、高效而易用特性的STL无疑是最值得C++程序员骄傲的部分。每一个C++程序员都应该好好学习STL。大体上包括container(容器)、algorithm(算法)和iterator(迭代器),容器和算法通过迭代器可以进行无缝连接。
学习STL需要泛型编程知识,包括多态,模板;C++语言基础;C++模板库的通用工具(个人认为数据结构中的链表,堆栈二叉树之类的也要懂点,最好学过数据结构,还有基本的算法)等。
STL有六大组件:
容器(Container)
算法(Algorithm)
迭代器(Iterator)----(你也可以理解为泛型指针)
仿函数(Function object)
适配器(Adaptor)
空间配置器(allocator)
作为STL的最主要组成部分--容器,分为向量(vector),双端队列(deque),表(list),队列(queue),堆栈(stack),集合(set),多重集合(multiset),映射(map),多重映射(multimap)。
向量vector:
可以用常数时间访问和修改任意元素,在序列尾部进行插入和删除时,具有常数时间复杂度,对任意项的插入和删除就有的时间复杂度与到末尾的距离成正比,尤其对向量头的添加和删除的代价是惊人的高的
头文件:<vector>
双端队列deque
基本上与向量相同,唯一的不同是,其在序列头部插入和删除操作也具有常量时间复杂度
头文件:<deque>
表list
对任意元素的访问与对两端的距离成正比,但对某个位置上插入和删除一个项的花费为常数时间。
头文件:<list>
队列queue
插入只可以在尾部进行,删除、检索和修改只允许从头部进行。按照先进先出的原则。
头文件:<queue>
堆栈stack
堆栈是项的有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则
头文件:<stack>
集合set
由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种作用于元素对的谓词排列,没有两个不同的元素能够拥有相同的次序,具有快速查找的功能。但是它是以牺牲插入删除操作的效率为代价的
头文件:<set>
多重集合multiset
和集合基本相同,但可以支持重复元素具有快速查找能力
头文件:<set>
映射map
由{键,值}对组成的集合,以某种作用于键对上的谓词排列。具有快速查找能力
<map>
多重集合multimap
比起映射,一个键可以对应多了值。具有快速查找能力
头文件:<map>
容器能力表:
对于set,map而言,两者的搜寻函数算法具有对数复杂度,当然与它以二叉树完成有关,而前面的三个就是普通的线性搜寻,进行遍历,速度自然慢。而且如果实在需要支持重复元素,不建议用multisets,我们直接map再套一个map。