[历史归档]本文原发布于 cstriker1407.info 个人博客内容为历史存档仅供参考。发布时间2014-06-19 标题C STL 读书笔记iterator分类编程 / C C / C STL 标签CC·stl·iteratorC STL 读书笔记iterator备注stl\_iterator\_base\_types.hstl\_iterator\_base\_funcs.h备注本读书笔记基于侯捷先生的《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.structinput_iterator_tag{};/// Marking output iterators.structoutput_iterator_tag{};/// Forward iterators support a superset of input iterator operations.structforward_iterator_tag:publicinput_iterator_tag{};/// Bidirectional iterators support a superset of forward iterator/// operations.structbidirectional_iterator_tag:publicforward_iterator_tag{};/// Random-access iterators support a superset of bidirectional/// iterator operations.structrandom_access_iterator_tag:publicbidirectional_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。templatetypename_Category,typename_Tp,typename_Distanceptrdiff_t,typename_Pointer_Tp*,typename_Reference_Tpstructiterator{/// One of the link iterator_tags tag typesendlink.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出来。templatetypename_Iteratorstructiterator_traits{typedeftypename_Iterator::iterator_category iterator_category;typedeftypename_Iterator::value_type value_type;typedeftypename_Iterator::difference_type difference_type;typedeftypename_Iterator::pointer pointer;typedeftypename_Iterator::reference reference;};//特化版本如果_Tp为原生指针比如 int *那么其内部就没有value_type于是将//value_type 通过typedef再次定义为_Tp比如 int/// Partial specialization for pointer types.templatetypename_Tpstructiterator_traits_Tp*{typedefrandom_access_iterator_tag iterator_category;typedef_Tp value_type;typedefptrdiff_t difference_type;typedef_Tp*pointer;typedef_Tpreference;};//特化版本如果_Tp为原生常量指针在上述特化版本的基础上需要继续考虑//因为value_type并不是常量比如_Tp是 const int *那么它的type其实是int而不是const int/// Partial specialization for const pointer types.templatetypename_Tpstructiterator_traitsconst_Tp*{typedefrandom_access_iterator_tag iterator_category;typedef_Tp value_type;typedefptrdiff_t difference_type;typedefconst_Tp*pointer;typedefconst_Tpreference;};/** * This function is not a part of the C standard but is syntactic * sugar for internal library use only. */templatetypename_Iterinlinetypenameiterator_traits_Iter::iterator_category__iterator_category(const_Iter){returntypenameiterator_traits_Iter::iterator_category();}//}_GLIBCXX_END_NAMESPACE#endif/* _STL_ITERATOR_BASE_TYPES_H */stl_iterator_base_funcs.h部分代码注释如下去掉了头部的版权注释。//使用std命名空间_GLIBCXX_BEGIN_NAMESPACE(std)//计算两个iterator之间的距离。templatetypename_InputIteratorinlinetypenameiterator_traits_InputIterator::difference_type__distance(_InputIterator __first,_InputIterator __last,input_iterator_tag)//Iterator的tag为input_iterator_tag。{// concept requirements__glibcxx_function_requires(_InputIteratorConcept_InputIterator)typenameiterator_traits_InputIterator::difference_type __n0;while(__first!__last){//采用循环累加计算方式来获取两个iterator间的距离参考链表__first;__n;}return__n;}//计算两个iterator之间的距离。templatetypename_RandomAccessIteratorinlinetypenameiterator_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来调动上述的哪个函数templatetypename_InputIteratorinlinetypenameiterator_traits_InputIterator::difference_typedistance(_InputIterator __first,_InputIterator __last){// concept requirements -- taken care of in __distancereturnstd::__distance(__first,__last,std::__iterator_category(__first));}//将iterator向前递增__n个距离templatetypename_InputIterator,typename_Distanceinlinevoid__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个距离templatetypename_BidirectionalIterator,typename_Distanceinlinevoid__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(__n0)while(__n--)__i;elsewhile(__n)--__i;}//将iterator向前递增__n个距离templatetypename_RandomAccessIterator,typename_Distanceinlinevoid__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来调用上述的不同版本的函数templatetypename_InputIterator,typename_Distanceinlinevoidadvance(_InputIterator__i,_Distance __n){// concept requirements -- taken care of in __advancetypenameiterator_traits_InputIterator::difference_type __d__n;std::__advance(__i,__d,std::__iterator_category(__i));}_GLIBCXX_END_NAMESPACE