TinySTL实现项目（四）：迭代器、反向迭代器及初始化工具

在进行vector、list等容器设计之前，我们还需要进行一些准备工作。首先因为容器主要是通过迭代器进行读取和修改操作的，所以我们需要设计迭代器相关工具；另外还需要为部分容器设计反向迭代器，令其支持反向读取操作；最后还需要一组初始化工具，用于容器对象创建时，开辟内存空间后，向其填充元素。

1 迭代器 iterator 概念

1.1 迭代器的作用

迭代器最直接的作用就是可以迭代地访问容器元素。

迭代器iterator在STL中的角色非常关键，可以说代表了STL设计的中心思想：将容器containers和算法algorithms分开，使用泛型思想独立设计，然后使用迭代器进行两者的交互，这样就可以在保证性能最大化的同时，让一种算法可以应用在多种容器上。

例如算法find

temlate <class InputIterator, class T>
InputIterator find(InputIterator first,
                   InputIterator last, 
                   const T& value) {
    while (first != last && *first != value)
        ++first;
    return first;
}

其可以接受两个迭代器，来表示容器中的一个前闭后开的区间范围，然后在这个范围中寻找是否含有值为value的目标迭代器，如果未找到，则返回区间最后一个迭代器。而这些迭代器可以来自vector、list、stack等等容器。

迭代器与指针又是什么关系呢？

迭代器的行为类似指针，可以说迭代器就是一种智能指针smart pointer，使用它不用担心内存泄露等等问题。

事实上，很多迭代器的实现，就是对指针的包装，其最重要的工作就是对operator*和operator->进行重载。

1.2 迭代器型别

在前面的文章中，已经提到过使用traits技巧可以“萃取”对象或类的某种特性。

那么迭代器有哪些特性需要供人“萃取”呢？那就要说到迭代器的五种型别

value_type：迭代器所指对象的型别。
difference_type：用来表示迭代器之间的距离，可以用来表示一个容器的最大容量。
reference：在对迭代器iter进行解引用*iter时应该返回的类型；若迭代器为mutable这里即为value_type&，若迭代器为constant，这里即为const value_type&。
pointer：迭代器所指对象的指针类型
iterator_category：迭代器的类型，这里所说的类型根据迭代器的移动和读写特性分成了五类。

迭代器的类型iterator_category分为以下5类

input iterator：只读，即不允许通过迭代器改变所指对象；单向移动，支持operator++
output iterator：只写；单向移动，支持operator++
forward iterator：允许读写；单向移动，支持operator++
bidirectional iterator：允许读写；双向移动，支持operator++和operator--
random access iterator：允许读写；既可双向移动，也可随机访问，即同时支持++、–-、+n、-n

迭代器的类型非常重要，根据迭代器的具体类型，可以为同一种算法提供不同设计，以达到最优效率。例如，显然random access iterator对元素的读取就比其他类型的迭代器方便得多，可以减少许多不必要的遍历，从而提升效率。

2 迭代器的设计

2.1 迭代器的五种类型设计

1.2节中已经提到，我们的算法可以根据不同的迭代器类型来优化，显然我们可以使用重载机制，根据参数中迭代器的类型对同一种算法进行重载。而重载函数需要区分形参的个数与类型，我们可以使用如下思路来设计

template <typename Iterator>
void algo(Iterator first, Iterator last){
    algo_aux(first, last, Iterator::iterator_category);
}

template <typename Iterator>
void algo_aux(Iterator first,Iterator last, InputIterator){
    // do something;
}

template <typename Iterator>
void algo_aux(Iterator first, Iterator last, RandomAccessIterator) {
    // do otherthing;
}

所以对于五种类型的设计，应当设计为不同的类型，以方便作为重载函数的形参，实现如下

iterator.h

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

这是五种没有任何成员的struct，并且之间还有继承关系。没有任何成员则不带来任何负担，而之间的继承关系，则可以保证作为子类的迭代器类型可以在为父类迭代器设计的函数中正常运行。

