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
3D Character Concept Art
Ryan McCombe
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},
    {"Helpful Guard", Friendly},
    {"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}, {"Helpful Guard", Friendly}, {"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,

Was this lesson useful?

Edit History

  • — First Published

Ryan McCombe
Ryan McCombe
Posted
7a.jpg
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
7a.jpg
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
3D Character Concept Art
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved