6

我写了这个分区函数：

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
4

3 回答 3

8

您的版本接近 Nico Lomuto partition。这样的partition工作在ForwardIterators 上并且是半稳定的（第一部分是稳定的，这在某些情况下可能很有用）。

您引用的标准库实现的版本接近于CAR Hoare在他的论文“Quicksort”中partition描述的。它适用于s，并不意味着任何稳定性。BidirectionalIterator

让我们在以下情况下比较它们：

FTTTT

前进partition将像这样进行：

FTTTT
TFTTT
TTFTT
TTTFT
TTTTF

导致swap除第一次之外的每次迭代，而双向分区将通过以下排列：

FTTTT
TTTTF

对所有迭代只产生一个swap。

此外，在一般情况下，双向最多会做 N/2swap秒，而前向版本最多可以做 ~Nswap秒。

std::partition在 C++98/03 中适用于BidirectionalIterators，但在 C++11 中，他们放宽了对ForwardIterators 的要求（尽管它不必是半稳定的）。复杂性要求：

复杂性：如果ForwardIterator满足 a 的要求BidirectionalIterator，最多 ( last- first) / 2 次交换；否则最多last-first交换完成。恰好最后 - 谓词的第一次应用完成。

如您所见，标准库的实现很可能会使用 Lomuto 的partitionfor ForwardIterators 和 Hoare 的partitionfor BidirectionalIterators。

Alexander Stepanovpartition在他与Paul McJones合着的Notes on Programming和Elements of Programming中讨论了问题

现场演示

#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为 3move秒）

于 2013-11-05T02:10:28.803 回答
3

您的函数存在严重缺陷。如果序列的初始元素满足谓词，它将每个满足谓词的元素与它自己交换。

于 2013-11-04T22:23:49.917 回答
1

来自STL 分区描述

复杂性 在第一个和最后一个之间的距离中线性：将 pred 应用于每个元素，并可能交换其中的一些（如果迭代器类型是双向的，最多交换一半，否则最多交换那么多）。

在您的实施中，您交换更多。

于 2013-11-04T22:28:57.303 回答