比如有一种算法，仅为input_iterator_tag和random_iterator_tag设计了重载函数，那么由于继承关系，类型为forward_iterator_tag和bidirectional_iterator_tag也可以使用为input_iterator_tag设计的版本。否则就需要为每一种可能可以使用的迭代器类型单独重载一个版本，这就带来了许多不必要的工作。

2.2 迭代器模板设计

由于规定了STL使用的迭代器必须拥有1.2节中所规定的型别定义，以供traits，所以可以写一个基本的迭代器模板，只包含型别定义，那么每次自己设计迭代器时，继承自这个基本迭代器即可，无需自己再写一遍型别定义。

iterator.h

template<typename Category, typename T, typename Distance = ptrdiff_t,
         typename Pointer = T*, typename Reference = T&>
struct iterator{
    using iterator_category = Category;
    using value_type        = T;
    using difference_type   = Distance;
    using pointer           = Pointer;
    using reference         = Reference;
};

2.3 迭代器的traits工具设计

因为实际使用中迭代器的设计各种各样，有的容器并不会单独设计一种迭代器，而是直接使用原生指针，那么直接通过iterator::value_type的方式来直接取得迭代器型别便不一定行得通。

那么为了统一接口，我们可以设计一个iterator_traits，用来取得所有被视为迭代器类型的型别。

iterator.h

// 迭代器的 traits
template <typename Iterator>
struct iterator_traits{
    using value_type        = typename Iterator::value_type;
    using iterator_category = typename Iterator::iterator_category;
    using difference_type   = typename Iterator::difference_type;
    using pointer           = typename Iterator::pointer;
    using reference         = typename Iterator::reference;
};

// 偏特化版本
template <typename T>
struct iterator_traits<T*>{
    using value_type        = T;
    using iterator_category = random_access_iterator_tag;
    using difference_type   = ptrdiff_t;
    using pointer           = T*;
    using reference         = T&;
};

template <typename T>
struct iterator_traits<const T*>{
    using value_type        = T;
    using iterator_category = random_access_iterator_tag;
    using difference_type   = ptrdiff_t;
    using pointer           = const T*;
    using reference         = const T&;
};

这里的偏特化版本，就可以解决那些采用原生指针作为迭代器的traits问题，从而保证只要被视为迭代器，都可以通过iterator_traits<iterator>::value_type的方式来获取型别。

然而在实际使用中，很多时候还需要在取得类型时加typename来表示我们取出的类型别名定义，而不是成员函数等等，而且还需要获得迭代器本身的类型作为模板参数。

1	typename iterator_traits<Iteraror>::value_type;

这样难免觉得麻烦，也降低了代码的可读性，所以我们可以定义一组函数，让函数直接接受迭代器对象作为参数，然后返回我们需要萃取的型别的对象，此返回的对象还可以直接作为我们重载函数的参数。如下

iterator.h

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

template <typename Iterator>
inline typename iterator_traits<Iterator>::difference_type* difference_type(const Iterator&) {
    return static_cast<typename iterator_traits<Iterator>::difference*>(0);
}

template <typename Iterator>
inline typename iterator_traits<Iterator>::value_type* value_type(const Iterator&) {
    return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}

2.4 advance 和 distance

在算法实现中，难免需要经常用到让迭代器前进一段距离，或是获取两个迭代器直接距离的操作。这对于分类为random_access_iterator_tag的随机访问迭代器来说，自然易如反掌，但对于仅支持operator++的其他迭代器来说，就有些麻烦，需要一位位地前进。

所以可以为这两个常用的迭代器操作各自设计函数，并且在函数实现中为不同类型的迭代器进行重载，保证所有类型迭代器都可用，还能兼顾效率。

实现如下

iterator.h

template <typename InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
distance_aux(InputIterator first, InputIterator last, input_iterator_tag) {
    typename iterator_traits<InputIterator>::difference_type n = 0;
    for (; first != last; ++first, ++n);
    return n;
}

