Remove Vector Element

[sma]

I am using a vector to manage the data within my app and need to delete elements within the vector.

The code below uses the remove_if and erase methods to achieve this however it only ever removes the last element of the vector and not the one allocated by the remove_if. Irrespective which element in the vector is to be removed only the last element is erased.

The code below first searches the vector for the required element and changes the data so that the SomeFunc function will return true indicating that this is the element to remove.

I then use the remove_if to process the vector in preparation for the erase.

bool SomeFunc(InsertionData& item)
{
	if (item.GetEntry() == 0 )
       return true;
    return false;
}



void FaultEntry::DeleteListing(int Entry)
{
    ListingDataVector::iterator ListingIterator;
    int VectorCount = 0;
    bool DoErase = false;
    
     if (Entry != 0)
    {
        for(ListingIterator = ListingsVector.begin(); ListingIterator != ListingsVector.end(); ListingIterator++)
        {
            if(ListingIterator->GetEntry() == Entry)
           {				
	ListingIterator->ClearContents();
	DoErase = true;
           }
        }

        if(DoErase)
       {
            ListingIterator = remove_if(ListingsVector.begin(), ListingsVector.end(), SomeFunc);

             this->ListingsVector.erase(ListingIterator, ListingsVector.end());
        }
    }
}

Can any please provide any insights?

[cilu]

The erase-remove part seems correct. Are you sure SomeFunc removes the expected elements from the vector?

[jwbarton]

The behavior you observed is normal.

When you use remove_if(), the vector is modified by shifting any elements which don't match the predicate up (any which SomeFunc() returns false). The remove_if() algorithm returns an iterator which is the start of the elements that you can then erase. If there weren't any, then it will return the end() iterator, so nothing would be erased.

If the SomeFunc() is matching on a single element in the vector, then all other elements are shifted up and the iterator returned will be one before the end() iterator.

So, if every time you use it you see that it always erases the last element, it is simply because remove_if() has shifted all the other elements up and you are just getting rid of the one element that matched.

[Paul McKenzie]

I am using a vector to manage the data within my app and need to delete elements within the vector.

The code below uses the remove_if and erase methods to achieve this however it only ever removes the last element of the vector and not the one allocated by the remove_if.

Another approach is to use std::stable_partition, which would eliminate the need for you to write the initial loop.

#include <vector>
#include <algorithm>

struct ListingData
{
    void ClearContents() { }
    int Entry;
    int GetEntry( ) const;
    ListingData(int Entry_ = 0 ) : Entry(Entry_) { }
};

typedef std::vector< ListingData> ListingDataVector;
//...
struct ProcessEntry
{
    int Entry_;
    ProcessEntry( int Entry) : Entry_(Entry) { }
    bool operator()( ListingData& ld ) const
    {
        return ld.GetEntry() == Entry_;
    }
};

void ClearEntry(ListingData& ld)
{
    ld.ClearContents();
}

void DeleteListing(int Entry)
{
    ListingDataVector v; 
    //...
    if (Entry != 0)
    {
        ListingDataVector::iterator it = std::stable_partition( v.begin(), v.end(), ProcessEntry( Entry ) );
        std::for_each( it, v.end(), ClearEntry );
        v.erase(it, v.end());
    }
}

The stable_partition places the items you want to clear on one side of the partition (the iterator that you see). Once you have those elements on that side of the partition, then you process them (the for_each clears each of them, and the erase removes them.

Basically, any time you write a loop that checks if an element has a certain property, then you can almost be assured there is an algorithm function already written (or set of algorithm functions already written) that does the same as your loop. The stable_partition algorithm gathers all of the iterms you want to process and places them at the end of the vector, similar to remove_if, but it does not invalidate them. Not invalidating them is the trick. Now you can process those elements and then later on, remove them.

Regards,

Paul McKenzie

[sma]

Thanks for the information,

The remove_if function is not moving the element that causes SomeFunc to return true to the end of the vector, eg the matching element is at vector index 0 and remains there as a result the iterator pointing to the end of the vector results in the erase deleting the last element which is valid.

[Lindley]

Thanks for the information,

The remove_if function is not moving the element that causes SomeFunc to return true to the end of the vector, eg the matching element is at vector index 0 and remains there as a result the iterator pointing to the end of the vector results in the erase deleting the last element which is valid.

Well, the remove_if function is certainly *trying* to move them. If the the type contained in the vector has a user-defined copy constructor, assignment operator, or the move equivalent of either, then I suggest you check those for correctness. Also check to see if there is an incorrect specialization of std::swap for the type.

[Paul McKenzie]

Thanks for the information,

The remove_if function is not moving the element that causes SomeFunc to return true to the end of the vector, eg the matching element is at vector index 0 and remains there as a result the iterator pointing to the end of the vector results in the erase deleting the last element which is valid.

First, you should post what your class actually consists of in terms of the member variables so that we can see if there is anything about that class that may not be correct when items are moved.

Second, I believe my approach is much more clear and concise than your hand-written loop version. Best of all, I know it works if the type in the vector is safely copyable, since it is purley calling algorithm functions with the appropriate iterators and functors. There are no hand-written loops to mess up or make unoptimal (your post increment of the iterator in the for loop is an example).

I would suggest you change your code to something similar to what I posted to see if you have the same issue as you have now with your hand-written loop.

Regards,

Paul McKenzie

[sma]

I will look at the copy constructor as the element being removed does not have a specific = operator.

I will let you know how I get on, once I have had a chance to to this.

Thank You

[Lindley]

I will look at the copy constructor as the element being removed does not have a specific = operator.

Curious. Usually, if the type is such that it requires a custom copy constructor, a custom operator= (and usually a custom destructor) is also required for correctness. This is called the "rule of three".

[sma]

The issue has been resolved.

After creating a custom = operator the routine no erases the correct element from the vector.


One further question regarding passing the SomeFunc and argument to compare, how would I need to change the syntax for the remove_if statement and the SomeFunc prototype?

[Paul McKenzie]

The issue has been resolved.

After creating a custom = operator the routine no erases the correct element from the vector.

So what was the reason why you needed to code a custom assignment operator?

Just remember that when you write a user-defined assignment operator, that routine has to be correct, and not just work for your issue. Assigning is a basic operation that is done many times, sometimes without you being aware of it. If that assignment operator is faulty in any way, you could introduce very hard-to-find bugs in the program.

You need to make sure you copied all of the members, call any assignment of the base class (if it has a base class), and ensure that when you copy, both objects are logically equivalent to each other (i.e. no side effects occur when an object is made equal to another).

Also, you need to implement the copy constructor in the same way.

Regards,

Paul McKenzie

[sma]

The = operator was required as the vector maintains instances of a class which has several data members in conjunction with a further vector which maintains CString objects of which there may be many for a single instance of the class.


This is the first time I have used vectors in an application to manage instances of classes so I am going through a bit of a learning curve.

The issue with the assignment operator again is a bit of a new activity as my previous apps used specific compare and or copy methods to enable the required activities to be completed rather than the operator overloading.