cppdraft_translate/cppdraft/iterator/requirements/general.md

[iterator.requirements.general]

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

## 24.3 Iterator requirements [[iterator.requirements]](iterator.requirements#general)

### 24.3.1 General [iterator.requirements.general]

[1](#1)

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

Iterators are a generalization of pointers that allow a C++ program to work with different data structures
(for example, containers and ranges) in a uniform manner[.](#1.sentence-1)

To be able to construct template algorithms that work correctly and
efficiently on different types of data structures, the library formalizes not just the interfaces but also the
semantics and complexity assumptions of iterators[.](#1.sentence-2)

An input iteratori supports the expression*i,
resulting in a value of some object typeT,
called the[*value type*](#def:value_type "24.3.1 General [iterator.requirements.general]") of the iterator[.](#1.sentence-3)

An output iterator i has a non-empty set of types that are[*writable*](#def:writable "24.3.1 General [iterator.requirements.general]") to the iterator;
for each such type T, the expression *i = o is valid where o is a value of type T[.](#1.sentence-4)

For every iterator typeX,
there is a corresponding signed integer-like type ([[iterator.concept.winc]](iterator.concept.winc "24.3.4.4 Concept weakly_­incrementable")) called the[*difference type*](#def:difference_type "24.3.1 General [iterator.requirements.general]") of the iterator[.](#1.sentence-5)

[2](#2)

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

Since iterators are an abstraction of pointers, their semantics are
a generalization of most of the semantics of pointers in C++[.](#2.sentence-1)

This ensures that every
function template
that takes iterators
works as well with regular pointers[.](#2.sentence-2)

This document defines
six categories of iterators, according to the operations
defined on them:[*input iterators*](#def:input_iterators),[*output iterators*](#def:output_iterators),[*forward iterators*](#def:forward_iterators),[*bidirectional iterators*](#def:bidirectional_iterators),[*random access iterators*](#def:random_access_iterators),
and[*contiguous iterators*](#def:contiguous_iterators),
as shown in Table [77](#tab:iterators.relations "Table 77: Relations among iterator categories")[.](#2.sentence-3)

Table [77](#tab:iterators.relations) — Relations among iterator categories [[tab:iterators.relations]](./tab:iterators.relations)  

| [🔗](#tab:iterators.relations-row-1)<br>**Contiguous** | → **Random Access** | → **Bidirectional** | → **Forward** | → **Input** |
| --- | --- | --- | --- | --- |
| [🔗](#tab:iterators.relations-row-2) |  |  |  | → **Output** |

[3](#3)

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

The six categories of iterators correspond to the iterator concepts

- [(3.1)](#3.1)

[input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_­iterator [iterator.concept.input]") ([[iterator.concept.input]](iterator.concept.input "24.3.4.9 Concept input_­iterator")),

- [(3.2)](#3.2)

[output_iterator](iterator.concept.output#concept:output_iterator "24.3.4.10 Concept output_­iterator [iterator.concept.output]") ([[iterator.concept.output]](iterator.concept.output "24.3.4.10 Concept output_­iterator")),

- [(3.3)](#3.3)

[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") ([[iterator.concept.forward]](iterator.concept.forward "24.3.4.11 Concept forward_­iterator")),

- [(3.4)](#3.4)

[bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") ([[iterator.concept.bidir]](iterator.concept.bidir "24.3.4.12 Concept bidirectional_­iterator")),

- [(3.5)](#3.5)

[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") ([[iterator.concept.random.access]](iterator.concept.random.access "24.3.4.13 Concept random_­access_­iterator")),
and

- [(3.6)](#3.6)

[contiguous_iterator](iterator.concept.contiguous#concept:contiguous_iterator "24.3.4.14 Concept contiguous_­iterator [iterator.concept.contiguous]") ([[iterator.concept.contiguous]](iterator.concept.contiguous "24.3.4.14 Concept contiguous_­iterator")),

respectively[.](#3.sentence-1)

The generic term [*iterator*](#def:iterator "24.3.1 General [iterator.requirements.general]") refers to any type that models the[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") concept ([[iterator.concept.iterator]](iterator.concept.iterator "24.3.4.6 Concept input_­or_­output_­iterator"))[.](#3.sentence-2)

[4](#4)

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

Forward iterators meet all the requirements of input
iterators and can be used whenever
an input iterator is specified;
Bidirectional iterators also meet all the requirements of
forward iterators and can be used whenever a forward iterator is specified;
Random access iterators also meet all the requirements of bidirectional
iterators and can be used whenever a bidirectional iterator is specified;
Contiguous iterators also meet all the requirements of random access
iterators and can be used whenever a random access iterator is specified[.](#4.sentence-1)

[5](#5)

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

Iterators that further meet the requirements of output iterators are
called [*mutable iterators*](#def:mutable_iterator "24.3.1 General [iterator.requirements.general]")[.](#5.sentence-1)

Nonmutable iterators are referred to
as [*constant iterators*](#def:constant_iterator "24.3.1 General [iterator.requirements.general]")[.](#5.sentence-2)

[6](#6)

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

In addition to the requirements in this subclause,
the nested [*typedef-name*](dcl.typedef#nt:typedef-name "9.2.4 The typedef specifier [dcl.typedef]")*s* specified in [[iterator.traits]](iterator.traits "24.3.2.3 Iterator traits") shall be provided for the iterator type[.](#6.sentence-1)

[*Note [1](#note-1)*:

Either the iterator type must provide the [*typedef-name*](dcl.typedef#nt:typedef-name "9.2.4 The typedef specifier [dcl.typedef]")*s* directly
(in which case iterator_traits pick them up automatically), or
an iterator_traits specialization must provide them[.](#6.sentence-2)

— *end note*]

[7](#7)

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

Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element
of the array, so for any iterator type there is an iterator value that points past the last element of a
corresponding sequence[.](#7.sentence-1)

Such a value is called a [*past-the-end value*](#def:iterator,past-the-end "24.3.1 General [iterator.requirements.general]")[.](#7.sentence-2)

Values of an iterator i for which the expression *i is defined
are called [*dereferenceable*](#def:iterator,dereferenceable "24.3.1 General [iterator.requirements.general]")[.](#7.sentence-3)

The library never assumes that past-the-end values are dereferenceable[.](#7.sentence-4)

Iterators can also have singular values that are not associated with any
sequence[.](#7.sentence-5)

Results of most expressions are undefined for singular values;
the only exceptions are destroying an iterator that holds a singular value,
the assignment of a non-singular value to
an iterator that holds a singular value, and, for iterators that meet the*Cpp17DefaultConstructible* requirements, using a value-initialized iterator
as the source of a copy or move operation[.](#7.sentence-6)

[*Note [2](#note-2)*:

This guarantee is not
offered for default-initialization, although the distinction only matters for types
with trivial default constructors such as pointers or aggregates holding pointers[.](#7.sentence-7)

— *end note*]

In these cases the singular
value is overwritten the same way as any other value[.](#7.sentence-8)

Dereferenceable
values are always non-singular[.](#7.sentence-9)

[8](#8)

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

Most of the library's algorithmic templates that operate on data structures have
interfaces that use ranges[.](#8.sentence-1)

A [*range*](#def:range "24.3.1 General [iterator.requirements.general]") is an iterator and a [*sentinel*](#def:sentinel "24.3.1 General [iterator.requirements.general]") that designate the beginning and end of the computation, or an iterator and a
count that designate the beginning and the number of elements to which the
computation is to be applied[.](#8.sentence-2)[198](#footnote-198 "The sentinel denoting the end of a range can have the same type as the iterator denoting the beginning of the range, or a different type.")

[9](#9)

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

An iterator and a sentinel denoting a range are comparable[.](#9.sentence-1)

A range [i, s)
is empty if i == s;
otherwise, [i, s)
refers to the elements in the data structure starting with the element
pointed to byi and up to but not including the element, if any, pointed to by
the first iterator j such that j == s[.](#9.sentence-2)

[10](#10)

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

A sentinel s is called [*reachable from*](#def:reachable_from "24.3.1 General [iterator.requirements.general]") an iterator i if
and only if there is a finite sequence of applications of the expression++i that makes i == s[.](#10.sentence-1)

If s is reachable from i,
[i, s) denotes a [*valid range*](#def:range,valid "24.3.1 General [iterator.requirements.general]")[.](#10.sentence-2)

[11](#11)

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

A [*counted range*](#def:range,counted "24.3.1 General [iterator.requirements.general]") i+[0, n) is empty if n == 0;
otherwise, i+[0, n) refers to
the n elements in the data structure
starting with the element pointed to by i and up to but not including
the element, if any, pointed to by
the result of n applications of ++i[.](#11.sentence-1)

A counted range i+[0, n) is [*valid*](#def:range,counted,valid "24.3.1 General [iterator.requirements.general]") if and only if n == 0;
or n is positive, i is dereferenceable,
and ++i+[0, --n) is valid[.](#11.sentence-2)

[12](#12)

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

The result of the application of library functions
to invalid ranges is undefined[.](#12.sentence-1)

[13](#13)

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

For an iterator i of a type that
models [contiguous_iterator](iterator.concept.contiguous#concept:contiguous_iterator "24.3.4.14 Concept contiguous_­iterator [iterator.concept.contiguous]") ([[iterator.concept.contiguous]](iterator.concept.contiguous "24.3.4.14 Concept contiguous_­iterator")),
library functions are permitted
to replace [i, s) with
[to_address(i), to_address(i + ranges​::​distance(i, s))), and
to replace i+[0, n) with [to_address(i), to_address(i + n))[.](#13.sentence-1)

[*Note [3](#note-3)*:

This means a program cannot rely on any side effects of
dereferencing a contiguous iterator i,
because library functions might operate on
pointers obtained by to_address(i) instead of operating on i[.](#13.sentence-2)

Similarly, a program cannot rely on any side effects of
individual increments on a contiguous iterator i,
because library functions might advance i only once[.](#13.sentence-3)

— *end note*]

[14](#14)

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

All the categories of iterators require only those functions that are realizable for a given category in
constant time (amortized)[.](#14.sentence-1)

Therefore, requirement tables and concept definitions for the iterators
do not specify complexity[.](#14.sentence-2)

[15](#15)

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

Destruction of an iterator may invalidate pointers and references previously
obtained from that iterator if its type does not meet the*Cpp17ForwardIterator* requirements and does not model [forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]")[.](#15.sentence-1)

[16](#16)

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

An [*invalid iterator*](#def:iterator,invalid "24.3.1 General [iterator.requirements.general]") is an iterator that may be singular[.](#16.sentence-1)[199](#footnote-199 "This definition applies to pointers, since pointers are iterators. The effect of dereferencing an iterator that has been invalidated is undefined.")

[17](#17)

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

Iterators meet the [*constexpr iterators*](#def:iterator,constexpr "24.3.1 General [iterator.requirements.general]") requirements
if all operations provided to meet iterator category requirements
are constexpr functions[.](#17.sentence-1)

[*Note [4](#note-4)*:

For example, the types “pointer to int” andreverse_iterator<int*> meet the constexpr iterator requirements[.](#17.sentence-2)

— *end note*]

[198)](#footnote-198)[198)](#footnoteref-198)

The sentinel denoting the end of a range
can have the same type as the iterator denoting the beginning of the range, or a
different type[.](#footnote-198.sentence-1)

[199)](#footnote-199)[199)](#footnoteref-199)

This definition applies to pointers, since pointers are iterators[.](#footnote-199.sentence-1)

The effect of dereferencing an iterator that has been invalidated
is undefined[.](#footnote-199.sentence-2)