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[]) {
char* fname = "SortTest.cpp";
if(argc > 1) fname = argv[1];
ifstream in(fname);
assure(in, fname);
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");
// 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).Comment
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.”Comment
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.Comment
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.Comment
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.Comment
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);Comment
Tells you whether value appears in the sorted range [first, last).Comment
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);Comment
Returns an iterator indicating the first occurrence of value in the sorted range [first, last). Returns last if value is not found.Comment
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);Comment
Returns an iterator indicating one past the last occurrence of value in the sorted range [first, last). Returns last if value is not found.Comment
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value);pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);Comment
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.Comment
Example
Here, we can use the approach from the previous example:Comment
//: C08:SortedSearchTest.cpp
//{L} ../C07/StreamTokenizer ../TestSuite/Test
// Test searching in sorted ranges
//{-g++295}
//{-msc}
//{-mwcc}