c++ - 将 std::partition 泛化为 multi_partition

Question

正如std::partition根据一元谓词对容器进行分区一样，multi_partition是根据UnaryPredicates...对容器进行分区...pred的顺序与UnaryPredicates...中列出的相同，顺序为false的元素UnaryPredicates...以及容器的末尾，并返回所有分区点的列表。但是我没有用这个辅助函数得到正确的结果:

template <typename ForwardIterator, typename UnaryPredicate, typename... UnaryPredicates>
std::list<ForwardIterator> multi_partition_helper (std::list<ForwardIterator>& partition_points, 
    ForwardIterator first, ForwardIterator last, UnaryPredicate pred, UnaryPredicates... rest) {
    while (true) {
        while ((first != last) && pred(*first))
            ++first;
        if (first == last--) break;
        while ((first != last) && !pred(*last))
            --last;
        if (first == last) break;
        std::iter_swap (first++, last);
    }
    partition_points.push_back (first);
    multi_partition_helper (partition_points, first, last, rest...);
}

template <typename ForwardIterator, typename UnaryPredicate, typename... UnaryPredicates>
std::list<ForwardIterator> multi_partition_helper (std::list<ForwardIterator>&, ForwardIterator, ForwardIterator) {
// End of recursion.
}

我做错了吗？

Answer 1

一个简单的实现是

template <typename BidirIt, typename... Predicates>
void trivial_mul_part( BidirIt first, BidirIt last, Predicates... preds )
{
    std::sort( first, last,
      [=] (decltype(*first) const& lhs, decltype(*first) const& rhs)
      {
          return std::make_tuple(preds(lhs)...) > std::make_tuple(preds(rhs)...);
      } );
}

并可作为引用算法。
真正的算法可以根据 std::partition 本身递归实现。这个想法是用第 n^th 谓词调用 std::partition，让迭代器到达第 n+1 范围的开头，然后以该迭代器作为第一个迭代器，以第 n+1^th 个谓词作为谓词进行下一次调用。

template <typename BidirIt, typename OutputIterator>
void multi_partition( BidirIt first, BidirIt last, OutputIterator out ) {}

template <typename BidirIt, typename OutputIterator,
          typename Pred, typename... Predicates>
void multi_partition( BidirIt first, BidirIt last,  OutputIterator out,
                      Pred pred, Predicates... preds )
{
    auto iter = std::partition(first, last, pred);
    *out++ = iter;
    multi_partition<BidirIt>(iter, last, out, preds...);
}

作为实际算法，可以按如下方式使用:

int arr[] {0, 1, 0, 1, 0, 2, 1, 2, 2};
std::vector<int*> iters;

multi_partition(std::begin(arr), std::end(arr), std::back_inserter(iters),
                 [] (int i) {return i == 2;},
                 [] (int i) {return i == 1;});

for (auto i : arr)
    std::cout << i << ", ";
std::cout << '\n';
for (auto it : iters)
    std::cout << "Split at " << it - arr << '\n';

Demo .