CODEWITHSUNDEEP
c++algorithmparameterspartition
Mohit Sharma
Mohit Sharma

Reputation: 39

What is the difference between std::stable_partition() and std::partition()?

stable_partition(vect.begin(), vect.end(), [](int x) { return x % 2 == 0; });

partition(vect.begin(), vect.end(), [](int x) {
  return x % 2 == 0;
});

Above code is to explain difference between two.

Upvotes: 2

Views: 2751

Answers (3)

Evg
Evg

Reputation: 26342

As explained in other answers, std::stable_partition preserves the relative order of elements in the groups for which the predicate returns true and false.

But this comes at a price: std::stable_partition has higher time/space complexity. If you can allocate additional storage, std::stable_partition can be implemented in O(n) time. However, in-place stable partition cannot be implemented in O(n) time. It can be done in O(n log n) time. An example of a simple divide-and-conquer algorithm can be found here.

C++ reference for std::stable_partition reads:

Complexity (std::stable_partition)

Given N = last - first,

Exactly N applications of the predicate and O(N) swaps if there is enough extra memory. If memory is insufficient, at most N log N swaps.

Also note that std::stable_partition requires bidirectional iterators, whereas std::partition can operate on forward ones. However, on bidirectional iterators it is more efficient:

Complexity (std::partition)

Given N = std::distance(first,last),

Exactly N applications of the predicate. At most N/2 swaps if ForwardIt meets the requirements of LegacyBidirectionalIterator, and at most N swaps otherwise.

If relative order of elements after partitioning is not important, use std::partition.

Upvotes: 4

Aykhan Hagverdili
Aykhan Hagverdili

Reputation: 29985

"stable" means the order of equivalent elements won't change:

std::stable_partition from cppreference.com:

Reorders the elements in the range [first, last) in such a way that all elements for which the predicate p returns true precede the elements for which predicate p returns false. Relative order of the elements is preserved.

Upvotes: 7

dragosht
dragosht

Reputation: 3275

The best way to figure this out is probably with an example. Let me plagiarize the example from cppreference here:

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

int main()
{
    std::vector<int> v{0, 0, 3, 0, 2, 4, 5, 0, 7};
    std::stable_partition(v.begin(), v.end(), [](int n){return n>0;});
    for (int n : v) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

Running this one gets you: 3 2 4 5 7 0 0 0 0. 3, 2, 4, 5, 7 are equivalent with respect to the relation defined by the > 0 predicate and as expected they are not reordered.

However, if you replace stable_partition with partition for the same example you get: 7 5 3 4 2 0 0 0 0. This time keeping the order of the equivalent elements was not guaranteed and obviously it wasn't.

Upvotes: 7

Related Questions