Partitioning

[next] [prev] [prev-tail] [tail] [up]

1.5.3.11 Partitioning

nth_element(r,r,r)

nth_element(r,r,r,bpred)

Partition a range of values so that the value pointed to by the middle r in the parameter list is in its correct sorted position, and no element to its left is greater than any element to its right.

b partition(b,b,upred)

Partition a range of values using a predicate, and return an iterator pointing to the first value for which upred returns false.

b stable_partition(b,b,upred)

Partition a range using a predicate without altering the relative order of the values, and return an iterator pointing to the first value for which upred returns false.

An example of partition:
std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};
auto it = std::partition(v.begin(), v.end(),
                         [](int i){return i % 2 == 0;});
  std::copy(std::begin(v), it,
               std::ostream_iterator<int>(std::cout, "␣"));
  std::copy(it, std::end(v),
               std::ostream_iterator<int>(std::cout, "␣"));
  \\output: 0 8 2 6 4   5 3 7 1 9
Partition return: Iterator to the first element of the second group.
All of the elements before this new nth element are less than or equal to the elements after the new nth element. 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.
If you use nth_element on most of the range, It may be slower than a full sort.

[next] [prev] [prev-tail] [front] [up]