std::ranges::partition

< cpp‎ | algorithm‎ | ranges
 
 
算法库
有制约算法及范围上的算法 (C++20)
有制约算法: std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
二分搜索操作
集合操作(在已排序范围上)
堆操作
(C++11)
最小/最大操作
(C++11)
(C++17)

排列
数值运算
C 库
 
有制约算法
不修改序列的操作
修改序列的操作
未初始化存储上的操作
划分操作
ranges::partition
排序操作
二分搜索操作
集合操作(在已排序范围上)
堆操作
最小/最大操作
排列
 
定义于头文件 <algorithm>
调用签名
template< std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,

          std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
  constexpr ranges::subrange<I>

partition( I first, S last, Pred pred, Proj proj = {} );
(1) (C++20 起)
template<ranges::forward_range R, class Proj = std::identity,

         std::indirect_unary_predicate<
             std::projected<ranges::iterator_t<R>, Proj>> Pred>
requires std::permutable<ranges::iterator_t<R>>
  constexpr ranges::borrowed_subrange_t<R>

partition(R&& r, Pred pred, Proj proj = {});
(2) (C++20 起)
1) 重排范围 [first, last) 中的元素,使谓词 pred 对其投影 proj 返回 true 的所有元素在谓词 pred 对其投影 proj 返回 false 的所有元素之前。不保持等价元素的相对顺序。
2)(1) ,但以 r 为源范围,如同以 ranges::begin(r)first 并以 ranges::end(r)last

此页面上描述的仿函数实体是 niebloid ,即:

实际上,它们能以函数对象,或以某些特殊编译器扩展实现。

参数

first, last - 要重排的范围
r - 要重排的范围
pred - 应用到投影后元素的谓词
proj - 应用到谓词的投影

返回值

始于指向第二组首元素的迭代器,终于等于 last 的迭代器的 subrange 。若 r 是非 borrowed_range 类型的右值则 (2) 返回 std::ranges::dangling

复杂度

给定 N = ranges::distance(first,last)

准确应用 N 次谓词与投影,若 I 实现 ranges::bidirectional_iterator 则至多交换 N/2 次,否则至多交换 N 次。

可能的实现

struct partition_fn {
  template<std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
           std::indirect_unary_predicate<std::projected<I, Proj>> Pred>
  constexpr ranges::subrange<I>
  operator()(I first, S last, Pred pred, Proj proj = {}) const
  {
      first = ranges::find_if_not(first, last, std::ref(pred), std::ref(proj));
      if (first == last) {
          return {first, first};
      }
 
      auto begin = first;
      for (auto i = ranges::next(first); i != last; ++i) {
          if (std::invoke(pred, std::invoke(proj, *i))) {
              ranges::iter_swap(i, first);
              ++first;
          }
      }
      return {std::move(begin), std::move(first)};
  }
 
  template<ranges::forward_range R, class Proj = std::identity,
           std::indirect_unary_predicate<
               std::projected<ranges::iterator_t<R>, Proj>> Pred>
  requires std::permutable<ranges::iterator_t<R>>
  constexpr ranges::borrowed_subrange_t<R>
  operator()(R&& r, Pred pred, Proj proj = {}) const
  {
    return (*this)(ranges::begin(r), ranges::end(r),
                   std::ref(pred), std::ref(proj));
  }
};
 
inline constexpr partition_fn partition;

示例

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <forward_list>
 
namespace ranges = std::ranges;
 
template <std::permutable I, std::sentinel_for<I> S>
void quicksort(I first, S last)
{
   if(first == last) {
       return;
   }
 
   auto pivot = *ranges::next(first, ranges::distance(first,last)/2, last);
   auto middle1 = ranges::partition(first, last, [pivot](const auto& em){
       return em < pivot;
   });
   auto middle2 = ranges::partition(middle1, last, [pivot](const auto& em){
       return !(pivot < em);
   });
   quicksort(first, middle1);
   quicksort(middle2, last);
}
 
int main()
{
    std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};
    std::cout << "Original vector:\n    ";
    for(int elem : v) {
        std::cout << elem << ' ';
    }
 
    auto it = ranges::partition(v, [](int i){return i % 2 == 0;});
 
    std::cout << "\nPartitioned vector:\n    ";
    ranges::copy(ranges::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
    std::cout << " * ";
    ranges::copy(it, ranges::end(v), std::ostream_iterator<int>(std::cout, " "));
 
    std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
    std::cout << "\nUnsorted list:\n    ";
    for(int n : fl) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
 
    quicksort(ranges::begin(fl), ranges::end(fl));
    std::cout << "Sorted using quicksort:\n    ";
    for(int fi : fl) {
        std::cout << fi << ' ';
    }
    std::cout << '\n';
}

输出:

Original vector:
    0 1 2 3 4 5 6 7 8 9 
Partitioned vector:
    0  * 2 4 6 8 
Unsorted list:
    1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92 
Sorted using quicksort:
    -4 -4 -8 -5 1 1 3 2 5 1 30 64 6 92

参阅

判断范围是否已按给定的谓词划分
(niebloid)
将元素分成二组,同时保持其相对顺序
(niebloid)
将范围中的元素分为两组
(函数模板)