(DIR) Return Create A Forum - Home --------------------------------------------------------- gworld (HTM) https://gworld.createaforum.com --------------------------------------------------------- ***************************************************** (DIR) Return to: C++PROGRAMMING LANGUAGE ***************************************************** #Post#: 147-------------------------------------------------- C++ ITERATORS By: eba95 Date: July 31, 2010, 4:35 am --------------------------------------------------------- C++ Iterators Iterators are used to access elements of a sequence, and can be used in a similar manner to pointers. For example, one might use an iterator to step through the elements of a vector. The following code creates and uses an iterator with a vector: v e c t o r < i n t > t he _ v e c t o r ; v e c t o r < i n t > : : i t e r a t o r t he _ i t e r a t o r ; f o r ( i n t i = 0 ; i < 1 0 ; i + + ) t he _ v e c t o r . pu s h _ ba c k ( i ) i n t t o t a l = 0 ; t he _ i t e r a t o r = t he _ v e c t o r . be g i n ( ) ; w h i l e ( t he _ i t e r a t o r ! = t he _ v e c t o r . e nd ( ) ) { t o t a l + = * t he _ i t e r a t o r ; + + t he _ i t e r a t o r ; } c ou t < < " T o t a l = " < < t o t a l < < e nd l ; Notice that you can access the elements of the container by dereferencing the iterator. NOTES: You should prefer pre- increment operator (+ + i t e r ) to post-increment operator ( i t e r + + ) if you are not going to use the old value. Post-increment is generally implemented as follows: I t e r ope r a t o r + + ( i n t ) { I t e r tm p ( * t h i s ) ; / / s t o r e t he o l d v a l ue i n a t e m po r a r y ob j e c t + + * t h i s ; / / c a l l p r e - i n c r e m e n t r e t u r n tm p ; / / r e t u r n t he o l d v a l ue } Obviously, it's less efficient than pre- increment. Iterator Categories Not every kind of iterator has exactly the same abilities. Reading and writing require different abilities. Random access is efficient and convenient for a v e c t o r , whereas it would be expensive for a l i s t . For this reason, iterators are classified into five categories according to their abilities: Iterator Category Description Providers Tag Input Read values with forward movement. These can be incremented, compared, and dereferenced. istream input_iterator_tag Output Write values with forward movement. These can be incremented and dereferenced. ostream, inserter output_iterator_tag Forward Read or write values with forward movement. These combine the functionality of input and output iterators with the ability to store the iterators value. slist forward_iterator_tag Bidirectional Read and write values with forward and backward movement. These are like the forward iterators, but you can increment and decrement them. list, map, multimap, set, multiset bidirectional_iterator_tag Random- access Read and write values with random access. These are the most powerful iterators, combining the functionality of bidirectional iterators with the ability to do pointer arithmetic and pointer comparisons. array, deque, string, vector random_access_iterator_tag Each of the STL containers is associated with a category of iterator, and each of the STL algorithms uses a certain category of iterator. For example, vectors are associated with random-access iterators, which means that they can use algorithms that require random access. Since random-access iterators encompass all of the characteristics of the other iterators, vectors can use algorithms designed for other iterators as well. v e c t o r < i n t > t he _ v e c t o r ( 1 0 ) ; / / ge ne r a t e _ n r e qu i r e s ou t pu t _ i t e r a t o r ge ne r a t e _ n ( t he _ v e c t o r . be g i n ( ) , 5 , r a nd ) ; / / f i l l r e qu i r e s f o rw a r d _ i t e r a t o r f i l l ( t he _ v e c t o r . be g i n ( ) + 5 , t he _ v e c t o r . e nd ( ) , 1 0 0 ) ; / / r a ndo m _ s hu f f l e r e qu i r e s r a ndo m _ a c c e s s _ i t e r a t o r r a ndo m _ s hu f f l e ( t he _ v e c t o r . be g i n ( ) , t he _ v e c t o r . e nd ( ) ) ; / / c opy r e qu i r e s i npu t _ i t e r a t o r c opy ( t he _ v e c t o r . be g i n ( ) , t he _ v e c t o r . e nd ( ) , o s t r e a m _ i t e r a t o r < i n t > ( c ou t , / / r e v e r s e _ c opy r e qu i r e s b i d i r e c t i ona l _ i t e r a t o r r e v e r s e _ c opy ( t he _ v e c t o r . be g i n ( ) , t he _ v e c t o r . e nd ( ) , o s t r e a m _ i t e r a t o r < i n t Auxiliary Iterator Functions The < i t e r a t o r > header file defines two auxiliary functions. v o i d a dv a n c e ( i npu t _ i t e r a t o r & po s , D i s t n ) ; a dv a n c e ( ) lets po s step n elements forward (or backward). For bidirectional and random_access_iterators, n can be negative to step backward. For random_access_iterators, a dv a n c e ( ) runs in constant time (simply calls po s +=n). For all other iterators, a dv a n c e ( ) has linear complexity (calls + + po s n times). t y pe na m e i t e r a t o r _ t r a i t s < i npu t _ i t e r a t o r > : : d i f f e r e n c e _ t y pe d i s t a n c e ( i npu t _ i t e r a t o r po s 1 , i npu t _ i t e r a t o r po s 2 ) ; d i s t a n c e ( ) returns the distance between two iterators. For random_access_iterators, d i s t a n c e ( ) runs in constant time (simply returns po s 2 - po s 1 ). For all other iterators, d i s t a n c e ( ) runs in linear time ( po s 1 is incremented until it reaches po s 2 , and returns the number of incrementation). Invalidating Iterators Iterators to exisiting elements in a container can become invalidated when the container is changed. This makes changing the container while iterating it problematic. The containers offer different guarantees in this regard: vectors: any insert that causes a reallocation invalidates all iterators, otherwise it invalidates all iterators to the insert position or after; erase invalidates all iterators to the erased elements and those after. list/map: insert invalidates no iterators; erase only invalidates iterators to the erased element(s) & no others. *****************************************************