2

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

PS：对不起，我不够清楚。请忽略这些函数来自 std 命名空间以及它们的具体作用。我只是想了解更多关于 C++ 中的模板/类型特征/重载规则。

4

3 回答 3

2

它不是强制性的，因为它不仅仅是一种优化，它的语义与您对 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 &);
于 2013-04-17T14:52:20.377 回答
1

list::remove或者list::erase单独做你所看到的擦除/删除向量的习语。

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

于 2013-04-17T14:46:36.087 回答
0

您收到的建议很好，但并不普遍。例如，这对 有好处std::vector，但对于std::list因为std::list::erase()并且std::list::remove()已经做了正确的事情而完全没有必要。它们会执行您要求的所有指针魔术，std::vector::erase()但由于其内部存储不同，因此无法执行某些操作。这就是为什么std::remove()不专门用于std::list: 的原因，因为在这种情况下不需要使用它。

于 2013-04-17T14:50:12.327 回答