...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
An Iterator is a restricted pointerlike object pointing into a vector or matrix container.
An Indexed Bidirectional Iterator is an iterator of a container that can be dereferenced, incremented, decremented and carries index information.
Assignable, Equality Comparable, Default Constructible.
Value type  The type of the value obtained by dereferencing a Indexed Bidirectional Iterator 
Container type  The type of the container a Indexed Bidirectional Iterator points into. 
I 
A type that is a model of Indexed Bidirectional Iterator 
T 
The value type of I 
C 
The container type of I 
it , itt, it1 , it2 
Objects of type I 
t 
Object of type T 
c 
Object of type C 
A Indexed Bidirectional Iterator may be mutable, meaning that the values referred to by objects of that type may be modified, or constant , meaning that they may not. If an iterator type is mutable, this implies that its value type is a model of Assignable; the converse, though, is not necessarily true.
A Indexed Bidirectional Iterator may have a singular value, meaning that the results of most operations, including comparison for equality, are undefined. The only operation that is guaranteed to be supported is assigning a nonsingular iterator to a singular iterator.
A Indexed Bidirectional Iterator may have a dereferenceable value, meaning that dereferencing it yields a welldefined value. Dereferenceable iterators are always nonsingular, but the converse is not true.
An Indexed Bidirectional Iterator is pasttheend if it points beyond the last element of a container. Pasttheend values are nonsingular and nondereferenceable.
In addition to the expressions defined for Assignable, Equality Comparable and Default Constructible, the following expressions must be valid.
Name  Expression  Type requirements  Return type 

Default constructor  I it 

Dereference  *it 
Convertible to T . 

Dereference assignment  *it = t 
I is mutable. 

Member access  it>m 
T is a type for which t.m is
defined. 

Preincrement  ++ it 
I & 

Postincrement  it ++ 
I 

Predecrement   it 
I & 

Postdecrement  it  
I 

Index  it.index () 
C::size_type 
Semantics of an expression is defined only where it differs from, or is not defined in, Assignable, Equality Comparable and Default Constructible.
Name  Expression  Precondition  Semantics  Postcondition 

Default constructor  I it 
it is singular. 

Dereference  *it 
it is dereferenceable. 

Dereference assignment  *it = t 
Same as for *it . 
*it is a copy of t. 

Member access  it>m 
it is dereferenceable. 
Equivalent to (*it).m 

