STL之iterator与traits技术

Posted on | Edited on

iterator模式定义如下：提供一种方法，使之能够依序寻访某个聚合物所含的各个元素，而又无需暴露该聚合物的内部表达形式

其中，c++里面各个容器的iterator扮演着将数据容器与算法结合起来的重要角色

将范型算法(find, count, find_if)用于某个容器中,最重要的是要给算法提供一个访问容器元素的工具，iterator就扮演着这个重要的角色

我们在算法中可能会定义简单的中间变量或者设定算法的返回变量类型，这时候需要知道迭代器所指元素的类型是什么，但是由于没有typeof这类判断类型的函数,我们无法直接获取，那该如何是好？

不要急，那首先先介绍一下iterator_tarit

iterator_trait

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

看到这个奇奇怪怪的东西，是不是感觉没什么用，嗯，没关系，先记着

下面，将接着之前的话题，来看看如何提取出iterator所指向的元素类型

value_type

例如

使用typedef

我们可以在迭代器中添加元素的类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 //取出迭代器类中的类型
//用以设定返回变量类型，但是如果I是指针就会错误
get (I ite) {
    return *ite;
}

但是，这个版本并不支持原生指针，然而就迭代器的行为而言，就是面向容器的指针，而正常的STL算法也是支持原生指针的，就如同下面的find一样

指针和迭代器的作用无非就是为stl算法提供了一个运算范围以及对容器（无论是vector，list，亦或是array）的访问

1
2
3
4
5
6
7
int main() {
    int a[5] = {1,2,2,2,2};
    int *begin = a;
    int *end = a+5;
    int count = std::count(begin, end, 2); //ok!
    return 0;
}

所以对于第一个版本，我们还要对指针类型进行模版偏特化

提取以及偏特化

前面也提到了，如果直接使用typename I::value_type，算法就无法接收原生指针，因为原生指针根本就没有value_type这个内嵌类型

因此，我们还需要加入一个中间层对其进行判断，看它是不是原生指针，注意，这就是traits技法的妙处所在

如果我们只使用上面的做法，也就是内嵌value_type，那么对于没有value_type的指针，我们只能对其进行偏特化，这种偏特化是针对可调用函数get的偏特化，假如get有100行代码，那么就会造成极大的视觉污染

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
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 //取出迭代器类中的类型
get (I ite) {
    std::cout << "class version" << std::endl;
    return *ite;
}

template <class I>
I get(I* ite) {
    std::cout << "pointer version" << std::endl;
    return *ite;
}

template <class I>
I get(const I* ite) {
    std::cout << "const pointer version" << std::endl;
    return *ite;
}

int main() {
    int i = 3;
    const int k = 3;
    MyIter<int> v(&i);
    std::cout << get(v) << std::endl;
    std::cout << get(&i) << std::endl;
    std::cout << get(&k) << std::endl;
    return 0;
}

就如同上面这个形式，设想往get中填充100行代码，简直不忍直视，你再看看下面这个，简直优雅！

利用一个中间层iterator_traits固定了get的形式，使得重复的代码大量减少，唯一要做的就是稍稍特化一下iterator_tartis使其支持pointer和const pointer:)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>

template <class T>
struct iterator_traits {
	typedef typename T::value_type value_type;
};

template <class T>
struct iterator_traits<T*> {
	typedef T value_type;
};

template <class T>
struct iterator_traits<const T*> {
	typedef T value_type;
};

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 iterator_traits<I>::value_type
get (I ite) {
    std::cout << "normal version" << std::endl;
    return *ite;
}

int main() {
    int i = 3;
    const int k = 3;
    MyIter<int> v(&i);
    std::cout << get(v) << std::endl;
    std::cout << get(&i) << std::endl;
    std::cout << get(&k) << std::endl;
    return 0;
}

通过定义内嵌类型，我们获得了知晓iterator所指元素类型的方法，通过traits技法，我们将函数模板对于原生指针和自定义iterator的定义都统一起来

这就是traits技法的妙处所在

difference type

difference type用于表示两个迭代器之间的距离的一个类型,也可以用来表示一个容器的最大的容量，因为对于连续空间的容器，头尾之间的距离就是最大容量

例如count()就必须返回的类型就是迭代器的difference type

对于STL容器类型，以及原生指针，traits有如下两个不同版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class I>
struct iterator_traits {
...
    typedef typename I::difference_type difference_type;
}

//原生指针
template<class I>
struct iterator_traits<T*> {
...
    typedef ptrdiff_t difference_type;
}

template<class I>
struct iterator_traits<const T*> {
...
    typedef ptrdiff_t difference_type;
}

reference type

标示了引用类型

pointer

标示了指针类型

测试

以上说明了迭代器内部的几种重要类型

下面对其进行一个测试，以此产生一个更直观的印象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <vector>

#define Test(x,z,y) std::cout<<std::is_same<std::iterator_traits<x>::z,y>::value<<std::endl

int main() {
#define IVec std::vector<int>::iterator
    Test(IVec,value_type,int); //true
    Test(IVec,difference_type,ptrdiff_t); //true
    Test(IVec,reference,int&); //true
    Test(IVec,pointer,int*); //true

    return 0;
}

从上面可以看出，一个vector<int>::iterator

  • value_type=int
  • difference_type=ptrdiff_t
  • reference=int&
  • pointer=int*

总结

要牢记iterator是为了访问容器内的元素而存在的，而它内置的类型就是范型算法与容器进行沟通的重要工具

而我们使用traits技法主要是为了解决原生指针和自定义iterator之间的不同所造成的代码冗余

type traits

type traits的出现和STL对于性能的要求有着千丝万缕的联系

试想，对于vector这种大块分配内存，然后大块析构的容器，如果容器里面是POD的话，那么只要等它的生命周期结束就行了，如果是非POD的话，那么就要判断是否拥有no-traits的析构函数

如果是这样的话，又回到了之前value_type的窘境，因此，我们只需要使用type_traits，对POD进行偏特化，通过两个神奇的类型进行判断

1
2
struct _true_type{};//无意义的析构函数  
struct _false_type{};//有意义的析构函数

这样子就可以让负责析构的模块进行判断了

具体的type_traits如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>  
struct type_traits  
{  
  
    typedef _false_type has_trivial_default_constructor;//默认构造函数是否有意义？  
    typedef _false_type has_trivial_copy_constructor;//拷贝构造函数是否有意义?  
    typedef _false_type has_trivial_assgignment_constructor;//拷贝赋值操作是否有意义?  
    typedef _false_type has_trivial_destructor;//析构函数是否有意义?  
    /*POD意指Plain Old Data,也就是标量型别或传统的C struct(传统的C struct只能 
    包含数据成员，不能包含函数成员。也就是所谓的聚合类。POD型别必然包含无意义 
    的ctor/dtor/copy/assignment函数。 
    */  
    typedef _false_type is_POD_type;//是否为Plain Old Data?  
};

总结

通过对type_traits进行特化，标注自己类中的构造，拷贝等行为是否是有意义的，可以大大提高适配算法的效率，这也是type traits存在的意义