Node:Examples of using iterator tags, Next:Library defined primitives, Previous:Iterator tags, Up:Iterator tags

Examples of using iterator tags

For all the regular pointer types we can define value_type and distance_type with the help of:

template 
inline T* value_type(const T*) { return (T*)(0); }

template 
inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }

Then, if we want to implement a generic reverse function, we do the following:

template 
inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
    __reverse(first, last, value_type(first), distance_type(first));
}

where __reverse is defined as:

template 
void __reverse(BidirectionalIterator first, BidirectionalIterator last, T*,
               Distance*) {
    Distance n;
    distance(first, last, n); // see Iterator operations section
    --n;
    while (n > 0) {
        T tmp = *first;
        *first++ = *--last;
        *last = tmp;
        n -= 2;
    }
}

If there is an additional pointer type __huge such that the difference of two __huge pointers is of the type long long, we define:

template 
inline T* value_type(const T __huge *) { return (T*)(0); }

template 
inline long long* distance_type(const T __huge *) { return (long long*)(0); }

input_iterator_tag	Tag
output_iterator_tag	Tag
forward_iterator_tag	Tag
bidirectional_iterator_tag	Tag
random_access_iterator_tag	Tag

It is often desirable for a template function to find out what is the most specific category of its iterator argument, so that the function can select the most efficient algorithm at compile time. To facilitate this, the library introduces category tag classes which are used as compile time tags for algorithm selection. They are: input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag and random_access_iterator_tag.

iterator_category (const iterator_type&)

Function

Every iterator i must have an expression iterator_category(i) defined on it that returns the most specific category tag that describes its behavior. For example, we define that all the pointer types are in the random access iterator category by:

template 
inline random_access_iterator_tag iterator_category(const T*) {
    return random_access_iterator_tag();
}

For a user-defined iterator BinaryTreeIterator, it can be included into the bidirectional iterator category by saying:

template 
inline bidirectional_iterator_tag iterator_category(
        const BinaryTreeIterator&) {
    return bidirectional_iterator_tag();
}

If a template function evolve is well defined for bidirectional iterators, but can be implemented more efficiently for random access iterators, then the implementation is like:

template 
inline void evolve(BidirectionalIterator first, BidirectionalIterator last) {
    evolve(first, last, iterator_category(first));
}

template 
void evolve(BidirectionalIterator first, BidirectionalIterator last,
            bidirectional_iterator_tag) {
    // ... more generic, but less efficient algorithm
}

template 
void evolve(RandomAccessIterator first, RandomAccessIterator last,
            random_access_iterator_tag) {
    // ... more efficient, but less generic algorithm
}