这是我的问题,让我说我有一个带有整数的std :: vector.
让我们说它有50,90,40,90,80,60,80.
我知道我需要删除第二,第五和第三个元素.我不一定总是知道要删除的元素的顺序,也不知道有多少.问题是通过擦除元素,这会更改其他元素的索引.因此,我怎么能擦除这些并补偿索引变化.(然后排序然后用偏移线性擦除不是一个选项)
谢谢
Pet*_* G. 29
我提供了几种方法:
1.一种不保留元素原始顺序的快速方法:
将向量的当前最后一个元素分配给要擦除的元素,然后擦除最后一个元素.这将避免大的移动,除了最后一个之外的所有索引将保持不变.如果从后面开始擦除,则所有预先计算的索引都是正确的.
void quickDelete( int idx )
{
vec[idx] = vec.back();
vec.pop_back();
}
我看到这基本上是Klaim指出的擦除删除成语的手工编码版本......
2.一种保留元素原始顺序的较慢方法:
步骤1:标记要删除的所有向量元素,即使用特殊值.这有O(|索引删除|).
第2步:使用删除所有标记的元素v.erase( remove (v.begin(), v.end(), special_value), v.end() );.这有O(| vector v |).
假设索引列表比矢量短,则总运行时间为O(|矢量v |).
3.另一种保留元素原始顺序的较慢方法:
如/sf/answers/244141971/中所述,使用谓词并删除.为了使这个有效并且遵守不"排序然后用偏移量线性擦除"的要求,我的想法是使用哈希表实现谓词并调整存储在哈希表中的索引,因为删除继续返回true,如Klaim建议.
Kla*_*aim 13
使用谓词和算法remove_if,您可以实现您想要的目标:请参阅http://www.cplusplus.com/reference/algorithm/remove_if/
不要忘记删除项目(请参阅删除 - 擦除习语).
您的谓词将只保留每个值的idx以删除并减少每次返回true时保留的所有索引.
也就是说,如果你能够使用移除擦除习惯来删除每个对象,那么只需通过这样做就可以简化你的生活.
向后删除项目.换句话说,首先擦除最高索引,然后擦除下一个最高等等.您不会使任何先前的迭代器或索引无效,因此您可以使用多个擦除调用的明显方法.
虽然Peter G. 在变体一（交换和弹出技术）中的这个答案在您不需要保留顺序时是最快的，但这里是未提及的维持顺序的替代方案。
使用 C++17 和 C++20，可以使用标准算法从向量中删除多个元素。由于 ，运行时间为 O(N * Log(N)) std::stable_partition。没有外部辅助数组，没有过多的复制，一切都就地完成。代码是“一行”：
template <class T>
inline void erase_selected(std::vector<T>& v, const std::vector<int>& selection)
{
v.resize(std::distance(
v.begin(),
std::stable_partition(v.begin(), v.end(),
[&selection, &v](const T& item) {
return !std::binary_search(
selection.begin(),
selection.end(),
static_cast<int>(static_cast<const T*>(&item) - &v[0]));
})));
}
上面的代码假设selection向量是排序的（如果不是这种情况，std::sort显然它可以完成这项工作）。
为了分解这个问题，让我们声明一些临时变量：
// We need an explicit item index of an element
// to see if it should be in the output or not
int itemIndex = 0;
// The checker lambda returns `true` if the element is in `selection`
auto filter = [&itemIndex, &sorted_sel](const T& item) {
return !std::binary_search(
selection.begin(),
selection.end(),
itemIndex++);
};
然后将此检查器 lambda 馈送到std::stable_partition算法，该算法保证对原始（未排列！）数组中的每个元素仅调用此 lambda 一次v。
auto end_of_selected = std::stable_partition(
v.begin(),
v.end(),
filter);
迭代end_of_selected器指向应保留在输出数组中的最后一个元素之后，因此我们现在可以缩小v大小。为了计算元素的数量，我们使用 来从两个迭代器中std::distance获取。size_t
v.resize(std::distance(v.begin(), end_of_selected));
这与顶部的代码不同（它用于itemIndex跟踪数组元素）。为了摆脱itemIndex，我们捕获对源数组的引用v并使用指针算术进行itemIndex内部计算。
多年来（在这个网站和其他类似网站上）已经提出了多种解决方案，但通常它们采用带有条件的多个“原始循环”和一些擦除/插入/push_back 调用。Sean Parent在这次演讲stable_partition中很好地解释了背后的想法。
此链接提供了类似的解决方案（并且它不假设已selection排序 -std::find_if而不是std::binary_search使用），但它还使用了一个辅助（增量）变量，该变量禁用了对较大数组进行并行处理的可能性。
std::stable_partition从 C++17 开始， ( )有一个新的第一个参数ExecutionPolicy，它允许算法自动并行化，进一步减少大数组的运行时间。为了让您相信这种并行化确实有效，Hartmut Kaiser发表了另一场演讲，解释了其内部原理。