6 Iterators

文本统计：约 789 个字 • 180 行代码

为什么我们需要迭代器？它能够在不知道容器内部结构的情况下，提供我们一种访问方式。可以被认为是指针的扩展。如果没有迭代器，有 N 种算法和 M 种相应的数据结构，那么我就要实现 N*M 次，这并不是我们所需要的。迭代器的一大作用就是将算法和数据结构解耦。

比如说下面这个利用迭代器的查找算法

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

使用的时候就传入迭代器的类型即可

vector<int> vecTemp;
list<double> listTemp;
if (find(vecTemp.begin(),vecTemp.end(),3) == vecTemp.end())
 cout << "3 not found in vecTemp" << endl;
if (find(listTemp.begin(),listTemp.end(),4) == listTemp.end())
 cout << "4 not found in listTemp" << endl;

---

下面以 List 容器为例，写一下它的实现方式

template<class T>
class List {
public:
     void insert_front();
     void insert_end();
     /* ... */
private:
     ListItem<T> *front;
     ListItem<T> *end;
     long _size;
};

template<class T>
class ListItem {
public:
     T& val() {
        return _value;
     }
     ListItem* next() {
        return _next;
     }
     /* ... */
private:
     T _value;
     ListItem *_next;
};

template<class T>
class ListIter {
    ListItem<T> *ptr;
public:
    ListIter(ListItem<T> *p=0) : ptr(p) {}

    ListIter<T>& operator++()
    { ptr = ptr->next(); return *this; }

    bool operator==(const ListIter& i) const
    { return ptr == i.ptr; }
     /* ... */
    T& operator*() { return ptr->val(); }
    T* operator->() { return &(**this);} 
    //一个可以直接用来访问当前元素成员的指针
};

使用场景如下

List<int> myList;
... // insert elements
ListIter<int> begin = myList.begin();
ListIter<int> end = myList.end();
ListIter<int> iter;

iter = find(begin, end, 3);
if (iter == end)
 cout << "not found" << endl;

---

但这个仍有一些问题，因为我们抽象给算法的是迭代器，而有些时候算法本身需要迭代器内部的一些信息，比如说迭代器类型，数据类型等等。有一个解决方法是传入相应的类型参数

// we do NOT know the data type of iter,
// so we need another variable v to infer T
template <class I, class T>
void func_impl(I iter, T& v)
{
 T tmp;
 tmp = *iter;
 // processing code here
}

当然我们也可以在外面再提供一层封装，这样我们依然只需要传入一个迭代器即可。

// a wrapper to extract the associated
// data type T
template <class I>
void func(I iter)
{
 func_impl(iter, *iter);
 // processing code here
}

但是我们可能需要更多关于迭代器的信息，于是我们可以选择在迭代器中显式地定义一些信息。如果我在下面这个迭代器中定义类型

template <class T>
struct myIter {
     typedef T value_type;
     /* ... */
     T* ptr;
     myIter(T *p = 0) : ptr(p) {}
     T& operator*() {
        return *ptr;
     }
};

这样我就可以在使用迭代器的时候调用相应的类型了，其中 typename 的作用是告诉编译器某个符号应该被解释为一个类型，避免编译器的歧义解析

template <class I>
typename I::value_type func(I iter) {
    return *iter;
}
// code
myIter<int> iter(new int(8));
cout << func(iter);

但是这样在处理原生指针的时候就出现了一些问题，因为原生指针（也可以被认为是一个迭代器）就没有相应的变量 value_type 这样就会造成错误，我们可以使用这样一个技巧 iterator_traits

template<class I>
class iterator_traits
{
public:
    typedef typename
     I::value_type value_type;
    typedef typename
     I:pointer_type pointer_type;
    /* ... */
};

提供一个特化模板用于处理指针的情况，接着再提供一份 const T* 的版本

template<class T>
class iterator_traits<T*>
{
public:
    typedef T value_type;
    typedef T* pointer_type;
    /* ... */
};

这样我们就可以处理指针作为迭代器的情况了

template <class I>
typename iterator_traits<I>::value_type
func(I iter) {
 return *iter;
}
// code
myIter<int> iter(new int(8));
cout << func(iter);
int* p = new int[20]();
cout << func(p);

而在标准库中 iterator_traits 还包含了其他信息

template<class I>
class iterator_traits
{
public:
    typedef typename I::iterator_category iterator_category;
    typedef typename I::value_type value_type;
    typedef typename I::difference_type differece_type;
    typedef typename I::pointer pointer;
    typedef typename I::reference reference;
 /* ... */
}

---

关于迭代器的类型，分为以下五种

• InputIterator

• OutputIterator

• ForwardIterator

• BidirectionalIterator

• RandomAccessIterator

不同的迭代器类型，同样的算法实现方式有时候并不相同。

比如说将当前迭代器平移 n 个单位，对于 InputIterator 来说，只能处理正的 n，并且只能一个一个移动；如果是 BidirectionalIterator 就可以双向移动，处理负的 n; 而对于 RandomAccessIterator 来说就可以直接移动 n 步。那么我应当如何根据不同的迭代器实现该算法呢？

我们设置一些迭代器结构，注意这些迭代器类型的继承关系

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 函数是最终的实现算法

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

这个 iterator_traits 还是一样，为了处理指针的问题，做了一个特化

template <class I>
struct iterator_traits {
 /* ... */
    typedef typename I::iterator_category iterator_category;
};
template <class T>
struct iterator_traits<T*> {
 /* ... */
    typedef random_access_iterator_tag iterator_category;
};

如果输入的是 ForwardIterator ，那么相应的 type 为 forward_iterator_tag，我们发现我之前并没有写相应的版本，但是它会 upcasting，当作 input_interator_tag 处理，调用 inputIterator 的版本

评论区

对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！