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.
Name | Description | Example |
---|---|---|
* | returns reference to the element that can be used to read or write |
|
++ | 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 |
|
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.
Name | Description | Operations | Examples |
---|---|---|---|
input | Reads 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 |
output | Writes an element at the position once. | *, ++ ,= | ostream |
forward | Same 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 |
bidirectional | Same as a forward iterator with additional operator support. | *, ->, ++, --, ==, != | list, set, multiset, map, multimap |
random access | Same 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.
Name | Description |
---|---|
difference_type | Type to express the result of subtracting one iterator from another. |
value_type | The type of the element the iterator can point to. |
pointer | The type of a pointer to an element the iterator can point to. |
reference | The type of a reference to an element the iterator can point to. |
iterator_category | The 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 intcout << "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 intcout << "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 intcout << "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.
Name | Description |
---|---|
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.
Name | Description |
---|---|
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.
Name | Description |
---|---|
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.
Name | Description |
---|---|
raw_storage_iterator➹ | output iterator operates on uninitialized memory blocks. |
No comments:
Post a Comment