Removing by indices several elements from a vector From a sorted vector of indices (toRemove), I would like to remove from another vector (v) the elements at these indices. Note that I need to preserve the order of the remaining elements in v. toRemove can be modified at will however.

An easy way to do it would be to start with the last element of toRemove and remove them sequentially. However, that would require copying elements at the end of the vector several times which is slow when the vector is large.

Here is an alternative using the erase-remove idiom:

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;string&gt;
#include &lt;algorithm&gt;

template &lt;typename INT, typename T&gt; // INT could be int, unsigned int, char, size_t, etc...
void removeIndicesFromVector(std::vector&lt;T&gt;&amp; v, std::vector&lt;INT&gt;&amp; rm )
{
  // For speed, I am assuming that 'rm' is sorted
  size_t rm_index = 0;
  v.erase(
    std::remove_if(std::begin(v), std::end(v), [&amp;](T&amp; elem)
    {
        if (rm.size() != rm_index &amp;&amp; &amp;elem - &amp;v[0] == rm[rm_index])
        {
           rm_index++;
           return true;
        }
        return false;
    }),
    std::end(v)
  );
}

template &lt;typename T&gt;
void print(std::vector&lt;T&gt; v)
{
    for (size_t i = 0 ; i &lt; v.size();i++)
    {
        std::cout &lt;&lt; v[i] &lt;&lt; " ";
    }
    std::cout &lt;&lt; std::endl;
}

int main()
{
    std::vector&lt;std::string&gt; v = {"Alice", "Smith", "is", "very", "clever", "and", "is", "very", "nice"};
    print(v);
    std::vector&lt;int&gt; toRemove = {1,6};
    removeIndicesFromVector(v,toRemove);
    print(v);

    return 0;
}


The code outputs as expected:



Alice Smith is very clever and is very nice 
Alice is very clever and very nice 


Is there a "better" alternative to my function removeIndicesFromVector?

By "better", I mean faster / better names / cleaner / more standard / one that is as fast but does not assume 'rm' is sorted. If it matters, note that the object that will need to be removed will rarely be any bigger than the std::strings considered here but the vector will be much longer.
That's a worthwhile problem to solve, and a good solution.

Trivial fix: std::size_t is misspelt in a couple of places.

One easy change I'd make is that rm can be const std::vector&lt;INT&gt;&amp;, since we won't be modifying it.  That's helpful, as it allows the reference to bind to an rvalue if we want (test by passing std::move(toRemove)).



It might be worthwhile passing rm as an iterator pair; we can still have an overload that accepts std::vector or other container:

#include &lt;algorithm&gt;
#include &lt;cassert&gt;
#include &lt;vector&gt;

template &lt;typename T, typename Iter&gt;
void removeIndicesFromVector(std::vector&lt;T&gt;&amp; v, Iter begin, Iter end)
    // requires std::is_convertible_v&lt;std::iterator_traits&lt;Iter&gt;::value_type, std::size_t&gt;
{
    assert(std::is_sorted(begin, end));
    auto rm_iter = begin;
    std::size_t current_index = 0;

    const auto pred = [&amp;](const T&amp;){
        // any more to remove?
        if (rm_iter == end) { return false; }
        // is this one specified?
        if (*rm_iter == current_index++) { return ++rm_iter, true; }
        return false;
    };

    v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());
}

template &lt;typename T, typename S&gt;
    // requires std::is_convertible_v&lt;S::value_type, std::size_t&gt;
void removeIndicesFromVector(std::vector&lt;T&gt;&amp; v, const S&amp; rm)
{
    using std::begin;
    using std::end;
    assert(std::is_sorted(begin(rm), end(rm)));
    return removeIndicesFromVector(v, begin(rm), end(rm));
}


I've changed the algorithm here to simply count the elements seen, which must be valid because std::remove_if() accepts input iterators and is specified to invoke the predicate exactly std::distance(first, last) times.

The requires lines are commented out, as I didn't manage to get them working as I'd like - I'd appreciate a comment or edit to fix that.



If we feel generous, we might be willing to accept non-sorted input (with a speed penalty, of course):

#include &lt;algorithm&gt;
#include &lt;vector&gt;

template &lt;typename T, typename Iter&gt;
void removeIndicesFromVector(std::vector&lt;T&gt;&amp; v, Iter begin, Iter end)
    // requires std::is_convertible_v&lt;std::iterator_traits&lt;Iter&gt;::value_type, std::size_t&gt;
{
    std::size_t current_index = 0;

    if (std::is_sorted(begin, end)) {

        // sorted version - advance through begin..end
        auto rm_iter = begin;
        const auto pred = [&amp;](const T&amp;) {
            // any more to remove?
            if (rm_iter != end &amp;&amp; *rm_iter == current_index++) {
                return ++rm_iter, true;
            }
            return false;
        };
        v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());

    } else {

        // unsorted version - search for each index in begin..end
        const auto pred = [&amp;](const T&amp;) {
            return std::find(begin, end, current_index++) != end;
        };
        v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());
    }
}

template &lt;typename T, typename S&gt;
    // requires std::is_convertible_v&lt;S::value_type, std::size_t&gt;
void removeIndicesFromVector(std::vector&lt;T&gt;&amp; v, const S&amp; rm)
{
    using std::begin;
    using std::end;
    return removeIndicesFromVector(v, begin(rm), end(rm));
}




Test of unordered remove:

#include &lt;array&gt;
#include &lt;iostream&gt;
#include &lt;string&gt;

template &lt;typename T&gt;
void print(const std::vector&lt;T&gt;&amp; v)
{
    for (auto const&amp; e: v) {
        std::cout &lt;&lt; e &lt;&lt; " ";
    }
    std::cout &lt;&lt; std::endl;
}

int main()
{
    std::vector v{"Alice", "Smith", "is", "very", "clever",
                  "and", "is", "very", "nice"};
    print(v);
    removeIndicesFromVector(v, std::array{6u,1u});
    print(v);

    return 0;
}