Learn STL Iterator, Traits Notes
Recently, I got a little gain of "STL source profile", and I also recorded my understanding of STL Iterator design, most of which came from the book. Welcome everyone to discuss with me, there is also a problem, I hope you can provide a valuable view!
I. Iterator recognizes if a set of universal containers is required, providing a unified algorithm, constructing the underlying data structure class library, Iterator design is undoubtedly very important. Iterator can facilitate the traversal of the container element, providing a unified parameter interface of the algorithm. How to say? First, let's consider an algorithm. Template ptrdiff_tdistance (T P1, T P2) {// Calculate distance between P1 and P2} Obviously this function wants to calculate the distance between two "locations". Here, "position" type T can be a (native) pointer to an element in an array, which may be a pointer to the chain table node, or any object used to record the location (for example, what we want to talk about Iterator). Regardless of these two locations, we must only designed a Distance function in the class, without having to have a different "location" in the design of the class library. Record mode, resulting in a number of such a Distance algorithm. Yes, we can completely abstract "position" concept, it is like a cursor, like a smart pointer, it can easily traverse the elements in the container, record the location, not to manage what type of container you root, this It is now the uTerator concept that is generally accepted by container designers.
II. Design of STL Iterator: Why don't you inherit the construct Iterator? The container abstract 5 Iterator type, Input <- Forward <- BidRectional <- random access iterator plus Output Iterator, can we design a few Iterator classes with inheritance relationships through the Refinement relationship? The Iterator class of each container then inherits these base classes. Then the above disatance function can design two versions PTRDIFF_T DISTANCE (InputITerator P1, INPUTITERATOR P2) {// InputIterator can only advance, such as linked list ptrdiff_t n = 0; while (p1! = P2) { P1; n;} return n;}
PTRDIFF_T DISTANCE (RandomaccessITERATOR P1) {// randomaccessItemrator can directly calculate the gap, such as array, Vector, etc. RETURN P2-P1;}
Does this seem to be feasible? But why does STL do not use this way? (Dear help me think, I am really a dish, I can't think of a good reason) I can think of: Iterator can be the type of native pointer, and the native pointer does not inherit the InputITOR class. (Is it still effective problem?)
Do not discuss why STL does not make this, or look at its beautiful handling method: First remind you, it uses the parameter derivation mechanism of function template (function template) to determine the function return value and parameter type.
(1) Through different Iterator concepts, do a few TAG classes that indicate the Iterator type. Input_iterator_tag <- forward_iterator_tag <- bidRectonal_Iterator_tag <- random_access_iterator_tag. There is Output_iterator_tag, these classes are empty, four inheritance relationships. (2) The Iterator class of the STL design requires a important type of typedef to indicate what type of Iterator is the TAG class in this item. For example, the iTerator class of list is: typedef bidRectonal_iterator_tag itrator_category; Another value_type type indicates what type of element is pointing. For example, the iTerator class of List is: typedef t value_type;
(3) Design Iterator_Traits class, this class is to extract the type of template parameter Iterator class. It is also implemented by TypeDef. As follows: Template struct iterator_traits {typedef typefetame itrator :: item_category itrator_category; typef type value ipy ;: value_type value_type; // .....};
In the second step, the Iterator class we designed has been able to sign the type through the Typedef alias, why should this intermediate conversion? The reason is usually we can write item :: itrator_category as a Typename, but if itrator is a native pointer T *, we write T * :: item_category can't get it. With Partial Specialization technology, you can specify and get the Iterator_category type of the native pointer by the intermediate layer iterator_traits, the code is as follows. (Such complex compilation technology, I really don't know what they are ... I can only see the Yang Xing 55)
Template struct itrator_traits {typef random_access_iterator_tag itrator_category; typef t value_type; // ........
(4) Envision to design an algorithm Template RET_TYPE GEN_FUN (Iterator P1, Iterator P2, ...). Usually such a process: template RET_TYPE gen_fun (Iterator p1, Iterator p2, ...) {typedef iterator_traits :: iterator_category category; typedef iterator_traits :: value_type type; // this type for the actual ITERATOR pointed to the object (* operator return type) __gen_fun (Iterator P1, Iterator P2, ..., category ());} category () constructs a temporary variable of an Iterator_TAG type, which is only used Distinguish the call function and do not participate in the actual algorithm implementation. The specific implementation method is as follows: (note that the last parameter is not used)
Template RET_TYPE __GEN_FUN (Iterator P1, Iterator P2, ..., Input_iterator_tag) actual implementation method / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / > RET_TYPE __GEN_FUN (Iterator P1, Iterator P2, ..., BidRectonal_iterator_tag) {// BidRectonal_ITerator type actual implementation method}
Template RET_TYPE __GEN_FUN (Iterator P1, Iterator P2, ..., Random_Access_iterator_tag) {// random_access_iterator type actual implementation method}
This achieves the parameter type identification by defining the parameter derivation mechanism of the Iterator Tag and the function template, and achieving the ability of the Iterator class implementation of the construct inheritance relationship. And there is no inheritance requires that strict, and Typedef is the work that is completed when compiling, does not affect the program running speed. If you increase the type of typedef in Iterator, such as Pointer, etc., you can enhance the functionality of parameter type identification.
Also need to remind that, in STL code, if random_access_iterator type of method, which is usually written template RET_TYPE __gen_fun (RandomAccessIterator p1, RandomAccessIterator p2, ..., random_access_iterator_tag) is input_iterator type of method, it is usually written Template RET_TYPE __GEN_FUN (INPUTITERATOR P1, INPUTITERATOR P2, ..., Input_iterator_tag) However, don't be confused by the RandomaccessITerator and InputIterator here, they are just template parameters, and there is no inheritance relationship, and there is no such class! (I was confused for a long time: () nor I started to construct a set of Iterator classes for inheritance. The template parameter writes RandomaccessITerator to indicate that the RandomAccessTiterator type is random_access_iterator, it is written into T, Type, but it doesn't matter Only Iterator_Traits get iterator_tag to indicate the true type of Iterator. I think it is written, just to remind you to call the ITerator type of the function. III. Take a look at the beginning of the DISTANCE () algorithm actually implement:
template inline iterator_traits :: difference_type__distance (InputIterator first, InputIterator last, input_iterator_tag) {// input_iterator type of implementation, according to input_iterator_tag inheritance, forward_iterator // and bidrectonal_iterator will call this function to achieve. Iterator_traits :: Difference_type n = 0; while (first! = Last) { first; n;} return n;}
template inline iterator_traits :: difference_type__distance (RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {// random_access_iterator type implementations return last - first;}
template inline iterator_traits :: difference_type distance (InputIterator first, InputIterator last) {// version typedef typename iterator_traits user call :: iterator_category category; return __distance (first, last, category ()) The above code is selected from the SGI STL2.91.57 version, 3. * Code is more complicated, but the technical ideas of Iterator and Traits should be almost. 2004.11.10
