[std.iterator.tags]

# 24 Iterators library [[iterators]](./#iterators)

## 24.4 Iterator primitives [[iterator.primitives]](iterator.primitives#std.iterator.tags)

### 24.4.2 Standard iterator tags [std.iterator.tags]

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2744)

It is often desirable for a
function template specialization
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[.](#1.sentence-1)

To facilitate this, the
library introduces[*category tag*](#def:category_tag "24.4.2 Standard iterator tags [std.iterator.tags]") classes which are used as compile time tags for algorithm selection[.](#1.sentence-2)

They are:output_iterator_tag,input_iterator_tag,forward_iterator_tag,bidirectional_iterator_tag,random_access_iterator_tag,
andcontiguous_iterator_tag[.](#1.sentence-3)

For every iterator of typeI,iterator_traits<I>​::​iterator_category shall be defined to be a category tag that describes the
iterator's behavior[.](#1.sentence-4)

Additionally,iterator_traits<I>​::​iterator_concept may be used to indicate conformance to
the iterator concepts ([[iterator.concepts]](iterator.concepts "24.3.4 Iterator concepts"))[.](#1.sentence-5)

namespace std {struct output_iterator_tag { }; struct input_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 { }; struct contiguous_iterator_tag: public random_access_iterator_tag { };}

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2788)

[*Example [1](#example-1)*:

A program-defined iterator BinaryTreeIterator can be included into the bidirectional iterator category by
specializing the iterator_traits template:template<class T> struct iterator_traits<BinaryTreeIterator<T>> {using iterator_category = bidirectional_iterator_tag; using difference_type = ptrdiff_t; using value_type = T; using pointer = T*; using reference = T&;};

â *end example*]

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2804)

[*Example [2](#example-2)*:

Ifevolve() is well-defined for bidirectional iterators, but can be implemented more
efficiently for random access iterators, then the implementation is as follows:template<class BidirectionalIterator>inline void evolve(BidirectionalIterator first, BidirectionalIterator last) { evolve(first, last, typename iterator_traits<BidirectionalIterator>::iterator_category());}template<class BidirectionalIterator>void evolve(BidirectionalIterator first, BidirectionalIterator last,
 bidirectional_iterator_tag) {// more generic, but less efficient algorithm}template<class RandomAccessIterator>void evolve(RandomAccessIterator first, RandomAccessIterator last,
 random_access_iterator_tag) {// more efficient, but less generic algorithm}

â *end example*]