Preincrement  ++ it 
it is dereferenceable. 
it is modified to point to the next element. 
it is dereferenceable or pasttheend.
.If it1 == it2 ,then ++ it1 == ++ it2 . 
Postincrement  it ++ 
Same as for ++ it . 
Equivalent to{ 
it is dereferenceable or pasttheend. 
Predecrement   it 
it is dereferenceable or pasttheend.There exists a dereferenceable iterator itt such that
it == ++ itt . 
it is modified to point to the previous
element. 
it is dereferenceable.&it = & it .If it1 == it2 ,then  it1 ==  it2 .If it2 is dereferenceable and it1 ==
++it2 ,then it1 == it2 . 
Postdecrement  it  
Same as for  it . 
Equivalent to{ 
it is dereferenceable. 
Index  it.index () 
it is dereferenceable. 
it.index () >= 0 and it.index () < it ().size () 
If it1 == it2 ,then it1.index () == it2 .index () .If it1 == it2 ,then it1.index () < (++ it2 ).index
() .If it1 == it2 ,then it1.index () > ( it2 ).index
() . 
The complexity of operations on indexed bidirectional iterators is guaranteed to be amortized constant time.
Identity  it1 == it2 if and only if &*it1 ==
&*it2 . 
Symmetry of increment and decrement  If it is dereferenceable, then ++ it;
it; is a null operation. Similarly,  it; ++
it; is a null operation. 
Relation between iterator index and container element operator  If it is dereferenceable, *it == it ()
(it.index ()) . 
sparse_vector<T>::iterator
An Indexed Random Access Iterator is an iterator of a container that can be dereferenced, moved forward, moved backward and carries index information.
LessThanComparable, Indexed Bidirectional Iterator .
Value type  The type of the value obtained by dereferencing a Indexed Random Access Iterator 
Container type  The type of the container a Indexed Random Access Iterator points into. 
I 
A type that is a model of Indexed Random Access Iterator 
T 
The value type of I 
C 
The container type of I 
it , itt, it1 , it2 
Objects of type I 
t 
Object of type T 
n 
Object of type C::difference_type 
An Indexed Random Access Iterator it1
is
reachable from an Indexed Random Access Iterator
it2
if, after applying operator ++
to
it2
a finite number of times, it1 ==
it2
.
In addition to the expressions defined for Indexed Bidirectional Iterator , the following expressions must be valid.
Name  Expression  Type requirements  Return type 

Forward motion  it += n 
I & 

Iterator addition  it + n 
I 

Backward motion  i = n 
I & 

Iterator subtraction  it  n 
I 

Difference  it1  it2 
C::difference_type 

Element operator  it [n] 
Convertible to T . 

Element assignment  it [n] = t 
I is mutable 
Convertible to T . 
Semantics of an expression is defined only where it differs from, or is not defined in, Indexed Bidirectional Iterator .
Name  Expression  Precondition  Semantics  Postcondition 

Forward motion  it += n 
Including it itself, there must be n
dereferenceable or pasttheend iterators following or preceding
it , depending on whether n is positive or
negative. 
If n > 0 , equivalent to executing ++
it n times. If n < 0 ,
equivalent to executing  it n times. If
n == 0 , this is a null operation. 
it is dereferenceable or pasttheend. 
Iterator addition  it + n 
Same as for i += n . 
Equivalent to{ 
Result is dereferenceable or pasttheend. 
Backward motion  it = n 
Including it itself, there must be n
dereferenceable or pasttheend iterators preceding or following
it , depending on whether n is positive or
negative. 
Equivalent to it += (n) . 
it is dereferenceable or pasttheend. 
Iterator subtraction  it  n 
Same as for i = n . 
Equivalent to{ 
Result is dereferenceable or pasttheend. 
Difference  it1  it2 
Either it1 is reachable from it2 or
it2 is reachable from it1 , or both. 
Returns a number n such that it1 == it2 +
n 

Element operator  it [n] 
it + n exists and is dereferenceable. 
Equivalent to *(it + n) 

Element assignment  i[n] = t 
Same as for it [n] . 
Equivalent to *(it + n) = t 
The complexity of operations on indexed random access iterators is guaranteed to be amortized constant time.
Symmetry of addition and subtraction  If it + n is welldefined, then it += n; it
= n; and (it + n)  n are null operations.
Similarly, if it  n is welldefined, then it =
n; it += n; and (it  n) + n are null
operations. 
Relation between distance and addition  If it1  it2 is welldefined, then it1 ==
it2 + (it1  it2) . 
Reachability and distance  If it1 is reachable from it2 , then
it1  it2 >= 0 . 
vector<T>::iterator
An Indexed Bidirectional Column/Row Iterator is an iterator of a container that can be dereferenced, incremented, decremented and carries index information.
Assignable, Equality Comparable, Default Constructible.
Value type  The type of the value obtained by dereferencing a Indexed Bidirectional Column/Row Iterator 
Container type  The type of the container a Indexed Bidirectional Column/Row Iterator points into. 
I1 
A type that is a model of Indexed Bidirectional Column/Row Iterator 
I2 
A type that is a model of Indexed Bidirectional Row/Column Iterator 
T 
The value type of I1 and I2 
C 
The container type of I1 and I2 
it1 , it1t, it11 ,
it12 
Objects of type I1 
it2 , it2t 
Objects of type I2 
t 
Object of type T 
c 
Object of type C 
In addition to the expressions defined for Assignable, Equality Comparable and Default Constructible, the following expressions must be valid.
Name  Expression  Type requirements  Return type 

Default constructor  I1 it1 

Dereference  *it1 
Convertible to T . 

Dereference assignment  *it1 = t 
I1 is mutable. 

Member access  it1>m 
T is a type for which t.m is
defined. 

Preincrement  ++ it1 
I1 & 

Postincrement  it1 ++ 
I1 

Predecrement   it1 
I1 & 

Postdecrement  it1  
I1 

Row Index  it1.index1 () 
C::size_type 

Column Index  it1.index2 () 
C::size_type 

Row/Column Begin  it1.begin () 
I2 

Row/Column End  it1.end () 
I2 

Reverse Row/Column Begin  it1.rbegin () 
reverse_iterator<I2> 

Reverse Row/Column End  it1.rend () 
reverse_iterator<I2> 
Semantics of an expression is defined only where it differs from, or is not defined in, Assignable, Equality Comparable and Default Constructible.
Name  Expression  Precondition  Semantics  Postcondition 

Default constructor  I1 it1 
it1 is singular. 

Dereference  *it1 
it1 is dereferenceable. 

Dereference assignment  *it1 = t 
Same as for *it1 . 
*it1 is a copy of t. 

Member access  it1>m 
it1 is dereferenceable. 
Equivalent to (*it1).m 

Preincrement  ++ it1 
it1 is dereferenceable. 
it1 is modified to point to the next element of
the column/row, i.e. for column iterators holdsit1.index1 () < (++ it1).index1 () andit1.index2 () == (++ it1).index2 () ,for row iterators holds it1.index1 () == (++ it1).index1 () andit1.index2 () < (++ it1).index2 () . 
it1 is dereferenceable or pasttheend.
.If it11 == it12 ,then ++ it11 == ++ it12 . 
Postincrement  it1 ++ 
Same as for ++ it1 . 
Equivalent to{ 
it1 is dereferenceable or pasttheend. 
Predecrement   it1 
it1 is dereferenceable or pasttheend.There exists a dereferenceable iterator it1t such that
it1 == ++ it1t . 
it1 is modified to point to the previous
element of the column/row, i.e. for column iterators holdsit1.index1 () > ( it1).index1 () andit1.index2 () == ( it1).index2 () ,for row iterators holds it1.index1 () == ( it1).index1 () andit1.index2 () > ( it1).index2 () . 
it1 is dereferenceable.&it1 = & it1 .If it11 == it12 ,then  it11 ==  it12 . 
Postdecrement  it1  
Same as for  it1 . 
Equivalent to{ 
it1 is dereferenceable. 
Row Index  it1.index1 () 
it1 is dereferenceable. 
it1.index1 () >= 0 andit1.index1 () < it () .size1 () 
If it11 == it12 ,then it11.index1 () == it12 .index1 ()
.If it11 , it12 are Indexed Bidirectional
Row Iterators with it11 == it12 ,then it11.index1 () < (++ it12 ).index1
() .If it11 , it12 are Indexed Bidirectional
Row Iterators with it11 == it12 ,then it11.index1 () > ( it12 ).index1
() . 
Column Index  it1.index2 () 
it1 is dereferenceable. 
it1.index2 () >= 0 andit1.index2 () < it () .size2 () 
If it11 == it12 ,then it11.index2 () == it12 .index2 ()
.If it11 , it12 are Indexed Bidirectional
Column Iterators with it11 == it12 ,then it11.index2 () < (++ it12 ).index2
() .If it11 , it12 are Indexed Bidirectional
Column Iterators with it11 == it12 ,then it11.index2 () > ( it12 ).index2
() . 
Row/Column Begin  it1.begin () 
it1 is dereferenceable. 
If it1 is a Indexed Bidirectional Column
Iterator,then it2 = it1.begin () is a Indexed Bidirectional Row
Iteratorwith it2.index1 () == it1.index1 () .
If 

Row/Column End  it1.end () 
it1 is dereferenceable. 
If it1 is a Indexed Bidirectional Column
Iterator,then it2 = it1.end () is a Indexed Bidirectional Row
Iteratorwith it2.index1 () == it1.index1 () .
If 

Reverse Row/Column Begin  it1.rbegin () 
it1 is dereferenceable. 
Equivalent to reverse_iterator<I2> (it1.end
()) . 

Reverse Row/Column End  it1.rend () 
it1 is dereferenceable. 
Equivalent to reverse_iterator<I2> (it1.begin
()) . 
The complexity of operations on indexed bidirectional column/row iterators is guaranteed to be logarithmic depending on the size of the container. The complexity of one iterator (depending on the storage layout) can be lifted to be amortized constant time. The complexity of the other iterator (depending on the storage layout and the container) can be lifted to be amortized constant time for the first row/first column respectively.
Identity  it11 == it12 if and only if &*it11 ==
&*it12 . 
Symmetry of increment and decrement  If it1 is dereferenceable, then ++ it1;
it1; is a null operation. Similarly,  it1; ++
it1; is a null operation. 
Relation between iterator index and container element operator  If it1 is dereferenceable, *it1 == it1 ()
(it1.index1 (), it2.index2 ()) 
Relation between iterator column/row begin and iterator index  If it1 is a Indexed Bidirectional Column Iterator
and it2 = it1.begin () then it2.index2 () <
it2t.index2 () for all it2t with it2t ()
== it2 () and it2t ().index1 () == it2 ().index1
() .
If 
Relation between iterator column/row end and iterator index  If it1 is a Indexed Bidirectional Column Iterator
and it2 = it1.end () then it2.index2 () >
it2t.index2 () for all it2t with it2t ()
== it2 () and it2t ().index1 () == it2 ().index1
() .
If 
sparse_matrix<T>::iterator1
sparse_matrix<T>::iterator2
An Indexed Random Access Column/Row Iterator is an iterator of a container that can be dereferenced, incremented, decremented and carries index information.
Indexed Bidirectional Column/Row Iterator .
Value type  The type of the value obtained by dereferencing a Indexed Random Access Column/Row Iterator 
Container type  The type of the container a Indexed Random Access Column/Row Iterator points into. 
I 
A type that is a model of Indexed Random Access Column/Row Iterator 
T 
The value type of I 
C 
The container type of I 
it , itt, it1 , it2 
Objects of type I 
t 
Object of type T 
c 
Object of type C 
In addition to the expressions defined for Indexed Bidirectional Column/Row Iterator , the following expressions must be valid.
Name  Expression  Type requirements  Return type 

Forward motion  it += n 
I & 

Iterator addition  it + n 
I 

Backward motion  i = n 
I & 

Iterator subtraction  it  n 
I 

Difference  it1  it2 
C::difference_type 

Element operator  it [n] 
Convertible to T . 

Element assignment  it [n] = t 
I is mutable 
Convertible to T . 
Semantics of an expression is defined only where it differs from, or is not defined in, Indexed Bidirectional Column/Row Iterator .
Name  Expression  Precondition  Semantics  Postcondition 

Forward motion  it += n 
Including it itself, there must be n
dereferenceable or pasttheend iterators following or preceding
it , depending on whether n is positive or
negative. 
If n > 0 , equivalent to executing ++
it n times. If n < 0 ,
equivalent to executing  it n times. If
n == 0 , this is a null operation. 
it is dereferenceable or pasttheend. 
Iterator addition  it + n 
Same as for i += n . 
Equivalent to{ 
Result is dereferenceable or pasttheend. 
Backward motion  it = n 
Including it itself, there must be n
dereferenceable or pasttheend iterators preceding or following
it , depending on whether n is positive or
negative. 
Equivalent to it += (n) . 
it is dereferenceable or pasttheend. 
Iterator subtraction  it  n 
Same as for i = n . 
Equivalent to{ 
Result is dereferenceable or pasttheend. 
Difference  it1  it2 
Either it1 is reachable from it2 or
it2 is reachable from it1 , or both. 
Returns a number n such that it1 == it2 +
n 

Element operator  it [n] 
it + n exists and is dereferenceable. 
Equivalent to *(it + n) 

Element assignment  i[n] = t 
Same as for it [n] . 
Equivalent to *(it + n) = t 
The complexity of operations on indexed random access Column/Row iterators is guaranteed to be amortized constant time.
Symmetry of addition and subtraction  If it + n is welldefined, then it += n; it
= n; and (it + n)  n are null operations.
Similarly, if it  n is welldefined, then it =
n; it += n; and (it  n) + n are null
operations. 
Relation between distance and addition  If it1  it2 is welldefined, then it1 ==
it2 + (it1  it2) . 
Reachability and distance  If it1 is reachable from it2 , then
it1  it2 >= 0 . 
matrix<T>::iterator1
matrix<T>::iterator2
Copyright (©) 20002002 Joerg Walter, Mathias Koch
Permission to copy, use, modify, sell and distribute this document
is granted provided this copyright notice appears in all copies.
This document is provided ``as is'' without express or implied
warranty, and with no claim as to its suitability for any
purpose.
Last revised: 1/15/2003