What is relative order and what does stable_partition do?

user_12940972 0
Viewed 920

So I got this code:

#include <vector>
#include <algorithm>

bool isEven(int x) {
    return x % 2 == 0;
}

int main() {

    std::vector<int> vec = {1,7,3,10,9,6};
    std::stable_partition(vec.begin(), vec.end(), isEven);
}

Now I didn't understand what was the concrete difference between stable_partition and partition.

So I looked in my book and it said that:

stable_partition maintains the relative order of elements in each partition

But I don't understand, what is the relative order of the elements?

Does it mean that the elements that don't match the partition predicate stay in the same order? if yes, how can they be changed in std::partition?

Thanks in advance.

stl c++
2 Answers

The relative order of the elements is simply the order that the elements within a particular partition have with respect to each other.

For example, after partitioning

{1,7,3,10,9,6}

we get:

   {6,10}  {1,3,7,9}   // one of the possible results
// ^^^^^^  ^^^^^^^^^      elements within partition can be in any order

so the relative order is not guaranteed to be maintained. Note that 6 comes before 10, whereas it came after 10 before the partitioning.

On the other hand, if you do a stable_partitioning, you get:

{10,6} {1,7,3,9}   // only possible result

and the relative order within each partition is guaranteed to be maintained.

user_83728530

The relative order means that in respect to the original order, the new partitioned set will maintain that ordering. In your example that means

{1,7,3,10,9,6}

become

{10,6,1,7,3,9}

Since the order of the even and odds does not change, just where in the set they are

user_43424980
Related