Deleting in a vector help please!!!

[gghf]

I created a very basic program which contains a vector (my vector) that holds 0, 1 and 1. This program compares each element in the vector. If the element after the one currently being compared is equal to it, it outputs "repeat found!" Now this all works perfectly, but my next step was to erase the repeated one. Everything was working up until the delete step. I get a weird error that says "vector iterator not dereferencable" Thanks if you can help.

// vector::begin/end
#include <iostream>
#include <vector>

using namespace std;

int main ()
{
  vector<int> myvector;
  myvector.push_back(0);
  myvector.push_back(1);
  myvector.push_back(1);



  cout << "myvector contains:" << endl;
  int x = 0;
  for (vector<int>::iterator i = myvector.begin(); i != (myvector.end()-1); ++i, ++x) {
	  
	  cout << *i;

	  if (*i == (myvector.at(x+1))) {
		  cout << " Repeat found!\n";
		  myvector.erase (myvector.begin()+(x+1));
	  }
	  
}
  cout << "\n First 3:" << myvector.at(0) << " " << myvector.at(1) << " " << myvector.at(2) ;
  cout << '\n';

  return 0;
}

[gghf]

please anyone help?

[SteveCodeMan]

Sure! it's fairly simple to remove duplicates! I started writing up my own method to do this for you, then realized someone had probably already done this and in a much more optimized way! Sure enough they had! lol only two lines is much shorter than mine was turning out to be! So full credit to Nate Kohl -> http://stackoverflow.com/questions/1041620/most-efficient-way-to-erase-duplicates-and-sort-a-c-vector

I should say though, the reason why you are getting that is because you cannot erase items from a vector while your are iterating through it! Also it isn't really a good idea to delete the next entry (x+1) unless you have checks to make sure for certain that there is a next entry, still in the case of vector iterators you for sure can't delete items while iterating! In general though it's a bad practice!

Know what you're going to delete by iterating the vector and storing which ones to delete, then delete those entries after that. That's what you'd have to do!

Try this sample code I modified yours into... two new include files though only one needs to be included if only using one method (which makes sense) though both good methods are shown.. <algorithm> is used in 'RemoveDuplicatesFromVector function' and <set> is used in 'RemoveDuplicatesFromVectorMethod2' function

// vector::begin/end
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

void DisplayVector(vector<int> &displaythis);
void RemoveDuplicatesFromVector(std::vector<int> &thisvector);
void RemoveDuplicatesFromVectorMethod2(std::vector<int> &thisvector);

int main ()
{
	vector<int> myvector;
	vector<int> myvectorExample2;

	for(int i = 0; i < 10; i++)
	{
		for(int w = 0; w < 4; w++)
		{
			myvector.push_back(i);
		}
	}

	myvectorExample2 = myvector;
	
	cout << "myvector and example vector 2 contain initially:\n";
	DisplayVector(myvector);

	RemoveDuplicatesFromVector(myvector);

	RemoveDuplicatesFromVectorMethod2(myvectorExample2);

	cout << "\n\nmyvector contains after duplicates removed:\n";
	DisplayVector(myvector);

	cout << "myvectorExample2 contains after duplicates removed:\n";
	DisplayVector(myvectorExample2);

	return 0;
}

void DisplayVector(vector<int> &displaythis)
{
	for(vector<int>::iterator i = displaythis.begin(); i != displaythis.end(); ++i)
	{
		cout << *i;
	}
	cout << "\n";
}

void RemoveDuplicatesFromVector(std::vector<int> &thisvector)
{
	sort(thisvector.begin(), thisvector.end());
	thisvector.erase(unique(thisvector.begin(), thisvector.end()), thisvector.end());
}

void RemoveDuplicatesFromVectorMethod2(std::vector<int> &thisvector)
{
	set<int> s;
	unsigned size = thisvector.size();

	for(unsigned i = 0; i < size; ++i) 
		s.insert(thisvector[i]);

	thisvector.assign(s.begin(), s.end());
}

