Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does the erase-remove idiom work with ranges/constrained algorithms?

I'm trying to use a c++20 constrained algorithm for the erase-remove idiom:

std::vector<int> v;
v.erase(std::unique(std::begin(v), std::end(v)), std::end(v));

but when I do a simple transformation:

v.erase(std::ranges::unique(v), std::end(v));

I get an error that the arguments to erase don't match:

error: no matching function for call to 'std::vector<int>::erase(std::ranges::borrowed_subrange_t<std::vector<int>&>, std::vector<int>::iterator)'

A similar error is produced if the second argument is std::ranges::end(v).

How can I get this to work?


The question originally used remove instead of unique, but there is an overloaded std::erase for all containers that makes that particular use case less motivating.

like image 793
cigien Avatar asked Oct 10 '20 19:10

cigien


People also ask

How does remove if work C++?

C++ Algorithm remove_if() function is used to eliminate all the elements that satisfy a predicate from a given range [first, last) without disturbing the order of the remaining elements. This function cannot alter the size of the container. It returns an iterator to the new end of the range.

What STD remove returns?

std :: remove Transforms the range [first,last) into a range with all the elements that compare equal to val removed, and returns an iterator to the new end of that range. The function cannot alter the properties of the object containing the range of elements (i.e., it cannot alter the size of an array or a container).

What is erase remove idiom in C++?

The erase–remove idiom is a common C++ technique to eliminate elements that fulfill a certain criterion from a C++ Standard Library container. A common programming task is to remove all elements that have a certain value or fulfill a certain criterion from a collection.

How does the remove algorithm eliminate elements from a container?

The std::remove algorithm does not eliminate elements from a container; it simply moves the elements not being removed to the front of the container, leaving the contents at the end of the container undefined.

How do you remove elements from a range?

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. Relative order of the elements that remain is preserved and the physical size of the container is unchanged.

How does the erase-remove idiom work?

The erase-remove idiom works as follow. Let say you have a vector {2, 4, 3, 6, 4} and you want to remove the 4:


2 Answers

std::ranges::unique (and std::ranges::remove) returns a sub range from the first removed element to the end of the container so you need to use std::begin before passing to std::vector::erase:

v.erase(std::ranges::begin(std::ranges::remove(v, 42)), std::end(v));
v.erase(std::ranges::begin(std::ranges::unique(v)), std::end(v));
like image 71
Alan Birtles Avatar answered Oct 12 '22 23:10

Alan Birtles


Another option would be decomposing the subrange returned by std::ranges::remove/unique, and use those iterators:

auto [Beg, End] = std::ranges::remove(v, 42);
v.erase(Beg, End);
like image 5
metalfox Avatar answered Oct 12 '22 21:10

metalfox