按给定的索引从向量中删除元素，顺序无关紧要。

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

然而，我在思考是否有更有效的方法来做这件事情，因为使用集合（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：我应该提到这个向量将有最多10个元素。但是在我的程序中，移除操作非常频繁（数十万次）。

- Jendas

---

通常当您想要对某些东西进行排序时，可以使用std::sort。 - T.C.

我能想到两种方法：1. 迭代并创建一个新的向量，其中包含不在索引列表中的元素。2. 定义一个函数对象并使用 erase_if，调用您的函数对象来比较索引并以此方式删除。 - EdChum

如果这些向量很小，那么从有效索引创建新向量应该是微不足道且快速的。 - EdChum

@EdChum remove_if 可能无法与测试元素的地址（或索引）而不是其值的谓词很好地配合使用，因为它会移动元素。 - T.C.

用户Nim的建议很好，只需跟踪无效条目并在添加新条目时交换这些条目即可。然后您的向量就不必不断重新创建，只需使旧条目无效，并用新条目覆盖旧条目即可。 - EdChum

Answer 1

set是一个不错的选择。我猜使用另一个分配器（例如arena）会产生最大的影响。为什么不一开始就使用set而不是元素的vector呢？

我看到以下相关变化：

• 不要使用remove，创建一个新的vector并复制保留的元素，然后再交换回来。
  这将保持您的索引稳定（与删除不同，后者需要排序或更新索引）。

• 不要使用索引的vector，使用与数据长度相同的bools的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);
}

- peterchen

Answer 2

您可以使用swap/pop_back来删除给定索引处的项目，并使用哈希表跟踪已移动的索引。这在移除数量方面是线性空间和时间。

std::vector<T> vec = ...;
std::vector<unsigned int> idxs;
std::unordered_map<unsigned int, unsigned int> map;

for(auto index : idxs) {
  unsigned int trueIndex = index;
  while (trueIndex >= vec.size()) {
    trueIndex = map[trueIndex];
  }

  // element at index 'vec.size()-1' is being moved to index 'index'   
  map[vec.size()-1] = index; 
  swap(vec[trueIndex], vec[vec.size()-1]);
  vec.pop_back();   
}

- JoeG

---

我并不认为你的代码是有效的，因为你根本没有使用trueIndex。但也许我是错的。 - Jendas

已更正。感谢您的发现。 - JoeG