如何为std::list重载std::remove？

Question

我曾经了解到，从容器中擦除元素的一般方法是通过erase-remove-idiom。但我惊讶地发现，至少g++的STL实现没有为std::list重载std::remove()，因为在这种情况下，通过指针操作进行重新排序可以节省大量的对象分配。

C++标准不要求这样的优化有什么原因吗？但我的主要问题是如何重载std::remove() (它不一定要在g++之外可移植)，所以我可以提供一个使用list::splice()/list::merge()的实现。我尝试了几个签名，但最多只能得到一个歧义错误，例如：

template <typename T>
typename std::list<T>::iterator
remove(typename std::list<T>::iterator first,
       typename std::list<T>::iterator last, const T &v);

附言:很抱歉我说得不够清楚。请忽略这些函数来自std名称空间，以及它们具体做了什么。我只想更多地了解C++中的模板/排版/重载规则。

Answer 1

它不是强制的，因为它不仅仅是一个优化，它具有不同于您对序列容器的期望的语义：

std::list<int> l;
l.push_back(1);
l.push_back(2);

std::list<int>::iterator one = l.begin();
std::list<int>::iterator two = l.end(); --two;

if (something) {
    l.erase(remove(l.begin(), l.end(), 1), l.end());
    // one is still valid and *one == 2, two has been invalidated
} else {
    l.remove(1);
    // two is still valid and *two == 2, one has been invalidated
}

关于实际的问题: ISWYM，我被困在如何编写一对函数模板，以便其中一个匹配任意迭代器，另一个匹配列表迭代器，而不会有歧义。

请注意，在标准中实际上并不能保证list<T>::iterator是与some_other_container<T>::iterator不同的类型。因此，尽管在实践中您希望每个容器都有自己的迭代器，但原则上这种方法是有缺陷的，因为您建议将重载放在std中。您不能单独使用迭代器来对其相应的容器进行“结构化”更改。

你可以在没有歧义的情况下做到这一点：

template <typename Container>
void erase_all(Container &, const typename Container::value_type &);

template <typename T>
void erase_all(std::list<T> &, const T &);

Answer 2

仅list::remove或list::erase就可以完成您已经看到的擦除/删除习惯用法对向量所做的事情。

值或谓词的remove。用于单个迭代器或范围的erase。

Answer 3

你收到的建议是好的，但不是通用的。例如，它对std::vector有好处，但对std::list来说完全没有必要，因为std::list::erase()和std::list::remove()已经做了正确的事情。它们可以完成你所请求的所有指针魔术，这是std::vector::erase()无法做到的，因为它的内部存储是不同的。这就是为什么std::remove()不专门用于std::list的原因:因为在这种情况下不需要使用它。