I have a vector that contains Points on a board
and I would like to do the following:
1) if a Point appears an even number of times i would like to delete all of the same Points.
2) if a Point appears an odd number of times i would like to leave only the last appearance.

here is my code, which makes an windows error while running. tried debugging but seems like its inside the vector file.

    vector<Point>::iterator i=_shapeOutline.begin();
    int counter=1;
    for (;i!=_shapeOutline.end();i++){
        vector<Point>::iterator j=i;
        j++;
        for(;j!=_shapeOutline.end();j++){
            if ((*i)==(*j))
                counter++;
        }
        bool saveOne= counter%2==0;
        if (counter!=1){
            Point t=(*i);
            for(vector<Point>::iterator j=_shapeOutline.begin();
                j!=_shapeOutline.end();j++)
                if (t==(*j)){
                    if(saveOne)
                        _shapeOutline.erase(j);
                    else{
                        if (counter==1)
                            break;
                        _shapeOutline.erase(j);
                        counter--;
                    }
                }
        }
        cout<<counter<<" "<< (*i).getX()<<" "<<(*i).getY()<<endl;

        counter=1;
    }

any idea whats the problem?

thanks!
is there a problem erasing while iterating? ive seen a few posts saying it might be a problem?
if i cant use iterator whats a good way to erase the way i need without sorting the vector?
need to keep it in the same order
thanks

Recommended Answers

All 5 Replies

Try this.. Works on integers. Deletes all the ONES if there are an even number of them.. and deletes all but the last one if it's odd.

#include <Windows.h>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> Meh;
    Meh.push_back(1); Meh.push_back(2); Meh.push_back(3);

    int tracker = 0;
    int LastOne = 0;

    for(int I = 0; I < Meh.size(); I++)
    {
        if (Meh[I] == 1)
        {
            ++tracker;
            ++LastOne;
        }
    }

    if(tracker % 2 == 0)
        for (int I = 0; I < Meh.size(); I++)
        {
            if (Meh[I] == 1)
            {
                Meh.erase(Meh.begin() + I);
                I = 0;
            }
        }
    else
        for (int I = 0; I < Meh.size(); I++)
        {
            if (LastOne == 1)
                break;

            if (I == LastOne + 1)
                break;

            if(Meh[I] == 1)
            {
                Meh.erase(Meh.begin() + I);
                I = 0;
                LastOne -= 1;
            }
        }

    for (int I = 0; I < Meh.size(); I++)
        cout<<Meh[I]<<endl;
}

I would think that good logic is to find a pair of same values and remove them, what is left is odd number values. Making new sequence could be safer to avoid problems in iterating changing sequence.

Thanks , but still I wonder is why iterating may cause a problem?

with size() mission accomplished ty

If you remove a pair, you must check again with same index for next pair as the value we have in current first index contains the value that used to be in next index.

["a", "b","a", "b"]
["b", "b"]
[]

I think from general viewpoint as I mostly program in Python

Erasing elements while iterating through them is a problem because, with a container like std::vector, any operation that adds or erases elements in the vector will cause all iterators to be invalid. In other words, your iterator it that you use in your loop becomes invalid as soon as an element is erased (or added) from the vector. It needs to be reset. This is because erasing or adding an element to a vector might cause a reallocation of the memory, and since iterators for a vector is often just a pointer (or a thin-wrapper for a pointer), if the memory is reallocated elsewhere, that iterator no longer points to a valid element of the vector.

Not all STL containers are like that. There are different containers for different needs. Vectors are often not the best if you are going to do a lot of insertions / deletions in the middle of the sequence. The alternative, linked-lists which are more efficient at mid-sequence insertion / deletion, also have many drawbacks that are not negligible either (locality of references) and often out-weight its theoretical performance benefits.

Normally, the preferred strategy for removing elements of a vector is to simply not erase them just yet. Instead, you implicitely remove them from the vector by re-packing all the remaining elements, leaving a bunch of empty elements at the end of the vector, which you erase afterwards.

I think you can implement your algorithm simply by making clever use of std::remove (ref). As follows:

void RemoveEvenDuplicates(std::vector<int>& v) {
  typedef std::vector<int>::reverse_iterator Iter; // notice the use of reverse_iterator here.
  Iter it_end = v.rend();
  for(Iter it = v.rbegin(); it != it_end; ++it) {
    // remove all elements of value '*it' after 'it'.
    Iter it_new_end = std::remove(it + 1, it_end, *it);
    // if we removed an odd number, we should also remove 'it' (to make it even).
    if( (it_end - it_new_end) % 2 == 1 ) {
      std::copy(it + 1, it_new_end, it);
      --it; --it_new_end;
    };
    // update the end iterator:
    it_end = it_new_end;
  };
  // after the loop is done, remove the empty elements:
  v.erase(v.begin(), it_end.base());
};

The use of a reverse iterator in the above code is simply because in your original code, if there was an odd number of elements with same value, you wanted to keep the last occurence in the vector. If you wanted to keep the first occurence of the element in the vector, then you would use normal iterators instead (the algorithm remains exactly the same). (i.e. in the above, I proceed in reverse and keep the first occurence of the value if the number is odd, which is the same as going forward and keeping the last occurence).

commented: Thanks for your expert advice! Nice to see I was correct. +12
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.