std::ranges::remove_copy() algorithm

od C++20

Simplified

// (1)
requires constexpr remove_copy_result<I, O>
    remove_copy( I first, S last, O result, const T& value, Proj proj = {} );

// (2)
requires constexpr remove_copy_result<ranges::borrowed_iterator_t<R>, O>
    remove_copy( R&& r, O result, const T& value, Proj proj = {} );

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

• I - std::input_iterator
• S - std::sentinel_for<I>
• O - std::weakly_incrementable
• R - std::input_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):

  indirectly_copyable<I, O>
  && indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
• (2):

  indirectly_copyable<ranges::iterator_t<R>, O>
  && 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::input_iterator I,
  std::sentinel_for<I> S,
  std::weakly_incrementable O,
  class T,
  class Proj = std::identity
>
requires std::indirectly_copyable<I, O> &&
         std::indirect_binary_predicate<ranges::equal_to,
             std::projected<I, Proj>, const T*>
constexpr remove_copy_result<I, O>
    remove_copy( I first, S last, O result, const T& value, Proj proj = {} );

// (2)
template<
  ranges::input_range R,
  std::weakly_incrementable O, class T,
  class Proj = std::identity
>
requires std::indirectly_copyable<ranges::iterator_t<R>, O> &&
         std::indirect_binary_predicate<ranges::equal_to,
             std::projected<ranges::iterator_t<R>, Proj>, const T*>
constexpr remove_copy_result<ranges::borrowed_iterator_t<R>, O>
    remove_copy( R&& r, O result, const T& value, Proj proj = {} );

With the helper types defined as follows:

template< class I, class O >
using remove_copy_result = ranges::in_out_result<I, O>;

• (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 copy.
r	The range of elements to copy.
result	The beginning of the destination range.
value	The value of elements >not to copy.
proj	The projection to apply to the elements.

Return value

{
  last,
  result + N
}

Where N is the number of elements copied.

Complexity

Exactly ranges::distance(first, last) applications of projection proj.

Exceptions

(none)

Possible implementation

remove_copy(1)

struct remove_copy_fn
{
    template<std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O,
             class T, class Proj = std::identity>
    requires std::indirectly_copyable<I, O> &&
             std::indirect_binary_predicate<ranges::equal_to,
                                            std::projected<I, Proj>, const T*>
    constexpr ranges::remove_copy_result<I, O>
        operator()(I first, S last, O result, const T& value, Proj proj = {}) const
    {
        for (; !(first == last); ++first)
        {
            if (value != std::invoke(proj, *first))
            {
                *result = *first;
                ++result;
            }
        }
        return {std::move(first), std::move(result)};
    }

    template<ranges::input_range R, std::weakly_incrementable O, class T,
             class Proj = std::identity>
    requires std::indirectly_copyable<ranges::iterator_t<R>, O> &&
             std::indirect_binary_predicate<ranges::equal_to,
             std::projected<ranges::iterator_t<R>, Proj>, const T*>
    constexpr ranges::remove_copy_result<ranges::borrowed_iterator_t<R>, O>
        operator()(R&& r, O result, const T& value, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::move(result), value,
                       std::move(proj));
    }
};

inline constexpr remove_copy_fn remove_copy {};

Notes

The algorithm is stable, that is, preserves the relative order of the copied elements.

Examples

Main.cpp

#include <algorithm>
#include <array>
#include <complex>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string_view>
#include <vector>

void print(const auto rem, const auto& v)
{
    std::cout << rem << ' ';
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}

int main()
{
    // Filter out the hash symbol from the given string.
    const std::string_view str {"#Small #Buffer #Optimization"};
    std::cout << "before: " << std::quoted(str) << '\n';

    std::cout << "after:  \"";
    std::ranges::remove_copy(str.begin(), str.end(),
                             std::ostream_iterator<char>(std::cout), '#');
    std::cout << "\"\n";

    // Copy only the complex numbers with positive imaginary part.
    using Ci = std::complex<int>;
    constexpr std::array<Ci, 5> source
    {
        Ci {1, 0}, Ci {0, 1}, Ci {2, -1}, Ci {3, 2}, Ci {4, -3}
    };
    std::vector<std::complex<int>> target;

    std::ranges::remove_copy_if(
        source,
        std::back_inserter(target),
        [](int imag) { return imag <= 0; },
        [](Ci z) { return z.imag(); }
    );

    print("source:", source);
    print("target:", target);
}

Output

before: "#Small #Buffer #Optimization"
after:  "Small Buffer Optimization"
source: (1,0) (0,1) (2,-1) (3,2) (4,-3)
target: (0,1) (3,2)