SGI STL 标准库 迭代器与类型萃取 2

STL 迭代器 类型萃取

github源码分析仓库
迭代器是一种抽象设计概念,Iterator模式定义:提供一种方法,使之能够依次遍历某个容器所包含的各个元素,而不需要暴露该容器的内部表达方式。
STL中心思想:将数据容器和算法分开,独立设计,再将其结合在一起使用。
迭代器是一种智能指针,迭代器重载operator*operator->操作符。
算法在使用迭代器时可能需要其相应的类型,比如迭代器所指之物的类型。

利用函数模版的参数推导机制获取型别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class I, class T>
void func_impl(I iter, T t)
{
T tmp; //T就是迭代器iter所指之物的类型
//func应该做的工作
}
template <class I>
inline void func(I iter)
{
func_impl(iter, *iter); //func的工作移到func_impl
}
int main()
{
int i;
func(&i);
}

声明内嵌类型获得迭代器所指之物及其它需要的类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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>
typename I::value_type func(I ite)
{
return *ite;
}

// ...
MyIter<int> ite(new ine(8));
cout<<func(ite);

利用在迭代器类内部内嵌类型声明,可以得到类内部所拥有的对象的各个类型,但迭代器还可以是原生指针,原生指针无法进行内嵌类型声明,需要使用C++模版偏特化,提供原生指针的特化版本解决问题。

1
2
3
4
5
template <class T>
T func(T* ite)
{
return *ite;
}

设计中间件萃取器获取迭代器所包含的类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//萃取器
template <class I>
struct iterator_traits {
typedef typename I::value_type value_type;
};

template <class I>
typename iterator_traits<I>::value_type fun(I ite) //返回值使用萃取器获取
{
return *ite;
}

//偏特化版本,用于迭代器是原生指针
template <class I>
struct iterator_traits<I*> {
typedef I value_type;
};

//偏特化版本,用于迭代器是const原生指针的情况
template <class I>
struct iterator_traits<const I*> {
typedef I value_type;
};

通过iterator_traits可以方便的获取迭代器的相应类型。
最常用的迭代器类型有五种:value_typedifference_typepointerreferenceiterator_category

1
2
3
4
5
6
7
8
template <class I>
struct iterator_traits {
typedef typename I::iterator_category iterator_category;
typedef typename I::value_type value_type;
typedef typename I::difference_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};

value_type即迭代器所指对象的类型。
difference_type用来表示两个迭代器之间的距离。
reference引用类型。
pointer指针类型。
iterator_category迭代器类型。

迭代器类型根据移动和可进行操作分为五种:

  • input iterator: 该类型迭代器所指对象不允许外界改变,只读 单向移动
  • output iterator: 唯写 单向移动
  • forward iterator: 读写 单向移动
  • bidirectional iterator: 可双向移动迭代器 读写
  • random access iterator: 随机迭代器 读写

迭代器的分类和从属关系:

1
2
3
4
5
6
7
input iterator      output iterator
| |
forward iterator
|
bidirectional iterator
|
random access iterator

它们的关系不是继承,而是概念和强化的关系。
由于各种迭代器不尽相同,设计算法时,应尽量针对某种迭代器提供明确定义,并针对更强化的某种迭代器提供另一种定义,在不同情况下提供最大效率。
在运行期根据迭代器类型选择不同算法版本,影响程序效率,利用重载函数机制,在编译器选择合适的版本。
利用萃取器取出迭代器的类型,利用迭代器类型形成函数重载,在编译器确定运行的算法版本。
定义五种迭代器类型作为标记用的型别:

1
2
3
4
5
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

使用class定义迭代器的标签,不仅促成重载机制成功运作,而且通过继承在调用函数时,如果不存在一个能力强的版本的函数,可以自动调用能力弱的版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class I>
void func(I& B, input_iterator_tag)
{
}
void func(I& B, bidirectional_iterator_tag)
{
}
int main()
{
func(1, input_iterator_tag()); //参数完全匹配 调用func(I& B, input_iterator_tag)
func(2, forward_iterator_tag()); //参数未能完全匹配 由于继承关系 调用func(I& B, input_iterator_tag)
func(3, bidirectional_iterator_tag()); //参数完全匹配 调用func(I& B, bidirectional_iterator_tag)
return 0;
}

STL中模板参数命名以算法所能接受的最初级类型为迭代器型别参数命名。

std::iterator的保证

STL中任何迭代器都应该提供五种内嵌相应型别,以利于traits萃取。STL提供iterator class使每个新设计的迭代器都继承它,保证符合STL规范。

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class Category,
class T,
class Distance = ptrdff_t,
class Pointer = T*,
class Reference = T&>
struct iterator
{
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
}

设置适当的相应类型,是迭代器的责任。设计适当的迭代器,是容器本身的责任。因为只有容器本身知道如何遍历自己。

SGI STL的__type_traits

STL使用traits,对迭代器进行规范,制定出iterator_category。SGI将traits扩大到迭代器以外的其它地方, 即__type_traits,是SGI STL内部私有的东西,不在STL标准规范之外。
iterator_category负责萃取迭代器特性,而__type_traits则负责萃取型别的特性。型别的特性是指其构造函数、拷贝构造函数、等号运算符重载函数、析构函数是否“没有价值”,如果答案为否定的,在对该型别进行构造、拷贝构造、析构、赋值时,可以采取效率更高的方法,直接对内存操作,不需要调用其构造、拷贝构造、析构、赋值函数。

1
2
3
4
5
6
7
8
9
10
11
12
struct __true_type {};
struct __false_type {};
template <class type>
struct __type_traits
{
typedef __true_type this_dummy_member_must_be_first;
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
};

SGI STL将所有都定义为最保守的值__false_type。然后针对每一种标量类型设计合适的__type_traits特化版本。

1
2
3
4
5
6
7
8
9
10
//举例
template <>
struct __type_traits<char>
{
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};

__type_traits在SGI STL中广泛使用。比如空间配置器中uninitialized_fill_n()函数、destroy()函数等。