STL学习笔记-3－迭代器(iterators)概念与traits编程技法

2016-04-13

auto_ptr

void remodel(string & str) {
    string * ps = new string(str); 
    str = ps;
    return;
}

这段代码会造成内存泄漏，我们会想说在函数return之前记得delete ps即可避免内存泄漏。

void remodel(string & str) {
    string * ps = new string(str); 
    if (weird_thing())
        throw exception(); 
    str = *ps;
    delete ps;
    return; 
}

但是这段代码在exception被抛出之后，delete这个句子不会被执行，也就造成了内存泄漏。

使用一个auto_ptr类型的话，在函数返回时，因为auto_ptr有自己的析构函数，所以会自己释放自己指向的内存空间。auto_ptr不能用于数组。

You should use an auto_ptr object only for memory allocated by new, not for memory allocated by new [] or by simply declaring a variable.

赋值操作

在正常的指针操作中，指针指间的相互赋值实际上是让多个指针同时指向一个内存空间。但是这个应用到auto_ptr上时就会有问题了，但删除两个auto_ptr时会导致程序对同一个内存空间进行了多次的delete操作。

为了避免这一个问题，可以用下面几个策略来避免：

让赋值操作变成deep copy，这会让两个指针指向不同的内存空间，其中一个将作为另一个的拷贝。
构建ownership概念，也就是拥有者概念。一个对象只能有一个智能指针拥有，只有拥有这个对象的智能指针能析构这个对象。赋值的同时转换拥有权。
创建一个更加智能的指针，对指向特定对象的指针进行跟踪。这个叫做reference counting。
当一个指针放弃了自己的拥有权之后，它可能会转变为不可用的状态。

iterator 是一种smart pointer

explicit

在类声明中使用这个可以避免隐形的转换。例如

class Star
{
...
public:
    explicit Start(const char*);
...
};
Star north;
north="polaris";//错误的使用方式
north=Star("polaris");//正确的使用方式

偏特化

两个说法

提供一份template定义式，其本身仍然是templaized。
针对任何template参数更进一步的条件限制所设计出来的一个特化版本。

例如下面的代码接受任意类型

1 2	template <typename T> class C{...}

而下面的代码只接受原生指针

1 2	template <typename T> class C<T> {...}

下面是一段用于类型萃取的代码

template <class I>
struct iterator_traits{ //traits意为特性
    typedef typename I::value_type value_type
}

如果class I有自己的value_type的话

template<class I>
typename iterator_traits<I>::valuetype //函数的返回类型
func(I ite){
    return *ite;
}

但是这个萃取器对于原生指针，像int* I这样的类型并不起作用，因为它并不是由用户定义的，因此并没有在内部定义一个value_type。因此需要一个特化版本的iterator_traits。如下所示

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

即使有这两个萃取器，对于像指向const int的指针类型的时候，我们只能获得一个无法更改的返回值。因此我们还需要另一个特化的萃取器。

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

最常用的迭代器(iterator)类型有物种:

value type
difference type
pointer
reference
iterator catagoly

3.4.1 value type

任何一个打算与STL配合的class都需要定义自己的value type内嵌型别。

3.4.2 difference type

difference type表示两个迭代器之间的距离。因此它可以用来表示一个容器的最大容量。如果需要提供一个计数功能count()的话，返回值就需要是difference type

template<class I,class T>
typename iterator_traits<I>::difference_type
count(I first,I last,const T& value){
    typename iterator_traist<I>::difference_type n=0;
    for (;first!=last;first++){
        if (*first==value) 
            ++n;
        return n;
    }
}

接着可以给出一个泛化版本的和两个特化版本的difference type的萃取器。

//泛化版本
template <class I>
struct iterator_traits{
    typedef typename I::differene_type difference_type;
}

//为原生指针特化的版本
template <class T>
struct iterator_traits<T*>{
    typedef ptrddif_t difference_type;
}

//为pointer to const偏特化的
template <class T>
struct iterator_traits<const T*>{
    typedef ptrddif_t difference_type;
}

有了这三个萃取器，我们想要任何迭代器的difference type的时候我们只需要一下代码:

1	typename iterator_traits<class I>::difference_type;

reference type

从迭代器所指之物的内容是否允许改变来看，可以将迭代器分为两种:

不允许改变所指对象之内容，称为constant iterators。例如const int* pic。
允许改变所指对象之内容，称为mutable iterators。例如int* pi。

当p是一个mutable iterators时，如果其value type是T，那么*p的型别不应是T，而应该是&T。以此类推，如果p是一个constant iter，其value type是T，那么*p的型别应该是const T&。这里所讨论的*p就是所谓的reference type。

