Thinking In C++. Volume 2: Practical Programming

Just like partial_sort( ), nth_element( ) partially orders a range of elements. However, it’s much "less ordered" than partial_sort( ). The only thing that nth_element( ) guarantees is that whatever location you choose will become a dividing point. All the elements in the range [first, nth) will pair-wise satisfy the binary predicate (operator< by default, as usual), and all the elements in the range (nth, last] will not. However, neither subrange is in any particular order, unlike partial_sort( ) which has the first range in sorted order.

If all you need is this very weak ordering (if, for example, you’re determining medians, percentiles, and that sort of thing), this algorithm is faster than partial_sort( ).

Locating elements in sorted ranges

Once a range is sorted, you can use a group of operations to find elements within those ranges. In the following functions, there are always two forms. One assumes the intrinsic operator< performs the sort, and the second operator must be used if some other comparison function object performs the sort. You must use the same comparison for locating elements as you do to perform the sort; otherwise, the results are undefined. In addition, if you try to use these functions on unsorted ranges, the results will be undefined.

bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);

Tells you whether value appears in the sorted range [first, last).

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value); ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);

Returns an iterator indicating the first occurrence of value in the sorted range [first, last). If value is not present, an iterator to where it would fit in the sequence is returned^.

ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value); ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);

Returns an iterator indicating one past the last occurrence of value in the sorted range [first, last). If value is not present, an iterator to where it would fit in the sequence is returned.

pair equal_range(ForwardIterator first, ForwardIterator last, const T& value); pair equal_range(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);

Essentially combines lower_bound( ) and upper_bound( ) to return a pair indicating the first and one-past-the-last occurrences of value in the sorted range [first, last). Both iterators indicate the location where value would fit if it is not found.

You may find it surprising that the binary search algorithms take a forward iterator instead of a random access iterator. (Most explanations of binary search use indexing.) Remember that a random access iterator "is-a" forward iterator, and can be used wherever the latter is specified. If the iterator passed to one of these algorithms in fact supports random access, then the efficient logarithmic-time procedure is used, otherwise a linear search is performed.^[88]

Example

The following example turns each input word into an NString and added to a vector. The vector is then used to demonstrate the various sorting and searching algorithms^.

//: C06:SortedSearchTest.cpp

// Test searching in sorted ranges

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include "NString.h"

#include "PrintSequence.h"

#include "../require.h"

using namespace std;

int main(int argc, char* argv[]) {

  typedef vector::iterator sit;

  char* fname = "test.txt";

  if(argc > 1) fname = argv[1];

  ifstream in(fname);

  assure(in, fname);

  srand(time(0));

  cout.setf(ios::boolalpha);

  vector original;

  copy(istream_iterator(in),

    istream_iterator(), back_inserter(original));

  require(original.size() >= 4, "Must have four elements");

  vector v(original.begin(), original.end()),

    w(original.size() / 2);

  sort(v.begin(), v.end());

  print(v.begin(), v.end(), "sort");

  v = original;

  stable_sort(v.begin(), v.end());

  print(v.begin(), v.end(), "stable_sort");

  v = original;

  sit it = v.begin(), it2;

  // Move iterator to middle

  for(size_t i = 0; i < v.size() / 2; i++)

    it++;

  partial_sort(v.begin(), it, v.end());

  cout << "middle = " << *it << endl;