4.2.3 Bidirectional Iterators

In addition to forward iterators, bidirectional iterators satisfy the following requirements:

Bidirectional Iterator Requirements (additional to forward iterators'):

Bidirectional iterators allow algorithms to pass through the elements forward and backward.

list<int> l (1, 1);
l.push_back (2);	// list l: 1 2

list<int>::iterator first = l.begin();
list<int>::iterator last  = l.end();

while (last != first) {
  cout << *last << " ";

Output: 2 1

The bubble sort algorithm serves as an example for a multi-pass one-directional algorithm.
template <class BidirectionalIterator, class Compare>
void bubble_sort (BidirectionalIterator first, BidirectionalIterator last,
                  Compare comp)
  BidirectionalIterator left_el = first, right_el = first;
  while (first != last)
    while (right_el != last) {
      if (comp(*right_el, *left_el)) iter_swap (left_el, right_el);
    left_el = first, right_el = first;

The binary function object Compare has to be provided by the user of bubble_sort. Compare, which implements a binary predicate, takes two arguments and returns the result (true or false) of the predicate provided with the two arguments.

list<int> l;    
// fill list
bubble_sort (l.begin(), l.end(), less<int>() );    // sort ascendingly
bubble_sort (l.begin(), l.end(), greater<int>() ); // sort descendingly   

sorts the list ascendingly.

Continue with section 4.2.4

Back to index

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