You’ll notice that the use of the second “comparator” forms of the functions are not exhaustively tested in the above example, but the use of a comparator is the same as in the first part of the example.
The test of nth_element does not use the NString objects because it’s simpler to see what’s going on if ints are used. Notice 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 can see that the elements before the nth element will be less than or equal to the nth element.
Locating elements in sorted ranges
Once a range is sorted, there are a group of operations that can be used to find elements within those ranges. In the following functions, there are always two forms, one that assumes the intrinsic operator< has been used to perform the sort, and the second that must be used if some other comparison function object has been used to perform 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). Returns last if value is not found.
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). Returns last if value is not found.
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value);
pair<ForwardIterator, ForwardIterator>
Chapter 15: Multiple Inheritance
316
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 last if value is not found.
Example
Here, we can use the approach from the previous example:
//: C05:SortedSearchTest.cpp //{L} ../C04/StreamTokenizer
// Test searching in sorted ranges #include "../C04/StreamTokenizer.h" #include "PrintSequence.h"
#include "NString.h" #include "../require.h" #include <algorithm> #include <fstream> #include <queue> #include <vector>
using namespace std;
int main() {
ifstream in("SortedSearchTest.cpp"); assure(in, "SortedSearchTest.cpp"); StreamTokenizer words(in); deque<NString> dstr;
string word;
while((word = words.next()).size() != 0) dstr.push_back(NString(word));
vector<NString> v(dstr.begin(), dstr.end()); sort(v.begin(), v.end());
print(v, "sorted");
typedef vector<NString>::iterator sit; sit it, it2;
string f("include");
cout << "binary search: "
<<binary_search(v.begin(), v.end(), f)
<<endl;
it = lower_bound(v.begin(), v.end(), f); it2 = upper_bound(v.begin(), v.end(), f); print(it, it2, "found range");
pair<sit, sit> ip =
Chapter 15: Multiple Inheritance
317
equal_range(v.begin(), v.end(), f); print(ip.first, ip.second,
"equal_range"); } ///:~
The input is forced to be the source code for this file because the word “include” will be used for a find string (since “include” appears many times). The file is tokenized into words that are placed into a deque (a better container when you don’t know how much storage to allocate), and left unsorted in the deque. The deque is copied into a vector via the appropriate constructor, and the vector is sorted and printed.
The binary_search( ) function only tells you if the object is there or not; lower_bound( ) and upper_bound( ) produce iterators to the beginning and ending positions where the matching objects appear. The same effect can be produced more succinctly using equal_range( ) (as shown in the previous chapter, with multimap and multiset).
Merging sorted ranges
As before, the first form of each function assumes the intrinsic operator< has been used to perform the sort. The second form must be used if some other comparison function object has been used to perform 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. 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 my own print template) work with arrays as well as containers.
Chapter 15: Multiple Inheritance
318
//: C05:MergeTest.cpp
// Test merging in sorted ranges #include <algorithm>
#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)); 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", " ");
//set_union is a merge that removes duplicates set_union(a, a + sz, a + sz, a + sz*2, b); print(b, b + sz*2, "set_union", " "); inplace_merge(a, a + sz, a + sz*2);
print(a, a + sz*2, "inplace_merge", " ");
}///:~
In main( ), instead of creating two separate arrays both ranges will be 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 the duplicates. Finally, inplace_merge( ) is used to combine both parts of a.
Set operations on sorted ranges
Once ranges have been sorted, you can perform mathematical set operations on them.
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
bool includes (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, StrictWeakOrdering binary_pred);
Returns true if [first2, last2) is a subset of [first1, last1). Neither range is required to hold only unique elements, but if [first2, last2) holds n elements of a particular value, then [first1, last1) must also hold n elements if the result is to be true.
Chapter 15: Multiple Inheritance
319
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result,
StrictWeakOrdering binary_pred);
Creates the mathematical union of two sorted ranges in the result range, returning the end of the output range. Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets, then the resulting set will contain the larger number of identical values.
OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
Produces, in result, the intersection of the two input sets, returning the end of the output range. That is, the set of values that appear in both input sets. Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets, then the resulting set will contain the smaller number of identical values.
OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
Produces, in result, the mathematical set difference, returning the end of the output range. All the elements that are in [first1, last1) but not in [first2, last2) are placed in the result set. Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets (n times in set 1 and m times in set 2), then the resulting set will contain max(n-m, 0) copies of that value.
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
Constructs, in result, the set containing:
•All the elements in set 1 that are not in set 2
•All the elements in set 2 that are not in set 1.
Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets (n times in set 1 and m times in set 2), then the resulting set
Chapter 15: Multiple Inheritance
320