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

Question

我曾经了解到从容器中删除元素的一般方法是通过删除-删除-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);

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