[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

STL iterators



Hallo!

Ok, back from work and just before germany beats the USA my promissed
summery about STL iterators. This is a simple list of feature, I've
added nearly no comments. I hope everybody somehow understand as much
C++ to know what is going on. I hope that this is enough information to
get some new aspects on possibilties regarding the use of iterators.
I also hope, that this is a base for a new discussion round. I do not
want to make a proposal yet, I'll wait for that. I'll have the
documentation at home so I'm able to answer questions regarding details.

----------------------------------------------------------------------

STL uses five basic iterator types:

input iterator          read only, forward moving
output iterator         write only, forward moving
forward iterator        both read and write, forward moving
bidirectional iterator  read and write, forward and backward moving
random access iterator  read and write, random access

This is the hierachical order:

  input output
     forward
  bidirectional
  random access

The STL supports also const and not const iteraotrs (using the const
keyword). However a output iterator is always non-const.

Which iterators are generated by which class:

input          istream_iterator
output         ostream_iterator, inserter, front_inserter, back_inserter
bidirectional  list, set, multiset, map, multimap
random access  ordinary pointers, vector, deque

input iterator
--------------

Visits each value once.

example (implementation of algorithm find for templated class T):

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
  while(first!=last && *first!=value) {
    ++first;
  }
  return first;
}

requirements for input iterator:

* can be compared against another iterator for equality.
* can be dereferenced using '*' resulting in the value.
* can be incremented using '++'.

Pointers are input iterators because of language (miss)features.

Another example:

list<int>::iterator where=find(aList.first(),aList.end(),7);

output iterator
---------------

Opposite of the input iterator. Output iterators can be used to assign
values in a sequence, but cannot be used to access values. An output
iterator can be used to modify the value it points to (overwrite).

example (generic copy algorithm):

template<class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last,
  OutputIterator result)
{
  while (first!=last) {
    *result++ = *first++;
  }
  return result;
}

Pointers are output iterators.

another example:

int data[100];

vector<int> newdata(100);

copy(data,data+100,newdata.begin());


Forward iterator
----------------

Combines features of input and output iterator (multiple inheritance).

Example (generic replace algorithm):

template <class ForwardIterator, class T>
void replace (ForwardIterator first, ForwardIterator last,
              const T& old_value, const T& new_value)
{
  while (first!=last) {
    if (*first==old_value) {
      *first=new_value;
    }
    ++first;
  }
}

Example (Replaces all instances of value 7 with value 11 in the given
vector):

replace(aVec.begin(),aVec.end(),7,11);

Bidirectional vector
--------------------

Is similar to forward iterator but supports '--', too.

Example (reversing values in a container by placing them into a new
container):

template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
                            BidirectionalIterator last,
                            OutputIterator result)
{
  while (first!=last) {
    *result++ = *--last;
  }
  return result;
}

list<int> aList;

...

list<int> aVec(aList.size());
reverse_copy(aList.begin(),aList.end(),aVec.begin());

Random access iterator
----------------------

besides features of bidirectional iterator it supports accessing values
by subscript. Also random access iterator can be substracted the get
the number of values between them. You can also apply nummerical
operations on them. You can compare them using relational operators
(All other iterator can only be compared for (in)euqality).

Pointers are random access iterators.

Example (randomly shuffeling values):

template<class RandomAccessIterator>
void mixup(RandomAccessIterator first, RandomAccessIterator last)
{
  while (first<last) {
    iter_swap(first,first+randomInterger(last-first));
    ++first;
  }
}

Reverse iterators
-----------------

Some container support reverse iterators, reversing the natural oder.
Reverse iterators are no new class but normal iterators with different
semantics.

list, set and map generate reverse bidiretcional interators using
rbegin() and rend(), vector and deque generate random acess iterators
using similar methods.

Stream iterators
----------------

stream iteators are special iterators (derived from input and output
iterator) working directly on streams. The output iterator uses the
'>>' operator for printing.

Example:

copy(newdata.begin(),newdata.end(),ostream_iterator<int>(cout," "));

printing all members of newdata to standard out deviding elements using
a space.

Example:

void main()
{
  istream_iterator<int,ptrdiff_t> input(cin),eof;
  ostream_iterator<int>           output(cout,"\n");

  remove_copy(input,eof,output,7);
}

reading a file of ints, removing all int equal to 7 and then dumping the
rest to the standard out (simple filter functionality).

Insert iterator
---------------

Normaly output iterators overite the value they point to. E.g.

vector<int> a(10);
vector<int> b(10);

copy (a.begin,a.end(),b.begin());

Copying a to b, overwriting values in b. This does even work on lists
if the list is large enough.

list<int> c;

copy (a.begin(),a.end(),c.begin());

Insert iterators do not overwrite but insert a new value.

list<int> d;
copy (a.begin(),a.end(),front_inserter(d));

There are three forms:

front_inserter
  Inserts values to the front of the container
back_inserter
  Inserts values to the back of the container. Both iterators are
  supported by list and seqques but not for sets and maps. back_inserter
  can be used for vectors, too.
inserter
  Inserts a value before a handed iterator position. Support by all of
the above and maps.

Iterator operations
-------------------

advance(InputIterator & iter, Distance & n);
distance(InputIterator & iter, Distance & n);

Manipulation of iterators depended of iteraotr type (workinfg directly
on random acess iterators, using loops for all others).

Ranges
------

Ranges are always given in the form [a,b[, e.g. including a but
excluding b. a.begin() generates an iterator pointing to the first
element, a.end() generates and iterator pointing *behind* the last
element.

Containers supported by STL
---------------------------

vector, list, deque, set, multiset, map, multimap, stack, queue,
priority queue.

Algorithms sorted by interator dependence
-----------------------------------------

no iterator:

min, max, swap

input iterator:

accumulate, count, count_if, equal, for_each, find, finf_if, includes,
inner_product, lexicogaphical_product, mismatch

output iterator:

fill_n, generate_n

read from input and write to output:

adjacent_difference, copy, merge, partial_sum, remove_copy,
remove_copy_if, replace_copy, replace_copy_if,
set-difference_set_intersection; set_symetric_difference, set_unon,
trasnform, unique_copy

forward iterators:

adjacent_find, binary_search, equal_range, fill, find_end,
find_first_of, generate, iter_swap, lower_bound, max_element,
min_element, remove, remove_if, replace, replace_if, rotate, search,
search_n, swap_ranges, unique, upper_bound

read from forward write to output:

rotate_copy

bidirectional iterator:

copy_backward, inplace_merge, next_permutation, partition,
prev_permutation, reverse, stable_permutation

read from bidirectional write to output:

reverse_copy

random access:

make_heap, nth_element, partial_sort, pop_heap, push_heap,
random_shuffle, sort, sort_heap, stable_sort

read from input write to rabdom access:

partial_sort_copy




-- 
Gru...
       Tim.