Partition Algorithms

A collection is partitioned if similar objects are grouped, based on some rule that separates those objects into two clusters.

For example, the following collection of numbers is partitioned into even and odd numbers. All of the even numbers are grouped at the start of the container, whilst the odd are grouped at the end:

14, -6, 2, 7, 1, 5

Specifically, we can imagine this partition is generated based on the following rule:

1[](int x){
2  return x % 2 == 0;
3}

In our collection, every element for which this function returns true (that is, every even number) occurs before every element for which the function returns false (that is, every odd number)

Partitioning vs Sorting

Partitioning a collection closely relates to the idea of sorting it. For example, the following collection is partitioned such that all negative numbers occur before all positive numbers:

1-6, -1, -2, 7, 1, 5

Sorting the collection would also generate an ordering that obeys that same partitioning rule:

1-6, -2, -1, 1, 5, 7

The key difference is that sorting a collection can require significantly more operations than partitioning it. As such, if our use case only requires partitioning our collection, we can get large performance benefits by not unnecessarily sorting everything.

This lesson introduces the 3 main standard library algorithms we have for creating partitioned collections:

• partition(): Partitions a collection in-place
• stable_partition(): Partitions a collection in place, whilst maintaining the previous relative order of elements within each partition
• partition_copy(): Partitions a collection into two new collections

We also cover two other related algorithms, that can help us when working with partitions:

• is_partitioned(): Returns a boolean representing whether a collection is partitioned
• partition_point(): Determines the position within the collection where one partition ends and the other starts

All of these algorithms are within the <algorithm> header and belong to the std::ranges namespace.

partition()

The most basic partitioning function in the standard library is std::ranges::partition(). It accepts a range to act upon, and a function that determines which partition each object belongs in.

This function will be called for every object in our collection, receiving that object as an argument. It then needs to return a boolean true or false value.

Our collection will be reordered such that all objects for which that function returned true occur before those for which it returned false.

Below, we partition our range such that all negative numbers appear before all non-negative numbers:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, -6, 7, 2, 5, 4};
7
8  std::ranges::partition(A, [](int x){
9    return x % 2 == 0;
10  });
11
12  for (int x : A) { std::cout << x << ", "; }
13}

14, -6, 2, 7, 5, 1,

Return Type

The partition() function returns a subrange, representing the second partition within the collection. It is the partition for which our predicate returned false. In this case, it is the partition containing all odd numbers:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, -6, 7, 2, 5, 4};
7
8  auto isEven{[](int x){ return x % 2 == 0; }};
9
10  auto SecondSR{
11    std::ranges::partition(A, isEven)};
12
13  std::cout << "Second Partition Size: "
14    << SecondSR.size() << '\n';
15
16  for (int x : SecondSR) {
17    std::cout << x << ", ";
18  }
19}

1Second Partition Size: 3
27, 5, 1,

This subrange, and its methods, are useful for most other follow-up operations we would need to perform.

For example, we can get an iterator representing the partition point using the begin() method on this subrange. Any object prior to that partition point belongs to the first partition, while any object from that point forward belongs to the second partition.

Below, we use this value to create a subrange for the first partition:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, -6, 7, 2, 5, 4};
7
8  auto isEven{[](int x){ return x % 2 == 0; }};
9
10  auto SecondSR{
11    std::ranges::partition(A, isEven)};
12
13  std::ranges::subrange FirstSR{
14    A.begin(), SecondSR.begin()};
15
16  std::cout << "First Partition Size: "
17    << FirstSR.size() << '\n';
18
19  for (int x : FirstSR) {
20    std::cout << x << ", ";
21  }
22}

1First Partition Size: 3
24, -6, 2,

stable_partition()

The stable_partition() algorithm works similarly to partition(), except the order of elements within each partition is constrained to match the order they had originally.

After using the basic partition() algorithm, there are often multiple ways in which our collection could be ordered.

For example, given the following collection:

1-1, -6, 1, 5, -2, 7

If we wanted to partition it such that negative numbers occur before positive numbers, there are many valid solutions. Some options include:

1-6, -1, -2, 7, 1, 5
2-1, -2. -6, 1, 5, 7
3-6, -2. -1, 5, 1, 7

The partition() algorithm could result in any of these outcomes and many others. But stable_partition() only has one valid solution:

1-1, -6, -2, 1, 5, 7

Within each partition, -1, -6, -2, and 1, 5, 7, the ordering of elements matches the ordering of those same elements within the original collection.

For example, in the original collection, -1 was before -6, and so that is also true in the resulting partition. The same restriction applies to every other element.

Ensuring this rule holds comes with a performance cost so, unless we require this behavior, we should just use the basic partition() algorithm.

