STL std::remove和std::remove_if

• remove 用来移除容器对应迭代器区间[first, last)中，所有值与value相等的元素。相等通过operator== 来比较。
• remove_if 用来移除容器对应迭代器区间[first, last)中，满足判别式p返回true的元素。

函数模板原型

#include  <algorithm>

template< class ForwardIt, class T >
ForwardIt remove( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class UnaryPredicate >
ForwardIt remove_if( ForwardIt first, ForwardIt last, UnaryPredicate p );

1. 对于vector、deque、string等连续内存的顺序容器

• remove 是通过迭代器的指针不断向前移动来“删除”元素的，最终会将值与value相等的元素移动到末尾，返回值就是这些与value相等的第一个元素位置对应的迭代器。remove 并不会改变这些容器的大小，如果要真正删除元素、同时减小容器实际元素个数，应该结合容器的erase成员函数。
• remove_if 原理类似于remove，区别在于前者是通过判别p返回值来删除元素的，后者是通过判断是否与value相等。

remove示例：
“虚假删除”vec中所有值与3相等的元素（容器尺寸不变）：

vector<int> vec({ 1, 2, 3, 3, 9, 10, 3, 4, 5, 8});

auto it = remove(vec.begin(), vec.end(), 3); // vec为"1 2 9 10 4 5 8 4 5 8"
auto d = std::distance(vec.begin(), it); // it到vec.begin的元素个数d为7
cout << *it << endl; // 打印"4"

vec共有3个"3"，所以remove调用后，3个"3"全部移动到vec末尾。也就是说，vec有效内容应该是"1 2 9 10 4 5 8 x x x" ，后面3个x是多余出来的空间，remove返回的迭代器指向第一个"x"。如果要真删除元素，就应该搭配容器的成员函数erase，来删除最后3个元素；或者调用resize重新调整容器大小。

下面用vector::erase 搭配remove，真正删除值为3的元素值（容器尺寸变小）：

vector<int> vec({ 1, 2, 3, 3, 9, 10, 3, 4, 5, 8});
// vector::erase + remove 删去一个元素
cout << vec.size() << endl; // 打印"10"
vec.erase(remove(vec.begin(), vec.end(), 3)); // vec为"1 2 9 10 4 5 8 5 8"，只会真正删除1个元素
cout << vec.size() << endl; // 打印"9"

// vector::erase + remove 删除一个区间
cout << vec.size() << endl; // 打印"10"
vec.erase(remove(vec.begin(), vec.end(), 3), vec.end()); // vec为"1 2 9 10 4 5 8"，删除一个区间元素
cout << vec.size() << endl; // 打印"7"

注意：前一个erase的参数只有一个迭代器，故只会删除迭代器指向的那1个元素；后一个erase的参数是一个区间，故删除若干个元素。

remove_if示例：
只举运用remove_if删除vector中元素值 > 4的例子：

#include <functional>

bool badValue(const int a, const int sz)
{
    return a > sz;
}

using std::placeholders::_1;

vector<int> vec({ 1, 2, 3, 3, 9, 10, 3, 4, 5, 8}); // 10个元素
const int sz = 4;

auto it = remove_if(vec.begin(), vec.end(), std::bind(badValue, _1, sz));  // vec为"1 2 3 3 3 4 3 4 5 8"
// auto it = remove_if(vec.begin(), vec.end(), [sz](const int a) { return a > sz; }); 等价于 上面的语句
cout << *it << endl;  // 打印"3"
cout << std::distance(vec.begin(), it) << endl; // 打印"6"

vec.erase(it, vec.end()); // vec为"1 2 3 3 3 4"
cout << vec.size() << endl; // 打印"6"

同样的，调用remove_if之后，vec会通过移动的方式覆盖掉待删除元素，成为"1 2 3 3 3 4 x x x x"（有4个元素值 > 4）。调用erase后，会真正删除末尾4个元素，减小容器尺寸。

2. 对于list、forward_list等不连续内存的顺序容器

• std::remove, std::remove_if也适用于list、forward_list
• 成员函数remove将移除元素

list::remove示例

list<int> lst = { 1,2,3,4,5,6,5,8,10 }; // 9个元素
cout << lst.size() << endl; // 打印9
for_each(lst.begin(), lst.end(), [](const int x) { cout << x << " "; }); // 1 2 3 4 5 6 5 8 10
cout << endl; // 打印7

lst.remove(5);

cout << lst.size() << endl;
for_each(lst.begin(), lst.end(), [](const int x) { cout << x << " "; }); // 1 2 3 4 6 8 10
cout << endl;

list::remove_if示例

list<int> lst = { 1,2,3,4,5,6,5,8,10 };
cout << lst.size() << endl; // 打印9
for_each(lst.begin(), lst.end(), [](const int x) { cout << x << " "; }); // 1 2 3 4 5 6 5 8 10
cout << endl;

int sz = 5;
lst.remove_if([sz](const int x) { return x >= sz; }); // 删除list中 >= 5的元素

cout << lst.size() << endl; // 打印4
for_each(lst.begin(), lst.end(), [](const int x) { cout << x << " "; }); // 1 2 3 4
cout << endl;

3. 对于std::set、std::map等关联容器

• remove算法、remove_if算法不能应用，因为它们的迭代器类型没有间接引用MoveAssignable（移动赋值）类型（容器中的key不能修改）。
• set、map也没有remove、remove_if成员函数。

如果要删除关联容器中的若干元素，可以先将不打算删除的元素拷贝到一个新容器中，然后再跟当前容器交换（swap）。

map删除元素示例
使用remove_copy_if + std::swap，拷贝并交换容器

map<string, int> m;
m.insert(pair<string, int>("aa", 1));
m["a"] = 1;
m["b"] = 2;
m["c"] = 3;
m["d"] = 4;

map<string, int> tmpm;

cout << m.size() << endl; // 打印5
// (a,1) (aa,1) (b,2) (c,3) (d,4)
for_each(m.begin(), m.end(), [](const pair<string, int>& pr) { cout << "(" << pr.first << "," << pr.second << ") "; });
cout << endl;

int sz = 3;
remove_copy_if(m.begin(), m.end(), inserter(tmpm, tmpm.end()),  [sz](const pair<string, int>& s) {
    return s.second >= sz;
});
m.swap(tmpm);

cout << m.size() << endl; // 打印3
// (a,1) (aa,1) (b,2)
for_each(m.begin(), m.end(), [](const pair<string, int>& pr) { cout << "(" << pr.first << "," << pr.second << ") "; });
cout << endl;

参考：remove | cppreference