c++ - 从给定索引上的 vector 中删除元素，顺序无关紧要

Question

我拥有的是元素的 vector ，我不关心它们的顺序。比起我有 N 索引(每个寻址 vector 中的唯一位置)要从 vector 中删除的元素。我希望尽快删除。

我能想到的最好办法是将索引存储在集合中(顺序索引):

std::set<unsigned int> idxs;
for (int i=0; i<N; ++i)
    idxs.insert(some_index);

并且不是以相反的顺序遍历集合并用 vector 的最后一个元素替换要删除的索引。

std::set<unsigned int>::reverse_iterator rit;
for (rit = idxs.rbegin(); rit != idxs.rend(); ++rit) {
    vec[*rit].swap(vec[vec.size() - 1]);
    vec.resize(vec.size() - 1);
}

但是我在想是否有一些更有效的方法来做到这一点，因为 set 的使用对我来说似乎有点矫枉过正，我很乐意避免排序全部。

编辑 1:让我们假设我使用 vector 并在之后对其进行排序。

std::vector<unsigned int> idxs;
for (int i=0; i<N; ++i)
    idxs.push_back(some_index);
std::sort(idxs.begin(), idxs.end());

我可以进一步插入它吗？

编辑 2:我应该提到 vector 最多有 10 个元素。但是，我的程序中的删除经常发生(数十万次)。

Answer 1

set 是个不错的选择。我猜想使用另一个分配器(例如竞技场)会产生最大的影响。为什么不使用集合而不是元素 vector 作为开始？

我看到以下相关变体:

• 不是删除，而是创建一个新 vector 并复制保留的元素，然后交换回来。
  这使您的索引保持稳定(不像删除，这需要排序或更新索引)。

• 不要使用索引 vector ，而是使用与数据长度相同的 bool vector 。给定“最大 10”的长度，一个位掩码似乎就足够了

所以，大致:

struct Index 
{
   DWORD removeMask = 0;  // or use bit vector for larger N
   void TagForRemove(int idx) { removeMask |= (1<<idx); }
   boll DoRemove(int idx) const { return (removeMask & (1<<idx)) != 0; }
}

// create new vector, or remove, as you like
void ApplyRemoveIndex(vector<T> & v, Index remove)
{
   vector<T> copy;
   copy.reserve(v.size());
   for (i=0..v.size())
     if (!remove.DoRemove(i))
       copy.push_back(v[i]);
   copy.swap(v);
}