The stable_partition() algorithm has the same API as the partition() algorithm, so we use it in the same way:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{-1, -6, 1, 5, -2, 7};
7
8  auto isNegative{[](int x){ return x < 0; }};
9
10  auto SecondSR{
11    std::ranges::stable_partition(
12      A, isNegative)};
13
14  std::ranges::subrange FirstSR{
15    A.begin(), SecondSR.begin()};
16
17  std::cout << "Container: ";
18  for (int x : A) { std::cout << x << ", "; }
19
20  std::cout << "\nFirst Partition: ";
21  for (int x : FirstSR) {
22    std::cout << x << ", ";
23  }
24
25  std::cout << "\nSecond Partition: ";
26  for (int x : SecondSR) {
27    std::cout << x << ", ";
28  }
29}

1Container: -1, -6, -2, 1, 5, 7,
2First Partition: -1, -6, -2,
3Second Partition: 1, 5, 7,

partition_copy()

Rather than rearranging elements in place, the partition_copy() algorithm copies each partition into a different collection. The original container is left unchanged.

The starting point of each output collection is represented by an iterator:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, -6, 4, 2, 5, 7};
7  std::vector<int> Even;
8  std::vector<int> Odd;
9
10  // Dangerous - see note below
11  Even.resize(3);
12  Odd.resize(3);
13
14  auto isEven{[](int x){ return x % 2 == 0; }};
15
16  std::ranges::partition_copy(
17    A, Even.begin(), Odd.begin(), isEven);
18
19  std::cout << "Container: ";
20  for (int x : A) { std::cout << x << ", "; }
21
22  std::cout << "\nEven: ";
23  for (int x : Even) { std::cout << x << ", "; }
24
25  std::cout << "\nOdd: ";
26  for (int x : Odd) { std::cout << x << ", "; }
27}

1Container: 1, -6, 4, 2, 5, 7,
2Even: -6, 4, 2,
3Odd: 1, 5, 7,

It is on us to ensure that each output iterator points to a location that has enough space to receive each partition. In the previous example, we resized each collection to accommodate 3 objects, because we knew which size each partition would be.

In real-world use cases, we rarely know this in advance, so we typically make our output containers match the size of the collection we’re partitioning:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, -6, 4, 2, 5, 7};
7  std::vector<int> Even;
8  std::vector<int> Odd;
9
10  Even.resize(A.size());
11  Odd.resize(A.size());
12
13  auto isEven{[](int x){ return x % 2 == 0; }};
14
15  std::ranges::partition_copy(
16    A, Even.begin(), Odd.begin(), isEven);
17
18  std::cout << "Even: ";
19  for (int x : Even) { std::cout << x << ", "; }
20}

Naturally, this means one or both of our output containers are going to be oversized. We can see that in the output of the previous program. Our partition only contains three objects, but our container holds 6 objects. Therefore, we have additional default-constructed integers:

1Even: -6, 4, 2, 0, 0, 0,

However, the return value of partition_copy() can help us here.

Return Type

The partition_copy() algorithm returns a std::partition_copy_result, which is an alias for std::ranges::in_out_out_result.

This is a struct that is commonly used for any range-based standard library algorithm that receives one input and produces two outputs. It contains three members:

• in: An iterator pointing to the end of the input range. This is most useful if the range is defined using a sentinel. Otherwise, it will be equivalent to the iterator returned from the input container’s end() method
• o1: An iterator pointing to the last element copied into the first output range. That is, the end of our first partition - the last object for which our predicate returned true
• o2: An iterator pointing to the last element copied into the second output range. That is, the end of our second partition - the last object for which our predicate returned false

Below, we show how we can use these returned iterators for some follow-up operations on one of our output containers:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, -6, 4, 2, 5, 7};
7  std::vector<int> Even;
8  std::vector<int> Odd;
9
10  Even.resize(A.size());
11  Odd.resize(A.size());
12
13  auto isEven{[](int x){ return x % 2 == 0; }};
14
15  auto [in, o1, o2]{
16    std::ranges::partition_copy(
17      A, Even.begin(), Odd.begin(), isEven)};
18
19  std::cout << "Even Partition Size: "
20    << o1 - Even.begin();
21
22  std::cout <<
23    "\nLast Element in Even Partition: "
24    << *(o1 - 1);
25
26  // Erasing excess elements from the output
27  Even.resize(o1 - Even.begin());
28
29  std::cout << "\nContents: ";
30  for (int x : Even) { std::cout << x << ", "; }
31}

1Even Partition Size: 3
2Last Element in Even Partition: 2
3Contents: -6, 4, 2,

is_partitioned()

