在给定索引列表的情况下如何从std :: vector删除项目 [英] How to delete items from a std::vector given a list of indices

问题描述

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

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

知道删除操作会影响 indicesToDelete 中的所有其他索引，执行删除的最佳方法是什么?

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

一些想法是:

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

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?

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

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;
}

推荐答案

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

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.

顺便说一句，这是在STL的 remove/remove_if 算法中实现的方法，区别在于您将条件保持在单独的有序向量中.

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.

这篇关于在给定索引列表的情况下如何从std :: vector删除项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！