Vector Erase Iterator

Vector erase iterator

res.erase(it) always returns the next valid iterator, if you erase the last element it will point to .end()

At the end of the loop ++it is always called, so you increment .end() which is not allowed.

Simply checking for .end() still leaves a bug though, as you always skip an element on every iteration (it gets 'incremented' by the return from .erase(), and then again by the loop)

You probably want something like:

 while (it != res.end()) {
        it = res.erase(it);    
 }

to erase each element

(for completeness: I assume this is a simplified example, if you simply want every element gone without having to perform an operation on it (e.g. delete) you should simply call res.clear())

When you only conditionally erase elements, you probably want something like

for ( ; it != res.end(); ) {
  if (condition) {
    it = res.erase(it);
  } else {
    ++it;
  }
}

c++ vector erase advances iterator

where does the iterator get advanced?

It doesn't, the iterator stays pointing to the same location. This is technically undefined behavior but if you think about what the loop is actually doing, you'll see why you get the "correct" results.

Your vector holds a pointer to the objects that it stores. Your iterator is going to point to that memory with the offset to the element you want. In this case it is going to point to the beginning of the data. When you erase the first element, the iterator is invalidated but it is still pointing to the beginning of the vector. erase moves all of the elements forward so when you go into the next iteration, your in the same state that you were in the first iteration except the vector is one element smaller. You repeatedly do this until there are no elements left and end() == begin()

You should not depend on this always happening though and instead just use clear() to remove all of the elements from the vector.

How can I erase elements from a vector given a list of iterator?

Using the iterator version.
Note:

1. Iterators are invalidated only when there is a reallocation.
2. Just replace iterators with index does not change the fact that they are invalid when some values are removed from the vector.
3. Using indexes is still a better approach as they don't get invalidated when more elements are added later.

Approach:
Create a copy of vector with elements that should not be removed

using Element = std::string;
using RenderData = int;
struct Ref {
    std::vector<RenderData>::iterator itr;
    bool should_remove;
};

struct Main {
    std::vector<RenderData> ints;
    std::unordered_map<Element, Ref> elements;
    void remove_stuff(){
        std::vector<RenderData> localCopy;        
        localCopy.swap(ints);
        ints.reserve(localCopy.size());        
        for(auto it = elements.begin(); it != elements.end();) {
            Ref& ref = it->second;
            if(ref.should_remove) {
                it = elements.erase(it);
            } else {
                ints.push_back(std::move(*ref.itr));
                ref.itr = ints.end() - 1;                
                it++;
            }
        }            
    }
};

Link: https://godbolt.org/g/SouZ5E

What iterator does vector::erase() return if passed an empty range?

This is specified in [sequence.reqmts]:

The iterator returned by a.erase(q1, q2) points to the element pointed to by q2 prior to any elements being erased. If no such element exists, a.end() is returned.

_{(Note: I linked the C++17 final working draft, but this wording exists since at least C++98, see comment by @Peter)}

So we should have it1 == v.begin() and it2 == v.end().

Live test:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v{1, 2, 3, 4};
    auto it1 = v.erase(v.begin(), v.begin());
    auto it2 = v.erase(v.end(), v.end());
    std::cout << std::distance(v.begin(), it1) << std::endl;
    std::cout << std::distance(v.begin(), it2) << std::endl;
}

Output:

0
4

To clarify this behavior, I have updated the cppreference documentation, which is now:

iterator erase( const_iterator pos );
iterator erase( const_iterator first, const_iterator last );

Return Value

Iterator following the last removed element.

If pos refers to the last element, then the end() iterator is returned.

If last==end() prior to removal, then the updated end() iterator is returned.

If [first, last) is an empty range, then last is returned.

Remove by iterator from std::vector

The first one is guaranteed to work correctly, while your second version may be faster (due to std::find stopping at the first item that matches), but it certainly is not safer.

auto it = find(vec.begin(), vec.end(), number_in);
if (it != vec.end())
   vec.erase(it);

That would ensure you are not erasing an invalid iterator.

So it depends on your needs. If you want a program that is correct, the first one works without further intervention, however the second requires a bug ticket from your customer and then you have to go fix it (as above).

vector erase() iterator outside range

As you erase elements of the vector, the vector gets smaller. Since your loop is going to N, eventually the loop index k gets larger than the remaining vector.

How can I implements erase( iterator erase(const_iterator first, const_iterator last)) of vector in c++

You don't need to reallocate the array; use move semantics instead. Even if you use the current implementation, you benefit from moving the values from the old array instead of copying them.

Furthermore it's more efficient for erase(const_iterator, const_iterator) to receive its own implementation.

Your actual problem here is the fact that you're invalidating the iterators by calling erase as noted by @UlrichEckhardt and even if you didn't reallocate the array, you'd need to call erase with first instead of it, since erasing the element at the current position of it shifts the remaining elements left by one resuling in the next element to be erased to be placed at the current position of it, not at the next position.

Here's a simplified vector implementation that should work:

template<class T>
class Vector
{
public:
    using iterator = T*;
    using const_iterator = T const*;

    Vector(std::initializer_list<T>&& list)
        : size(list.size()),
        objects(size == 0 ? nullptr : new T[size])
    {
        auto out = objects;
        for (auto& e : list)
        {
            *out = std::move(e);
            ++out;
        }
    }

    ~Vector()
    {
        delete[] objects;
    }

    iterator begin() noexcept
    {
        return objects;
    }

    iterator end() noexcept
    {
        return objects + size;
    }

    const_iterator cbegin() const noexcept
    {
        return objects;
    }

    const_iterator cend() const noexcept
    {
        return objects + size;
    }

    iterator erase(const_iterator pos)
    {
        auto const result = objects + std::distance(cbegin(), pos);
        auto const endIter = end();
        for (auto p = result; p != endIter;)
        {
            auto& lhs = *p;
            ++p;
            lhs = std::move(*p);
        }
        --size;
        return result;
    }

    iterator erase(const_iterator first, const_iterator last)
    {
        auto const result = objects + std::distance(cbegin(), first);
        if (first == last)
        {
            // empty delete sequence
            return result;
        }

        // shift the elements after last
        auto writeIter = result;
        auto readIter = objects + std::distance(cbegin(), last);

        for (auto const endIter = end(); readIter != endIter; ++writeIter, ++readIter)
        {
            *writeIter = std::move(*readIter);
        }
        // remove extra elements from the end
        size = std::distance(objects, writeIter);
        return result;
    }

private:
    size_t size;
    T* objects;
};

int main()
{
    {
        Vector<int> a = { 1, 2, 3, 4, 5 };

        auto iter = a.erase(a.cbegin() + 1, a.cend() - 1);
        std::cout << "element pointed to by returned value: " << *iter << '\n';
        for (auto i : a)
        {
            std::cout << i << '\n';
        }
    }

    {
        Vector<int> a = { 1, 2, 3, 4, 5 };

        auto iter = a.erase(a.cbegin() + 1);
        std::cout << "element pointed to by returned value: " << *iter << '\n';
        for (auto i : a)
        {
            std::cout << i << '\n';
        }
    }
}

Note: The loops in the member functions can be replaced by the overload of std::move taking iterators.

Is erasing a range more efficient than erasing each of the elements separately?

Of course it depends on circumstance but you can have a feeling by running some specifics. Let's see one example:

#include <iostream>
#include <vector>

uint64_t now() {
    return __builtin_ia32_rdtsc();
}

template< typename T >
void erase1( std::vector<T>& vec ) {
    while ( !vec.empty() ) {
        vec.erase( vec.begin() );
    }
}

template< typename T >
void erase2( std::vector<T>& vec ) {
    while ( !vec.empty() ) {
        vec.erase( vec.begin()+vec.size()-1 );
    }
}

template< typename T > 
void erase3( std::vector<T>& vec ) {
    vec.erase( vec.begin(), vec.end() );
}


int main() {
    for ( unsigned N = 1; N< (1<<20); N*=2 ) { 
        std::vector<int> vec;
        vec.resize( N );
        for ( uint32_t j=0; j<N; ++j ) vec[j] = N;
        uint64_t t0 = now();
        erase1( vec );
        uint64_t t1 = now();

        vec.resize( N );
        for ( uint32_t j=0; j<N; ++j ) vec[j] = N;
        uint64_t t2 = now();
        erase2( vec );
        uint64_t t3 = now();

        vec.resize( N );
        for ( uint32_t j=0; j<N; ++j ) vec[j] = N;
        uint64_t t4 = now();
        erase3( vec );
        uint64_t t5 = now();
        std::cout << (t1-t0) << " " << (t3-t2) << " " << (t5-t4) << std::endl;
    }
}

erase1() will erase one by one from the front. erase2() will erase item by item from the back and erase3() will erase on the entire range.

The results of this run are:

Program stdout
54 46 22
1144 66 24
230 116 22
362 74 24
596 108 24
924 128 22
2906 230 38
4622 270 24
11648 542 22
31764 960 34
94078 1876 24
313308 3874 32
1089342 7470 34
4967132 14792 34
25695930 14720 24
134255144 61492 24
585366944 122838 34
3320946224 115778 22
17386215680 484930 24

Results are in cycles.

You can see that erasing from the front is very costly. From the back is way faster but still apparently O(N). And erasing the range is almost instantaneous and O(1).

Vector erase iterator outside range when trying to erase a previously saved iterator

Yes since your code invokes undefined behavior.

Adding items to vector invalidates all iterator and use of invalidated iterator leads to undefined behavior.

Reason is that there is some reserved memory for items of vector. When this memory is not enough to hold new item, new fragment of memory is allocated and content is copied to new place. Then old fragment of memory is freed. Old iterator still points to old place which was just freed.

In documentation you can find:

std::vector<T,Allocator>::push_back - cppreference.com

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

To fix issue (and make code faster) you can reserve required amount of space for given number of items.

---

Related Topics