The is_partioned() algorithm returns true if a range is partitioned, with respect to the predicate we provide:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{2, -6, 4, 1, -5, 3};
7
8  auto isEven{[](int x){ return x % 2 == 0; }};
9  auto isNeg{[](int x){ return x < 0; }};
10
11  if (std::ranges::is_partitioned(A, isEven)) {
12    std::cout <<
13      "A is partitioned with respect to isEven";
14  }
15
16  if (!std::ranges::is_partitioned(A, isNeg)) {
17    std::cout <<
18      "\nA is NOT partitioned with respect to isNeg";
19  }
20}

1A is partitioned with respect to isEven
2A is NOT partitioned with respect to isNeg

partition_point()

The partition_point() algorithm returns an iterator to the first object for which a provided predicate returns false. If our range is partitioned, this means it returns an iterator to the first object in the second partition:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{2, -6, 4, 1, -5, 3};
7  auto isEven{[](int x){ return x % 2 == 0; }};
8  auto PartitionPoint{
9    std::ranges::partition_point(A, isEven)};
10
11  std::cout <<
12    "The first element in the second partition is "
13    // Dangerous - see note below
14    << *PartitionPoint;
15}

1The first element in the second partition is 1

Note that the iterator may be past-the-end of the input container, so we should be careful when dereferencing it. This can occur when our predicate returns true for every object - that is, every object is in the first partition:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{2, -6, 4, 6, 0, 8};
7  auto isEven{[](int x){ return x % 2 == 0; }};
8  auto PartitionPoint{
9    std::ranges::partition_point(A, isEven)};
10
11  if (PartitionPoint == A.end()) {
12    std::cout <<
13      "The second partition is empty";
14  }
15}

1The second partition is empty

The iterator returned by partition_point() is equivalent to the start of the subrange returned by the partition() call that would have partitioned the collection using the same predicate.

Therefore, it is useful for follow-up operations in the same way we covered earlier:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{2, -6, 4, 8, 1, -5};
7  auto isEven{[](int x){ return x % 2 == 0; }};
8  auto PartitionPoint{
9    std::ranges::partition_point(A, isEven)};
10
11  std::cout << "First partition's size: "
12    << PartitionPoint - A.begin();
13
14  std::cout << "\nSecond partition's size: "
15    << A.end() - PartitionPoint;
16
17  std::cout << "\nSecond partition subrange: ";
18  for (auto x : std::ranges::subrange{
19         PartitionPoint, A.end()}) {
20    std::cout << x << ", ";
21  }
22}

1First partition's size: 4
2Second partition's size: 2
3Second partition subrange: 1, -5,

Partitioning Custom Types

Naturally, we’re not restricted to just partitioning containers of simple, built-in types.

Below, we partition a container of custom Actor objects, such that all the unfriendly characters are moved to the start of the collection:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5enum class Mood { Friendly, Neutral, Hostile };
6
7class Actor {
8public:
9  Actor(std::string Name, Mood Mood)
10    : Name{Name}, Mood{Mood}{}
11
12  Mood Mood;
13  std::string Name;
14};
15
16int main(){
17  using enum Mood;
18  std::vector<Actor> Actors{
19    {"Angry Goblin", Hostile},
20    {"Helpful Guard", Friendly},
21    {"Surly Goat", Neutral},
22  };
23
24  auto isFriendly{[](Actor& A) {
25      return A.Mood == Friendly;
26    }};
27
28  auto Unfriendlies{
29    std::ranges::partition(Actors, isFriendly)};
30
31  std::cout << "Unfriendlies: ";
32  for (Actor& A : Unfriendlies) {
33    std::cout << A.Name << ", ";
34  }
35}

1Unfriendlies: Angry Goblin, Surly Goat,

Type Requirements and std::permutable

Like most algorithms that rearrange objects in a container, the type of those objects needs to support such operations.

Our previous Actor type supported this by default, but that is not always the case. The compiler may report an error where our type does not satisfy the std::permutable concept, meaning we need to add this capability to our type manually.

This means we will need to add appropriate move semantics to our type. This can include adding a move assignment operator, or an implementation of the swap function:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5enum class Mood { Friendly, Neutral, Hostile };
6
7class Actor {
8public:
9  Actor(std::string Name, Mood Mood)
10    : Name{Name}, Mood{Mood}{}
11
12  Actor(const Actor& Other) = default;
13
14  Actor& operator=(Actor&& Other){
15    std::swap(Name, Other.Name);
16    std::swap(Mood, Other.Mood);
17    return *this;
18  }
19
20  Mood Mood;
21  std::string Name;
22};
23
24void swap(Actor& A, Actor& B){
25  std::cout << "Swapping " << A.Name
26    << " and " << B.Name << '\n';
27  std::swap(A.Name, B.Name);
28  std::swap(A.Mood, B.Mood);
29}
30
main function (Unchanged)|Show
31int main(){/*...*/};

