iterators

Overview
STL provides a host of template based iterators that act as glue between containers and algorithms.

Details
Operation
An iterator basically wraps a range of elements from a STL container or even an array. It's analogues to a smartpointer. 
A range of elements is marked by begin and end, which are returned by methods begin() and end(). begin points to the first element in the range and end points to the element after the last element in the range.


For example, in the range {1,2,3,4}, begin() points to the position pointed by element the first element(1) and end()points to the position after the last element(4).

Individual elements can be accessed by overloaded dereference operator(*). Iterators can be conditionally forward or backward using overloaded increment(++) or decrement(--) operators. An iterator also support additional overloaded operators.  =  returns an iterator. ==,!=,<,>,<=,>= compares two iterators. In addition, += and -= are also overloaded in certain categories of iterators.
In the example below, itr  points to the first element. ++itr moves it to element 2 and so on until itr  points to end. Note that the for loop exists after the check itr!=end() becomes true.
    int v[]{1,2,3,4};
    for (int *itr=begin(v); itr != end(v); ++itr)
        cout << *itr << " ";
    //prints 1 2 3 4

overloaded operators
The table below describes each of the overloaded operator in detail.
NameDescriptionExample
*returns reference to the element that can be used to read or write
vector<int> v{1,2,3,4};
vector<int>::iterator ita;

//*ita=1
ita = begin(v);
//prints 1
cout << *ita << endl;
++Moves iterator forward by an element
vector<int> v{1,2,3,4};
vector<int>::iterator ita, itb;
//*ita=1
ita = begin(v);

//pre ++
//*ita=2 *itb=1
itb = ita++;


//*ita=1
ita = begin(v);

//post ++
//*ita=2 *itb=2
itb = ++ita;
--Moves iterator backward by an element
vector<int> v{1,2,3,4};
vector<int>::iterator ita, itb;
//*ita=1
ita = begin(v);
//*ita=2
++ita;

//pre --
//*ita=1 *itb=2
itb = ita--;

//*ita=1
ita = begin(v);
//*ita=2
++ita;

//post --
//*ita=1 *itb=1
itb = --ita;
->returns member of the element(class)vector<pair<int,int>> pv{{1,2}};
//prints 1
cout << begin(pv)->first << endl;
[]returns reference to the element after adding in the index
vector<int> v{1,2,3,4};
vector<int>::iterator ita;
//*ita=1
ita = begin(v); 
//*ita=2
++ita;
//[]
//i=2
int i = ita[0];
//i=1
i = ita[-1];
//i=3
i = ita[1];
+returns iterator after adding index to the iterator
vector<int> v{1,2,3,4};
vector<int>::iterator ita, itb;

//*ita=1
ita = begin(v); 

//+
//*itb=2
itb = ita+1;
-returns iterator after subtracting index to the iterator
vector<int> v{1,2,3,4};
vector<int>::iterator ita, itb;
//*ita=1
ita = begin(v); 
//*ita=2
++ita;

//-
//*itb=1
itb = ita-1;
+=adds index to self
vector<int> v{1,2,3,4};
vector<int>::iterator ita;
//*ita=1
ita = begin(v); 

 //+=
//*ita=2
ita += 1;
-=subtracts index to self
vector<int> v{1,2,3,4};
vector<int>::iterator ita;
//*ita=1
ita = begin(v); 
++ita;

 //-=
//*ita=1
ita -= 1;
== != < > >= <=relational operators
vector<int> v{1,2,3,4};
vector<int>::iterator ita, itb;

//*ita=1
ita = begin(v); 
//*ita=2 *itb=1
itb = ita++;

//== != < > >= <=
//ita == itb    F
//ita != itb    T
//ita >  itb    F
//ita >= itb    F
//ita <  itb    T
//ita <= itb    T

Iterator Classification
Iterators can be broadly classified as below based on their behavior.
The following diagram illustrates the hierarchy.


