我拥有的是元素的向量，我不在乎它们的顺序。比我有 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：让我们假设我使用向量并在之后对其进行排序。
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个元素。但是，我的程序中的删除经常发生（数十万次）。
设置是一个不错的选择。我想使用另一个分配器（例如竞技场）会产生最大的影响。为什么不使用集合而不是元素向量来开始呢？
我看到以下相关变化：
>
不是删除，而是创建一个新的矢量并复制保留的元素，然后交换回来。
这样可以保持索引稳定（与删除不同，删除需要对索引进行排序或更新）。
不要使用索引向量，而是使用与数据长度相同的布尔向量。给定“最大 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);
}
您可以使用 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();
}
