标准库分区算法

Question

我写了这个分区函数:

template <class I, class P> I partition(I beg, I end, P p)
{
    I first = beg;
    while(beg != end) {
        if(!p(*beg))
            beg++;
        else {
            // if(beg != first) - EDIT: add conditional to prevent swapping identical elements
            std::swap(*beg, *first);
            first++;
            beg++;
        }
    }
    return first;
}

我用几个输出测试了它,我没有发现它有什么问题.

标准库分区功能相当于:

template <class BidirectionalIterator, class UnaryPredicate>
  BidirectionalIterator partition (BidirectionalIterator first,
                                   BidirectionalIterator last, UnaryPredicate pred)
{
  while (first!=last) {
    while (pred(*first)) {
      ++first;
      if (first==last) return first;
    }
    do {
      --last;
      if (first==last) return first;
    } while (!pred(*last));
    swap (*first,*last);
    ++first;
  }
  return first;
}

后者似乎要复杂得多并且有嵌套循环.我的版本有问题吗？如果不是为什么更复杂的版本？

以下是使用以下谓词的输出:

bool greaterthantwo(double val)
{
    return val > 2;
}

MAIN

std::vector<double> test{1,2,3,4,2,5,6,7,4,8,2,4,10};
std::vector<double>::iterator part = ::partition(test.begin(), test.end(), greaterthantwo);
for(const auto &ref:test)
    std::cout << ref << " ";
std::cout << std::endl;
for(auto it = part; it != test.end(); it++)
    std::cout << *it << " ";
std::cout << std::endl;

OUTPUT

3 4 5 6 7 4 8 4 10 2 2 2 1 
2 2 2 1 

Answer 1

你的版本接近Nico Lomuto partition.这种partition作品在ForwardIterators和半稳定(第一部分是稳定的,在某些情况下可能有用).

从实施的标准库,你引述的版本是接近partition所描述CAR Hoare的在他的论文"快速排序".它适用于BidirectionalIterators,并不意味着任何稳定性.

让我们根据以下情况对它们进行比较:

FTTTT

转发partition将如下进行:

FTTTT
TFTTT
TTFTT
TTTFT
TTTTF

导致swap每次迭代除了第一次,而双向分区将通过以下排列:

FTTTT
TTTTF

swap所有迭代只产生一个.

此外,一般情况下,双向swap最大值为N/2 秒,而正向版本最多可以达到~N swap秒.

std::partition在C++ 98/03中,它适用于BidirectionalIterators,但在C++ 11中它们放宽了对ForwardIterators的要求(尽管它不必是半稳定的).复杂性要求:

复杂性:如果ForwardIterator满足a的要求BidirectionalIterator,最多(last- first)/ 2次交换完成; 否则最多last- first交换完成.完全是最后 - 谓词的第一个应用程序已完成.

正如您所看到的,标准库的实现很可能会使用Lomuto partition用于ForwardIterators和Hoare partition用于BidirectionalIterators.

亚历山大·斯捷潘诺夫铁饼partition在他的问题上编程的注意事项,并在编程的元素与合着保罗McJones

现场演示

#include <initializer_list>
#include <forward_list>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int counter = 0;

struct T
{
    int value;
    T(int x = 0) : value(x) {}
    T(const T &x)
    {
        ++counter;
        value = x.value;
    }
    T &operator=(const T &x)
    {
        ++counter;
        value = x.value;
        return *this;
    }
};
auto pred = [](const T &x){return x.value;};

template<typename Container>
void test()
{
    Container l = {0, 1, 1, 1, 1};
    counter = 0;
    partition(begin(l), end(l), pred);
    cout << "Moves count: " << counter << endl;
}

int main()
{
    test<forward_list<T>>();
    test<list<T>>();
}

输出是:

Moves count: 12
Moves count: 3

(swap是3 moves)