Proposed resolution:

Change [depr.lib.iterator.primitives], Iterator primitives, as indicated:

To simplify the use of iterators and provide backward compatibility with previous C++ Standard Libraries, the library provides several classes and functions. Unless otherwise specified, these classes and functions shall be defined in header <iterator>.

Change [iterator.backward], Iterator backward compatibility, as indicated:

The library provides concept maps that allow iterators specified with iterator_traits to interoperate with algorithms that require iterator concepts. These concept maps shall be defined in the same header that defines the iterator. [Example:

[ 2009-07 Frankfurt ]

We believe this is NAD Concepts, but this needs to be reviewed against the post-remove-concepts draft.

[ Batavia (2009-05): ]

We agree with the direction of the proposed resolution. Move to Tentatively Ready.

Which header must a user #include to obtain the library-supplied concept_maps declared in this paragraph?

This is important information, as existing user code will break if this header is not included, and we should make a point of mandating this header is #include-d by library headers likely to make use of it, notably <algorithm>. See issue 1001 for more details.