ConceptC++ Concept Web: Header

Concepts in the header <iterator>


Concept IteratorAssociatedTypes

concept IteratorAssociatedTypes<typename X> {
  typename value_type = X::value_type;
  typename difference_type = X::difference_type;
  typename reference = X::reference;
  typename pointer = X::pointer;
};

The IteratorAssociatedTypes concept houses all of the associated types used in the iterator concepts from the ConceptC++ Standard Library.


Concept InputIterator

concept InputIterator<typename X> 
  : IteratorAssociatedTypes, CopyConstructible, EqualityComparable {
 
  requires Assignable, SameType<Assignable::result_type, X&>;
 
  requires SignedIntegral,
           Convertible,
           Convertibleconst value_type*>;
 
  typename postincrement_result;
  requires Dereferenceable, 
           Convertible<Dereferenceable::reference, value_type>;
 
  pointer operator->(X);
  X& operator++(X&);
  postincrement_result operator++(X&, int);
  reference operator*(X);
 
  bool operator!=(X, X);
};

In the InputIterator concept, the term the domain of == is used in the ordinary mathematical sense to denote the set of values over which == is (required to be) defined. This set can change over time. Each algorithm places additional requirements on the domain of == for the iterator values it uses. These requirements can be inferred from the uses that algorithm makes of == and !=.
[ Example: the call find(a,b,x) is defined only if the value of a has the property p defined as follows: b has property p and a value i has property p if (*i==x) or if (*i!=x and ++i has property p). - end example ]

[ Note: For input iterators, a == b does not imply ++a == ++b. (Equality does not guarantee the substitution property or referential transparency.) Algorithms on input iterators should never attempt to pass through the same iterator twice. They should be single pass algorithms. These algorithms can be used with istreams as the source of the input data through the istream_iterator class. - end note ]

reference operator*(X a );

Requires: a is dereferenceable.

Remarks: If b is a value of type X, a == b and (a, b) is in the domain of == then *a is equivalent to *b.

pointer operator->(X a);

Requires: (*a ).m is well-defined


Concept OutputIterator

concept OutputIterator<typename X, typename Value> : CopyConstructible {
  typename value_type = Value;
  typename reference = X::reference;
 
  requires SameType,
           Assignable;
 
  typename postincrement_result;
  requires Dereferenceable,
           Convertibleconst X&>,
           Assignable<Dereferenceable::reference,
                      value_type>;
 
  reference operator*(X&);
  X& operator++(X& r);
  postincrement_result operator++(X& r, int);
};

The OutputIterator concept describes an output iterator that may permit output of many different value types.

X& operator++(X& r);

Postcondition: &r == &++r.

postincrement_result operator++(X& r, int); 

Effects: equivalent to

{ X tmp = r; 
++r; 
return tmp; }   


Concept BasicOutputIterator

concept BasicOutputIterator<typename X>
  : IteratorAssociatedTypes, CopyConstructible
{
  requires Assignable;
 
  typename postincrement_result = X;
  requires Dereferenceable,
           Assignable<Dereferenceable::reference,
                      value_type>,
           Convertibleconst X&>;
 
  reference operator*(X&);
  X& operator++(X&);
  postincrement_result operator++(X&, int);
};

The BasicOutputIterator concept describes an output iterator that has one, fixed value type. Unlike OutputIterator, BasicOutputIterator is a part of the iterator refinement hierarchy.

X& operator++(X& r);

Postcondition: &r == &++r.

postincrement_result operator++(X& r, int); 

Effects: equivalent to

{ X tmp = r; 
++r; 
return tmp; }   

Every BasicOutputIterator is an OutputIterator for value types Assignable to its value_type. This allows algorithms specified with OutputIterator (the less restrictive concept) to work with iterators that have concept maps for the more common BasicOutputIterator concept.

template<BasicOutputIterator X, typename Value>
requires Assignable
concept_map OutputIterator {
  typedef Value                       value_type;
  typedef X::reference                reference;
  typedef X::postincrement_result     postincrement_result;
};