The following tables describes in detail.
NameDescriptionOperationsExamples
inputReads an element at the position any number of times.
After the increment, none of the other copies of the iterator can safely be compared, dereferenced, or incremented later.
*, ++,  ==, !=istream
outputWrites an element at the position once.*, ++ ,=ostream
forwardSame as an input iterator except reads or write any element any number of times.  Multiple copies of the iterator can be made that can be dereferenced and incremented independently.*,  ->, ++, ==, !=forward_list, unordered_set, unordered_multiset, unordered_map, and unordered_multimap
bidirectionalSame as a forward iterator with additional operator support.*,  ->, ++, --,  ==, !=list, set, multiset, map, multimap
random accessSame as a bidirectional iterator with additional operator support.*,  ->, ++, --, +-.    -=, ==, !=, [], < , >,  >=, <=vector, deque, array, built-in arrays, string

iterator traits
As noted earlier, an iterator acts as glue between containers and algorithms. An algorithm need not know all about the containers except for a few specific details such as type of iterator, or the value_ type.
For every iterator type, a corresponding specialization of iterator_traits class template shall be defined, with at least the following member types defined.
NameDescription
difference_typeType to express the result of subtracting one iterator from another.
value_typeThe type of the element the iterator can point to.
pointerThe type of a pointer to an element the iterator can point to.
referenceThe type of a reference to an element the iterator can point to.
iterator_categoryThe iterator category. It can be one of these: input_iterator_tag output_iterator_tag forward_iterator_tag bidirectional_iterator_tag random_access_iterator_tag

The tags are declared as empty structs having same hierarchy as the iterators shown above.
The following lists iterator_traits for legacy iterators and a specialization for native arrays.
//legacy iterator 
template< class Iterator >
struct iterator_traits
{
   typedef typename Iterator::iterator_category iterator_category;
   typedef typename Iterator::value_type value_type;
   typedef typename Iterator::difference_type difference_type;
   typedef difference_type distance_type;
   typedef typename Iterator::pointer pointer;
   typedef typename Iterator::reference reference;
};

//specialization for pointer types 
template< class T >
struct iterator_traits<T*>
{
   typedef random_access_iterator_tag iterator_category;
   typedef T value_type;
   typedef ptrdiff_t difference_type;
   typedef difference_type distance_type;
   typedef T* pointer;
   typedef T& reference;
};

The following example lists usage of iterator_traits within an algorithm for different  container types.
template<class iter>
void iterinfo(iter it)
{
    cout << "iterator_category\t";
    cout <<  typeid(typename iterator_traits<iter>::iterator_category).name() << endl;

    cout << "value_type\t\t";
    cout <<  typeid(typename iterator_traits<iter>::value_type).name() << endl;

    cout << "difference_type\t\t";
    cout <<  typeid(typename iterator_traits<iter>::difference_type).name() << endl;
    
    cout << "distance_type\t\t";
    cout <<  typeid(typename iterator_traits<iter>::difference_type).name() << endl;

    cout << "pointer\t\t\t";
    cout <<  typeid(typename iterator_traits<iter>::pointer).name() << endl;

    cout << "reference\t\t";
    cout <<  typeid(typename iterator_traits<iter>::reference).name() << endl;
}

//vector<int>
//iterator_category	struct //std::random_access_iterator_tag
//value_type		int
//difference_type	__int64
//distance_type		__int64
//pointer		int * __ptr64
//reference		int
 
    cout << "vector<int>" << endl;
    std::vector<int> v{1, 2, 3, 4, 5};
    iterinfo(begin(v));
    cout << endl;
 

//list<int>
//iterator_category	struct //std::bidirectional_iterator_tag
//value_type		int
//difference_type	__int64
//distance_type		__int64
//pointer		int * __ptr64
//reference		int

    cout << "list<int>" << endl;
    std::list<int> l{1, 2, 3, 4, 5};
    iterinfo(l.begin());
    cout << endl;

