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
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
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
//: C06:SortedSearchTest.cpp
// Test searching in sorted ranges
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include "NString.h"
#include "PrintSequence.h"
#include "../require.h"
using namespace std;
int main(int argc, char* argv[]) {
typedef vector
char* fname = "test.txt";
if(argc > 1) fname = argv[1];
ifstream in(fname);
assure(in, fname);
srand(time(0));
cout.setf(ios::boolalpha);
vector
copy(istream_iterator
istream_iterator
require(original.size() >= 4, "Must have four elements");
vector
w(original.size() / 2);
sort(v.begin(), v.end());
print(v.begin(), v.end(), "sort");
v = original;
stable_sort(v.begin(), v.end());
print(v.begin(), v.end(), "stable_sort");
v = original;
sit it = v.begin(), it2;
// Move iterator to middle
for(size_t i = 0; i < v.size() / 2; i++)
it++;
partial_sort(v.begin(), it, v.end());
cout << "middle = " << *it << endl;