迭代器（Iterators）：用来在一个对象集合的元素上进行遍历动作。扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种将operator* , operator-> , operator++, operator–-等指针相关操作予以重载的class template。所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。

仿函数(Function object)：行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了operator()的class 或者class template。在使用到c++ stl中算法的时候，很多情况下需要传入函数对象或函数指针，传递函数对象运行效率要比函数指针高。原因是算法函数中可以根据函数对象内联展开调用的函数，而当传入函数指针时，这种内联展开的技术不可能实现，因此存在大量函数调用的情况。c++11新特性中提供了lambda函数，lambda函数是一种匿名函数，使用lambda函数的效率与使用函数对象是一样的，他们都能够在编译期将代码内联展开，减少函数调用的时间。编译器实际上将lambda函数转化为一个函数对象，所以，它与使用函数对象是一样高效的。

适配器(Adaptor)：一种用来修饰容器或者仿函数或迭代器接口的东西。

空间配置器（Allocator）：负责空间的配置与管理。从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte。

STL 的基本观念就是将数据和操作分离。数据由容器进行管理，操作则由算法进行，而迭代器在两者之间充当粘合剂，使任何算法都可以和任何容器交互运作。通过迭代器的协助，我们只需撰写一次算法，就可以将它应用于任意容器之上，这是因为所有容器的迭代器都提供一致的接口。

STL六大组件的交互关系，容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同的策略的变化，适配器可以修饰仿函数。

容器类型

按内存分布的分类

连续内存容器

是基于数组的容器，元素存放在一块或多块内存中，每块内存中存有对个元素，当插入或删除时，同一个内存中的其他元素要向前或向后移动，这种移动影响效率和异常安全性。支持随机访问迭代器。

基于节点的容器

每一个动态分配的内存块中只存放一个元素。容器中插入或删除值影响到指向节点的指针，而不影响节点本身的内容。链表和红黑树支持双向访问迭代器。哈希表只支持前向迭代器。

按元素在容器中的排列特性分类

序列式容器

序列式容器实现能按顺序访问的数据结构，不是数值顺序。其中每个元素均有固定位置—取决于插入时机和地点，和元素值无关。如果你以追加方式对一个群集插入六个元素，它们的排列次序将和插入次序一致。STL提供了以下几种序列式容器：

array(C++11)	静态的连续数组(类模板)
vector	动态的连续数组(类模板)
deque	双端队列(类模板)
forward_list(C++11 起)	单链表(类模板)
list	双链表(类模板)

关联式容器

每个元素位置取决于特定的排序准则以及元素值，和插入次序无关。关联容器基于【红黑树】。实现能快速查找（ O(log n) 复杂度）的数据结构。

set	唯一键的集合，按照键排序(类模板)
map	键值对的集合，按照键排序，键是唯一的(类模板)
multiset	键的集合，按照键排序(类模板)
multimap	键值对的集合，按照键排序(类模板)

无序关联容器

每个元素位置取决于特定的排序准则以及元素值，和插入次序无关。无序关联容器基于【哈希表】。无序关联容器提供能快速查找（均摊 O(1) ，最坏情况 O(n) 的复杂度）的无序（哈希）数据结构。

unordered_set(C++11 起)	唯一键的集合，按照键生成散列(类模板)
unordered_map(C++11 起)	键值对的集合，按照键生成散列，键是唯一的(类模板)
unordered_multiset(C++11 起)	键的集合，按照键生成散列(类模板)
unordered_multimap(C++11 起)	键值对的集合，按照键生成散列(类模板)

容器适配器

容器适配器提供顺序容器的不同接口。

stack	适配一个容器以提供栈（LIFO 数据结构）(类模板)
queue	适配一个容器以提供队列（FIFO 数据结构）(类模板)
priority_queue	适配一个容器以提供优先级队列(类模板)

以上是对stl的简单介绍，在后续的文章中在列出使用中的问题。

凡是过往，即为序章

码农公寓

引言

STL有六大组件