c++ - 为什么 std::list 有 remove 和 remove_if 函数

Question

为什么 std::list 有 remove 和 remove_if 函数？这似乎与同名算法函数的行为重复。如果 remove 和 remove_if 有意义，为什么不 find 和 find_if？

标签： c++algorithm

Answer 1

这是因为考虑到std::list（或者更准确地说 - 标准强制执行的可能实现）的性质，标准算法在使用std::remove时std::remove_if效率低下。

std::list的实现必须满足一些要求，这基本上迫使它是基于节点的，与指针结构链接。

这种实现有其缺点。例如，它不允许随机访问迭代器，因此std::sort根本不适合它，因为它需要随机访问。这是极端情况。有一些有效的算法可以处理std::list可能实现的特定性质，并且它们在 member 中使用std::list::sort。虽然std::sort 可以使用相同的实现，但其他场景可能会遭受性能损失。

不太极端的情况就是这种remove情况。Standardstd::remove与成员函数（erase-remove idiom）配对erase是处理删除元素的好方法......除非内部实现使这些操作成本高昂。On std::list，std::remove与天真的调用配对erase将平均需要O(n)（其中n等于列表的size）操作。这可以通过利用内部实现来大大简化（在这种情况下 - 可能的实现中的指针操作）。如果您可以直接访问要删除的元素，则此操作将变为O(1).

那么 -std::find和是怎么回事std::find_if？问题是没有替代方案std::list可以从其内部实施中受益。可能有一个成员findand find_if，但它们与它们的版本几乎相同<algorithm>，因此无需介绍它们。