本文涉及到 SGI STL 源码的文件有 iterator.h
, stl_iterator_base.h
, concept_checks.h
, stl_iterator.h
, type_traits.h
, stl_construct.h
, stl_raw_storage_iter.h
等7个文件。
1. 迭代器的设计思维
迭代器(iterators)是一种抽象的设计概念,显示程序中并没有直接对应于这个概念的实体。在 Design Patterns 一书中,对 iterators 模式的定义如下:提供一种方法,使之能够依序遍历某个聚合物(容器)所包含的各个元素,而又无需暴露该聚合物内部的表述方式。
在STL中迭代器扮演着重要的角色。STL的中心思想在于:将数据容器(container)和算法(algorithm)分开,彼此独立设计,最后再通过某种方式将他们衔接在一起。容器和算法的泛型化,从技术的角度来看并不困难,C++ 的 class template 和 function template 可以分别达到目标,难点在于如何设计二者之间的衔接器。
在STL中,起者这种衔接作用的是迭代器,它是一种行为类似指针的对象。指针的各种行为中最常见也最重要的便是内容获取(dereference)和成员访问(member access),因此迭代器最重要的工作就是对 operator*
和 operator->
进行重载。然而要对这两个操作符进行重载,就需要对容器内部的对象的数据类型和存储结构有所了解,于是在 STL 中迭代器的最终实现都是由容器本身来实现的,每种容器都有自己的迭代器实现,例如我们使用vector容器的迭代器的时候是这样用的 vector<int>::iterator it;
。而本文所讨论的迭代器是不依存于特定容器的迭代器,它在STL中主要有以下两个方面的作用(我自己的理解和总结):
- 规定容器中需要实现的迭代器的类型及每种迭代器的标准接口
- 通过Traits编程技巧实现迭代器相应型别的获取,弥补 C++ 模板参数推导的不足,为配置器提供可以获取容器中对象型别的接口
其中前一个没啥好解释的。关于第二个,后面第3节会详细介绍,那就是Traits编程技巧。