Sorting
The sort algorithms require ranges delimited by random-access iterators, such as a vector or deque. The list container has its own built-in sort( ) function, since it only supports bi-directional iteration.
void sort(RandomAccessIterator first, RandomAccessIterator last); void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);
Sorts [first, last) into ascending order. The first form uses operator< and the second form uses the supplied 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.).
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.
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); RandomAccessIterator partial_sort_copy(InputIterator first, 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), the smaller number of elements is used.
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 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<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);
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<NString>. The vector is then used to demonstrate the various sorting and searching algorithms.
//: C06:SortedSearchTest.cpp
// Test searching in sorted ranges
#include <algorithm>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <cstddef>
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
#include "NString.h"
#include "PrintSequence.h"
#include "../require.h"
using namespace std;