std::ranges::remove() 算法

自 C++20 起

简化

// (1)
constexpr ranges::subrange<I>
    remove( I first, S last, const T& value, Proj proj = {} );

// (2)
constexpr ranges::borrowed_subrange_t<R>
    remove( R&& r, const T& value, Proj proj = {} );

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

• I - std::permutable
• S - std::sentinel_for<I>
• R - std::ranges::forward_range
• T - （无）
• Proj - (无)

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

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

• (1) - indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
• (2) - permutable<ranges::iterator_t<R>> && indirect_binary_predicate<ranges::equal_to, projected<ranges::iterator_t<R>, Proj>, const T*>

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

详细

// (1)
template<
  std::permutable I,
  std::sentinel_for<I> S,
  class T,
  class Proj = std::identity
>
requires std::indirect_binary_predicate<ranges::equal_to, std::projected<I, Proj>, const T*>
constexpr ranges::subrange<I>
    remove( I first, S last, const T& value, Proj proj = {} );

// (2)
template<
  ranges::forward_range R,
  class T,
  class Proj = std::identity
>
requires std::permutable<ranges::iterator_t<R>> &&
         std::indirect_binary_predicate<ranges::equal_to,
             std::projected<ranges::iterator_t<R>, Proj>, const T*>
constexpr ranges::borrowed_subrange_t<R>
    remove( R&& r, const T& value, Proj proj = {} );

• (1) 移除所有等于 value 的元素，使用 std::invoke(proj, *i) == value 进行比较。

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

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

重要

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

警告

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

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

参数

first last	要处理的元素范围。
r	要处理的元素范围。
值	要移除的元素的值。
proj	应用于元素的投影。

返回值

{
  ret,
  last
}

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

复杂度

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

最多 N 次投影应用，以及最多 N - 1 次移动操作。

异常

(无)

可能的实现

remove(1)

struct remove_fn
{
    template<std::permutable I, std::sentinel_for<I> S, class T,
             class Proj = std::identity>
    requires std::indirect_binary_predicate<
                 ranges::equal_to, std::projected<I, Proj>, const T*>
    constexpr ranges::subrange<I>
        operator()(I first, S last, const T& value, Proj proj = {}) const
    {
        first = ranges::find(std::move(first), last, value, proj);
        if (first != last)
        {
            for (I i {std::next(first)}; i != last; ++i)
            {
                if (value != std::invoke(proj, *i))
                {
                    *first = ranges::iter_move(i);
                    ++first;
                }
            }
        }
        return {first, last};
    }

    template<ranges::forward_range R, class T, class Proj = std::identity>
    requires std::permutable<ranges::iterator_t<R>> &&
             std::indirect_binary_predicate<
                 ranges::equal_to, std::projected<
                     ranges::iterator_t<R>, Proj>, const T*>
    constexpr ranges::borrowed_subrange_t<R>
        operator()(R&& r, const T& value, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), value, std::move(proj));
    }
};

inline constexpr remove_fn remove {};

备注

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

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

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

标准库还在 <cstdio> 中定义了std::remove的重载，它接受一个 const char* 并用于删除文件。

因为std::remove通过引用获取value，如果它是范围 [first; last) 中元素的引用，则可能导致意外行为。

示例

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`, 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`, size: 36)
 ^^^^^^
"SFINAE" (v2 after `erase`, size: 6)

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