Vectors

Page Contents

Erasing Elements

If you don't want to use remove_if() use the following... 

myVector::iterator itr = myVector.begin();
myVector::iterator itrEnd = myVector.end();
while(itr != itrEnd)
{
    if (delete_condition)
    {
        it = v.erase(it); # erase invalidates the iterator passed to it and
                          # returns a new iterator that is correctly set to the
                          # element following the last removed element or end()
    }
    else
    {
        ++it;
    }
}

If it is a simple find-by-some-condition and you are using C++11 use: 

#include <algorithm>
myVector.erase(
    std::remove_if(
        myVector.begin(), myVector.end(), [](T const & x) -> bool { /* Code here */ }),
    myVector.end());

But, of course, you might not be using C++11, in which case use a callable instead of the lambda. This can be a function or a structure implementing the call operator. Example below: 

class MyComparitor
{
public:
    MyComparitor
    (
        std::string needle
    ) : mNeedle(needle)
    {
    }

    bool operator()(const MyObject *const obj) const
    {
        return obj->someProperty == mNeedle;
    }
private:
    std::string mNeedle;
};

myVector.erase(
    std::remove_if(
        myVector.begin(), myVector.end(), MyComparitor("String to find"));

You may be wondering if the order of evaluation of the vec.erase() parameter vec.end() (repeated twice) matters. The answer is it does not. The reason is that std::remove() does not change the size of vec. The remove operation works by moving elements around so that to the left of the returned new end iterator is the new contents and to the right (and including) is effectively invalid. Hence the end iterator does not change: the location remains the same, it's just the contents that differs!

Note that, particularly for vectors, this erase-remove idiom would be a lot faster than removing each matching element individualy, if there is more than one such element. The reason is that removing each element individually requires every element "to the right" in the vector's array to be moved left by one. Therefore, if there are n targets, you do n swaps rather than n removes and array reshuffles (a lot more work!).

We can look at this a little more closely by just looking at what remove() does... 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

template<typename T>
void PrintElements(const std::string &prefix, const T &container, const unsigned int width=3)
{
   std::cout < prefix;
   for (const auto &elem : container) std::cout < std::setw(width) < std::right < elem;
   std::cout <lt; std::endl;
}

template<typename T>
void PrintEnd(const std::string &prefix, T itA, T itB, const unsigned int width=3)
{
   auto dist = (std::distance(itA, itB) + 1u) * width + prefix.size() + 1u;
   std::cout <lt; std::setw(dist) <lt; std::right <lt; "^\n";
}

int main(int argc, char *argv[])
{
   std::vector testVec = { 1, 10, 2, 10, 3, 10, 4, 10, 5, 10, 6 };

   PrintElements("Before remove: ", testVec);
   PrintEnd("Before remove: ", testVec.begin(), testVec.end());

   auto newEnd = std::remove(testVec.begin(), testVec.end(), 10);
   PrintElements("After remove:  ", testVec);
   PrintEnd("After remove:  ", testVec.begin(), newEnd);

   testVec.erase(testVec.begin(), newEnd);
   PrintElements("After erase:   ", testVec);
   PrintEnd("After erase:   ", testVec.begin(), testVec.end());

   return 0;
}
/* 
 * OUTPUTS:
 * Before remove:   1 10  2 10  3 10  4 10  5 10  6
 *                                                   ^
 * After remove:    1  2  3  4  5  6  4 10  5 10  6
 *                                    ^
 * After erase:     4 10  5 10  6
 *                                 ^
 */