# Partition Algorithms

An introduction to partitions, and the C++ standard library algorithms that create them
This lesson is part of theÂ course:

### Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, Unlimited Access
###### Ryan McCombe
Posted

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

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:

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

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

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

Such that 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:

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

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

-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:

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
std::vector A{1, -6, 7, 2, 5, 4};

std::ranges::partition(A, [](int x){
return x % 2 == 0;
});

for (int x : A) { std::cout << x << ", "; }
}
4, -6, 2, 7, 5, 1,

### Predicates

A function that returns a boolean is sometimes referred to as a predicate. So isEven() in our previous program is an example of aÂ predicate.

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:

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
std::vector A{1, -6, 7, 2, 5, 4};

auto isEven{[](int x){ return x % 2 == 0; }};

auto SecondSR{
std::ranges::partition(A, isEven)};

std::cout << "Second Partition Size: "
<< SecondSR.size() << '\n';

for (int x : SecondSR) {
std::cout << x << ", ";
}
}
Second Partition Size: 3
7, 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:

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
std::vector A{1, -6, 7, 2, 5, 4};

auto isEven{[](int x){ return x % 2 == 0; }};

auto SecondSR{
std::ranges::partition(A, isEven)};

std::ranges::subrange FirstSR{
A.begin(), SecondSR.begin()};

std::cout << "First Partition Size: "
<< FirstSR.size() << '\n';

for (int x : FirstSR) {
std::cout << x << ", ";
}
}
First Partition Size: 3
4, -6, 2,

## Partitioning Custom Types

Naturally, weâ€™re not restricted to just partitioning containers of simple, built-inÂ types.

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

#include <algorithm>
#include <iostream>
#include <vector>

enum class Mood { Friendly, Neutral, Hostile };

class Character {
public:
Character(std::string Name, Mood Mood)
: Name{Name}, Mood{Mood}{}

Mood Mood;
std::string Name;
};

int main(){
using enum Mood;
std::vector<Character> A{
{"Angry Goblin", Hostile},
{"Surly Goat", Neutral},
};

auto isFriendly{
[](Character& c){
return c.Mood == Friendly;
}};

auto Unfriendlies{
std::ranges::partition(A, isFriendly)};

std::cout << "Unfriendlies: ";
for (Character& c : Unfriendlies) {
std::cout << c.Name << ", ";
}
}
Unfriendlies: Angry Goblin, Surly Goat,

## Partition Type Requirements - std::permutable

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

Our previous Character 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 overload for the swapÂ function:

#include <algorithm>
#include <iostream>
#include <vector>

enum class Mood { Friendly, Neutral, Hostile };

class Character {
public:
Character(std::string Name, Mood Mood)
: Name{Name}, Mood{Mood}{}

Character(const Character& Other) = default;

Character& operator=(Character&& Other){
std::swap(Name, Other.Name);
std::swap(Mood, Other.Mood);
return *this;
}

Mood Mood;
std::string Name;
};

void swap(Character& A, Character& B){
std::cout << "Swapping " << A.Name
<< " and " << B.Name << '\n';
std::swap(A.Name, B.Name);
std::swap(A.Mood, B.Mood);
}

int main(){/*...*/};

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

Even in scenarios where this is not required, our code may be more performant if we implement these steps. We covered move semantics in more detail in an earlierÂ chapter:

## Projections

As with other range-based algorithms, we can pass a projection function as an additional argument to std::partition().

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 character to their MoodÂ field.

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

#include <algorithm>
#include <iostream>
#include <vector>

enum class Mood {/*...*/};

int main(){
using enum Mood;
std::vector<Character> A{
{"Angry Goblin", Hostile},
{"Surly Goat", Neutral},
};

auto isFriendly{
[](Mood m){ return m == Friendly; }};

auto Unfriendlies{
std::ranges::partition(A, isFriendly,
&Character::Mood)};

std::cout << "Unfriendlies: ";
for (Character& c : Unfriendlies) {
std::cout << c.Name << ", ";
}
}
Unfriendlies: Angry Goblin, Surly Goat,

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

## 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, -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:

-6, -1, -2, 7, 1, 5
-1, -2. -6, 1, 5, 7
-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, -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:

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
std::vector A{-1, -6, 1, 5, -2, 7};

auto isNegative{[](int x){ return x < 0; }};

auto SecondSR{
std::ranges::stable_partition(
A, isNegative)};
std::ranges::subrange FirstSR{
A.begin(), SecondSR.begin()};

std::cout << "Container: ";
for (int x : A) { std::cout << x << ", "; }

