Erasing Vector::End from Vector

Erasing vector::end from vector

The standard doesn't quite spell it out, but v.erase(q) is defined, "Erases the element pointed to by q" in [sequence.reqmts]. This means that q must actually point to an element, which the end iterator doesn't. Passing in the end iterator is undefined behavior.

Unfortunately, you need to write:

auto it = std::find(...);
if (it != <the part of ... that specifies the end of the range searched>) {
    v.erase(it);
}

Of course, you could define:

template typename<Sequence, Iterator>
Iterator my_erase(Sequence &s, Iterator it) {
    if (it == s.end()) return it;
    return s.erase(it);
}

my_erase(v, std::find(v.begin(), v.end(), whatever));

c.erase() on an associative container returns void, so to generalize this template to all containers you need some -> decltype action.

Is passing vector's end() to std::vector::erase valid?

An invalid position or range causes undefined behavior.

From here

The iterator pos must be valid and dereferenceable. Thus the end()
iterator (which is valid, but is not dereferencable) cannot be used as
a value for pos.

Erasing from vector by swapping to the end

You can use std::partition instead of std::remove/std::remove_if:

Keep only values greater than 3:

std::vector foo{1,2,3,4,5,6,7,8};

foo.erase(std::partition(foo.begin(),
                         foo.end(),
                         [](auto& v) { return v > 3; }
                        ),
          foo.end());

Or you could make it similar to the std::erase / std::erase_if (std::vector) pair that was added in C++20 and return the number of erased elements. I call them unstable__erase and unstable__erase_if.

// Erases all elements that compare equal to value
template<class T, class Alloc, class U>
[[maybe_unused]] constexpr typename std::vector<T,Alloc>::size_type
unstable_erase(std::vector<T,Alloc>& c, const U& value) {
    return unstable_erase_if(c, [&value](auto& v) { return v == value; });
}

// Erases all elements that satisfy the predicate pred
template<class T, class Alloc, class Pred>
[[maybe_unused]] constexpr typename std::vector<T,Alloc>::size_type
unstable_erase_if(std::vector<T,Alloc>& c, Pred pred) {
    using size_type = typename std::vector<T,Alloc>::size_type;

    auto p = std::partition(c.begin(), c.end(), std::not_fn(pred));
    auto count = static_cast<size_type>(std::distance(p, c.end()));
    c.resize(c.size() - count);

    return count;
}

Since std::partition swaps elements I was expecting to be able to improve on the speed by replacing the above

    auto p = std::partition(c.begin(), c.end(), std::not_fn(pred));

with

    auto p = unstable_remove_if(c.begin(), c.end(), pred);

where I've defined unstable_remove_if as below:

template<class ForwardIt, class UnaryPredicate>
constexpr ForwardIt
unstable_remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p) {
    for(;first != last; ++first) {
        if(p(*first)) { // found one that should be removed

            // find a "last" that should NOT be removed
            while(true) {
                if(--last == first) return last;
                if(not p(*last)) break;          // should not be removed
            }
            *first = std::move(*last);           // move last to first
        }
    }
    return last;
}

but, to my surprise, running that in https://quick-bench.com/ showed that they performed equally fast for fundamental types (up to long double).

Edit: For larger types, it showed a big improvement (8-16 times as fast for 32 - 64 byte types), so using the unstable_remove_if in unstable_erase_if (std::vector) is probably the way to go for a generic solution of removing elements matching a certain predicate or value.

Will the end address of the vector change if we erase some elements from the vector because in vector, memory is allotted sequentially (same as array)

Yes you are correct.

More formally, all iterators and references at or after the first point of the erase, including the end() iterator, are invalidated.

In other words the addresses of the elements prior to the point of the erase stay the same, but not those after.

Segmentation fault on erasing the last element from the vector C++

The problem is that std::vector::end returns an iterator to the element following the last element of the container, not to the last element.

What you want should be

vec.erase(vec.end() - 1); // trying to erase the last element of vec

Erasing vector.end() fails

vector::end() does not point to the last element, it points to the element just after the last element.

Quoting cplusplus.com,

std::vector::end

Returns an iterator referring to the past-the-end element in the
vector container.

The past-the-end element is the theoretical element that would follow
the last element in the vector. It does not point to any element, and
thus shall not be dereferenced.

Because the ranges used by functions of the standard library do not
include the element pointed by their closing iterator, this function
is often used in combination with vector::begin to specify a range
including all the elements in the container.

Hence, it has nothing to erase() there, and hence the error.

Replace

c.erase(c.end());

with

c.erase(c.end() - 1);

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

Using the iterator version.
Note:

Iterators are invalidated only when there is a reallocation.
Just replace iterators with index does not change the fact that they are invalid when some values are removed from the vector.
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

C++ Erase vector element by value rather than by position?

How about std::remove() instead:

#include <algorithm>
...
vec.erase(std::remove(vec.begin(), vec.end(), 8), vec.end());

This combination is also known as the erase-remove idiom.

C++ Vector.erase() last element corrupts iterator

Let's say you have 2 objects in your vector and the last one is is marked as destroyed. When you call erase, it will return a new, valid iterator pointing at the element after the erased element. There is no element after the erased element, so the returned iterator is gameObjects.end(). You then continue to the top of the loop and dereference this iterator, which is not valid. You need to decrement your iterator after the erase if you want it pointing at a valid element.

One other note: If you ever wanted your first element removed, it will not be. Your loop exits when the iterator == gameObjects.begin(), so the first element is never checked.

Is there some reason you wanted to do this in reverse? If there is no specific reason, I would recommend you use the method recommended by @Borgleader.

Why erasing vector.end() is allowed?

It is undefined behaviour.
In particular, it means that you may see size decreased by one

Erasing Vector::End from Vector