4.2.3 Bidirectional Iterators

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

Bidirectional Iterator Requirements (additional to forward iterators'):

• pre/post decrement operator

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) {
  --last;
  cout << *last << " ";
}

Output: 2 1

template <class BidirectionalIterator, class Compare>
void bubble_sort (BidirectionalIterator first, BidirectionalIterator last,
                  Compare comp)
{
  BidirectionalIterator left_el = first, right_el = first;
  right_el++;
  while (first != last)
  {
    while (right_el != last) {
      if (comp(*right_el, *left_el)) iter_swap (left_el, right_el);
      right_el++;
      left_el++;
    }
    last--;
    left_el = first, right_el = first;
    right_el++;
  }
}

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