std::cout << "\nFirst Partition: ";
for (int x : FirstSR) {
std::cout << x << ", ";
}

std::cout << "\nSecond Partition: ";
for (int x : SecondSR) {
std::cout << x << ", ";
}
}
Container: -1, -6, -2, 1, 5, 7,
First Partition: -1, -6, -2,
Second 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:

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
std::vector A{1, -6, 4, 2, 5, 7};
std::vector<int> Even;
std::vector<int> Odd;

// Dangerous - see note below
Even.resize(3);
Odd.resize(3);

auto isEven{[](int x){ return x % 2 == 0; }};

std::ranges::partition_copy(
A, Even.begin(), Odd.begin(), isEven);

std::cout << "Container: ";
for (int x : A) { std::cout << x << ", "; }

std::cout << "\nEven: ";
for (int x : Even) { std::cout << x << ", "; }

std::cout << "\nOdd: ";
for (int x : Odd) { std::cout << x << ", "; }
}
Container: 1, -6, 4, 2, 5, 7,
Even: -6, 4, 2,
Odd: 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:

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
std::vector A{1, -6, 4, 2, 5, 7};
std::vector<int> Even;
std::vector<int> Odd;

Even.resize(A.size());
Odd.resize(A.size());

auto isEven{[](int x){ return x % 2 == 0; }};

std::ranges::partition_copy(
A, Even.begin(), Odd.begin(), isEven);

std::cout << "Even: ";
for (int x : Even) { std::cout << x << ", "; }
}

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:

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

However, the return value of partition_copy() can help us here. partition_copy() 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:

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
std::vector A{1, -6, 4, 2, 5, 7};
std::vector<int> Even;
std::vector<int> Odd;

Even.resize(A.size());
Odd.resize(A.size());

auto isEven{[](int x){ return x % 2 == 0; }};

auto [in, o1, o2] =
std::ranges::partition_copy(
A, Even.begin(), Odd.begin(), isEven);

std::cout << "Even Partition Size: "
<< o1 - Even.begin();

std::cout <<
"\nLast Element in Even Partition: "
<< *(o1 - 1);

// Erasing excess elements from the output
Even.resize(o1 - Even.begin());

std::cout << "\nContents: ";
for (int x : Even) { std::cout << x << ", "; }
}
Even Partition Size: 3
Last Element in Even Partition: 2
Contents: -6, 4, 2,

## is_partitioned()

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

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
std::vector A{2, -6, 4, 1, -5, 3};

auto isEven{[](int x){ return x % 2 == 0; }};
auto isNeg{[](int x){ return x < 0; }};

if (std::ranges::is_partitioned(A, isEven)) {
std::cout <<
"A is partitioned with respect to isEven";
}

if (!std::ranges::is_partitioned(A, isNeg)) {
std::cout <<
"\nA is NOT partitioned with respect to isNeg";
}
}
A is partitioned with respect to isEven
A 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:

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
std::vector A{2, -6, 4, 1, -5, 3};
auto isEven{[](int x){ return x % 2 == 0; }};
auto PartitionPoint =
std::ranges::partition_point(A, isEven);

std::cout <<
"The first element in the second partition is "
// Dangerous - see note below
<< *PartitionPoint;
}
The 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:

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
std::vector A{2, -6, 4, 6, 0, 8};
auto isEven{[](int x){ return x % 2 == 0; }};
auto PartitionPoint =
std::ranges::partition_point(A, isEven);

if (PartitionPoint == A.end()) {
std::cout <<
"The second partition is empty";
}
}
The 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:

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
std::vector A{2, -6, 4, 8, 1, -5};
auto isEven{[](int x){ return x % 2 == 0; }};
auto PartitionPoint =
std::ranges::partition_point(A, isEven);

std::cout << "First partition's size: "
<< PartitionPoint - A.begin();

std::cout << "\nSecond partition's size: "
<< A.end() - PartitionPoint;

std::cout << "\nSecond partition subrange: ";
for (auto x : std::ranges::subrange{
PartitionPoint, A.end()}) {
std::cout << x << ", ";
}
}
First partition's size: 4
Second partition's size: 2
Second partition subrange: 1, -5,

### Edit History

• â€” First Published

###### Ryan McCombe
Posted
This lesson is part of theÂ course:

### Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, Unlimited Access

###### Partition Algorithms

An introduction to partitions, and the C++ standard library algorithms that create them

This lesson is part of the course:

## Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

### This course includes:

• 114 Lessons
• 550+ Code Samples
• 96% Positive Reviews
• Regularly Updated
• Help and FAQ
Next Lesson

### Set Algorithms

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