The programmer has the responsibility to remove or resize the elements from the actual container. The only exception is when remove and remove_if are members of a container, which is the case of std::list remove_if.
Warning: Thinking that std::remove and std::remove_if will actually remove elements from a container is wrong. Both methods will move and/or copy elements around within the container, but it will never remove elements or resize the container.
The C++ methods std::remove_if and std::remove live in the header
std::remove_if lambda
After the stern warning in the introduction, here is how to use C++ std remove_if with lambda for predicate. Let’s start with the most elementary and simple example case.
With a vector of ints, we can inspect the vector before and after the two steps.
// Vector with numbers, initialized with an initializer list
std::vector<int> numbers{ 1,1,2,3,4,5,6 };
At this step, the contents of the vector looks like this.
| Original vector |
Then we decide we want to filter out some values, say any value less than 3 must be removed. For this we can use std::remove_if. It will do what you asked for, except you must combine it with an explicit erase of the container. Why will be explained later.
The lambda expression looks like this. It has the same argument as the vector value type (int).
// Lambda for removing numbers less than 3
auto removeNumbers = [&](int number) -> bool
{
return number < 3;
};
Call std::remove_if with the lambda as predicate.
// Call std::remove_if and obtain iterator auto iterator = std::remove_if(numbers.begin(), numbers.end(), removeNumbers);
After remove_if, the vector will look like this.
| Original vector |
| After remove_if |
Red numbers are removed, green are kept, while gray numbers are surplus.
To remove the elements, we will have to call erase on the vector.
numbers.erase(iterator, numbers.end());
The arguments for erase is a range of elements to be removed.
| Original vector |
| After remove_if |
| After erase |
Here is a graphical presentation of the vector.
Why remove_if can’t delete from the container
The simple answer: It’s not possible.
The longer answer: The arguments for std::remove_if doesn’t include the container type. It only includes an iterator range and a predicate (or value in the case of std::remove). The method itself doesn’t know about the underlying storage. If and only if remove_if were limited to vector or list, then it would have been possible to actually remove elements. But that is not the case.
It’s possible to create iterators from a regular array, and it’s not possible to resize an array without reallocating memory, thus copying (or moving) elements from the old array to the new array.
That’s why std::remove and std::remove_if doesn’t actually remove elements, it only moves elements to be kept.
One other thing to remember is that removed elements will be destroyed. After remove_if, there may or may not be usable data in the area after the iterator returned by the method.
Practical use for remove_if
The most practical use for remove and remove_if is to remove elements from a range.
With some collections counting millions of elements, it’s not feasible to remove one element at a time. With a logical deleted tag, it’s possible to remove all elements with linear complexity, also known as O(n).
The rationale of using std::remove_if is simple. If you’re deleting 10000 elements from a vector containing 1 million elements, you will, in the worst case scenario, move or copy most elements 10000 times. With 1 million elements, it will be close to 10 billion copies or moves.
Here is one example. Widget is an example struct for some user supplied type.
struct Widget
{
std::string name; // Widget name
bool deleted; // Should be deleted
};
Fill a vector with Widget data.
// Store them in a container
std::vector<Widget> widgets;
widgets.emplace_back(Widget{ "W1", true });
widgets.emplace_back(Widget{ "W2", true });
widgets.emplace_back(Widget{ "W3", false });
widgets.emplace_back(Widget{ "W4", true });
widgets.emplace_back(Widget{ "W5", false });
widgets.emplace_back(Widget{ "W6", true });
widgets.emplace_back(Widget{ "W7", true });
widgets.emplace_back(Widget{ "W8", false });
The data will look like this in the vector.
| Original |
After std::remove_if, the vector will still have the same size, but notice how the move operator have actually moved the string names from the end of the vector to the beginning of the vector. This is most apparent with W5 and W8. The corresponding value after is an empty string.
| Original |
| After remove_if |
After erase, the vector have been resized to contain only non-deleted elements.
| Original |
| After remove_if |
| After erase |
See Also
- Default explicit equality operator
- Mistakes
- compile_commands.json with CMake
- Samsung Magician Stops Ctrl-w From Working
- Default Route and Dns With Opensuse Tumbleweed with static IP