Concept ForwardIterator

concept ForwardIterator<typename X> : InputIterator, DefaultConstructible {
  requires Convertibleconst value_type&>,
           Convertibleconst X&>;
};

[ Note: The condition that a == b implies ++a == ++b (which is not true for input and output iterators) and the removal of the restrictions on the number of the assignments through the iterator (which applies to output iterators) allows the use of multi-pass one-directional algorithms with forward iterators. - end note ]

bool operator==(X, X); 

If a and b are equal, then either a and b are both dereferenceable or else neither is dereferenceable.

If a and b are both dereferenceable, then a == b if and only if *a and *b are the same object.


Concept MutableForwardIterator

concept MutableForwardIterator<typename X> : ForwardIterator, BasicOutputIterator {
  requires SameType, SameType;
};

The MutableForwardIterator concept builds on the ForwardIterator concept by introducing the ability to modify the values referenced by the iterator.


Concept BidirectionalIterator

concept BidirectionalIterator<typename X> : ForwardIterator {
  typename postdecrement_result;
  requires Dereferenceable,
           Convertible<Dereferenceable::reference, 
                       value_type>,
           Convertibleconst X&>;
 
  X& operator--(X&);
  postdecrement_result operator--(X&, int);
};

Bidirectional iterators allow algorithms to move iterators backward as well as forward.


Concept MutableBidirectionalIterator

concept MutableBidirectionalIterator<typename X> 
  : BidirectionalIterator, MutableForwardIterator { };

The MutableBidirectionalIterator concept builds on the BidirectionalIterator concept by introducing the ability to modify the values referenced by the iterator.


Concept RandomAccessIterator

concept RandomAccessIterator<typename X> : BidirectionalIterator, LessThanComparable {
  X& operator+=(X&, difference_type);
  X  operator+ (X, difference_type);
  X  operator+ (difference_type, X);
  X& operator-=(X&, difference_type);
  X  operator- (X, difference_type);
 
  difference_type operator-(X, X);
  reference operator[](X, difference_type);
 
  bool operator>=(X, X);
  bool operator>(X, X);
  bool operator<=(X, X);
};

Random access iterators allow algorithms to move iterators an arbitrary number of steps forward or backward in constant time.

X& operator+=(X&, difference_type); 

Effects: equalivalent to

{ difference_type m = n; 
if (m >= 0) while (m--) ++r; 
else while (m++) --r; 
return r; } 
X operator+(X a, difference_type n); 
X operator+(difference_type n, X a); 

Effects: equivalent to

{ X tmp = a; 
return tmp += n; } 

Postcondition: a + n == n + a

X& operator-=(X& r, difference_type n); 

Returns: r += -n

X operator-(X, difference_type); 

Effects: equivalent to

{ X tmp = a; 
return tmp -= n; } 
difference_type operator-(X a, X b); 

Precondition: there exists a value n of difference_type such that a + n == b.

Effects: b == a + (b - a)

Returns: (a < b) ? distance(a,b) : -distance(b,a)

bool operator>(X, X); 

Effects: > is a total ordering relation opposite to <.

Pointers to constant values are random access iterators:

template<typename T> concept_map RandomAccessIterator<const T*> {
  typedef T value_type;
  typedef std::ptrdiff_t difference_type;
  typedef const T& reference;
  typedef const T* pointer;
};

Concept MutableRandomAccessIterator

concept MutableRandomAccessIterator<typename X>
  : RandomAccessIterator, MutableBidirectionalIterator { };

The MutableRandomAccessIterator concept builds on the RandomAccessIterator concept by introducing the ability to modify the values referenced by the iterator.

Pointers are mutable random access iterators:

template<typename T> concept_map MutableRandomAccessIterator {
  typedef T value_type;
  typedef std::ptrdiff_t difference_type;
  typedef T& reference;
  typedef T* pointer;
};