5.5 Iterator Tags

Every iterator i must have an expression iterator_tag(i) defined, which returns the most specific category tag that describes its behaviour.

The available iterator tags are: input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iteerator_tag, random_access_iterator_tag.

The most specific iterator tag of a built in pointer would be the random access iterator tag.

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

A user defined iterator which satisfies, for example, the requirements of a bidirectional iterator can be included into the bidirectional iterator category.

template <class T>
inline bidirectional_iterator_tag iterator_category (const MyIterator<T>&) {
	return bidirectional_iterator_tag();
}

Iterator tags are used as "compile time tags for algorithm selection", [2], 5.6. They enable the compiler to use the most efficient algorithm at compile time.

Imagine the template function binary_search which could be designed to work with bidirectional iterators as well as with random access iterators. To use the tag mechanism, the two algorithms should be implemented as follows:

template<class BidirectionalIterator, class T>
BidirectionalIterator binary_search (BidirectionalIterator first,
                                     BidirectionalIterator last,
                                     const T& value,
                                     bidirectional_iterator_tag) {
	// more generic, but less efficient algorithm
}

template<class RandomAccessIterator, class T>
RandomAccessIterator binary_search (RandomAccessIterator first,
                                    RandomAccessIterator last,
                                    const T& value,
                                    random_access_iterator_tag) {
	// more efficient, but less generic algorithm
}

To use binary_search, a kind of stub function has to be written:

template<class BidirectionalIterator, class T>
inline BidirectionalIterator binary_search (BidirectionalIterator first,
                                            BidirectionalIterator last,
                                            const T& value) {
        binary_search (first, last, value, iterator_category(first));
}

At compile time, the compiler will choose the most efficient version of binary_search. The tag mechanism is fully transparent to the user of binary_search.

Continue with section 5.6

Back to index