Erase-remove Idiom 再探

• 下载源代码 - 3.7 KB

最近，我重新阅读了Scott Meyers撰写的经典著作清除-移除习语 (现在已经过时了)，因此我还查阅了2017年出版的另一本STL书籍中关于同一主题的内容。如何从容器中移除元素是一个常见的C++面试题，所以你可能需要认真听讲。

std::vector包含一个erase函数来移除元素。问题是，一旦调用erase，所有迭代器都将失效。这意味着如果std::vector包含多个满足移除条件的元素，开发人员必须从vector::begin()获取新的iterator来重新开始迭代。一个更好的方法是使用清除-移除习语。首先，我们使用STL的remove/remove_if将要移除的元素移动到向量的末尾。STL的remove/remove_if虽然名字叫移除，但它们并不能从std::vector中移除任何元素，因为它们操作的是迭代器，并且不知道底层容器对象。因此，在调用remove/remove_if之后，我们必须调用容器的erase来真正删除元素。

remove以要移除的值作为最后一个参数：任何与该值匹配的元素都会被“移除”。而remove_if以函数对象或lambda表达式作为谓词作为最后一个参数：任何满足谓词的元素都会被“移除”。

  // initializes a vector that holds the numbers from 0-9.
  std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  print(v);
 
  // removes all elements with the value 5
  v.erase( std::remove( v.begin(), v.end(), 5 ), v.end() ); 
  print(v);

  // removes all odd numbers
  v.erase( std::remove_if(v.begin(), v.end(), is_odd), v.end() );
  print(v);

std::remove/std::remove_if Output:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 6 7 8 9
0 2 4 6 8

来自维基百科清除-移除习语

STL remove/remove_if返回新值范围的末尾后迭代器（如果这不是末尾，那么它指向一个未指定的值，迭代器指向这个迭代器和末尾之间的任何值也是如此）。

如果没有元素被“移除”，remove/remove_if将返回v.end()，因此erase调用实际上什么也不做，不会移除任何元素。

v.erase( v.end(), v.end() );

STL remove/remove_if会将剩余的元素移动来填补被移除元素留下的空隙。如果不需要保持元素之间的相对顺序，则可以提高性能。Arthur O'Dwyer 在其著作精通C++17 STL中提到，unstable_remove已经被提议用于未来的标准化，但尚未被添加到STL中。unstable_remove不会移动剩余元素来填补“空洞”，而是将最后一个元素移动到“空洞”处。

namespace my 
{
    template<class BidirIt, class T>
    BidirIt unstable_remove(BidirIt first, BidirIt last, const T& value)
    {
        while (true) 
        {
            // Find the first instance of "value"...
            first = std::find(first, last, value);
            // ...and the last instance of "not value"...
            do 
            {
                if (first == last) 
                    return last;
                --last;
            } 
            while (*last == value);
            // ...and move the latter over top of the former.
            *first = std::move(*last);
            // Rinse and repeat.
            ++first;
        }
    }
    template<class BidirIt, class Pred>
    BidirIt unstable_remove_if(BidirIt first, BidirIt last, Pred predicate)
    {
        while (true) 
        {
            // Find the first instance of "value"...
            first = std::find_if(first, last, predicate);
            // ...and the last instance of "not value"...
            do 
            {
                if (first == last) 
                    return last;
                --last;
            } 
            while (predicate(*last));
            // ...and move the latter over top of the former.
            *first = std::move(*last);
            // Rinse and repeat.
            ++first;
        }
    }
} // namespace my

unstable_remove的用法与std::remove相同，但它们的输出不同。

  // initializes a vector that holds the numbers from 0-9.
  std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  print(v);
 
  // removes all elements with the value 5
  v.erase( my::unstable_remove( v.begin(), v.end(), 5 ), v.end() ); 
  print(v);

  // removes all odd numbers
  v.erase( my::unstable_remove_if(v.begin(), v.end(), is_odd), v.end() );
  print(v);

my::unstable_remove/my::unstable_remove_if Output:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 9 6 7 8
0 8 2 6 4

Arthur在他的书中还指出：

对于std::list容器，std::list::erase可能比std::list上的清除-移除习语快得多。

特别关注点：此习语可与std::unique一起使用，其中连续的相同值将被移动到容器的末尾。清除-移除习语不能用于返回const_iterator的容器（例如，set）。另一个重要的注意事项是，清除-移除习语只能用于包含具有完整值语义的元素的容器，而不会造成资源泄漏，这意味着不应在容器中存储指向已分配内存的原始指针，智能指针是可以的。

参考

• 维基百科清除-移除习语
• Scott Meyers 的《Effective STL》
• Arthur O'Dwyer 的《精通C++17 STL》：此处介绍的unstable_remove来自他的书