pointer type

1 2	Item& operator* () const{ return ptr;} Item operator->() const { return ptr;}

Item&便是reference type，而Item*便是其pointer type。

直接献上完整的代码(Orz):

template <class Iterator>
struct iterator_traits {
  typedef typename Iterator::iterator_category iterator_category;
  typedef typename Iterator::value_type        value_type;
  typedef typename Iterator::difference_type   difference_type;
  typedef typename Iterator::pointer           pointer;
  typedef typename Iterator::reference         reference;
};

template <class T>
struct iterator_traits<T*> {
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

template <class T>
struct iterator_traits<const T*> {
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef const T*                   pointer;
  typedef const T&                   reference;
};

iterator_category

根据移动特性与施行操作，迭代器被分为五类:

input iterator:这种迭代器所指的对象，不允许外界改变。只读(read only)。
output iterator:write only。
forward iterator:允许“写入型”算法（例如replace()）在此迭代器所形成的区间上进行读写操作。
bidirectional iterator:可双向移动。某些算法需要逆向走访某个迭代器区间（例如逆向拷贝某范围内的元素），可以使用这种迭代器。
random access iterator:前四种迭代器都只供应一部分指针算数能力（前三种支持operator++，第四种再加上operator–），第五种则涵盖所有指针算数能力，包括p+n`p-np[n]p1-p2p1<p2`。

advance()

这是许多算法内部常用的一个函数，该函数有两个参数p和n。表示函数将p累进n次。下面有三份定义，分别针对Input Iterator`Bidirectional IteratorRandom Access Iterator。而对ForwardIterator来说，它的版本与Input Iterator`的版本一致。

template <class InputIterator, class Distance>
void advance_II(InputIterator& i,Distance n)
{
    //单向，逐一前进
    while(n--) ++i;
}

template <class BidirectionalIterator, class Distance>
void advance_BI(BidirectionalIterator& i,Distance n)
{
    //双向，逐一前进
    if (n>=0)
        while (n--) ++i;
    else
        while (n++) --i;
}

template <class RandomAccessIterator, class Distance>
void advance_RAI(RandomAccessIterator& i,Distance n)
{
    //双向，跳跃前进
    i+=n;
}

但是这样的话我们还需要一个函数来判断迭代器的类型然后调用相应的函数。

定义五个classes

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 {};

设计五个用于内部调用的函数，最后一个参数只是为了激活函数的重载。

template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
  while (n--) ++i;
}

template <class BidirectionalIterator, class Distance>
inline void __advance(BidirectionalIterator& i, Distance n, 
                      bidirectional_iterator_tag) {
  if (n >= 0)
    while (n--) ++i;
  else
    while (n++) --i;
}

template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n, 
                      random_access_iterator_tag) {
  i += n;
}

这里使用的方法是添加一个单纯的调用函数advance()，这个函数只接受两个参数，当它将工作转向__advance()的时候，自行通过traits机制加上第三个参数，也就是前面定义的五个classes。

template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n) {
  __advance(i, n, iterator_category(i));
}

然后再定义函数iterator_category()。

template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
  typedef typename iterator_traits<Iterator>::iterator_category category;
  return category();
}

可以注意到我们在列举__advance()函数的时候，少列举了两种，一种是OutputIterator，另一种是ForwardIterator。前者是因为可以同InputIterator共用，后者是因为可以消除单纯只做传递调用的函数，所以就没有对应的__advance()函数了。

__types_traits

这个技巧类似于前面的iterator_traits，都是用于解析特征。这里需要解析看这个类型能否使用更快速的内存上的操作进行操作，避免使用高层次的函数。

使用场景：uninitialized_fill_n()

template <class ForwardIterator, class Size, class T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n,
                                            const T& x) {
  return __uninitialized_fill_n(first, n, x, value_type(first));
}

上面这个函数以x为蓝本，自迭代器first开始构造n个元素。为求取最大效率，首先以value_type()萃取出迭代器first的value type，再利用__type_traits判断该型别是否为POD型别：

template <class ForwardIterator, class Size, class T, class T1>
inline ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n,
                                              const T& x, T1*) {
  typedef typename __type_traits<T1>::is_POD_type is_POD;
  return __uninitialized_fill_n_aux(first, n, x, is_POD());
                                    
}

接着调用了上面这个函数，其中is_POD()是一个struct，然后调__uninitialized_fill_n_aux函数，其中编译器会根据is_POD()来重载函数，分配到是POD和不是POD对应的函数中。

Blog

Learning