《STL源码剖析》读书笔记
迭代器的设计
1. 迭代器iterator
模式在《Design Patterns》中是这么定义的:
提供一直方法,使之能够依序巡防某个聚合物所含的各个元素,而又无线暴露该聚合物的
内部表述方式。
2. 获取迭代器所指对象的型别
template <class I, class T>
void func_impl(I iter, T t)
{
T tmp;
}
template <class I>
inline
void func(I iter) {
func_impl(iter, *iter)
}
int main() {
int i;
func(&i);
}
这里利用function template
的参数推导机制获取迭代器的相应型别。
3. Traits 技巧
由于function template
推导的是模板参数,无法推导函数的返回值型别、
所以用 声明内嵌型别的方式
template <class T>
struct MyIter {
typedef T value_type;
T* ptr;
MyIter(T* p = 0) : ptr(p) {}
T& operator*() const { return *ptr; }
}
template <class I>
tpyename I::value_type
func(I ite) {
return *ite;
}
MyIter<int> ite(new int(8));
cout << func(ite); // print: 8
又由于内嵌型别只能用于class type
,对于原生指针又无法支持。所以需要用到
template partial specialization
模板偏特化来对原生指针做支持
利用了偏特化的方式我们提取迭代器value type
就可以这么写:
template <class I>
struct iterator_traits {
typedef typename I::value_type value_type;
}
template <class T>
struct iterator_traits<T*> { //偏特化版本,迭代器是原生指针
typedef T value_type;
}
//同样的,对const int *,提取int
//即:对const T*,我们提取类型为T
template <class T>
struct iterator_traits<const T*> {
typedef T value_type;
}
4. 迭代器分类
根据移动特性和施行操作,迭代器被分为五类:
- Input Iterator: 所指对象只读。支持++操作
- Output Iterator: Write Only.支持++操作
- Forward Iterator: 允许写入。支持++操作
- Bidirectional Iterator: 可双向移动。
- Random Access Iterator:
利用重载函数来对同一个算法的不同类型迭代器做不同的操作,定义相应的五种迭代器结构.
在traits
里加入一条iterator_category
.
template <class I>
struct iterator_traits {
...
typedef typename I::iterator_category iterator_category;
}
//还需要对原生指针进行偏特化处理
//在算法中就这样使用,来激发函数重载机制(编译时期).
template <class I, class Distance>
inline void advance(I& i, Distance n) {
__advance(i, n, iterator_traits<I>::iterator_category());//做对应的操作
}
5. stl::iterator
STL为我们提供了一个iterator class
我们的迭代器继承它就能符合stl的标准了。
template <class Item>
struct ListIter : public std::iterator<std::forward_iterator_tag, Item> { ... };