从给定索引上的向量中删除元素,顺序无关紧要

Question

我所拥有的是一个元素向量,我不关心它们的顺序.比我有N从矢量中删除的元素的索引(每个寻址向量中的唯一位置).我希望删除尽可能快.

我能想出的最好的方法是在集合(订单索引)中存储索引:

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

然后以相反的顺序迭代集合并将索引替换为向量的最后一个元素.

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

然而,我在想是否有更有效的方法来做到这一点,因为使用套装对我来说似乎有点矫枉过正,我希望避免排序.

编辑1: 我们假设我使用向量并在之后对其进行排序.

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

我可以再推一下吗？

EDIT2: 我应该提到矢量最多有10个元素.然而,我的程序中的删除经常发生(数十万次).

Answer 1

set是一个不错的选择。我猜想使用另一个分配器（例如 arena）会产生最大的影响。为什么不首先使用集合而不是元素向量呢？

我看到以下相关变化：

• 创建一个新向量并复制保留的元素，然后交换回来，而不是删除。
  这可以保持索引稳定（与删除不同，删除需要排序或更新索引）。

• 使用与数据长度相同的布尔向量，而不是索引向量。给定“最大 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);
}