Delete from specific indexes in a std::vector

Question

Say I have a std::vector with 5 elements and I need to delete elements from indexes 1 and 3 what would be the fastest way to do this. Are there any helper methods in the standard library that could do this for me ?

Answer 1

You could use the erase function. For this specific case you mention something like this:

myvector.erase (myvector.begin()+3);
myvector.erase (myvector.begin()+1);

will do the trick. You have to provide an iterator to the erase function and I suggest you read documentation for its use. The above should work for your case. Note that each call to erase will change the index of the remaining elements AFTER the removed position though as the internal array elements will be adjusted relative to the item removed.

In response to your comment, you can only erase one element at a time, UNLESS they are contiguous indices in which case you can use the range based version of erase taking a start and end iterator. For example if you want to erase indices 1,2 AND 3 use

myvector.erase (myvector.begin()+1,myvector.begin()+4);

As I already mentioned the indices of items after the one you erase will downshift accordingly. This is unavoidable though as an array cannot have "gaps" in it.

Answer 2

This should be a fairly efficient implementation using std::move and only moving each element max once. It requires the indexes to remove in to_remove to be ordered.

template<typename T>
  void remove_index(std::vector<T>& vector, const std::vector<int>& to_remove)
  {
    auto vector_base = vector.begin();
    std::vector<T>::size_type down_by = 0;

    for (auto iter = to_remove.cbegin(); 
              iter < to_remove.cend(); 
              iter++, down_by++)
    {
      std::vector<T>::size_type next = (iter + 1 == to_remove.cend() 
                                        ? vector.size() 
                                        : *(iter + 1));

      std::move(vector_base + *iter + 1, 
                vector_base + next, 
                vector_base + *iter - down_by);
    }
    vector.resize(vector.size() - to_remove.size());
  }

// Usage:
//
// std::vector<std::string> values = { "0", "1", "2", "3", "4", "5"};
// remove_index(values, { 1, 3 });

Answer 3

This is a lot faster than removing them one-by-one (though it can still be sped up in some cases):

template<class It>
struct remover
{
    size_t *i;
    It *begin;
    It const *end;
    explicit remover(size_t &i, It &begin, It const &end) : i(&i), begin(&begin), end(&end) { }
    template<class T>
    bool operator()(T const &)
    {
        size_t &i = *this->i;
        It &begin = *this->begin;
        It const &end = *this->end;
        while (begin != end && *begin < i)  /* only necessary in case there are duplicate indices */
        { ++begin;  }
        bool const b = begin != end && *begin == i;
        if (b) { ++begin; }
        ++i;
        return b;
    }
};
template<class Container, class IndexIt>
IndexIt remove_indices(Container &items, IndexIt indices_begin, IndexIt const &indices_end)
{
    size_t i = 0;
    std::sort(indices_begin, indices_end);
    items.erase(std::remove_if(items.begin(), items.end(), remover<IndexIt>(i, indices_begin, indices_end)), items.end());
    return indices_begin;
}
int main()
{
    std::vector<int> items(100);
    std::vector<size_t> indices;
    indices.push_back(5);
    indices.push_back(1);
    remove_indices(items, indices.begin(), indices.end());
}

Answer 4

If you want to erase some arbitrary elements in a vector you can do this the following way

for ( int i : { 3, 1 } ) v.erase( std::next( v.begin(), i ) );

Take into account that items in the initializer list should be in descending order.