CONTENTS
备注:
本读书笔记基于侯捷先生的《STL源码剖析》,截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL,部分代码删除了头部的版权注释,但代码版权属于原作者。
小弟初看stl,很多代码都不是太懂,注释可能有很多错误,还请路过的各位大牛多多给予指导。
备注:作者语文学的不好,这部分的注释写的乱七八糟的,可以参考《STL源码剖析》的3.3节的内容来详细解释。
stl_iterator_base_types.h
根据include文件包含,我们首先看下stl_iterator_base_types.h,删掉了头部的版权注释。
//在std命名空间中 _GLIBCXX_BEGIN_NAMESPACE(std) /** * @defgroup iterators Iterators * Abstractions for uniform iterating through various underlying types. */ //@{ //iterator的各种标签,具体的定义可以参考《STL源码剖析》3.4.5章节 /** * @defgroup iterator_tags Iterator Tags * These are empty types, used to distinguish different iterators. The * distinction is not made by what they contain, but simply by what they * are. Different underlying algorithms can then be used based on the * different operations supported by different iterator types. */ //@{ /// Marking input iterators. struct input_iterator_tag { }; /// Marking output iterators. struct output_iterator_tag { }; /// Forward iterators support a superset of input iterator operations. struct forward_iterator_tag : public input_iterator_tag { }; /// Bidirectional iterators support a superset of forward iterator /// operations. struct bidirectional_iterator_tag : public forward_iterator_tag { }; /// Random-access iterators support a superset of bidirectional /// iterator operations. struct random_access_iterator_tag : public bidirectional_iterator_tag { }; //@} /** * @brief Common %iterator class. * * This class does nothing but define nested typedefs. %Iterator classes * can inherit from this class to save some work. The typedefs are then * used in specializations and overloading. * * In particular, there are no default implementations of requirements * such as @c operator++ and the like. (How could there be?) */ //首先定义一个模板结构体,名字为iterator,内部有5个typdef。 template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t, typename _Pointer = _Tp*, typename _Reference = _Tp&> struct iterator { /// One of the @link iterator_tags tag types@endlink. typedef _Category iterator_category; /// The type "pointed to" by the iterator. typedef _Tp value_type; /// Distance between iterators is represented as this type. typedef _Distance difference_type; /// This type represents a pointer-to-value_type. typedef _Pointer pointer; /// This type represents a reference-to-value_type. typedef _Reference reference; }; /** * @brief Traits class for iterators. * * This class does nothing but define nested typedefs. The general * version simply @a forwards the nested typedefs from the Iterator * argument. Specialized versions for pointers and pointers-to-const * provide tighter, more correct semantics. */ //“萃取” //首先定义一个结构体模板,将上述的iterator的typedef再次typedef出来。 template<typename _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; }; //特化版本,如果_Tp为原生指针(比如 int *),那么其内部就没有value_type,于是将 //value_type 通过typedef再次定义为_Tp(比如 int) /// Partial specialization for pointer types. template<typename _Tp> struct iterator_traits<_Tp*> { typedef random_access_iterator_tag iterator_category; typedef _Tp value_type; typedef ptrdiff_t difference_type; typedef _Tp* pointer; typedef _Tp& reference; }; //特化版本,如果_Tp为原生常量指针,在上述特化版本的基础上,需要继续考虑, //因为value_type并不是常量(比如_Tp是 const int *,那么它的type其实是int,而不是const int) /// Partial specialization for const pointer types. template<typename _Tp> struct iterator_traits<const _Tp*> { typedef random_access_iterator_tag iterator_category; typedef _Tp value_type; typedef ptrdiff_t difference_type; typedef const _Tp* pointer; typedef const _Tp& reference; }; /** * This function is not a part of the C++ standard but is syntactic * sugar for internal library use only. */ template<typename _Iter> inline typename iterator_traits<_Iter>::iterator_category __iterator_category(const _Iter&) { return typename iterator_traits<_Iter>::iterator_category(); } //@} _GLIBCXX_END_NAMESPACE #endif /* _STL_ITERATOR_BASE_TYPES_H */
stl_iterator_base_funcs.h
部分代码注释如下,去掉了头部的版权注释。
//使用std命名空间 _GLIBCXX_BEGIN_NAMESPACE(std) //计算两个iterator之间的距离。 template<typename _InputIterator> inline typename iterator_traits<_InputIterator>::difference_type __distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)//Iterator的tag为input_iterator_tag。 { // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) typename iterator_traits<_InputIterator>::difference_type __n = 0; while (__first != __last) {//采用循环累加计算方式来获取两个iterator间的距离(参考链表) ++__first; ++__n; } return __n; } //计算两个iterator之间的距离。 template<typename _RandomAccessIterator> inline typename iterator_traits<_RandomAccessIterator>::difference_type __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)//Iterator的tag为random_access_iterator_tag。 { // concept requirements __glibcxx_function_requires(_RandomAccessIteratorConcept< _RandomAccessIterator>) return __last - __first;//如果是iterator支持随机读取,那么两个iterator间的距离很好计算 //直接相减即可(参考数组) } /** * @brief A generalization of pointer arithmetic. * @param first An input iterator. * @param last An input iterator. * @return The distance between them. * * Returns @c n such that first + n == last. This requires that @p last * must be reachable from @p first. Note that @c n may be negative. * * For random access iterators, this uses their @c + and @c - operations * and are constant time. For other %iterator classes they are linear time. */ //计算两个iterator之间的距离,根据iterator的tag来调动上述的哪个函数 template<typename _InputIterator> inline typename iterator_traits<_InputIterator>::difference_type distance(_InputIterator __first, _InputIterator __last) { // concept requirements -- taken care of in __distance return std::__distance(__first, __last, std::__iterator_category(__first)); } //将iterator向前递增__n个距离 template<typename _InputIterator, typename _Distance> inline void __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) {//iterator的tag为input_iterator_tag。 // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) while (__n--) ++__i;//通过循环累加的方式使iterator向前递增 } //将iterator向前递增__n个距离 template<typename _BidirectionalIterator, typename _Distance> inline void __advance(_BidirectionalIterator& __i, _Distance __n, bidirectional_iterator_tag)//iterator的tag为bidirectional_iterator_tag。 { //由于iterator的tag为bidirectional_iterator_tag,因此可以双向移动,那么__n可以为负数 // concept requirements __glibcxx_function_requires(_BidirectionalIteratorConcept< _BidirectionalIterator>) if (__n > 0) while (__n--) ++__i; else while (__n++) --__i; } //将iterator向前递增__n个距离 template<typename _RandomAccessIterator, typename _Distance> inline void __advance(_RandomAccessIterator& __i, _Distance __n, random_access_iterator_tag)//iterator的tag为random_access_iterator_tag。 { // concept requirements __glibcxx_function_requires(_RandomAccessIteratorConcept< _RandomAccessIterator>) __i += __n;//iterator支持随机读取,直接相加即可。 } /** * @brief A generalization of pointer arithmetic. * @param i An input iterator. * @param n The @a delta by which to change @p i. * @return Nothing. * * This increments @p i by @p n. For bidirectional and random access * iterators, @p n may be negative, in which case @p i is decremented. * * For random access iterators, this uses their @c + and @c - operations * and are constant time. For other %iterator classes they are linear time. */ //将iterator向前递增__n个距离,根据iterator的tag,来调用上述的不同版本的函数 template<typename _InputIterator, typename _Distance> inline void advance(_InputIterator& __i, _Distance __n) { // concept requirements -- taken care of in __advance typename iterator_traits<_InputIterator>::difference_type __d = __n; std::__advance(__i, __d, std::__iterator_category(__i)); } _GLIBCXX_END_NAMESPACE
发表评论