template <typename RandomAccessIterator>
inline typename iterator_traits<RandomAccessIterator>::difference_type
distance_aux(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {
    return last - first;
}

template <typename InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last) {
    return distance_aux(first, last, iterator_category(first));
}

template <typename InputIterator, typename Distance>
inline void advance_aux(InputIterator iter,const Distance& n, input_iterator_tag) {
    for(; n != 0; --n, ++iter);
}

template <typename BidirectionIterator, typename Distance>
inline void advance_aux(BidirectionIterator iter, const Distance& n, bidirectional_iterator_tag) {
    if (n >= 0)
        for(; n != 0; --n, ++iter);
    else
        for(; n != 0; ++n, --iter);
}

template <typename RandomAccessIterator, typename Distance>
inline void advance_aux(RandomAccessIterator iter, const Distance& n, random_access_iterator_tag) {
    iter += n;
}

template <typename InputIterator, typename Distance>
inline void advance(InputIterator iter, const Distance& n) {
    advance_aux(iter, n, iterator_category(iter));
}

3 反向迭代器的设计

在STL为支持随机访问的容器如vector提供了反向迭代器，使用方法如下

vector<int> vec = {1, 2, 3, 4, 5};
cout << *vec.rbegin() << endl; 		 // 5
cout << *(vec.rbegin() + 1) << endl; // 4
cout << *(vec.rend() - 1) << endl; 	 // 1

显然对于一个反向迭代器对象，+1则指向对象的索引-1，反之亦然。所以对于反向迭代器，最关键的实现部分就是对其操作符进行重载。

在实现思路上，我们可以设计一个模板类，接受一个普通迭代器类型作为模板参数，然后这个反向迭代器的模板类中，唯一的成员就是这个普通迭代器对象，然后按照反向迭代器的逻辑对各种操作符进行重载。

3.1 基本设计

说到底，其实反向迭代器不过就是初始迭代器的一个封装，只是要求封装后的接口能够满足“反向”的逻辑。

首先，我们要求能够转换为反向迭代器的初始迭代器的访问类型必须是random access iterator，自然也就能支持自增、自减操作。

然后反向迭代器也是迭代器，故而用于traits的型别定义不能少。另外还需定义一个成员函数base()用于取出其初始迭代器。

其基本的代码实现如下：

iterator.h

// 反向迭代器的实现
template <typename RandomAccessIterator, typename T,
          typename Reference = T&,
          typename Distance = ptrdiff_t>
class reverse_iterator{
protected:
    using self = reverse_iterator<RandomAccessIterator, T>;
    RandomAccessIterator current;
public:
    using iterator_category = random_access_iterator_tag;
    using value_type        = T;
    using difference_type   = Distance;
    using pointer           = T*;
    using reference         = Reference;
    reverse_iterator() {}
    explicit reverse_iterator(RandomAccessIterator iter) : current(iter) {}
    RandomAccessIterator base() const { return current; }
    // 还需实现操作符重载
};

3.2 类内操作符重载

操作符的重载其实是有固定的实现方法，故而不对语法进行详细分析，这里仅仅需要将原来的+、-、+=、-=的逻辑进行加减互换即可

iterator.h

template <typename RandomAccessIterator, typename T,
          typename Reference = T&,
          typename Distance = ptrdiff_t>
class reverse_iterator{
    /* 接迭代器基本设计之后 */
    
	// 各种操作符重载
    Reference operator*() const { return *(current - 1); }
    pointer operator->() { return &(operator*()); }
    self& operator++() {
        --current;
        return *this;
    }
    self operator++(int) {
        self tmp = *this;
        --current;
        return tmp;
    }
    self& operator--() {
        ++current;
        return *this;
    }
    self operator--(int) {
        self tmp = *this;
        ++current;
        return *this;
    }
    self operator+(Distance n) {
        return self(current - n);
    }
    self& operator+=(Distance n) {
        current -= n;
        return *this;
    }
    self operator-(Distance n) {
        return self(current + n);
    }
    self& operator-=(Distance n) {
        current += n;
        return *this;
    }
    Reference operator[](Distance n) const { return *(*this); }
}; // end reverse_iterator