//forward_list<int>
//iterator_category	struct //std::forward_iterator_tag
//value_type		int
//difference_type	__int64
//distance_type		__int64
//pointer		int * __ptr64
//reference		int

    cout << "forward_list<int>" << endl;
    std::forward_list<int> fl{1, 2, 3, 4, 5};
    iterinfo(fl.begin());
    cout << endl;

//int []
//iterator_category	struct std::random_access_iterator_tag
//value_type		int
//difference_type	__int64
//distance_type		__int64
//pointer		int * __ptr64
//reference		int    

    cout << "int []" << endl;
    int a[]{1, 2, 3, 4, 5};
    iterinfo(begin(a)); 

iterator apis
iterator apis generate iterators and enable manipulating iterators to change positions. As shown below, two categories of iterators are supported - forward and reverse. Forward iterators traverse from the first element to the last element. Reverse iterators traverse from the last element to the first element.


NameDescription
void advance
(InputIterator& it, Distance n)
Moves iterator it by n elements. Distance type represents distances between iterators of this type. Note that negative n is applicable to bidirectional and random iterators only.
difference_type  distance
(InputIterator first, InputIterator last)
Returns  distance between iterators as (last - first). It's same as the number of increments needed to go from first to last. Note that negative value is returned for bidirectional and random iterators only.
ForwardIterator next
(ForwardIterator it, difference_type n = 1)
Returns an valarray after applying the function asin/acos/atan/atan2 to each element of valarray.
BidirectionalIterator prev
(BidirectionalIterator it, difference_type n = 1)
Returns an valarray after applying the function sinh/cosh/tanh to each element of valarray.
iterator begin()
iterator end()
Returns iterator to beginning and end
Example:
vector<int> v{1,2,3,4,5};
//prints 1 2 3 4 5
for (auto itr=v.begin(); itr!=v.end(); ++itr)
    cout << *itr << ' ';
reverse_iterator rbegin()
reverse_iterator rend()
Returns reverse_iterator  to reverse beginning and reverse end.
Example:
vector<int> v{1,2,3,4,5};
//prints 5 4 3 2 1
for (auto itr=v.rbegin(); itr!=v.rend(); ++itr)
    cout << *itr << ' ';
const_iterator cbegin()
const_iterator cend()
Returns const_iterator to beginning and end.
Example:
vector<int> v{1,2,3,4,5};
//prints 1 2 3 4 5
for (auto itr=v.cbegin(); itr!=v.cend(); ++itr)
    cout << *itr << ' ';
const_reverse_iterator crbegin()
const_reverse_iterator crend()
Returns const_reverse_iterator  to reverse beginning and reverse end.
Example:
vector<int> v{1,2,3,4,5};
//prints 5 4 3 2 1
for (auto itr=v.crbegin(); itr!=v.crend(); ++itr)
    cout << *itr << ' ';

predefined iterator adaptors 
Iterator adaptors are a separate type of iterators with special behavior. They simplify the work with containers and are very useful in standard algorithms.
Following iterator adapters are predefined.
NameDescription
reverse_iterator➹
make_reverse_iterator➹
An iterator adaptor for reverse-order traversal
Utility to creates reverse_iterator adaptor.
move_iterator➹
make_move_iterator➹
An iterator adaptor which dereferences to an rvalue
creates move_iterator adaptor.

predefined stream iterators
Following stream iterators are predefined.
NameDescription
istream_iterator➹input iterator that reads from basic_istream
ostream_iterator➹output iterator that writes to basic_ostream
istreambuf_iterator➹input iterator that reads from basic_streambuf
ostreambuf_iterator➹output iterator that writes to basic_streambuf

uninitialized_memory
Following iterators are defined.
NameDescription
raw_storage_iterator➹output iterator operates on uninitialized memory blocks.

No comments:

Post a Comment