c++ - 如何在给定索引列表的情况下从 std::vector 中删除项目

Question

我有一个项目 vector items，以及一个应该从 items 中删除的索引 vector :

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)
// ???

知道每次删除都会影响 indicesToDelete 中的所有其他索引，执行删除的最佳方法是什么？

几个想法是:

1. 将 items 复制到一个新的 vector 中，一次一项，如果索引在 indicesToDelete
中则跳过
2. 迭代 items 并为每次删除，递减 indicesToDelete 中具有更大索引的所有项目。
3. 首先对 indicesToDelete 进行排序，然后迭代 indicesToDelete，并为每次删除递增一个 indexCorrection，该 indexCorrection 从后续索引中减去。

似乎我在想这样一个看似微不足道的任务。有更好的想法吗？

---

编辑这是解决方案，基本上是 #1 的变体，但使用迭代器来定义要复制到结果的 block 。

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

我会选择 1/3，即:对索引 vector 排序，在数据 vector 中创建两个迭代器，一个用于读取，一个用于写入。将写入迭代器初始化为要删除的第一个元素，并将读取迭代器初始化为超出该元素的一个。然后在循环的每个步骤中，将迭代器递增到下一个值(写入)和下一个不被跳过的值(读取)并复制/移动元素。在循环结束时调用 erase 以丢弃最后写入位置之外的元素。

顺便说一句，这是在 STL 的 remove/remove_if 算法中实现的方法，不同之处在于您将条件保存在单独的有序 vector 中。