3.3 全局比较操作符重载

显然在类的设计中，还需要对==等比较操作符重载，在此将其作为全局操作符实现。实现代码如下

iterator.h

template <typename RandomAccessIterator,
          typename T,
          typename Reference,
          typename Distance>
inline bool operator<(reverse_iterator<RandomAccessIterator, T, Reference, Distance>& lhs,
                      reverse_iterator<RandomAccessIterator, T, Reference, Distance>& rhs) {
    return lhs.base() < rhs.base();
}

template <typename RandomAccessIterator,
          typename T,
          typename Reference,
          typename Distance>
inline Distance operator-(reverse_iterator<RandomAccessIterator, T, Reference, Distance>& lhs,
                          reverse_iterator<RandomAccessIterator, T, Reference, Distance>& rhs) {
    return lhs.base() - rhs.base();
}

template <typename RandomAccessIterator,
          typename T,
          typename Reference,
          typename Distance>
inline reverse_iterator<RandomAccessIterator, T, Reference, Distance> operator+(Distance n,
                      reverse_iterator<RandomAccessIterator, T, Reference, Distance>& iter) {
    return reverse_iterator<RandomAccessIterator, T, Reference, Distance>(iter.base() - n);
}

该反向迭代器的使用将会在下一篇vector的实现中看到。

4 容器初始化工具设计

在之前空间分配器allocator的设计中已经提到，在STL中，将容器对象创建过程中的分配内存、构造对象分成了两步。在分配内存中我们已经拥有了alloc（实际STL标准中没有此接口）和allocator两种工具，这里，我们实现一下在分配好的内存中填充元素的初始化工具。

4.1 uninitialized_copy

在STL容器的使用中，我们是可以通过许多方法来创建新容器，既可以自己设定初始值，也可以拷贝已有容器内的元素。如下

vector<int> vec1(5, 5);
list<int> lis1 = {1, 2, 3, 4, 5};
vector<int> vec2(vec1.begin(), vec1.end());
list<int> lis2(vec2.begin()+1, vec.end());

其中后面两种方法通过迭代器将已有容器的元素进行拷贝，来初始化创建的容器对象。

所以我们需要使用一个工具，可以接受两个迭代器表示需要拷贝的范围，然后还需要一个迭代器参数，表示目的地点，返回值则是一个迭代器，指向拷贝完成的后一个位置。函数原型如下

template <typename InputIterator, typename ForwardIterator>
inline ForwardIterator uninitialized_copy(InputIterator first,
                                          InputIterator last,
                                          ForwardIterator result);

注意两个模板参数的命名，可以看出迭代器参数的iterator_category类型，一个是input一个是forward。这是STL中的命名习惯，表示该算法所接受迭代器最低类型要求，也就是说，first和last只需是input类型及以上都可以，但是result至少得是forward类型的，如果也是input类型，则函数无法正常运行。

而根据迭代器指向对象的不同，如是否为POD类型，来决定拷贝对象的方式，来达到效率的提升。关于POD类型，可见TinySTL实现项目（一）：traits 技巧与 type_traits 模板。

具体实现如下

uninitialized.h

template <typename InputIterator, typename ForwardIterator>
inline ForwardIterator uninitialized_copy(InputIterator first,
                                          InputIterator last,
                                          ForwardIterator result) {
    using value_type =
        typename mystl::iterator_traits<ForwardIterator>::value_type;
    using is_POD = typename type_traits<value_type>::is_POD_type;
    return uninitialized_copy_aux(first, last, result, is_POD());
}

template <typename InputIterator, typename ForwardIterator>
inline ForwardIterator uninitialized_copy_aux(InputIterator first,
                                              InputIterator last,
                                              ForwardIterator result,
                                              _true_type) {
    return std::copy(first, last, result);
}

