Erasing Elements from a Vector

How to safely erase elements in a std::vector [duplicate]

You can't remove like:

if (!equal) {
    vector2.erase(it);
}

erase operation invalidates it, so the next ++it is an error.

Instead of it, you might rewrite the outer cycle as:

for (std::vector<int>::iterator it (vector2.begin()); it != vector2.end();)

and change it inside the for loop:

if (!equal) {
    it = vector2.erase(it);
} else {
    ++it;
}

DEMO

Note, that you might use remove-erase idiom as well:

vector2.erase(
    std::remove_if(std::begin(vector2), std::end(vector2), [&vector1](const auto& e) {
        return std::find(std::cbegin(vector1), std::cend(vector1), e) == std::end(vector1);
    }),
    std::end(vector2)
);

which is a standard way to do the things like this.

Erasing elements from a vector

Use the remove/erase idiom:

std::vector<int>& vec = myNumbers; // use shorter name
vec.erase(std::remove(vec.begin(), vec.end(), number_in), vec.end());

What happens is that remove compacts the elements that differ from the value to be removed (number_in) in the beginning of the vector and returns the iterator to the first element after that range. Then erase removes these elements (whose value is unspecified).

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

Erase an element from vector by address

While

int* to_delete = &numbers[2];
numbers.erase(numbers.begin() + (to_delete - &numbers[0]));

will work, there are pitfalls. If any new items are added to and/or existing items are removed from numbers between the two lines, the code will result in undefined behavior. But then, dereferencing the pointer will also result in undefined behavior under such circumstances.

If possible, store the index in client code, access the element from the std::vector when you need a handle to the object using index, and delete the element using the index too.

std::vector<int> numbers(5);

size_t index = 2;  // Make sure to use index only after this.

// Access the element using index.
// Use numbers[index];

// Delete the element using the index
if ( index < numbers.size() )
{
   numbers.erase(numbers.begin() + index); 
}
else
{
   // Index is no longer valid.
   // Can't erase from the vector.
}

Erasing() an element in a vector doesn't work

If there are at least 3 items in the vector, to delete the last 3 items is simple -- just call pop_back 3 times:

#include <vector>
#include <iostream>

int main() 
{
    std::vector<float> v = { 1, 2, 3, 4, 5 };
    for (int i = 0; i < 3 && !v.empty(); ++i)
       v.pop_back();

    for ( const auto &item : v ) std::cout << item << ' ';
        std::cout << '\n';
}

Output:

1 2

erasing elements from a vector (hackerrank)

The question aims to make you familiar with 2 common syntax of vector erase method
.
For deleting single element use ,

v.erase( pass iterator pointing to the element that you want to erase)

For example , v.erase(v.begin()) will erase first element of the vector or in other words will erase element at position 0 of the vector.

Since here v.begin() is iterator to the first element of the vector , provided vector isn't empty .

Similarly ,

v.erase(v.begin() + x -1);

erases element at position x of the vector.

Now to erase a range in the vector , overloaded method of erase is used . It is used as follows ,

v.erase(iter1,iter2)

It will erase all the elements in the range of iter1 to iter2 but not including iter2 , that is elements in the range [iter2 , iter2) will be erased . Remember iter2 won't be erased .
Thus this code ,

v.erase(v.begin() + b - 1, v.begin() + c - 1);

will erase all the elements from index b to index c , but not including index c .

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.

How do I erase an element from std::vector by index?

To delete a single element, you could do:

std::vector<int> vec;

vec.push_back(6);
vec.push_back(-17);
vec.push_back(12);

// Deletes the second element (vec[1])
vec.erase(std::next(vec.begin()));

Or, to delete more than one element at once:

// Deletes the second through third elements (vec[1], vec[2])
vec.erase(std::next(vec.begin(), 1), std::next(vec.begin(), 3));

Erase elements in vector using for loop

You would normally employ the erase–remove idiom to delete multiple elements from a vector efficiently (erasing them one by one is generally less efficient, and, as you’ve seen, not always trivial). In its most general form, the idiom looks like this:

data.erase(remove_algorithm(begin(data), end(data)), end(data));

In your case, the remove_algorithm is based off indices in another vector, so we need to provide those as well:

data.erase(
    remove_indices(begin(data), end(data), begin(to_erase), end(to_erase)),
    end(data));

Unfortunately, such an algorithm isn’t contained in the standard library. However, it’s trivial to write yourself¹:

template <typename It, typename It2>
auto remove_indices(It begin, It end, It2 idx_b, It2 idx_e) -> It {
    using idx_t = typename std::iterator_traits<It2>::value_type;
    std::sort(idx_b, idx_e, std::greater<idx_t>{});

    for (; idx_b != idx_e; ++idx_b) {
        auto pos = begin + *idx_b;
        std::move(std::next(pos), end--, pos);
    }
    return end;
}

Here, we first sort the indices to be removed from largest to smallest. Next, we loop over those indices. We then (maximally efficiently) move all elements between the current position (to be deleted) and the end of the vector forward by one. Subsequently, the end is decreased by one (to account for the fact that an element got deleted).

Live code

¹ *Ahem* Once you’ve removed all the silly typos in your code.