std::ranges::remove() algorithm

od C++20

Simplified

// (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 = {} );

The type of arguments are generic and have the following constraints:

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

The Proj template argument has a default type of std::identity for all overloads.

Additionally, each overload has the following constraints:

• (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*>

(The std:: namespace was ommitted here for readability)

Detailed

// (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) Removes all elements that are equal to value, using std::invoke(proj, *i) == value to compare.

• (2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

Removing is done by shifting (by means of move assignment) the elements in the range in such a way that the elements that are not to be removed appear in the beginning of the range.

important

Relative order of the elements that remain is preserved and the physical size of the container is unchanged.

warning

Iterators pointing to an element between the new logical end and the physical end of the range are still dereferenceable, but the elements themselves have unspecified values (as per MoveAssignable post-condition). (od C++11)

The function-like entities described on this page are niebloids.

Parameters

first last	The range of elements to process.
r	The range of elements to process.
value	The value of elements to remove.
proj	Projection to apply to the elements.

Return value

{
  ret,
  last
}

Where [first; ret) is the resulting subrange after removal, and the elements in subrange [ret; last) are all in valid but unspecified state.

Complexity

Given N as ranges::distance(first, last)

Exactly N applications of the projection, and N - 1 move operations at worst.

Exceptions

(none)

Possible implementation

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 {};

Notes

A call to remove is typically followed by a call to a container's erase member function, which erases the unspecified values and reduces the physical size of the container to match its new logical size. These two invocations together constitute a so-called Erase–remove idiom, which can be achieved by the free function std::erase that has overloads for all standard sequence containers, or std::erase_if that has overloads for all standard containers (od C++20)

The similarly-named container member functions list::remove, list::remove_if, forward_list::remove, and forward_list::remove_if erase the removed elements.

These algorithms cannot be used with associative containers such as std::set and std::map because their iterator types do not dereference to MoveAssignable types (the keys in these containers are not modifiable).

The standard library also defines an overload of std::remove in <cstdio>, which takes a const char* and is used to delete files.

Because std::remove takes value by reference, it can have unexpected behavior if it is a reference to an element of the range [first; last).

Examples

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';
}

Output

"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