(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.
*****************************************************