Examples
Figure: partition.
Use partition to just divide the range into two groups: all elements that satisfy the predicate, followed by all elements that don't. This is all you need to answer questions like these:
"Who are all the students with a grade of B+ or better?"
For example, partition( students.begin(), students.end(), GradeAtLeast("B+") ); does the work and returns an iterator to the first student whose grade is not at least B+.
"What are all the products with weight less than 10kg?"
For example, partition( products.begin(), products.end(), WeightUnder(10) ); does the work and returns an iterator to the first product whose weight is 10kg or less.
Figure: nth_element.
Use nth_element to put a single element in the correct nth position it would occupy if the range were completely sorted, and with all other elements correctly preceding or following that nth element. This is all you need to answer questions like these:
"Who are my top 20 salespeople?"
For example, nth_element( s.begin(), s.begin()+19, s.end(), SalesRating ); puts the 20 best elements at the front.
"What is the item with the median level of quality in this production run?"
That element would be in the middle position of a sorted range. To find it, do nth_element( run.begin(), run.begin()+run.size()/2, run.end(), ItemQuality );.
"What is the item whose quality is at the 75^{th} percentile?"
That item would be 25% of the way through the sorted range. To find it, do nth_element( run.begin(), run.begin()+run.size()*.25, run.end(), ItemQuality );.
Figure: partial_sort.
partial_sort does the work of nth_element, plus the elements preceding the nth are all in their correct sorted positions. Use partial_sort to answer questions similar to those nth_element answers, but where you need the elements that match to be sorted (and those that don't match don't need to be sorted). This is all you need to answer questions like, "Who are the first, second, and thirdplace winners?" For example, partial_sort( contestants.begin(), contestants.begin()+3, contestants.end(), ScoreCompare ); puts the top three contestants, in order, at the front of the containerand no more.
