在保留原始顺序的同时删除/删除多个std::vector元素的最有效方法?

在 <algorithm> remove_if function 它将所有未移除的值挤压到前面以保持顺序。如果这200个元素可以完全由值决定,而不是由索引决定,那么这个方法是可行的。

这基本上就是您所链接到的擦除删除习惯用法。 如果删除 可以保证执行O(N)比较(最多为O(N)复制),这比排序(O(N logn))更有效,尽管如果索引是根据值确定的,则最后一个选项实际上不需要排序(复制时只需反向扫描)。

然而,使用 如果删除 什么 怎样 )去做。

如何循环遍历向量,对于每个需要删除的元素,将下一个不需要删除的元素复制到该位置。当你到达终点时,截短它。

int last = 0;
for(int i=0; i<vec.size(); ++i, ++last)
{
   while(needs_to_be_removed(i))
      ++i;
   if(i >= vec.size()) break;

   vec[last] = vec[i];   
}

vec.resize(last);

首先,不要打电话 erase

我想我要做的第一件事应该和你现在的代码相似:

• 对索引排序
• 创建大小为n-m的新向量
• 在原始向量上迭代,复制 indexes[0] 元素,跳过元素,然后复制 indexes[1] - indexes[0] - 1 元素、跳过元素等。
• swap 新向量的原始向量。

remove_copy_if 以及一个包含状态的谓词(计算它复制了多少个项,以及它在排序的索引列表中的距离), 但是 由于极其乏味和模糊的原因,这并不能保证工作(具有可变状态的算法谓词是有问题的,似乎大家一致认为标准不能保证 同一份 在整个算法中都使用了。所以我真的不建议尝试,但是记住你写的基本上是 删除副本如果

你可以使用 back_inserter 而不是预先设定向量的大小,尽管您可能仍然会提前保留空间。

删除副本如果 remove_if ,然后复制到矢量中的较早点。那么 擦除 resize 最后。我不会担心 O(m log m) 如果删除 可能是,也可能不是 O(1) m .]

使第二个容器成为一个映射,以便它自动为您保持索引排序。

回应评论

维护一个映射的代价与维护另一个结构(列表或向量)然后对其进行排序是最坏的情况。如果你已经这样做了,你最好把它作为一张地图。抱怨地图的开销和排序列表的开销是没有意义的。

对于我建议算法的性能,如果m是要删除的元素数,n是元素总数,则结果是O(n-m)。

当然,这主要是在幽默你试图用一个向量优化。

2-不要维护第二个数据结构,而是在容器中标记需要直接删除的元素。一个简单的方法是使用容器<T>使用容器<std::pair<T,char>,并使用char来跟踪元素状态。

如果执行1和2,则完全删除所有复制并获得更高效的实现。

什么元素?也许我是认真对待你的文章,但如果你有一个1000个元素的向量,为什么不标记那些不再有效的元素,并在第一时间消除。显然我在这里假设你的元素不需要太多的内存。

我提这个只是因为你好像很关心速度。如果已经给出的建议没有奏效,也许这个想法值得一想!从本质上讲,一开始就不做手术会加快速度。

如果您有一组(例如无序的)要删除的索引,可以使用:

template <typename Type>
void erase_indices(
        const std::unordered_set<size_t>& indices_to_erase,
        std::vector<Type>& vec) {
    std::vector<bool> erase_index(vec.size(), false);
    for (const size_t i: indices_to_erase) {
        erase_index[i] = true;
    }
    std::vector<bool>::const_iterator it_to_erase = erase_index.cbegin();
    typename std::vector<Type>::iterator it_erase_from = std::remove_if(
        vec.begin(), vec.end(),
        [&it_to_erase](const Type&) -> bool {
          return *it_to_erase++ == true;
        }
    );
    vec.erase(it_erase_from, vec.end());
}

这是我想到的最快的解决办法。你需要 C++ 11 不过。删除索引2和5处的元素的用法示例:

constexpr size_t num = 10u;
std::vector<int> vec(num);
std::iota(vec.begin(), vec.end(), 0);

std::unordered_set<size_t> indices_to_erase;
indices_to_erase.insert(2u);
indices_to_erase.insert(5u);

erase_indices(indices_to_erase, vec);

0 1 2 3 4 5 6 7 8 9

之后:

0 1 3 4 6 7 8 9

编辑: 如果希望对保持索引擦除的容器类型更灵活:

template <typename Type, typename Container>
void erase_indices(
        const Container& indices_to_erase,
        std::vector<Type>& vec) {
    typedef typename Container::value_type IndexType;
    static_assert(std::is_same<IndexType, std::size_t>::value,
        "Indices to be erased have to be of type std::size_t");
    std::vector<bool> erase_index(vec.size(), false);
    for (const IndexType idx_erase: indices_to_erase) {
        erase_index[idx_erase] = true;
    }
    std::vector<bool>::const_iterator it_to_erase = erase_index.cbegin();
    typename std::vector<Type>::iterator it_erase_from = std::remove_if(
        vec.begin(), vec.end(),
        [&it_to_erase](const Type&) -> bool {
          return *it_to_erase++ == true;
        }
    );
    vec.erase(it_erase_from, vec.end());
}

现在您可以使用 Containers Library 提供要删除的索引,只要 value_type 那个集装箱的 std::size_t . 用法不变。

我写了一个函数,基于Benjamin Lindley的答案 https://stackoverflow.com/a/4115582/2835054

#include <iostream>
#include <algorithm>
#include <vector>

template <typename elementType, typename indexType>
void remove_multiple_elements_from_vector(std::vector<elementType> &vector,
std::vector<indexType> &indexes)
{
    // 1. indexType is any integer.
    // 2. elementType is any type.
    // 3. Indexes should be unique.
    // 4. The largest index inside indexes shouldn't be larger than
    //    the largetst index in the vector.
    // 5. Indexes should be sorted in ascending order
    //    (it is done inside function).
    std::sort(indexes.begin(), indexes.end());
    indexType currentIndexInIndexesVector = 0;
    indexType last = 0;
    for(indexType i=0; i<vector.size(); ++i, ++last)
    {
       while(indexes[currentIndexInIndexesVector] == i)
       {
          ++i;
          ++currentIndexInIndexesVector;
       }
       if(i >= vector.size()) break;

       vector[last] = vector[i];   
    }

    vector.resize(last);
}


int main()
{
    std::vector<int> vector = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> indexes = {0, 10, 5};

    for (auto &vectorElement : vector)
    {
        std::cout << vectorElement << " ";
    }    
    std::cout << "\n";

    remove_multiple_elements_from_vector<int, int>(vector, indexes);

    for (auto &vectorElement : vector)
    {
        std::cout << vectorElement << " ";
    }
}