C++ 各个STL容器删除元素的最佳方法

假设容器为 Container<int> c;, 其中Container为vector, deque, string, list, map, set等

删除指定值

对于 vector、deque、string

最佳方法

c.erase(remove(c.begin(), c.end(), 1963), c.end());

这些容器都是连续内存的容器，删除一个会发生平移操作，由于容器中可能有多个指定值的元素，上述删除方法可以只移动一次，然后把指定值全删除掉

例子

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <list>
#include <algorithm>

using namespace std;

// erase
int main()
{
    // vector
    vector<int> nums = { 2, 4, 3, 2, 4, 7, 3, 7 };
    for (int num : nums) {
        cout << num << "\t";
    }
    cout << endl;
    nums.erase(remove(nums.begin(), nums.end(), 4), nums.end());
    for (int num : nums) {
        cout << num << "\t";
    }
    cout << endl << endl;


    // deque
    deque<int> dq = { 2, 4, 3, 2, 4, 7, 3, 7 };
    for (int num : dq) {
        cout << num << "\t";
    }
    cout << endl;
    dq.erase(remove(dq.begin(), dq.end(), 4), dq.end());
    for (int num : dq) {
        cout << num << "\t";
    }
    cout << endl << endl;

    // string
    string s = "24324737";
    cout << s << endl;
    s.erase(remove(s.begin(), s.end(), '4'), s.end());
    cout << s << endl << endl;
    
    system("pause");
    return 0;
}

效果如下：

对于 list

最佳方法

c.remove(1963);

因为list是链表形式的，直接remove就很高效

例子

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

// erase
int main()
{
    // list
    list<int> l;
    l.push_back(2); l.push_back(4); l.push_back(3); l.push_back(2);
    l.push_back(4); l.push_back(7); l.push_back(3); l.push_back(7);
    for (int num : l) {
        cout << num << "\t";
    }
    cout << endl;
    l.remove(4);
    for (int num : l) {
        cout << num << "\t";
    }
    cout << endl << endl;

    system("pause");
    return 0;
}

对于 map/multimap、set/multiset 关联型容器

最佳方法

c.erase(1963);

使用成员函数erase(),因为关联型容器底层都是平衡二叉树结构

例子

#include <algorithm>
#include <map>
#include <set>

using namespace std;

// erase
int main()
{
    // multimap
    multimap<int, bool> m;
    m.insert(make_pair(2, true));  m.insert(make_pair(4, true));  m.insert(make_pair(3, true));
    m.insert(make_pair(2, true));  m.insert(make_pair(4, true));  m.insert(make_pair(7, true));
    m.insert(make_pair(3, true));  m.insert(make_pair(7, true));

    for (auto e : m) {
        cout << "(" << e.first << "," << e.second << ")" << "\t";
    }
    cout << endl;
    m.erase(4);
    for (pair<int, bool> e : m) {
        cout << "(" << e.first << "," << e.second << ")" << "\t";
    }
    cout << endl << endl;

    // set
    multiset<int> s;
    s.insert(2); s.insert(4); s.insert(3); s.insert(2);
    s.insert(4); s.insert(7); s.insert(3); s.insert(7);
    for (int num : s) {
        cout << num << "\t";
    }
    cout << endl;
    s.erase(4);
    for (int num : s) {
        cout << num << "\t";
    }
    cout << endl << endl;

    system("pause");
    return 0;
}

效果如下:

参考资料

《Effective STL》 Scott Meyers