4.4.2 Iterator Adaptors

Reverse Iterators. For the bidirectional and random access iterators corresponding reverse iterator adaptors that iterate through a data structure in the opposite direction are provided.


list<int> l;
// fill l with 1 2 3 4
reverse_bidirectional_iterator<list<int>::iterator,						
                               list<int>::value_type,						
                               list<int>::reference_type,						
                               list<int>::difference_type> r (l.end());

cout << *r << " ";
r++;
cout << *r << " ";
r --;
cout << *r;

Output: 4 3 4


Note: To use reverse_bidirectional_iterator or reverse_iterator include iterator.h
list<int> l;
// fill l with 1 2 3 4

copy (reverse_iterator<int*, int, int&, ptrdiff_t> (l.end()),
      reverse_iterator<int*, int, int&, ptrdiff_t> (l.begin()),
      ostream_iterator<int> (cout, " ") );

Output: 4 3 2 1


For all the sequence containers (vector, list and deque) the member functions rbegin and rend are provided, which return the appropriate reverse iterators.
list<int> l;
// fill l with 1 2 3 4

copy (l.rbegin(), l.rend(), ostream_iterator<int> (cout, " "));

Output: 4 3 2 1


Insert Iterators. A kind of iterator adaptors, called insert iterators, simplify the insertion into containers. The principle is that writing a value to an insert iterator inserts this value into the container out of which the insert iterator was constructed. To define the position, where the value is inserted, three different insert iterator adaptors are provided:

back_insert_iterator and front_insert_iterator are constructed out of a container and insert elements at the end and at the beginning of this container, respectively. A back_insert iterator requires the container out of which it is constructed to have push_back defined, a front_insert_iterator correspondingly requires push_front.


deque<int> d;
back_insert_iterator<deque<int> >	bi (d);
front_insert_iterator<deque<int> >	fi (d);

insert_iterator is constructed out of a container and an iterator i, before which the values written to the insert iterator are inserted.


deque<int> d;
insert_iterator<deque<int> >	i (d, d.end() );

Insert iterators satisfy the requirements of output iterators, that means that an insert iterator can always be used when an output iterator is required. operator* returns the insert iterator itself.

The three functions back_inserter, front_inserter and inserter return the appropriate insert iterators.


template <class Container>
back_insert_iterator<Container> back_inserter(Container& x) {
   return back_insert_iterator<Container>(x);
}

template <class Container>
front_insert_iterator<Container> front_inserter(Container& x) {
   return front_insert_iterator<Container>(x);
}

template <class Container, class Iterator>
insert_iterator<Container> inserter(Container& x, Iterator i) {
   return insert_iterator<Container>(x, Container::iterator(i));
}

ifstream f ("example");	// file example: 1 3

deque<int> d;
copy (istream_iterator<int, ptrdiff_t>(f),		
      istream_iterator<int, ptrdiff_t>(),		
      back_inserter(d) );

vector<int> w (2,7);

copy (w.begin(), w.end(), front_inserter (d) );
      insert_iterator<deque<int> > i = inserter (d, ++d.begin() );
*i = 9;

Ouptut: 7 9 7 1 3


Raw Storage Iterator. A raw_storage_iterator enables algorithms to store results into uninitialized memory.


vector<int> a (2, 5);
vector<int> b (2, 7);

int *c = allocate((ptrdiff_t) a.size(), (int*)0 );

transform (a.begin(), a.end(), b.begin(),			
           raw_storage_iterator<int*, int> (c), plus<int>() );
copy (&c[0], &c[2], ostream_iterator<int> (cout, " ") );

Output: 12 12


The function allocate is provided by the STL allocator (see 4.5), transform is an algorithm of group 2 (see 4.3.2). To use a raw storage iterator for a given type T, a construct function must be defined, which puts results directly into uninitialized memory by calling the appropriate copy constructor. The following construct function is provided by STL:
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
   new (p) T1(value);
}

int a[10] = {1, 2, 3, 4, 5};
copy (&a[0], &a[5], raw_storage_iterator<int*, int> (&a[5]) );

Continue with section 4.4.3

Back to index


Johannes Weidl (J.Weidl@infosys.tuwien.ac.at) - Apr 16, 1996