std::ranges::remove_if() 算法

自 C++20 起

简化

// (1)
constexpr ranges::subrange<I> remove_if( I first, S last, Pred pred, Proj proj = {} );

// (2)
constexpr ranges::borrowed_subrange_t<R> remove_if( R&& r, Pred pred, Proj proj = {} );

参数类型是泛型的，并具有以下约束

• I - std::permutable
• S - std::sentinel_for<I>
• R - std::ranges::forward_range
• Pred:
  • (1) - std::indirect_unary_predicate<std::projected<I, Proj>>
  • (2) - std::projected<ranges::iterator_t<R>, Proj>>
• T - （无）
• Proj - (无)

对于所有重载，Proj 模板参数的默认类型为 std::identity。

此外，每个重载都有以下约束

• (1) - std::permutable<ranges::iterator_t<R>>

（为方便阅读，此处省略了 std:: 命名空间）

详细

// (1)
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> remove_if( I first, S last, Pred pred, Proj proj = {} );

// (2)
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>
    remove_if( R&& r, Pred pred, Proj proj = {} );

• (1) 移除所有满足 std::invoke(pred, std::invoke(proj, *i)) 返回 true 的元素。

• (2) 与 (1) 相同，但使用 r 作为源范围，如同使用 ranges::begin(r) 作为 first 和 ranges::end(r) 作为 last。

移除通过移动赋值来完成，即移动范围内的元素，使不需要移除的元素出现在范围的开头。

重要

保留其余元素的相对顺序，且容器的物理大小不变。

警告

指向范围新_逻辑_末端和_物理_末端之间元素的迭代器仍然可以解引用，但元素本身具有未指定的值（根据MoveAssignable 后置条件）。 (自 C++11 起)

本页描述的函数类实体是niebloids。

参数

first last	要处理的元素范围。
r	要处理的元素范围。
pred	应用于投影元素的谓词。
proj	应用于元素的投影。

返回值

{
  ret,
  last
}

其中 [first; ret) 是移除后的结果子范围，子范围 [ret; last) 中的元素都处于有效但未指定的状态。

复杂度

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

最多精确执行 N 次投影和谓词应用，以及 N - 1 次移动操作。

异常

(无)

可能的实现

remove_if(1)

struct remove_if_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(std::move(first), last, pred, proj);
        if (first != last)
        {
            for (I i {std::next(first)}; i != last; ++i)
            {
                if (!std::invoke(pred, std::invoke(proj, *i)))
                {
                    *first = ranges::iter_move(i);
                    ++first;
                }
            }
        }
        return {first, last};
    }

    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), pred, std::move(proj));
    }
};

inline constexpr remove_if_fn remove_if {};

备注

对 remove_if 的调用通常会紧接着对容器的 erase 成员函数的调用，该函数会擦除未指定的值并将容器的_物理大小_减小以匹配其新的_逻辑大小_。这两个调用共同构成了所谓的擦除-移除习语，这可以通过自由函数 std::erase 实现，该函数具有所有标准序列容器的重载，或者 std::erase_if 具有所有标准容器的重载 (自 C++20 起)

名称相似的容器成员函数 list::remove、list::remove_if、forward_list::remove 和 forward_list::remove_if 会擦除被移除的元素。

这些算法不能与关联容器（如 std::set 和 std::map）一起使用，因为它们的迭代器类型不能解引用为 MoveAssignable 类型（这些容器中的键不可修改）。

示例

Main.cpp

#include <algorithm>
#include <cctype>
#include <iomanip>
#include <iostream>
#include <string>
#include <string_view>

int main()
{
    std::string v1 {"No - Diagnostic - Required"};
    std::cout << std::quoted(v1) << " (v1, size: " << v1.size() << ")\n";
    const auto ret = std::ranges::remove(v1, ' ');
    std::cout << std::quoted(v1) << " (v1 after `remove`, size: " << v1.size() << ")\n";
    std::cout << ' ' << std::string(std::distance(v1.begin(), ret.begin()), '^') << '\n';
    v1.erase(ret.begin(), ret.end());
    std::cout << std::quoted(v1) << " (v1 after `erase`, size: " << v1.size() << ")\n\n";

    // remove_if with custom unary predicate:
    auto rm = [](char c) { return !std::isupper(c); };
    std::string v2 {"Substitution Failure Is Not An Error"};
    std::cout << std::quoted(v2) << " (v2, size: " << v2.size() << ")\n";
    const auto [first, last] = std::ranges::remove_if(v2, rm);
    std::cout << std::quoted(v2) << " (v2 after `remove_if`, size: " << v2.size() << ")\n";
    std::cout << ' ' << std::string(std::distance(v2.begin(), first), '^') << '\n';
    v2.erase(first, last);
    std::cout << std::quoted(v2) << " (v2 after `erase`, size: " << v2.size() << ")\n\n";

    // creating a view into a container that is modified by `remove_if`:
    for (std::string s : {"Small Object Optimization", "Non-Type Template Parameter"})
        std::cout << std::quoted(s) << " => "
                  << std::string_view {begin(s), std::ranges::remove_if(s, rm).begin()}
                  << '\n';
}

输出

"No _ Diagnostic _ Required" (v1, size: 26)
"No_Diagnostic_Requiredired" (v1 after `remove_if`, size: 26)
 ^^^^^^^^^^^^^^^^^^^^^^
"No_Diagnostic_Required" (v1 after `erase`, size: 22)

"Substitution Failure Is Not An Error" (v2, size: 36)
"SFINAEtution Failure Is Not An Error" (v2 after `remove_if_if`, size: 36)
 ^^^^^^
"SFINAE" (v2 after `erase`, size: 6)

"Small Object Optimization" => SOO
"Non-Type Template Parameter" => NTTP