进一步的 std::set 问题

Question

我之前问过这个问题。 我对 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 是相同的，所以我不知道如果这是合法的。 但是，我似乎无法找到另一种方法来获得我需要的操作，无论类型如何。 我可以诉诸模板专门化，但是最好不必首先专门化。

Answer 1

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

两种方法：

1. 使用remove_copy_if复制所有
   值到另一个临时值
   容器，然后交换内容
   原来的容器与那些
   临时的一个。 [请参阅我对相关问题的答案]
2. 另一个是循环步行
   当您将迭代器传递给擦除时，容器元素和 post 会递增迭代器。

有关更多详细信息，请参阅此问题： remove_if 相当于 std::map

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

Answer 2

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

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

Answer 3

我认为“正确”的答案是为 std::set 重载 remove_elements 。 由于集合是有序的并且不包含重复项，因此删除等于removal_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 是您询问的唯一类，我认为这是您实际使用的唯一棘手的情况，至少目前是这样。 如有必要，您可以使用特征根据容器的属性选择正确的算法版本。