[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.
- References:
- ADT Lib (6)
- From: Michael van Acken <KK120y2@mail.lvr.de>