STL“擦除 - 删除”成语：为什么不“调整大小 - 删除”？

人们普遍认为，从std::vector完全删除所需项目的好方法是erase-remove idiom。STL“擦除 - 删除”成语：为什么不“调整大小 - 删除”？

正如上面的链接注意（如本发布之日起），在代码中擦除删除成语是这样的：

int main() 
{ 
    // initialises a vector that holds the numbers from 0-9. 
    std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 

    // erase-remove idiom to completely eliminate the desired items from the vector 
    v.erase(std::remove(std::begin(v), std::end(v), 5), std::end(v)); 
}

我想知道resize-remove成语是否功能和性能等同于erase-remove习语。或者，也许我错过了一些明显的东西？

以下是resize-remove成语等同于上述erase-remove成语吗？

int main() 
{ 
    std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 

    // Is this "resize-remove" approach equivalent to the "erase-remove" idiom? 
    v.resize(std::remove(std::begin(v), std::end(v), 5) - v.begin()); 
}

来源

2014-04-04 Dan Nissenbaum

“resize-remove”是 - 根据定义 - 不是“成语”，因为该短语不被其他人使用...... –

@TonyD这本身就是一个非常强烈的理由，喜欢删除成语。 –

在我看来，有两个原因：

std::remove算法只需要前向迭代器，但是-需要随机访问迭代器。
std::remove的结果表示“容器的新结束”。从逻辑上讲，我们应该抹掉[“容器的新结束”，“容器的旧结束”）。

来源

2014-04-04 10:41:52 ikh

第一个是非常好的一点（尽管它不会影响'std :: vector'）。 –

我觉得erase在erase(first,last)保证first之前没有单元访问或修改，而resize只保证这个在没有重新分配是因为调整大小的。

编辑：为别人指出的那样，这样的重新分配将永远不会发生，所以没有区别

来源

2014-04-04 10:34:08 Pieter

确保将尺寸调整为较小尺寸不会重新分配。 –

更明确地说：'resize'是用'erase'和'insert'来定义的。所以当它擦除时，它与'擦除'具有相同的保证。 –

它等价于std :: vector，但不适用于std :: list或其他容器。不知道是否减法迭代器甚至可以用于std :: list，即使它是，它也是一个O（N）操作。

来源

2014-04-04 10:43:03

这是不可能的。你必须使用'std :: distance'，它是O（N）。 –

然后再次，它是O（N）中的元素删除，再加上它将这些元素缓存。所以实际上它并不可怕。 – MSalters

@ MSalters：这是相反的。元素中的O（N）不能删除。这个成语的整体复杂性不会改变，因为'std :: remove（）'已经是O（N），但在实践中常量也很重要。 –

它应该没有任何区别; resize由insert和erase的条款定义。但通常最好使用标准成语，以便于识别。而当然，删除删除语言将与任何序列容器，而不仅仅是那些支持resize。（所有的标准集装箱似乎支持resize，但似乎并没有成为一个要求。因此，它可能无法使用用户定义的容器，即使他们支持所有所需的操作。）

在性能方面：resize必须做一个额外的测试，以确定它是擦除还是插入，但我无法想象这会产生重大影响。

来源

2014-04-04 10:45:50

'std :: list'上的'resize'还有一个缺点，就是它必须通过迭代O（n）来找到列表的新结尾，而'remove'返回的精确结束迭代器已经被抛弃了计算'X-begin（），这又是O（n）。 –

@ArneMertz：'std :: list'是双向的（双链接）。找到新的结果非常便宜：您只需弹出当前的结尾，直到尺寸合适。新的结尾是最后一个弹出元素的前身。 – MSalters

@ArneMertz我在想这件事。我没想到甚至找不到它，因为它不能有效地实施。（当然，如果它们不是随机访问，你不能直接对迭代器做不同的处理） –

STL“擦除 - 删除”成语：为什么不“调整大小 - 删除”？

回答

相关问题