Erase elements from vector while iterating through vector

[p al]

Hi guys,

I am trying to erase elements from a vector that are equal to the 1st element of the vector. The following code works fine when v.size is even but it erases only some of the elements when v.size is odd.
I understand that iterating through the vector while erasing causes issues. I also read about the remove-erase idiom but it also doesn't work (I think because I have vector<int> v and not vector<int>& v)

Does anyone have a suggestion? I have thought of copying the elements not to be deleted to an array and then delete all the elements from the vector and then do
v(array,array+sizeof(array)/sizeof(arra[0]))) but obviously that would not be very efficient...

Thank you in advance!

//assume I have initilised vector<int> v with some values
//and the value of v[0] to be erased occurs multiple times

  	for (int i=1; i<v.size(); ++i)
		{
			if(v[i]==v[0])
			{
				v.erase(v.begin()+i);
			}
		}

[cire]

If v is an alias for adj_list[row] then your code is incorrect whenever you have consecutive elements that compare equal to the first element of the vector. (And, why wouldn't you use the alias instead of the full name?)

    unsigned i=1;
    while (i < v.size())
    {
        if ( v[i] == v[0] )
            v.erase(v.begin()+i);
        else
            ++i;
    }

Or using the remove-erase idiom:

v.erase(std::remove(v.begin()+1, v.end(), v.front()), v.end());

[p al]

Hi,

Thanks for your response. I corrected the code part you mentioned.

I am trying to use the remove-erase idiom but it gives me an error and it won't even compile:

More specifically it says:

Error: no suitable conversion from vector to constant char*.

And could you please explain what is it exactly that happens and the while loop with the erase command does not work?


Thanks a lot for your help!
P

[cire]

Thanks for your response. I corrected the code part you mentioned.

Actually, you made it look more wrong.

v.erase(adj_list[row].begin()+i);

If v is an alias for adj_list[row] then why not just use the alias v? If it is not an alias for v the code is incorrect. Feeding an iterator from one container to another container results in undefined behavior.

I am trying to use the remove-erase idiom but it gives me an error and it won't even compile:

More specifically it says:

Error: no suitable conversion from vector to constant char*.

I can't imagine how that would happen, especially since you said v is a vector of int.

Generally speaking it is a good idea to reduce your problem to a simple, compilable code sample that reproduces your issue. Perhaps you should do that now. All we've dealt with so far are incomplete snippets of code out of context, and I suspect your problems are in the context.

And could you please explain what is it exactly that happens and the while loop with the erase command does not work?

Can you please explain why, exactly, you don't believe it works?

Here is a compilable example:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

template <typename iter_type>
void print(iter_type beg, iter_type end)
{
    std::cout << "{ ";
    while (beg != end)
        std::cout << *beg++ << ' ';
    std::cout << "}\n";
}

template <typename container_type>
void print(const container_type& container)
{
    print(std::begin(container), std::end(container));
}

void remove_copies_of_front_with_remove_erase_idiom(std::vector<int>& v)
{
    v.erase(std::remove(v.begin()+1, v.end(), v.front()), v.end());
}

void remove_copies_of_front_with_while_loop(std::vector<int>& v)
{
    unsigned i = 1;
    while (i < v.size())
    {
        if (v[i] == v[0])
            v.erase(v.begin() + i);
        else
            ++i;
    }
}

int main()
{
    using vec_t = std::vector<int>;

    vec_t original = { 1, 1, 1, 2, 1, 3, 1, 1, 4, 1, 1, 5 };
    vec_t expected_result = { 1, 2, 3, 4, 5 };

    auto a = original;
    std::cout << "Before remove-erase idiom applied\n\ta: ";
    print(a);

    remove_copies_of_front_with_remove_erase_idiom(a);
    std::cout << "\nAfter removal\n\ta: ";
    print(a);

    if (a == expected_result)
        std::cout << "Success!\n\n";
    else
        std::cout << "Failure!\n\n";

    auto b = original;
    std::cout << "Before while removal\n\tb: ";
    print(b);

    remove_copies_of_front_with_while_loop(b);
    std::cout << "\nAfter removal\n\tb: ";
    print(b);

    if (b == expected_result)
        std::cout << "Success!\n\n";
    else
        std::cout << "Failure!\n\n";
}

With online demo: http://ideone.com/JalrWr

[p al]

Hi thanks,

I know it doesn't work... I just wanted to know the reason why it doesn't...

I was expecting some simple explanation as to why iterating through a vector while erasing elements doesn't work like:

"Everytime it erases an element it returns the pointer to the element next to it so it is as if it skips it (i.e. does not check if it is equal to the element to be erased) and that's why we need the idiom"

which is just my guess of what happens.


The code to replicate the problem with the idiom would be:

#include<iostream>
#include<vector>

using namespace std;

int main()
{

	int arr[]={1,2,3,4,1,3,4,2,1};

	vector<int> v (arr,arr+sizeof(arr)/sizeof(arr[0]));

	v.erase(remove(v.begin()+1,v.end(), v.front()), v.end()); 


	cin.get();
	return 0;
}

It gives me the afformentioned error and it does not compile.

Thanks a lot!

[keskiverto]

Odd. It should give

error: ‘remove’ was not declared in this scope

Reason: std::remove is declared in <algorithm>.


Perhaps the use of "using namespace std;" with your compiler finds some other 'remove' from the headers that you do include.

[p al]

Oh thanks! That was the problem! I hadn't included the header algorithm! Now it works fine! Thanks a lot!