# 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
Updated

A collection is partitioned when similar objects are grouped together based on a rule that separates those objects into twoÂ clusters.

For example, the following collection of numbers is partitioned into even and odd numbers. All the even numbers are grouped at the start of the container, while the odd numbers 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;
}

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 is closely related to 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 three 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 value is sometimes referred to as a predicate. The isEven() function in our previous example is aÂ predicate.

### Return Type

The partition() function returns a subrange representing the second partition within the collection, which consists of elements 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 obtain an iterator representing the partition point using the begin() method on this subrange. Any object before this partition point belongs to the first partition, while any object from that point onward 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,

## 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 instance, in the original collection, -1 was before -6, and this order is preserved in the resulting partition. The same restriction applies to all otherÂ elements.

Ensuring this rule holds comes with a performance cost, so unless we require this behavior, we should 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()

Instead of rearranging elements in place, the partition_copy() algorithm copies each partition into a different collection, leaving the original containerÂ unchanged.

The starting point of each output partition 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.

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

#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_partitioned() 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, meaning 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,

## Partitioning Custom Types

Naturally, we are not restricted to partitioning containers of simple, built-in typesÂ only.

Below, we partition a container of custom Actor 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 Actor {
public:
Actor(std::string Name, Mood Mood)
: Name{Name}, Mood{Mood}{}

Mood Mood;
std::string Name;
};

int main(){
using enum Mood;
std::vector<Actor> Actors{
{"Angry Goblin", Hostile},
{"Helpful Guard", Friendly},
{"Surly Goat", Neutral},
};

auto isFriendly{[](Actor& A) {
return A.Mood == Friendly;
}};

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

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

## Type Requirements and std::permutable

Like most algorithms that rearrange objects in a container, the types of those objects need 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 implementing the swapÂ function:

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

enum class Mood { Friendly, Neutral, Hostile };

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

Actor(const Actor& Other) = default;

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

Mood Mood;
std::string Name;
};

void swap(Actor& A, Actor& 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 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:

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

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

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

int main(){
using enum Mood;
std::vector<Actor> Actors{
{"Angry Goblin", Hostile},
{"Helpful Guard", Friendly},
{"Surly Goat", Neutral},
};

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

auto Unfriendlies{
std::ranges::partition(Actors, isFriendly,
&Actor::Mood)};

std::cout << "Unfriendlies: ";
for (Actor& 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 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 while excluding the first and lastÂ elements:

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

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

std::ranges::partition(
A.begin() + 1, A.end() - 1, [](int x){
return x % 2 == 0;
});

for (int x : A) { std::cout << x << ", "; }
}
1, -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:

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

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

std::partition(
A.begin() + 1, A.end() - 1, [](int x){
return x % 2 == 0;
});

for (int x : A) { std::cout << x << ", "; }
}
1, -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
New: AI-Powered AssistanceAI Assistance

### Questions and HelpNeed Help?

Get instant help using our free AI assistant, powered by state-of-the-art language models.

Updated
Lesson Contents

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

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

• 124 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
Contact|Privacy Policy|Terms of Use
Copyright Â© 2024 - All Rights Reserved