Обобщение std :: partition для multi_partition
Точно так же, как std :: partition разделяет контейнер в соответствии с унарным предикатом, multi_partition предназначена для разделения контейнера в соответствии с UnaryPredicates … pred в том же порядке, что и в UnaryPredicates …, и ложными элементами в порядке 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.
}
Я поступаю неправильно?
Решение
Тривиальная реализация
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 сам. Идея состоит в том, чтобы позвонить std::partition с нго предикат, получить итератор к началу n + 1го ранжировать и сделать следующий вызов с этим итератором в качестве первого итератора и n + 1го Предикат в качестве предиката.
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';
демонстрация.
Другие решения