erase–remove idiom 是C++中一种用于在符合条件的容器中删除特定元素的技巧,应用了标准库重的std::erasestd::remove,它们的用法可以参看文档。当然,最容易想到的做法是遍历容器中每个元素,并删除符合条件的,而用erase-remove,写法更简洁,性能上也更有优势。

对比

下面的例子是删除空数组:

// Using a hand-written loop
std::vector<vector<int> > vv = {{1}, {}, {1,2,3}, {4,5}, {}, {6,7,8,9}};
for (auto iter = vv.cbegin(); iter < vv.cend(); /*iter++*/)
{
    if ((*iter).size() == 0)
        iter = v.erase(iter);
    else ++iter;
}


// Using the erase–remove idiom
std::vector<vector<int> > vv = {{1}, {}, {1,2,3}, {4,5}, {}, {6,7,8,9}};
vv.erase(std::remove(vv.begin(), vv.end(), vector<int>{}), vv.end());

下面的例子是删除奇数:

// Using a hand-written loop
std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for (auto iter = v.cbegin(); iter < v.cend(); /*iter++*/)
{
    if (is_odd(*iter))
    {
        iter = v.erase(iter);
    }
    else
    {
        ++iter;
    }
}

// Using the erase–remove idiom
std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
v.erase(std::remove_if(v.begin(), v.end(), is_odd), v.end());

解释

erase用于从一个集合中删除一个元素,但是对于基于数组的容器,如vector,存储在被删除元素后的所有元素都需要向前移动以避免集合中有一个空位(gap)。在同一容器中多次调用产生了大量移动元素的开销。

removeremove_if并没有从容器删除元素,而是把不“符合”删除标准的元素搬移到容器的前部,并保持这些元素的相对次序。随后调用erase 一次性删除,一次性移动,相比多次删除+移动提高性能。

举例

#include <vector> // the general-purpose vector container
#include <iostream> // cout
#include <algorithm> // remove and remove_if

bool is_odd(int i)
{
    return (i % 2) != 0;
}

void print(const std::vector<int> &vec)
{
    for (const auto& i : vec)
        std::cout << i << ' ';
    std::cout << std::endl;
}

int main()
{
    // initializes a vector that holds the numbers from 1-10.
    std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    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);

    // removes multiples of 4 using lambda
    v.erase(std::remove_if(v.begin(), v.end(), [](int n) { return (n % 4) == 0; }), v.end());
    print(v);

    return 0;
}

/*
Output:
1 2 3 4 5 6 7 8 9 10
1 2 3 4 6 7 8 9 10
2 4 6 8 10
2 6 10
*/

参考

https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Erase-Remove

https://www.freecodecamp.org/news/how-to-remove-elements-from-a-container-in-c/

https://www.codeproject.com/Articles/1227392/Erase-remove-Idiom-Revisited

最后修改:2022 年 02 月 21 日
如果觉得我的文章对你有用,请随意赞赏