How to delete items from a std::vector given a list of indices

Question

I have a vector of items items, and a vector of indices that should be deleted from items:

std::vector<T> items;
std::vector<size_t> indicesToDelete;

items.push_back(a);
items.push_back(b);
items.push_back(c);
items.push_back(d);
items.push_back(e);

indicesToDelete.push_back(3);
indicesToDelete.push_back(0);
indicesToDelete.push_back(1);

// given these 2 data structures, I want to remove items so it contains
// only c and e (deleting indices 3, 0, and 1)
// ???

What's the best way to perform the deletion, knowing that with each deletion, it affects all other indices in indicesToDelete?

A couple ideas would be to:

1. Copy items to a new vector one item at a time, skipping if the index is in indicesToDelete
2. Iterate items and for each deletion, decrement all items in indicesToDelete which have a greater index.
3. Sort indicesToDelete first, then iterate indicesToDelete, and for each deletion increment an indexCorrection which gets subtracted from subsequent indices.

All seem like I'm over-thinking such a seemingly trivial task. Any better ideas?

---

Edit Here is the solution, basically a variation of #1 but using iterators to define blocks to copy to the result.

template<typename T>
inline std::vector<T> erase_indices(const std::vector<T>& data, std::vector<size_t>& indicesToDelete/* can't assume copy elision, don't pass-by-value */)
{
    if(indicesToDelete.empty())
        return data;

    std::vector<T> ret;
    ret.reserve(data.size() - indicesToDelete.size());

    std::sort(indicesToDelete.begin(), indicesToDelete.end());

    // new we can assume there is at least 1 element to delete. copy blocks at a time.
    std::vector<T>::const_iterator itBlockBegin = data.begin();
    for(std::vector<size_t>::const_iterator it = indicesToDelete.begin(); it != indicesToDelete.end(); ++ it)
    {
        std::vector<T>::const_iterator itBlockEnd = data.begin() + *it;
        if(itBlockBegin != itBlockEnd)
        {
            std::copy(itBlockBegin, itBlockEnd, std::back_inserter(ret));
        }
        itBlockBegin = itBlockEnd + 1;
    }

    // copy last block.
    if(itBlockBegin != data.end())
    {
        std::copy(itBlockBegin, data.end(), std::back_inserter(ret));
    }

    return ret;
}

Answer 1

I would go for 1/3, that is: order the indices vector, create two iterators into the data vector, one for reading and one for writting. Initialize the writing iterator to the first element to be removed, and the reading iterator to one beyond that one. Then in each step of the loop increment the iterators to the next value (writing) and next value not to be skipped (reading) and copy/move the elements. At the end of the loop call erase to discard the elements beyond the last written to position.

BTW, this is the approach implemented in the remove/remove_if algorithms of the STL with the difference that you maintain the condition in a separate ordered vector.

Answer 2

std::sort() the indicesToDelete in descending order and then delete from the items in a normal for loop. No need to adjust indices then.