[analysis of STL source code] summary notes (6): Design of iterator and magical traits

【STL Source analysis 】 Summary notes （6）：iterator Design and magic traits

00 Write it at the front

Last time we started list Starting with , Illustrates the list Of iterator Cleverness in the implementation process .link

And this is also iterator The key to design .

01 iterator and traits

iterator It's a pointer like object , We are learning about list in iterator In the process of implementation, we will find , Want to design list Of iterator, You need to be right about list Very familiar with the implementation structure of . So put list iterator The development of the project was entrusted to list Designer , That's why everyone STL All containers have their own iterators .

But if we stand higher , Can the algorithm get a certain type of feature ？ At this time traits It's useful .

traits Is a clever programming technique , We also call it “ Extractor ”. All types traits, Used to extract this type of feature .

Before we begin the description , Let's start with list Of iterator Starting with , Take a look at the details that have been overlooked .

02 associated types

In the first article we said , iterator （iterator） It's a container （containers） Sum algorithm （algorithms） The bridge . Algorithms ask questions , Finding the answer is left to the iterator .

iterators Must be able to answer algorithms The question of , And in the C++ During the development of the standard library , There are five types of such questions (associated types)：

( That's the front list The five mentioned )

template <class T,class Ref,class Ptr>
struct _list_iterator{
    
	typedef bidirectional_iterator_tag iterator_category;//1
    typedef T value_type;//2
	typedef ptrdiff_t defference_type;//3
    typedef Ptr pointer;//4
    typedef Ref reference;//5
    ...
}

1. Types of iterators . It can be understood that some iterators can only ++, Some can only –, Some can walk three spaces in one step and so on .bidirectional_iterator_tag Description is a two-way linked list
2. The type of the element pointed to by the iterator
3. The distance between iterators , It is also the maximum capacity of a container （ Continuous space ）
4. Not yet used
5. Not yet used

In fact, this question and answer mechanism is actually based on template Parameter derivation mechanism to obtain different solutions .

But if iterator Is not a class, Just a normal pointer （ Regarded as degraded iterator）, Can't you answer these questions ？

03 traits The magic effect of

Now traits That comes in handy .iterator traits It solved the problem well .

iterator traits That's it “ Extractor ” You must distinguish what you receive iterator yes class Of iterator It's normal iterator

The extractor is like an intermediate layer , Then proceed to the next step through its judgment , Instead of the algorithm directly to iterator Want answers .

04 Partial specialization

traits The focus of the implementation of is actually partial specialization （partial specialization）, It means for any template Parameters further restrict the design of a specific version .

for instance ：

template <class T>
struct iterator_traits{
    
    typedef typename I::value_type value_type;
};


// Partial specialized version 
template <class T>
struct iterator_traits<T*>{
    
    typedef T value_type;
};

template <class T>
struct iterator_traits<const T*>{
    
    typedef T value_type;
};

When you need to know I Of value type when ：

template <typename I,...>
void algorithm(...){
    
    typename iterator_traits<I>::value_type v1;
}

1. If I yes class iterator, Then you will enter the first , That is, the question and answer session we mentioned earlier .
2. If I It's a pointer or a pointer const The pointer to , Then you will enter the partial specialization version , Answer the question directly , return T by value type
3. Why pointers and points to const All the pointers of the return are T Well ？ because value type It is mainly used to declare variables , If you add const It's no use if it can't be assigned .

Then several other problems can be solved .

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

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 T>
struct iterator_traits<const T*>{
    
    typedef random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef const T* pointer;
    typedef const T& reference;
};

05 Elaborate on the five types

So far we have mastered traits The essence of , But only for the time being iterator traits. The five types also have certain contents .

value_type

The type of object the iterator refers to ,

### difference_type

Represents the distance between two iterators . It is also the maximum capacity of a container （ Continuous space ）.

The value returned by the counting function of the generic algorithm must use difference_type;

### reference

If we start from the angle of whether the object referred to by the iterator can be changed , Can be divided into those that cannot change the content of the object constant iterators And can change the content of the object mutable iterators.

Yes mutable iterators To dereference , What you get is an lvalue （ May change ）

Yes constant iterators To dereference , You get the right value （ It can't be changed ）

When p yes mutable iterators when ,*p The type of T&

When p yes constant iterators when ,*p The type of const T&

### pointer

Since we can return an lvalue , Make it stand for p Object referred to , Then it must be possible to return an lvalue , Make it stand for p The address of the object referred to .

### iterator_category

According to the movement characteristics and operation , Iterators are divided into the following categories ：

• input iterator： The object is not allowed to be changed , Is read-only .
• output iterator： Just write
• forward iterator： allow “ Write type ” Algorithm , Read and write on the interval formed by this iterator .
• bidirectional iterator： It can move in both directions , Use when you need to backtrack iterator intervals .
• random access iterator： The first four only provide part of the arithmetic ability , For example, the first three types of support operator++, The fourth support operator–, The last one covers all arithmetic skills .

It should be noted that ：

The classification here is actually a process of continuous reinforcement , Try to provide a clear definition of an iterator in the design , Maximize efficiency in different situations .

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-VKbFdLcy-1635937254996)(https://i.loli.net/2021/10/27/S7B1eKqGkfFrHsZ.png#alt=PNG%E5%9B%BE%E5%83%8F%2014)]

For example, the algorithm is acceptable forward iterator, that random access iterator Of course, it's also possible , But it's not the best .

Take a good example advance() Implementation examples to illustrate ：

advance() There are two parameters , iterator p And numbers n. Role is to p Progressive n Time , That is to move forward n.

Let's first implement three versions of advence():

template <class InputIterator,class Distance>// in the light of InputIterator Version of 
void advance_II(InputIterator& i,Distance n){
    
    while(n--)++i;
}

template <class BidirectionalIterator,class Distance>// in the light of BidirectionalIterator Version of 
void advance_BI(BidirectionalIterator& i,Distance n){
    
    if(n>=0)
        while(n--)++i;
    else
        while(n++)--i;
}

template <class RandomAccessIterator,class Distance>// in the light of RandomAccessIterator Version of 
void advance_RAI(RandomAccessIterator& i,Distance n){
    
    i+=n;
}

The above implements three versions of advance(),（fowarditerator and inputiterator equally ）

Now there is a problem when calling this function , That is the definition of which version to use .

InputIterator The version of is not as efficient as RandomAccessIterator The version of （O（n） and O（1））

however RandomAccessIterator Version of is not acceptable InputIterator

Want to combine the three effectively , You can use function overloading . If you use traits You can get the type of iterator , Then we can use it as the third parameter to implement the overload .（ Of course, this parameter needs to be a class type, Overloading can only be realized by different types ）

So let's design five tag classes （ No members ）

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

And redesign advance()

template <class InputIterator,class Distance>
void _advance(InputIterator& i,Distance n,input_iterator_tag){
    
    while(n--)++i;
}

template <class ForwardIterator,class Distance>
void _advance(ForwardIterator& i,Distance n,forward_iterator_tag){
    
    _advance(i,n,input_iterator_tag());// Simply used to pass calling functions 
}

template <class BidirectionalIterator,class Distance>
void _advance(BidirectionalIterator& i,Distance n,bidirectional_iterator_tag){
    
    if(n>=0)
        while(n--)++i;
    else
        while(n++)--i;
}

template <class RandomAccessIterator,class Distance>
void _advance(RandomAccessIterator& i,Distance n,random_access_iterator_tag){
    
    i+=n;
}

At this time, an upper interface is required , But the upper interface only needs two parameters , To _advance() The third parameter will be added .

So the derivation of types is left to traits Mechanism .

template <class InputIterator,class Distance>
inline void advance(InputIterator& i,Distance n)
{
    
    _advance(i,n,iterator_traits<InputIterator>::iterator_category());
}

there iterator_traits The design of is consistent with what we said above in partial specialization .

template <class Iterator>
struct iterator_traits{
    
    typedef typename Iterator::iterator_category iterator_category;
};

template <class T>
struct iterator_traits<T*>{
    
    typedef random_access_iterator_tag iterator_category;
};

template <class T>
struct iterator_traits<const T*>{
    
    typedef random_access_iterator_tag iterator_category;
};

Native pointer and native pointer const The pointer to is a kind of random access iterator

tips：

1. It should be noted that advance() Of template The name is InputIterator, This is actually STL Algorithm naming conventions ： Name the type parameter with the lowest order iterator that the algorithm can accept .

2. Use class There is another benefit to being a label for iterator classification , It is a function that can eliminate the simple passing of calls . For example, we designed a forward_iterator_tag, Its content is similar to input_iterator_tag There's no difference .
   In fact, the inheritance relationship we have set can be omitted forward_iterator_tag, When the parameters do not match, the call is automatically passed , That's it input_iterator_tag.
   
   

06 summary

iterator traits The design method of is really amazing . In fact, there are many traits, such as type traits, Are designed according to this idea “ Extractor for extraction characteristics ”.

This time we mainly master iterator traits The design method of , Know five associated types. At the same time through advance() The example of shows how the algorithm and iterator are passed through traits Ask and answer .