Partition vs Stable Partition Performance

How does the partition() algorithm differ from the stable_partition() algorithm in terms of performance?

The partition() and stable_partition() algorithms in C++ are used to divide a collection into two parts based on a predicate, but they differ significantly in terms of performance.

partition()

The partition() algorithm is designed for speed and efficiency. It rearranges elements within the collection based on the predicate without caring about the order of elements within each partition.

This lack of order preservation means partition() can often be implemented with fewer swaps and less overhead, making it faster and more efficient in terms of time complexity.

It typically operates in O(n)O(n) time, where n is the number of elements in the collection.

stable_partition()

On the other hand, stable_partition() preserves the relative order of elements within each partition. This means that if two elements are equal according to the predicate, their order in the original collection is maintained in the resulting partitions.

While this stability is useful in many scenarios, it comes at a performance cost. To maintain this order, stable_partition() generally requires additional temporary storage and more complex operations, resulting in higher time and space complexity compared to partition().

It often operates in O(nlogn)O(n log n) time due to the need for additional operations to maintain order. Here's a comparison in code:

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

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

  // Using partition()
  std::ranges::partition(A, [](int x) {
    return x < 0; });

  std::cout << "After partition: ";
  for (int x : A) std::cout << x << ", ";

  // Using stable_partition()
  std::ranges::stable_partition(A, [](int x) {
    return x < 0; });

  std::cout << "\nAfter stable_partition: ";
  for (int x : A) std::cout << x << ", ";
}
After partition: -6, 2, 7, 1, 5, 4,
After stable_partition: -6, 1, 7, 2, 5, 4,

In this example, partition() is faster but may not maintain the order of elements. stable_partition() maintains the order but at a higher computational cost.

Choose between them based on whether maintaining the order of elements is crucial for your application.

Partition Algorithms

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

Questions & Answers

Answers are generated by AI models and may not have been reviewed. Be mindful when running any code on your device.

Partitioning Custom Data Types
Can the partition() function be used with custom data types, and if so, how?
Determining Partition Size
How can I determine the size of each partition after using the partition() function?
When to Use partition_copy()
What are the use cases for partition_copy() over partition() or stable_partition()?
Understanding partition_point()
How does the partition_point() algorithm determine the boundary between partitions?
Safe Iterator Handling in partition_point()
How can I handle the iterator returned by partition_point() to avoid dereferencing issues?
Partitioning Without Random Access Iterators
Is it possible to use the partition() algorithm with containers that do not support random access iterators?
Alternatives to partition()
Are there any alternatives to using std::partition() or std::ranges::partition() that offer better performance or additional features?
Or Ask your Own Question
Get an immediate answer to your specific question using our AI assistant