template <typename InputIterator, typename ForwardIterator>
inline ForwardIterator uninitialized_copy_aux(InputIterator first,
                                              InputIterator last,
                                              ForwardIterator result,
                                              _false_type) {
    ForwardIterator cur = result;
    try {
        for (; first != last; ++first, ++cur)
            construct(cur, *first);
        return cur;
    } catch (...) {
        destroy(result, cur);
        throw;
    }
}

如在POD类型的介绍中所说，如果是POD类型，则可以使用memcpy等C函数来提升效率。这里为了不影响代码的阅读逻辑，并且控制项目的复杂度，所以在is_POD为_true_type的重载版本中直接调用copy函数。本项目当前主要专注于容器和算法的设计上，暂未实现自己的copy函数，所以先调用STL中的接口。

事实上，copy函数也不过是对各种数据类型的重载和偏特化罢了，核心思想还是使用traits技巧来进行dismatch，以此提高效率。在思想和技巧上我们已经体现，所以暂时也没必要浪费时间在此。

关于异常处理，STL的思想是commit or rollback，大概意思就是全部成功或一个不留，如果构造填充的过程出了错，就需要将已构造的部分进行析构，恢复原样。

4.2 uninitialized_fill

该函数也是类似的，只不过是想目标区域填充固定的数，而不是从某一个范围拷贝。

其接口是接受一个范围作为填充目标区域，当然还需要接受一个值作为填充初始值。注意此函数返回值为void，这是STL标准中要求的。直接看代码

uninitialized.h

template <typename ForwardIterator, typename T>
inline void uninitialized_fill(ForwardIterator first,
                                          ForwardIterator last,
                                          const T& value) {
    using value_type =
        typename mystl::iterator_traits<ForwardIterator>::value_type;
    using is_POD = typename type_traits<value_type>::is_POD_type;
    uninitialized_fill_aux(first, last, value, is_POD());
}

template <typename ForwardIterator, typename T>
inline void uninitialized_fill_aux(ForwardIterator first,
                                              ForwardIterator last,
                                              const T& value,
                                              _true_type) {
    std::fill(first, last, value);
}

template <typename ForwardIterator, typename T>
inline void uninitialized_fill_aux(ForwardIterator first,
                                              ForwardIterator last,
                                              const T& value,
                                              _false_type) {
    ForwardIterator cur = first;
    try {
        for (; cur != last; ++cur)
            construct(cur, value);
        return cur;
    } catch (...) {
        destroy(first, cur);
        throw;
    }
}

4.3 uninitialized_fill_n

此函数同uninitialized_fill作用类似，只不过只需接受一个迭代器参数表示填充起点，另外接受一个参数表示填充个数。最后其返回值是一个迭代器，指向填充完成后的下一个位置

uninitialized.h

template <typename ForwardIterator, typename T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first,
                                            size_t n,
                                            const T& value) {
    using value_type =
        typename mystl::iterator_traits<ForwardIterator>::value_type;
    using is_POD = typename type_traits<value_type>::is_POD_type;
    return uninitialized_fill_n_aux(first, n, value, is_POD());
}

template <typename ForwardIterator, typename T>
inline ForwardIterator uninitialized_fill_n_aux(ForwardIterator first,
                                                size_t n,
                                                const T& value,
                                                _true_type) {
    return std::fill_n(first, n, value);
}

template <typename ForwardIterator, typename T>
inline ForwardIterator uninitialized_fill_n_aux(ForwardIterator first,
                                                size_t n,
                                                const T& value,
                                                _false_type) {
    ForwardIterator cur = first;
    try {
        for (; n != 0; --n, ++cur)
            construct(cur, value);
        return cur;
    } catch (...) {
        destroy(first, cur);
        throw;
    }
}

5 结束语

在本部分主要进行了迭代器、反向迭代器以及容器初始化工具的实现，其完整代码同样可以在这里看到。下一篇开始，将开始容器的设计。