本文共 2160 字,大约阅读时间需要 7 分钟。
STL的基本观念就是将数据和操作分离。数据由容器类别加以管理,操作则由可定制的算法加以定义。迭代器在两者之间充当粘合剂,使任何算法都可以喝任何容器交换操作。STL将数据和算法分开对待,而不是合并考虑。因此从某种意义上说,STL的概念和面向对象设计的最初思想是矛盾的。然而这么做有很重要的原因。首先,你可以将各种容器与各种算法结合起来,在很小的框架内拥有非常大的弹性。
STL提供六大组件,彼此可以组合套用:
1、 容器(Containers):各种数据结构,如:vector、list、deque、set、map。用来存放数据。从实现的角度来看,STL容器是一种class template。
2、 算法(algorithms):各种常用算法,如:sort、search、copy、erase。从实现的角度来看,STL算法是一种 function template。
3、 迭代器(iterators):容器与算法之间的胶合剂,是所谓的“泛型指针”。共有五种类型,以及其他衍生变化。从实现的角度来看,迭代器是一种将 operator*、operator->、operator++、operator- - 等指针相关操作进行重载的class template。所有STL容器都有自己专属的迭代器,只有容器本身才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。
4、 仿函数(functors):行为类似函数,可作为算法的某种策略(policy)。从实现的角度来看,仿函数是一种重载了operator()的class或class template。一般的函数指针也可视为狭义的仿函数。
5、 配接器(adapters);一种用来修饰容器、仿函数、迭代器接口的东西。例如:STL提供的queue 和 stack,虽然看似容器,但其实只能算是一种容器配接器,因为它们的底部完全借助deque,所有操作都由底层的deque供应。改变functors接口者,称为function adapter;改变 container 接口者,称为container adapter;改变iterator接口者,称为iterator adapter。
6、 配置器(allocators):负责空间配置与管理。从实现的角度来看,配置器是一个实现了动态空间配置、空间管理、空间释放的class template。
这六大组件的交互关系:container(容器) 通过 allocator(配置器) 取得数据储存空间,algorithm(算法)通过iterator(迭代器)存取 container(容器) 内容,functor(仿函数) 可以协助 algorithm(算法) 完成不同的策略变化,adapter(配接器) 可以修饰或套接 functor(仿函数)。
附:
容器 | 特性 | 所在头文件 |
向量vector | 可以用常数时间访问和修改任意元素,在序列尾部进行插入和删除时,具有常数时间复杂度,对任意项的插入和删除就有的时间复杂度与到末尾的距离成正比,尤其对向量头的添加和删除的代价是惊人的高的 | <vector> |
双端队列deque | 基本上与向量相同,唯一的不同是,其在序列头部插入和删除操作也具有常量时间复杂度 | <deque> |
表list | 对任意元素的访问与对两端的距离成正比,但对某个位置上插入和删除一个项的花费为常数时间。 | <list> |
队列queue | 插入只可以在尾部进行,删除、检索和修改只允许从头部进行。按照先进先出的原则。 | <queue> |
堆栈stack | 堆栈是项的有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则 | <stack> |
集合set | 由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种作用于元素对的谓词排列,没有两个不同的元素能够拥有相同的次序,具有快速查找的功能。但是它是以牺牲插入删除操作的效率为代价的 | <set> |
多重集合multiset | 和集合基本相同,但可以支持重复元素具有快速查找能力 | <set> |
映射map | 由{键,值}对组成的集合,以某种作用于键对上的谓词排列。具有快速查找能力 | <map> |
多重集合multimap | 比起映射,一个键可以对应多了值。具有快速查找能力 | <map> |
STL容器能力表:
迭代器功能 | ||
输入迭代器 Input iterator | 向前读 Reads forward | istream |
输出迭代器 Output iterator | 向前写 Writes forward | ostream,inserter |
前向迭代器 Forward iterator | 向前读写 Read and Writes forward | |
双向迭代器 Bidirectional iterator | 向前向后读写 Read and Writes forward and backward | list,set,multiset,map,mul timap |
随机迭代器 Random access iterator | 随机读写 Read and Write with random access | vector,deque,array,string |