如何在线性时间内建立稳定的二进制值？

Question

让我们假设我们有一个:

class Widget;
std::vector<Widget>;

我们有一个功能:

bool belongsToLeft(Widget w);

我想根据这个谓词对容器进行排序.到目前为止,我虽然这个算法.它从范围的两端发展.一旦找到一对同时属于另一端的值,它就会交换它们.

template <typename TIterator, typename TPredicate>
TIterator separate(TIterator begin, TIterator end, TPredicate belongsLeft)
{
    while (true)
    {
        while (begin != end && belongsLeft(*begin))
            ++begin;
        while (begin != end && !belongsLeft(*end))
            --end;
        if (begin == end)
            return begin;
        std::swap(*begin, *end);
    }
}

问题是这个算法不稳定:

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> numbers = {6, 5, 4, 3, 2, 1};
    separate(numbers.begin(), numbers.end(), [](int x){return x%2 == 0;});

    for (int x : numbers)
        std::cout << x << std::endl;
    return 0;
}

输出:

6
2
4
3
5
1

如何修改此算法以保持稳定并保持线性时间？

Answer 1

std::stable_partition与谓词一起使用以numbers线性复杂度分成两部分

#include <algorithm>

std::stable_partition(
    numbers.begin(), numbers.end(), 
    [](int x) { return x % 2 == 0; } // or belongsToLeft()
);