STL之iterator源码解析

摘要

迭代器是一种行为类似指针的对象，本文介绍iterator与traits的关系,以及对traits内容的补充。包含stl_iterator.h的部分内容，并用c++11对其进行略微改写。

iterator的五种类型

上篇文章已经介绍了这五种类型的特征，它们只是为了激活重载机制而设定，并不需要其他成员。它们的定义如下：

//五种迭代器类型

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

接下来是iterator的定义：

//自造的iterator最好继承下面的std::iterator

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;

};

//萃取机Traits

//萃取出迭代器的特性

template<typename Iterator>

struct iterator_traits

{

    using iterator_category = typename Iterator::iterator_category;

    using value_type = typename Iterator::value_type;

    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 iterator_category = random_access_iterator_tag;

    using value_type = T;

    using difference_type = ptrdiff_t;

    using pointer = T*;

    using reference = T&;

};

//pointer-to-const

template<typename T>

struct iterator_traits<const T*>

{

    using iterator_category = random_access_iterator_tag;

    using value_type = T;

    using difference_type = ptrdiff_t;

    using pointer = const T*;

    using reference = const T&;

};

//确定某个迭代器类型,并返回该类型的一个迭代器对象，方便进行函数重载

template<typename Iterator>

inline typename iterator_traits<Iterator>::iterator_category

iterator_category(const Iterator&)

{

    using category = typename iterator_traits<Iterator>::iterator_category;

    return category();

}

//确定某个迭代器的distance type

template<typename Iterator>

inline typename iterator_traits<Iterator>::difference_type*

distance_type(const Iterator&)

{

    return static_cast<typename iterator_traits<Iterator>::difference_type*>(nullptr);

}

//确定某个迭代器的value type

template<typename Iterator>

inline typename iterator_traits<Iterator>::value_type*

value_type(const Iterator&)

{

    return static_cast<typename iterator_traits<Iterator>::value_type*>(nullptr);

}

//整个distance函数的实现,第三个参数只是激活重载机制，无其他用处

template<typename InputIterator>

inline typename iterator_traits<InputIterator>::difference_type

_distance(InputIterator first, InputIterator last, input_iterator_tag)

{

    typename iterator_traits<InputIterator>::difference_type n = 0;

    while(first != last)

    {

        ++first;

        ++n;

    }

}

template<typename RandomAccessIterator>

inline typename iterator_traits<RandomAccessIterator>::difference_type

_distance(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)

{

    //先利用traits确定迭代器的类型

    using category = typename iterator_traits<InputIterator>::iterator_category;

    //利用函数重载,第三个参数只是激活重载机制，无其他用处

    _distance(first, last, category());

}

//整个advance函数的实现，第三个参数只是激活重载机制，无其他用处

template<typename InputerIterator, typename Distance>

inline void _advance(InputerIterator& i, Distance n, input_iterator_tag)

{

    while(n--) ++i;

}

template<typename BidirectionalIterator, typename Distance>

inline void _advance(BidirectionalIterator i, Distance n, bidirectional_iterator_tag)

{

    if(n >= 0)

        while(n--) ++i;

    else

        while(n++) --i;

}

template<typename RandomAccessIterator, typename Distacne>

inline void _advance(RandomAccessIterator& i, Distacne n, random_access_iterator_tag)

{

    i += n;

}

//对外接口,适应不同类型的迭代器

template<typename InputIterator, typename Distance>

inline void advance(InputIterator& i , Distance n)

{

    _advance(i, n, iterator_category(i));

}

#endif //STL_ITERATOR_H

巴特西

STL之iterator源码解析

摘要

iterator的五种类型

最新文章

热门文章