I want to clear a element from a vector using the erase method. But the problem here is that the element is not guaranteed to occur only once in the vector. It may be present multiple times and I need to clear all of them. My code is something like this:
void erase(std::vector<int>& myNumbers_in, int number_in)
{
std::vector<int>::iterator iter = myNumbers_in.begin();
std::vector<int>::iterator endIter = myNumbers_in.end();
for(; iter != endIter; ++iter)
{
if(*iter == number_in)
{
myNumbers_in.erase(iter);
}
}
}
int main(int argc, char* argv[])
{
std::vector<int> myNmbers;
for(int i = 0; i < 2; ++i)
{
myNmbers.push_back(i);
myNmbers.push_back(i);
}
erase(myNmbers, 1);
return 0;
}
This code obviously crashes because I am changing the end of the vector while iterating through it. What is the best way to achieve this? I.e. is there any way to do this without iterating through the vector multiple times or creating one more copy of the vector?
Depending on why you are doing this, using a std::set might be a better idea than std::vector.
It allows each element to occur only once. If you add it multiple times, there will only be one instance to erase anyway. This will make the erase operation trivial. The erase operation will also have lower time complexity than on the vector, however, adding elements is slower on the set so it might not be much of an advantage.
This of course won't work if you are interested in how many times an element has been added to your vector or the order the elements were added.
You can iterate using the index access,
To avoid O(n^2) complexity you can use two indices, i - current testing index, j - index to store next item and at the end of the cycle new size of the vector.
code:
void erase(std::vector<int>& v, int num)
{
size_t j = 0;
for (size_t i = 0; i < v.size(); ++i) {
if (v[i] != num) v[j++] = v[i];
}
// trim vector to new size
v.resize(j);
}
In such case you have no invalidating of iterators, complexity is O(n), and code is very concise and you don't need to write some helper classes, although in some case using helper classes can benefit in more flexible code.
This code does not use erase method, but solves your task.
Using pure stl you can do this in the following way (this is similar to the Motti's answer):
#include <algorithm>
void erase(std::vector<int>& v, int num) {
vector<int>::iterator it = remove(v.begin(), v.end(), num);
v.erase(it, v.end());
}
To erase 1st element you can use:
vector<int> mV{ 1, 2, 3, 4, 5 };
vector<int>::iterator it;
it = mV.begin();
mV.erase(it);
You can iterate using the index access,
To avoid O(n^2) complexity you can use two indices, i - current testing index, j - index to store next item and at the end of the cycle new size of the vector.
code:
void erase(std::vector<int>& v, int num)
{
size_t j = 0;
for (size_t i = 0; i < v.size(); ++i) {
if (v[i] != num) v[j++] = v[i];
}
// trim vector to new size
v.resize(j);
}
In such case you have no invalidating of iterators, complexity is O(n), and code is very concise and you don't need to write some helper classes, although in some case using helper classes can benefit in more flexible code.
This code does not use erase method, but solves your task.
Using pure stl you can do this in the following way (this is similar to the Motti's answer):
#include <algorithm>
void erase(std::vector<int>& v, int num) {
vector<int>::iterator it = remove(v.begin(), v.end(), num);
v.erase(it, v.end());
}
Depending on why you are doing this, using a std::set might be a better idea than std::vector.
It allows each element to occur only once. If you add it multiple times, there will only be one instance to erase anyway. This will make the erase operation trivial. The erase operation will also have lower time complexity than on the vector, however, adding elements is slower on the set so it might not be much of an advantage.
This of course won't work if you are interested in how many times an element has been added to your vector or the order the elements were added.
Calling erase will invalidate iterators, you could use:
void erase(std::vector<int>& myNumbers_in, int number_in)
{
std::vector<int>::iterator iter = myNumbers_in.begin();
while (iter != myNumbers_in.end())
{
if (*iter == number_in)
{
iter = myNumbers_in.erase(iter);
}
else
{
++iter;
}
}
}
Or you could use std::remove_if together with a functor and std::vector::erase:
struct Eraser
{
Eraser(int number_in) : number_in(number_in) {}
int number_in;
bool operator()(int i) const
{
return i == number_in;
}
};
std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), Eraser(number_in)), myNumbers.end());
Instead of writing your own functor in this case you could use std::remove:
std::vector<int> myNumbers;
myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end());
In C++11 you could use a lambda instead of a functor:
std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), [number_in](int number){ return number == number_in; }), myNumbers.end());
In C++17 std::experimental::erase and std::experimental::erase_if are also available, in C++20 these are (finally) renamed to std::erase and std::erase_if (note: in Visual Studio 2019 you'll need to change your C++ language version to the latest experimental version for support):
std::vector<int> myNumbers;
std::erase_if(myNumbers, Eraser(number_in)); // or use lambda
or:
std::vector<int> myNumbers;
std::erase(myNumbers, number_in);
You can iterate using the index access,
To avoid O(n^2) complexity you can use two indices, i - current testing index, j - index to store next item and at the end of the cycle new size of the vector.
code:
void erase(std::vector<int>& v, int num)
{
size_t j = 0;
for (size_t i = 0; i < v.size(); ++i) {
if (v[i] != num) v[j++] = v[i];
}
// trim vector to new size
v.resize(j);
}
In such case you have no invalidating of iterators, complexity is O(n), and code is very concise and you don't need to write some helper classes, although in some case using helper classes can benefit in more flexible code.
This code does not use erase method, but solves your task.
Using pure stl you can do this in the following way (this is similar to the Motti's answer):
#include <algorithm>
void erase(std::vector<int>& v, int num) {
vector<int>::iterator it = remove(v.begin(), v.end(), num);
v.erase(it, v.end());
}
Calling erase will invalidate iterators, you could use:
void erase(std::vector<int>& myNumbers_in, int number_in)
{
std::vector<int>::iterator iter = myNumbers_in.begin();
while (iter != myNumbers_in.end())
{
if (*iter == number_in)
{
iter = myNumbers_in.erase(iter);
}
else
{
++iter;
}
}
}
Or you could use std::remove_if together with a functor and std::vector::erase:
struct Eraser
{
Eraser(int number_in) : number_in(number_in) {}
int number_in;
bool operator()(int i) const
{
return i == number_in;
}
};
std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), Eraser(number_in)), myNumbers.end());
Instead of writing your own functor in this case you could use std::remove:
std::vector<int> myNumbers;
myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end());
In C++11 you could use a lambda instead of a functor:
std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), [number_in](int number){ return number == number_in; }), myNumbers.end());
In C++17 std::experimental::erase and std::experimental::erase_if are also available, in C++20 these are (finally) renamed to std::erase and std::erase_if (note: in Visual Studio 2019 you'll need to change your C++ language version to the latest experimental version for support):
std::vector<int> myNumbers;
std::erase_if(myNumbers, Eraser(number_in)); // or use lambda
or:
std::vector<int> myNumbers;
std::erase(myNumbers, number_in);
You can iterate using the index access,
To avoid O(n^2) complexity you can use two indices, i - current testing index, j - index to store next item and at the end of the cycle new size of the vector.
code:
void erase(std::vector<int>& v, int num)
{
size_t j = 0;
for (size_t i = 0; i < v.size(); ++i) {
if (v[i] != num) v[j++] = v[i];
}
// trim vector to new size
v.resize(j);
}
In such case you have no invalidating of iterators, complexity is O(n), and code is very concise and you don't need to write some helper classes, although in some case using helper classes can benefit in more flexible code.
This code does not use erase method, but solves your task.
Using pure stl you can do this in the following way (this is similar to the Motti's answer):
#include <algorithm>
void erase(std::vector<int>& v, int num) {
vector<int>::iterator it = remove(v.begin(), v.end(), num);
v.erase(it, v.end());
}
Calling erase will invalidate iterators, you could use:
void erase(std::vector<int>& myNumbers_in, int number_in)
{
std::vector<int>::iterator iter = myNumbers_in.begin();
while (iter != myNumbers_in.end())
{
if (*iter == number_in)
{
iter = myNumbers_in.erase(iter);
}
else
{
++iter;
}
}
}
Or you could use std::remove_if together with a functor and std::vector::erase:
struct Eraser
{
Eraser(int number_in) : number_in(number_in) {}
int number_in;
bool operator()(int i) const
{
return i == number_in;
}
};
std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), Eraser(number_in)), myNumbers.end());
Instead of writing your own functor in this case you could use std::remove:
std::vector<int> myNumbers;
myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end());
In C++11 you could use a lambda instead of a functor:
std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), [number_in](int number){ return number == number_in; }), myNumbers.end());
In C++17 std::experimental::erase and std::experimental::erase_if are also available, in C++20 these are (finally) renamed to std::erase and std::erase_if (note: in Visual Studio 2019 you'll need to change your C++ language version to the latest experimental version for support):
std::vector<int> myNumbers;
std::erase_if(myNumbers, Eraser(number_in)); // or use lambda
or:
std::vector<int> myNumbers;
std::erase(myNumbers, number_in);
Depending on why you are doing this, using a std::set might be a better idea than std::vector.
It allows each element to occur only once. If you add it multiple times, there will only be one instance to erase anyway. This will make the erase operation trivial. The erase operation will also have lower time complexity than on the vector, however, adding elements is slower on the set so it might not be much of an advantage.
This of course won't work if you are interested in how many times an element has been added to your vector or the order the elements were added.
To erase 1st element you can use:
vector<int> mV{ 1, 2, 3, 4, 5 };
vector<int>::iterator it;
it = mV.begin();
mV.erase(it);
Depending on why you are doing this, using a std::set might be a better idea than std::vector.
It allows each element to occur only once. If you add it multiple times, there will only be one instance to erase anyway. This will make the erase operation trivial. The erase operation will also have lower time complexity than on the vector, however, adding elements is slower on the set so it might not be much of an advantage.
This of course won't work if you are interested in how many times an element has been added to your vector or the order the elements were added.
Source: Stackoverflow.com