c++ - 如何为 std::list 重载 std::remove ？

Question

我曾经了解到从容器中删除元素的一般方法是通过删除删除惯用语。但我惊讶地发现至少 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);

P.S.:很抱歉我说得不够清楚。请忽略这些函数来自 std 命名空间以及它们的具体用途。我只是想了解更多关于 C++ 中的模板/类型特征/重载规则。

Answer 1

这不是强制性的，因为它不仅仅是一种优化，它的语义与您对 Sequence 容器的期望不同:

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 &);