2

我之前问过这个问题。我对 std::set 很感兴趣，但我还有另一个令人困惑的场景。

即，对于 T=std::vector 和 T=std::set，以下代码是否合法、可移植的 c++：

template <typename T>
void remove_elements(T& collection, int removal_value)
{
    typename T::iterator new_end = 
        std::remove(collection.begin(), collection.end(), removal_value);
    collection.erase(new_end, collection.end());
}

根据 SGI 参考，set::iterator 和 set::const_iterator 是一样的，所以我不知道这是否合法。但是，无论类型如何，我似乎都找不到另一种方法来获得我需要工作的操作。我可以求助于模板专业化，但是最好不必一开始就专门化。

4

3 回答 3

2

擦除删除习语仅适用于序列容器。对于标准的关联容器，它不起作用，解决方案也不是那么简单。

两种方法：

  1. 用于remove_copy_if将所有值复制到另一个临时容器中，然后将原始容器的内容与临时容器的内容交换。[参考我对相关问题的回答]
  2. 另一种是循环遍历容器元素并在将迭代器传递给擦除时发布增量。

有关更多详细信息，请参阅此 Q：remove_if 等效于 std::map

另外，请参阅第 9 项。在 Scott Meyers 的 Effective STL 中仔细选择擦除选项。

于 2009-05-27T06:43:40.030 回答
1

不，它不适用于std::set，因为 的要求之一std::remove()是迭代器是可变的迭代器，而std::set的迭代器是不可变的。

不幸的是，我没有任何好的替代方案可以建议。您可以做的一件事可能是使用std::find()找到元素出现的迭代器，然后使用.erase()迭代器上的方法（同时存在于std::vectorand中std::set）来擦除它；并继续这样做，直到不再有这样的元素。但这可能非常低效，O(n^2) 而不是 O(n)。

于 2009-05-27T06:32:42.093 回答
0

我认为“正确”的答案是remove_elements为std::set. 由于 set 是有序的并且不包含重复项，因此删除等于removing_value 的元素比用于向量或通用序列要简单得多。你真的不想对所有事情都使用相同的算法，即使你可以：

template <typename T>
void remove_elements(T& collection, const typename T::value_type& removal_value)
{
    typename T::iterator new_end = 
        std::remove(collection.begin(), collection.end(), removal_value);
    collection.erase(new_end, collection.end());
}

template<typename T>
void remove_elements(std::set<T>& collection, const T& removal_value)
{
    collection.erase(removal_value);
}

我有点担心这些是否模棱两可，但在最明显的用例中，它们似乎对我有用。

如果您有除 std::set 之外的其他唯一排序关联容器要担心，这会有点痛苦。您正在进入 std::swap 领域，您实现的每个类都必须提供 remove_elements 的重载。但是由于 set 是您要询问的唯一类，我认为它是您实际使用的唯一棘手的情况，至少目前是这样。如有必要，您可以使用特征根据容器的属性选择正确的算法版本。

于 2009-05-27T11:58:21.773 回答