1Swapping Angry Goblin and Helpful Guard
2Unfriendlies: Angry Goblin, Surly Goat,

Even in scenarios where this is not required, our code may be more performant if we implement these capabilities. Whilst an algorithm may work without move semantics and swap() function, it may do so using slow copy operations.

We covered copy and move semantics in more detail in an earlier chapter:

Copy Semantics and Return Value Optimization

Learn how to control exactly how our objects get copied, and take advantage of copy elision and return value optimization (RVO)

Move Semantics

Learn how we can improve the performance of our types using move constructors, move assignment operators and std::move()

Projections

As with other range-based algorithms, we can pass a projection function as an additional argument to the partitioning algorithms.

The objects in the collection are passed to this projection function, which returns a new object, referred to as the projection of our original. This new object - the projection - is what gets passed to our predicate, to determine how our objects are partitioned.

The projection does not need to be the same type as the original object, as the following example demonstrates.

Within our partition() call, we are providing a third argument - a function that projects each actor to their Mood field.

Our partition predicate then receives these Mood objects, rather than the entire Player:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Mood and Character Classes (Unchanged)|Show
5enum class Mood {/*...*/};
16
17int main(){
18  using enum Mood;
19  std::vector<Actor> Actors{
20    {"Angry Goblin", Hostile},
21    {"Helpful Guard", Friendly},
22    {"Surly Goat", Neutral},
23  };
24
25  auto isFriendly{
26    [](Mood m){ return m == Friendly; }};
27
28  auto Unfriendlies{
29    std::ranges::partition(Actors, isFriendly,
30                           &Actor::Mood)};
31
32  std::cout << "Unfriendlies: ";
33  for (Actor& c : Unfriendlies) {
34    std::cout << c.Name << ", ";
35  }
36}

1Unfriendlies: Angry Goblin, Surly Goat,

The option of providing a projection function is also available with all of the other algorithms we covered in this lesson.

Using Iterator-Sentinel Pairs

Our previous examples provided our ranges as a single argument of a type that implements a begin() and end() method. However, as usual, we can define a range using any iterator-sentinel pair, passed as two arguments.

Below, we use this technique to partition a container, excluding the first and last elements:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, -6, 3, 7, 2, 5, -2, 4};
7
8  std::ranges::partition(
9    A.begin() + 1, A.end() - 1, [](int x){
10      return x % 2 == 0;
11  });
12
13  for (int x : A) { std::cout << x << ", "; }
14}

11, -6, -2, 2, 7, 5, 3, 4,

Using Iterator-Based Algorithms

This lesson focused on algorithms that are part of the <ranges> library, introduced in C++20. Older, iterator-based algorithms are available for every function we covered in this lesson.

These are available by excluding ranges from the identifier. For example, we can use std::partition instead of std::ranges::partition:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, -6, 3, 7, 2, 5, -2, 4};
7
8  std::partition(
9    A.begin() + 1, A.end() - 1, [](int x){
10      return x % 2 == 0;
11  });
12
13  for (int x : A) { std::cout << x << ", "; }
14}

11, -6, -2, 2, 7, 5, 3, 4,

Compared to their range-based counterparts, the iterator-based variations of these algorithms have three disadvantages:

• We must provide our collections as two arguments - we don’t have the option of providing a single argument, such as a container or a view
• The end of our input must be provided as an iterator, rather than the more flexible sentinel option of the range-based algorithms
• They do not support projection functions

Summary

In this lesson, we introduced the standard library partitioning algorithms. The key takeaways are:

• Partitioning is the process of dividing a collection into two parts based on a predicate, grouping similar objects together
• Partitioning is subtly different from sorting in that it doesn't care about the ordering of elements within each partition.
• The partition() algorithm partitions a container based on a predicate we provide, without preserving the relative order of elements.
• stable_partition() also partitions elements but preserves their relative order.
• partition_copy() partitions elements into two new collections based on a predicate, leaving the original collection unchanged.
• is_partitioned() checks if a range is partitioned according to a given predicate.
• partition_point() finds the partition point in a range that has been partitioned.
• We can partition containers of custom types by defining appropriate predicates.
• The std::permutable concept ensures that elements can be reordered through moving.
• Projections allow partitioning algorithms to act based on derived data, or specific properties of custom types.
• Iterator-sentinel pairs can define ranges for partitioning, allowing for flexible manipulation of container elements.

Next Lesson

Set Algorithms

An introduction to set algorithms, and how to implement them using the C++ standard library

ContinueView Course