I had the functions take a reference & to the vector rather than a copy of it, so it actually effects the passed in vector!

The first remove duplicates method works like this, it sorts the numbers so each one that is the same are next to each other, then calling erase with the unique function in that way removes the duplicates (but it only works if sorted first)

Second method creates a set out of your vector and then dumps it back into your vector... a set automatically has unique entries (no duplicates) so that is taken advantage of in this method!

Hope this helps! I was recently playing with vectors as well they are handy aren't they? :)

[JLBorges]

Erasing an element from a vector invalidates iterators to that element and every element after it. Instead, use the value returned by erase() - a valid iterator to the next element after the erased element.
http://en.cppreference.com/w/cpp/container/vector/erase

Repeatedly erasing elements from the the vector is expensive - O(N) for each element erased. The canonical way to do this is to use the remove - erase idiom.

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

int main()
{
    {
        std::vector<int> seq { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
        for( int v : seq ) std::cout << v << ' ' ;
        std::cout << '\n' ;

        // erase odd numbers from the vector
        for( auto iter = std::begin(seq) ; iter != std::end(seq) ; )
        {
            if( *iter%2 ) iter = seq.erase(iter) ; // erase if odd
            else ++iter ;
        }

        for( int v : seq ) std::cout << v << ' ' ;
        std::cout << '\n' ;
    }

    {
        std::vector<int> seq { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
        for( int v : seq ) std::cout << v << ' ' ;
        std::cout << '\n' ;

        // erase odd numbers from the vector

        // step 1. move all odd numbers to the end of the vector
        // http://en.cppreference.com/w/cpp/algorithm/remove
        auto iter = std::remove_if( std::begin(seq), std::end(seq),
                                      []( int i ) { return i%2 == 1 ; } ) ;

        // step 2. iter 'points' to the first odd number, erase everything from there on
        seq.erase( iter, std::end(seq) ) ;

        for( int v : seq ) std::cout << v << ' ' ;
        std::cout << '\n' ;
    }

    {
        std::vector<int> seq { 0, 1, 1, 2, 3, 3, 3, 3, 4, 4, 5, 6, 6 } ;
        for( int v : seq ) std::cout << v << ' ' ;
        std::cout << '\n' ;

        // erase adjacent duplicates from the vector

        // step 1. move duplicate adjacent elements to the end of the vector
        // http://en.cppreference.com/w/cpp/algorithm/unique
        auto iter = std::unique( std::begin(seq), std::end(seq) ) ;

        // step 2. iter 'points' to the first of the duplicates, erase everything from there on
        seq.erase( iter, std::end(seq) ) ;

        for( int v : seq ) std::cout << v << ' ' ;
        std::cout << '\n' ;
    }

}

http://coliru.stacked-crooked.com/a/e0c628f4b2cad8f5

[abhishekm71]

@JLBorges, one query:

After remove_if, does the remaining extra vector necessarily contain the removed items?

The link you provided says that the extra items' have "unspecified values" which is why usually the erase function is called to shorten the vector's length to the new logical length.

[JLBorges]

> After remove_if, does the remaining extra vector necessarily contain the removed items?

No.

That is of no concern to us; we are going to erase all of them (those with "unspecified values") in the very next step.

A call to remove is typically followed by a call to a container's erase method, which erases the unspecified values and reduces the physical size of the container to match its new logical size. - cppreference

Note: To reorder a sequence, with no intent to remove the elements moved to the end of the sequence,
use std::partition() http://en.cppreference.com/w/cpp/algorithm/partition


> which is why usually the erase function is called to shorten the vector's length to the new logical length.

No. erase() is usually used to remove a sub-sequence of one or more contiguous elements.

remove() - erase() is usually used to remove selected elements which are not necessarily contiguous. (After remove, the elements to be erased form a contiguous sub-sequence at the end).

std::swap() with the back() of the sequence, followed by a pop_back() can be used to remove one element if the relative order need not be maintained.

[abhishekm71]

Great! That clarifies things.

Thanks!