print(v.begin(), cit, "after remove_if", "");
//Copying versions are not shown for remove
//and remove_if.
sort(v.begin(), cit); print(v.begin(), cit, "sorted", ""); vector<char> v2;
unique_copy(v.begin(), cit, back_inserter(v2)); print(v2, "unique_copy", "");
// Same behavior:
cit = unique(v.begin(), cit, equal_to<char>()); print(v.begin(), cit, "unique", "");
} ///:~
The vector<char> v is filled with randomly-generated characters and then copied into a set. Each element of the set is used in a remove statement, but the entire vector v is printed out each time so you can see what happens to the rest of the range, after the resulting endpoint (which is stored in cit).
To demonstrate remove_if( ), the address of the Standard C library function isupper( ) (in <cctype> is called inside of the function object class IsUpper, an object of which is passed as the predicate for remove_if( ). This only returns true if a character is uppercase, so only lowercase characters will remain. Here, the end of the range is used in the call to print( ) so only the remaining elements will appear. The copying versions of remove( ) and remove_if( ) are not shown because they are a simple variation on the non-copying versions which you should be able to use without an example.
The range of lowercase letters is sorted in preparation for testing the “unique” functions (the “unique” functions are not undefined if the range isn’t sorted, but it’s probably not what you want). First, unique_copy( ) puts the unique elements into a new vector using the default element comparison, and then the form of unique( ) that takes a predicate is used; the predicate used is the built-in function object equal_to( ), which produces the same results as the default element comparison.
Sorting and operations on sorted ranges
There is a significant category of STL algorithms which require that the range they operate on be in sorted order.
There is actually only one “sort” algorithm used in the STL. This algorithm is presumably the fastest one, but the implementer has fairly broad latitude. However, it comes packaged in various flavors depending on whether the sort should be stable, partial or just the regular sort. Oddly enough, only the partial sort has a copying version; otherwise you’ll need to make your own copy before sorting if that’s what you want. If you are working with a very large number of items you may be better off transferring them to an array (or at least a vector, which uses an array internally) rather than using them in some of the STL containers.
Chapter 15: Multiple Inheritance
311
Once your sequence is sorted, there are many operations you can perform on that sequence, from simply locating an element or group of elements to merging with another sorted sequence or manipulating sequences as mathematical sets.
Each algorithm involved with sorting or operations on sorted sequences has two versions of each function, the first that uses the object’s own operator< to perform the comparison, and the second that uses an additional StrictWeakOrdering object’s operator( )(a, b) to compare two objects for a < b. Other than this there are no differences, so the distinction will not be pointed out in the description of each algorithm.
Sorting
One STL container (list) has its own built-in sort( ) function which is almost certainly going to be faster than the generic sort presented here (especially since the list sort just swaps pointers rather than copying entire objects around). This means that you’ll only want to use the sort functions here if (a) you’re working with an array or a sequence container that doesn’t have a sort( ) function or (b) you want to use one of the other sorting flavors, like a partial or stable sort, which aren’t supported by list’s sort( ).
void sort(RandomAccessIterator first, RandomAccessIterator last); void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering binary_pred);
Sorts [first, last) into ascending order. The second form allows a comparator object to determine the order.
void stable_sort(RandomAccessIterator first, RandomAccessIterator last); void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering binary_pred);
Sorts [first, last) into ascending order, preserving the original ordering of equivalent elements (this is important if elements can be equivalent but not identical). The second form allows a comparator object to determine the order.
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering binary_pred);
Sorts the number of elements from [first, last) that can be placed in the range [first, middle). The rest of the elements end up in [middle, last), and have no guaranteed order. The second form allows a comparator object to determine the order.
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);
RandomAccessIterator partial_sort_copy(InputIterator first,
Chapter 15: Multiple Inheritance
312
InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, StrictWeakOrdering binary_pred);
Sorts the number of elements from [first, last) that can be placed in the range [result_first, result_last), and copies those elements into [result_first, result_last). If the range [first, last) is smaller than [result_first, result_last), then the smaller number of elements is used. The second form allows a comparator object to determine the order.
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, StrictWeakOrdering binary_pred);
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 be less than (they could also be equivalent to) whatever element ends up at location nth and all the elements in the range (nth, last] will be greater than whatever element ends up location nth. However, neither range 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( ).
Example
The StreamTokenizer class from the previous chapter is used to break a file into words, and each word is turned into an NString and added to a deque<NString>. Once the input file is completely read, a vector<NString> is created from the contents of the deque. The vector is then used to demonstrate the sorting algorithms:
//: C05:SortTest.cpp
//{L} ../C04/StreamTokenizer
// Test different kinds of sorting #include "../C04/StreamTokenizer.h" #include "NString.h"
#include "PrintSequence.h" #include "Generators.h" #include "../require.h" #include <algorithm> #include <fstream> #include <queue>
#include <vector> #include <cctype> using namespace std;
Chapter 15: Multiple Inheritance
313
// For sorting NStrings and ignore string case: struct NoCase {
bool operator()(
const NString& x, const NString& y) {
/* Somthing's wrong with this approach but I can't seem to see it. It would be much faster:
const string& lv = x; const string& rv = y;
int len = min(lv.size(), rv.size()); for(int i = 0; i < len; i++)
if(tolower(lv[i]) < tolower(rv[i])) return true;
return false;
}
*/
// Brute force: copy, force to lowercase: string lv(x);
string rv(y); lcase(lv); lcase(rv); return lv < rv;
}
void lcase(string& s) { int n = s.size();
for(int i = 0; i < n; i++) s[i] = tolower(s[i]);
}
};
int main(int argc, char* argv[]) { requireArgs(argc, 1);
ifstream in(argv[1]); assure(in, argv[1]); StreamTokenizer words(in); deque<NString> nstr; string word;
while((word = words.next()).size() != 0) nstr.push_back(NString(word));
print(nstr);
// Create a vector from the contents of nstr: vector<NString> v(nstr.begin(), nstr.end()); sort(v.begin(), v.end());
print(v, "sort");
Chapter 15: Multiple Inheritance
314
//Use an additional comparator object: sort(v.begin(), v.end(), NoCase()); print(v, "sort NoCase"); copy(nstr.begin(), nstr.end(), v.begin()); stable_sort(v.begin(), v.end());
print(v, "stable_sort");
//Use an additional comparator object: stable_sort(v.begin(), v.end(),
greater<NString>());
print(v, "stable_sort greater"); copy(nstr.begin(), nstr.end(), v.begin());
//Partial sorts. The additional comparator
//versions are obvious and not shown here. partial_sort(v.begin(),
v.begin() + v.size()/2, v.end()); print(v, "partial_sort");
//Create a vector with a preallocated size: vector<NString> v2(v.size()/2); partial_sort_copy(v.begin(), v.end(),
v2.begin(), v2.end()); print(v2, "partial_sort_copy");
//Finally, the weakest form of ordering: vector<int> v3(20);
generate(v3.begin(), v3.end(), URandGen(50)); print(v3, "v3 before nth_element");
int n = 10;
vector<int>::iterator vit = v3.begin() + n; nth_element(v3.begin(), vit, v3.end()); cout << "After ordering with nth = " << n
<<", nth element is " << v3[n] << endl; print(v3, "v3 after nth_element");
}///:~
The first class is a binary predicate used to compare two NString objects while ignoring the case of the strings. You can pass the object into the various sort routines to produce an alphabetic sort (rather than the default lexicographic sort, which has all the capital letters in one group, followed by all the lowercase letters).
As an example, try the source code for the above file as input. Because the occurrence numbers are printed along with the strings you can distinguish between an ordinary sort and a stable sort, and 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.”
Chapter 15: Multiple Inheritance
315