如何从向量中删除第一次出现的值？

Question

我试图从向量中获取单个元素并将其推送到向量的后面然后将其删除,这样我就不会在内存中有空的部分.擦除删除习惯用法可以执行此操作,但它会删除特定值的所有实例.我只想删除第一个.

我对标准库算法没有太多经验,我找不到合适的方法(如果有的话)来做到这一点.这是一个例子:

int main() {
    std::vector<int> v{1, 2, 3, 3, 4};

    remove_first(v, 3);

    std::cout << v; // 1, 2, 3, 4
}

那么我该如何从这个向量中删除第一次出现的3？

Answer 1

先找到它,然后删除它:

auto it = std::find(v.begin(),v.end(),3);
// check that there actually is a 3 in our vector
if (it != v.end()) {
  v.erase(it);
}

@Dave:可能不是,实际上.列表与缓存不兼容.你可以*使它们与缓存一起使用,但是在使用向量分析之前,它并不比使用向量更容易. (3认同)
@Dave True，但是数据结构的选择不仅取决于此。如果您大量擦除，这是一个问题，但是通常您只擦除几次，但始终访问索引元素，这很烂。 (2认同)
从列表中擦除是O（1），但在列表中找到元素是O（n）。向量和向量两者的组合查找/擦除操作为O（n）-众所周知，向量的常数趋于*实质上*小于列表的常数。 (2认同)

Answer 2

如果您不关心维护向量中元素的顺序,则可以避免在擦除时复制剩余元素的"尾部":

auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) {
  std::iter_swap(it, v.end() - 1);
  v.erase(v.end() - 1);
}