迭代器类型

五种STL中迭代器的类型

// 输入迭代器
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 Category,class T,class Distance=ptrdiff_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;
};
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;
};
// const T*也是一样
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 Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&)
{
    typedef typename iterator_traits<Iterator>::iterator_category category;
    return category();
}
// 用于萃取迭代器距离的类型
template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type*
distance_type(const Iterator&)
{
    return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}
// 用于萃取迭代器所指对象的指针类型
template <class Iterator>
inline typename iterator_traits<Iterator>::value_type*
value_type(const Iterator&)
{
    return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}
// 下面是计算两个迭代器之间的距离
template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type
distance(Iterator first, Iterator last)
{
    typedef typename iterator_traits<Iterator>::iterator_category category;
    // step 1
    return __distance(first, last, category());
}
template <class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag)
{
    // step 1.1 步进迭代器，算出距离
    iterator_traits<InputIterator>::difference_type n = 0;
    while (first != last) ++first, ++n;
    return n;
}
template <class RandomAccessIterator>
inline typename iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIteratorfirst, RandomAccessIteratorlast, random_access_iterator_tag)
{
    // step 1.2 随机访问迭代器可以直接用迭代器相减，如vector的迭代器
    return last - first;
}
// 以下是迭代器前进的函数
template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n)
{
    typedef typename iterator_traits<InputIterator>::iterator_category category;
    // step 1
    return __advance(i, n, category());
}
template <class InputIterator, class Distance>
inine void
__advance(InputIterator& i, Distance n, input_iterator_tag)
{
    // step 1.1 前向迭代器，向前走n步
    while (n--) ++i;
}
template <class BidirectionalIterator, class Distance>
inine void
__advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag)
{
    // step 1.2 双向迭代器，需要走n步
    if (n >=0)
        while (n--) ++i;
    else
        while (n++) --i;
}
template <class RandomIterator, class Distance>
inine void
__advance(RandomIterator& i, Distance n, random_access_iterator_tag)
{
    // step 1.3 随机访问迭代器，直接+n
    i += n;
}