「STL详解」STL概述和迭代器

什么是STL标准模版库/h2>

在我们学习 STL 之前首先了解什么是标准模版库（STL）。

STL（Standard Template Library），即标准模板库，是一个高效的C++程序库，包含了常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming）。在这种思想里，大部分基本算法被抽象，被泛化，独立于与之对应的数据结构，用于以相同或相近的方式处理各种不同情形。从实现层次看，整个STL是以一种类型参数化（type parameterized）的方式实现的：基于模板(template)。

STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器）。

STL六大组件

1. 容器（Containers）：各种数据结构，如 Vector, List, Deque, Set, Map，用来存放数据，STL容器是一种Class Template,就体积而言，这一部分很像冰山载海面的比率。
2. 算法（Algorithms）：各种常用算法如 Sort, Search, Copy, Erase，从实现的角度来看，STL算法是一种Function Templates。
3. 迭代器（Iterators）：扮演容器与算法之间的胶合剂，是所谓的“泛型指针”，共有五种类型，以及其它衍生变化，从实现的角度来看，迭代器是一种将：Operators*,Operator->,Operator++,Operator–等相关操作予以重载的Class Template。所有STL容器都附带有自己专属的迭代器——是的，只有容器设计者才知道如何遍历自己的元素，原生指针（Native pointer）也是一种迭代器。
4. 仿函数（Functors）： 即函数对象，行为类似函数，可作为算法的某种策略（Policy）,从实现的角度来看，仿函数是一种重载了 Operator() 的 Class 或 Class Template。一般函数指针可视为狭义的仿函数。
5. 配接器（适配器）（Adapters）：一种用来修饰容器（Containers）或仿函数（Functors）或迭代器（Iterators）接口的东西，例如：STL提供的 Queue 和 Stack，虽然看似容器，其实只能算是一种容器配接器，因为它们的底部完全借助 Deque，所有操作有底层的 Deque 供应。改变 Functor 接口者，称为 Function Adapter；改变 Container 接口者，称为Container Adapter；改变 Iterator 接口者，称为 Iterator Adapter。配接器的实现技术很难一言蔽之，必须逐一分析。
6. 分配器（Allocators）：即空间配置器，负责空间配置与管理，从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的 Class Template。

迭代器（iterator）

迭代器基本概念

迭代器（iterator）是一种对象，它能够用来遍历标准模板库容器中的部分或全部元素，每个迭代器对象代表容器中的确定的地址。它提供了一种能够寻访容器元素的方法，能够将容器和算法粘合在一起。例如算法 find() 中使用了两个迭代器和一个搜索值：

只要给出不同的迭代器，find() 就能在不同容器中进行查找操作：

注意：end并不指向容器的任何元素，而是指向容器的最后元素的下一位置，称为超出末端迭代器。如果 vector 为空，则 begin 返回的迭代器和 end 返回的迭代器相同。一旦向上面这样定义和初始化，就相当于把该迭代器和容器进行了某种关联，就像把一个指针初始化为指向某一空间地址一样。

迭代器是一种 smart pointer

迭代器是一种类似于指针的对象，其最重要的编程工作就是 reference 和 member access，即对 和 进行重载。

既然说迭代器是一种smart pointer，我们就来看看 是怎么实现的。下面是 的一种用法：

可以不使用 对内存手动释放，因为 会自动释放内存。 的源码在头文件 中，下面是一份精简版代码，用来说明 的行为和能力：

根据 的实现方法，我们可以设计一个 list 容器的迭代器。当我们 reference 这个迭代器时，应该返回一个 LIstItem 对象；当我们递增该迭代器时，它应该指向下一个 ListItem 对象。

iterator class

为了保证迭代器能与其他 STL 组件顺利搭配，STL 提供了一个 iterator class，每个新设计的迭代器都继承自 iterator class。

iterator class 不含任何成员，只有类型定义，所以继承时没有任何负担。后面三个参数有默认值，所以设计新的迭代器只需要提供两个参数。