Thinking In C++. Volume 2: Practical Programming

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

  v = original;

  // Move iterator to a quarter position

  it = v.begin();

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

    it++;

  // Less elements to copy from than to the destination

  partial_sort_copy(v.begin(), it, w.begin(), w.end());

  print(w.begin(), w.end(), "partial_sort_copy");

  // Not enough room in destination

  partial_sort_copy(v.begin(), v.end(), w.begin(),

    w.end());

  print(w.begin(), w.end(), "w partial_sort_copy");

  // v remains the same through all this process

  assert(v == original);

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

  cout << "The nth_element = " << *it << endl;

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

  string f = original[rand() % original.size()];

  cout << "binary search: "

    << binary_search(v.begin(), v.end(), f)

    << endl;

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

  it = lower_bound(v.begin(), v.end(), f);

  it2 = upper_bound(v.begin(), v.end(), f);

  print(it, it2, "found range");

  pair ip =

    equal_range(v.begin(), v.end(), f);

  print(ip.first, ip.second,

    "equal_range");

} ///:~

This example uses the NString class seen earlier, which stores an occurrence number with copies of a string. The call to stable_sort( ) shows how the original order for objects with equal strings is preserved. You can also see what happens during a partial sort (the remaining unsorted elements are in no particular order). There is no "partial stable sort."^.

Notice in the call to nth_element( ) that, whatever the nth element turns out to be (which will vary from one run to another because of URandGen), the elements before that are less, and after that are greater, but the elements have no particular order other than that. Because of URandGen, there are no duplicates, but if you use a generator that allows duplicates, you’ll see that the elements before the nth element will be less than or equal to the nth element.

This example also illustrates all three binary search algorithms. As advertised, lower_bound( ) refers to the first element in the sequence equal to a given key, upper_bound( ) points one past the last, and equal_range( ) returns both results as a pair^.

Merging sorted ranges

As before, the first form of each function assumes the intrinsic operator< performs the sort. The second form 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.

OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);

Copies elements from [first1, last1) and [first2, last2) into result, such that the resulting range is sorted in ascending order. This is a stable operation.

void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, StrictWeakOrdering binary_pred);

This assumes that [first, middle) and [middle, last) are each sorted ranges in the same sequence. The two ranges are merged so that the resulting range [first, last) contains the combined ranges in sorted order^.

Example

It’s easier to see what goes on with merging if ints are used; the following example also emphasizes how the algorithms (and our own print template) work with arrays as well as containers^.

//: C06:MergeTest.cpp

// Test merging in sorted ranges

#include

#include "PrintSequence.h"

#include "Generators.h"

using namespace std;

int main() {

  const int sz = 15;

  int a[sz*2] = {0};

  // Both ranges go in the same array:

  generate(a, a + sz, SkipGen(0, 2));

  a[3] = 4;

  a[4] = 4;

  generate(a + sz, a + sz*2, SkipGen(1, 3));

  print(a, a + sz, "range1", " ");

  print(a + sz, a + sz*2, "range2", " ");

  int b[sz*2] = {0}; // Initialize all to zero

  merge(a, a + sz, a + sz, a + sz*2, b);

  print(b, b + sz*2, "merge", " ");

  // Reset b

  for(int i = 0; i < sz*2; i++)

    b[i] = 0;

  inplace_merge(a, a + sz, a + sz*2);

  print(a, a + sz*2, "inplace_merge", " ");

  int* end = set_union(a, a + sz, a + sz, a + sz*2, b);

  print(b, end, "set_union", " ");

} ///:~

In main( ), instead of creating two separate arrays, both ranges are created end to end in the same array a. (This will come in handy for the inplace_merge.) The first call to merge( ) places the result in a different array, b. For comparison, set_union( ) is also called, which has the same signature and similar behavior, except that it removes duplicates from the second set. Finally, inplace_merge( ) combines both parts of a^.