C++程序设计——STL算法

算法概述

STL模板库提供了一组适合于多数容器的通用算法，他们包含在<algorithm> 头文件中

• 可以实现查找、排序、遍历并处理元素等基本功能
• 强大之处在于算法独立于底层的数据结构同时独立于容器类型
• 算法仅仅使用迭代器作为接口实现操作与具体容器类型无关
• 多数算法允许用户提供回调函数，通过函数指针或者函数对象实现操作行文上的定制，如自定义排序算法准则等

find()

功能

• 在指定的迭代器区间查找与指定元素相同的第一个元素，其可适配任意容器
• 若是找到该元素返还该元素的迭代器
• 若是未找到该元素返还迭代器区间的末尾

示例

前两个参数指定迭代器的区间，第三个参数指定要查找的元素

int main() {
    vector<int> myVector;
    myVector.push_back(78);
    myVector.push_back(56);
    myVector.push_back(88);
    myVector.push_back(90);
    vector<int>::iterator it = find(myVector.begin(), myVector.end(), 88);
    if (it == myVector.end())
        cout << "Could not find " << endl;
    else
        cout << "Found " << *it << endl;
    return 0;
}

模拟

值得一提的是，find() 函数的底层实现，其实就是用 == 运算符将 val 和 [first,last) 区域内的元素逐个进行比对。这也就意味着，[first,last) 区域内的元素必须支持 == 算符

template <typename T>
iterator find(iterator start, iterator end, T value) {
    for (iterator it = start; it != end; ++it) {
        if (*it == value)
            return it;
    }
    return end;
}
vector<int>::iterator it = find(myVector.begin(), myVector.end(), 88);

find_if()

功能

• 与 find() 算法类似，find_if() 也可以实现元素查找
• find_if() 的前两个参数还是指定迭代器的区间，第三个参数不直接指定要查找的元素，而是提供一个用于匹配的判别式（可以是函数指针、函数对象或者 Lambda 表达式）
• find_if() 对迭代器区间的每个元素调用一次判别式，当返还为 true 是表示匹配到元素并返还其迭代器

示例

bool perfectScore(int num) {
    return num >= 100;
}

vector<int>::iterator it = find_if(myVector.begin(), myVector.end(), perfectScore);
if (it == myVector.end())
    cout << "No perfect scores\n";
else
    cout << "Found a \"perfect\" score of " << *it << endl;

模拟

template <typename T>
iterator find_if(iterator start, iterator end,
                 bool (*fun)(T)) {
    for (iterator it = start; it != end; ++it) {
        if (fun(*it) == true)
            return it;
    }
    return end;
}
vector<int>::iterator it = find(myVector.begin(), myVector.end(), perfectScore);

accumulate()

用法

• 用法一
• 用法二

accumulate() 默认是累加迭代器内的数值，前两个参数指定迭代器的区间，第三个数指定开始累加的初始值

#include <numeric>
#include <vector>
using namespace std;
double arithmeticMean(const vector<int>& nums) {
    double sum = accumulate(nums.begin(), nums.end(), 0);
    return (sum / nums.size());
}

前三个参数同上，还可以传入第四个参数指定具体的累计方法（这个自定义函数需要两个元素），这里定义的是乘积

int product(int num1, int num2) {
    return (num1 * num2);
}

double geometricMean(const vector<int>& nums) {
    double mult = accumulate(nums.begin(), nums.end(), 1, product);
    return (pow(mult, 1.0 / nums.size()));
}

模拟

template <typename T>
T accumulate(iterator start, iterator end, T initial, bool (*fun)(T)) {
    for (iterator it = start; it != end; ++it) {
        initial = fun(*it, initial);
    }
    return initial;
}

double mult = accumulate(nums.begin(), nums.end(), 1, product);

可调用对象（具有回调功能）

可调用对象分类

1. 函数或者函数指针（函数名）
2. 指向成员函数的指针
3. 函数对象：实现了 operator() 的类对象
4. Lambda 表达式：匿名的函数对象

在 STL 的诸多算法中以上可调用函数都可以当做参数传递，根据指定的规则进行比较并返还结果，这就是回调函数

函数对象

概念

• C++ 中可以重载函数调用运算符：operator()

• 在类中定义一个 operator() 方法，该类对象就变成了函数对象，可以将该函数对象当做函数指针使用

• 函数对象也成为仿函数，但是本质还是一个对象，它有公有、私有成员

  因为它可以的标志是重载过的 ()，而且功能和被调用的函数（函数指针）很想，所以可以看做是一个仿函数

函数对象是一个对象，但是使用的形式看起来像函数调用，实际上也执行了函数调用，因而得名

示例

一旦定义了函数对象，即可以将其当成函数进行调用，将对象本身当做一个函数

普通成员函数必须通过对象间接调用成员函数但是函数对象直接对象名调用

class FunctionObject {
   public:
    int operator()(int inParam); //重载()产生函数对象
    int aMethod(int inParam);
};

int FunctionObject::operator()(int inParam) {
    return (inParam * inParam);
}
int FunctionObject::aMethod(int inParam) {
    return (inParam * inParam);
}

int main() {
    int x = 3, xSquared, xSquaredAgain;
    FunctionObject square;
    xSquared = square(x);  //调用函数对象
    xSquaredAgain = square.aMethod(x);  //调用对象成员函数
}

STL 中的函数对象

概述

• 在 STL 中很多算法都提供一个函数指针来指定运算规则，前面将的 find_if() 和 accumulate()

• 可以给需要的地方传入一个函数指针，也可以传入一个函数对象或者 Lambda 表达式

• STL 中提供了多个函数对象类实现基本的运算

函数对象类模板

包含在头文件 <functional> 中，定义了 C++ 标准中多个用于表示函数对象的类模板，包括算法操作、比较操作、逻辑操作以及用于绑定函数对象的实参值的绑定器

一元函数对象类

函数对象类模板	其成员函数 T operator(const T &x)
negate<T>	return -x

函数对象类模板	其成员函数 bool operator(const T &x)
negate<T>	return !x

二元函数对象类

算术运算函数对象类

• STL 预先准备了一些函数对象模板，例如下面的五个算术类函数对象类

  函数对象类模板	其成员函数 T operator(const T &x,const T &y)
  plus<T>	return x+y
  minus<T>	return x-y
  multiplies<T>	return x*y
  divides<T>	return x/y
  modulus<T>	return x%y

• 5 个对象是基于模板的类，真正的运算由包装的数据类型实现

• 示例

  #include <functional>
  #include <iostream>
  using namespace std;
  int main()
  {
  	plus<int> myPlus;
  	int res = myPlus(4, 5);
  	cout << res << endl;
  	return 0;
  }

  myPlus 是用于执行两个整数加法运算的函数对象，把 myPlus 当成函数可以调用两个整数的加法运算

  若是 plus 的模板参数为自定义类型需要实现具体的加法

  double geometricMean(const vector<int>& nums) {
      double mult = accumulate(nums.begin(), nums.end(), 1, multiplies<int>());
      return (pow(mult, 1.0 / nums.size()));
  }

  前两个参数指定累积运算的数据范围，第三个参数指定累计的初始初始值，第四个参数传入一个函数对象指定具体的运算为整数乘法运算，实例化一个对象作为一个 accumulate() 的运算

比较类函数对象类

• 对于用于优先级队列、关联容器提供比较类函数对象，实现排序是的比较运算需要用到比较类函数对象类

函数对象类模板	其成员函数 bool(const T &x,const T &y)
equal_to<T>	return x==y
not_equal_to<T>	return x!=y
greater<T>	return x>y
less<T>	return x<y
greater_equal<T>	return x>=y
less_equal<T>	return x<=y
logical_and<T>	return x &&y
logical_or<T>	return x||y

• 示例

• 示例一
• 示例二

缺省的优先队列使用 less 类对象，实现按照权值从大到小的顺序出列

int main() {
    priority_queue<int> myQueue;
    myQueue.push(3);
    myQueue.push(4);
    myQueue.push(2);
    myQueue.push(1);
    while (!myQueue.empty()) {
        cout << myQueue.top() << endl;
        myQueue.pop();
    }
    return 0;
}

想要优先队列由小到大出列需要传入比较函数，第二个参数指定底层的容器类型为 vector ，第三个参数指定比较用的函数对象类为 greater

int main() {
    priority_queue<int, vector<int>, greater<int> > myQueue;
    myQueue.push(3);
    myQueue.push(4);
    myQueue.push(2);
    myQueue.push(1);
    while (!myQueue.empty()) {
        cout << myQueue.top() << endl;
        myQueue.pop();
    }
    return 0;
}

这里传入的 greater<int> 不同于上述之前讲的传入的函数对象，它末尾没有加 ()，这里我们要清楚一个问题就是模板参数类型的时候不需要加 ()，但函数对象类型的时候就需要加 ()

sort(a,a+n,greater<int>())
functional<int(int,int)> ope;
ope=plus<int>();

加 () 就是因为传入的和指定的都是类型为 int的函数对象。一般情况下都是加 () 的因为我们一般需要的都是函数对象

函数对象适配器

动机

• 在某些算法中，STL 现有的函数对象无法匹配，如 find_if 算法就无法使用现有的函数对象类，因为参数的个数无法匹配（回调函数只能传递一个参数）

  find_if(vec.bedin(),vec.end(),greater_equal<int>()) 这是错的因为 greater_equal 需要传入两个参数，但是现在每次调用只能获得 vec 内部的一个参数

• 函数对象适配器就是用来解决这些问题的，通过函数对象的组合从而穿件满足需求的行为

band1st 和 band2nd

将二元函数（对象）转换为一元函数（对象）并返还，方法是将指定的参数绑定为某个函数对象的第一个参数或者第二个参数从而满足需要两个参数的函数对象，需要注意的是绑定的参数放在适配器中的第二位

• 示例：找出 myVector 内第一个大于或者等于 100 的元素的迭代器

vector<int> myVector;
vector<int>::iterator it = find_if(myVector.begin(), myVector.end(), bind2nd(greater_equal<int>(), 100));

这里用 bind2nd 将指定的 100 作为第二个位置和 myVector 传入的参数绑定在一起满足函数对象 greater_equal 两个参数的要求

not1 和 not2

取反某个函数对象或适配器的运算结果，not1 作用于 1 元的函数对象或者适配器，not2 作用于 2 元的函数对象或者适配器

• 示例：查找 myVector 第一个低于 100 的元素迭代器

vector<int> myVector;
vector<int>::iterator it = find_if(myVector.begin(), myVector.end(), not1(bind2nd(greater_equal<int>(), 100)));

通过 bind2nd 将 greater_equal 适配为只需要一个参数的 1 元操作，not1 再将计算结果取法从而实现小于，这里如果将 greater_eaqul 改用为 less 则不需要用 not1 了

C++ 11 中的 bind

定义

C++ STL bind1st bind2nd bind 的使用

C++ 11 中通过 bind 适配器绑定函数的参数，取代 bind1st 和 bind2nd，通过站位符指定参数绑定还可以调整位置。它不仅适用于二元函数也是用与多元函数

C++ 11 中不建议使用 bind1st 和 bind2nd，建议使用 bind 或者 Lambda 表达式

void func(int num, const string& str) { cout << num << "," << str << endl; }

string str = "abc";
auto f1 = bind(func, std::placeholders::_1, str);
f1(16);

通过 bind 指定将 func 函数绑定为新的函数对象，保存在 f1 中，调用 f1 是将 16（_1标识）绑定为 func 的第一个参数，将 str 作为其第二个参数，再调用 func 函数，_1 等位于 std::placeholder 命名空间

bind 改变参数位置

void func(int num, const string& str) { cout << num << "," << str << endl; }

string str = "abc";
auto f2 = bind(func, std::placeholders::_2, std::placeholders::_1);
f2(16, str);

• 通过调用 bind 将 func 绑定为新的函数对象，保存在 f2 中
• 调用 f2 的时候，将 16（_1标识） 绑定为 func 的第二个参数，将 str（_2标识）作为其第一个参数，再调用 func 函数
• 也就是说 _1，_2 这些标识符都是代表传入的参数的先后顺序，而 bind 可以更改他们在函数对应的形参顺序

bind 应用

vector<int> myVector;
... 
vector<int>::iterator it = find_if(myVector.begin(), myVector.end(),bind(greater_equal<int>(), _1, 100));

查找第一个大于等于 100 的元素前两个参数指定查找的区间范围，遍历区间时每次只能得到一个整数，bind 将当前遍历的整数（_1标识）和 100 绑定为两个参数，作为 greater_equal 的参数从而支持函数对象的使用

适配器用法比较复杂，建议使用Lambda表达式

bind调用成员的方法

void findEmptyString(const vector<string>& strs) {
    auto end = strs.end();
    auto it = find_if(strs.begin(), end, mem_fn(&string::empty));
    if (it != end) {
        ...
    }
}

找出容器中的第一个空串，前两个参数指定迭代器的区间，第三个参数标识调用当前遍历对象（字符串）的 empty 的方法，如果 empty 返回 true 则表示找到。men_fn 也是用来存储指针的容器，调用对象成员的方法

C++11 简单的 Lambda 表达式

C++ 11 除了使用上述采用适配器，还可以使用 C++ 11 引入的 Lambda 表达式来更快捷简便的解决问题

定义

Lambda 表达式被编译器翻译成一个未命名类的未命名对象，并且它是一个可以被调用或者作为参数传递给其他的算法，相当于一个函数对象

[] {
    cout << "Hello lambda" << endl;
}();  //相当于匿名的函数对象

auto mylambda = [] {  //借助 Lambda 表达式生成一个函数对象
    cout << "Hello lambda" << endl;
};
mylambda();

传参和返还值

auto ff = [](int a, int b) -> int {
    return a + b;
}

• Lambda 表达式也可以传递参数
• 通过 -> 指定返回值的数据类型，对于本例中根据 a+b 可以推测出返还值类型为 int，-> 也就可以省略了

捕获本地变量

方法

使用 Lambda 捕获值列表允许我们在 Lambda 表达式的函数体中直接使用这些值，捕获值列表能捕获的值是所有在此作用域可以访问的值，包括这个作用域里面的临时变量，类的可访问成员，全局变量

捕获值的方式分两种：一种是按值捕获，一种是按引用捕获。顾名思义，按值捕获是不改变原有变量的值，按引用捕获是可以在 Lambda 表达式中改变原有变量的值

格式

[](){} 的中括号是用来捕获变量的，无论需不需要都必须有标志着 Lambda 表达式，小括号是用来传递参数的可以省略，花括号是该函数对象内部的实现可以省略

注意的是捕获发生在 Lambda 表达式定义的时候，而不是调用的时候

捕获值列表

主要是两种，一种是传入变量名进行值捕获，在表达式内只能只读访问不可修改，一种是借助 & 进行引用捕获，在表达式内可以访问并且修改

[] 内的内容	作用
空	没有使用任何函数对象参数
=	函数体内可以使用 Lambda 所在作用范围内所有可见的局部变量（包括 Lambda 所在类的 this），并且是值传递方式（相当于编译器自动为我们按值传递了所有局部变量）
&	函数体内可以使用 Lambda 所在作用范围内所有可见的局部变量（包括 Lambda 所在类的 this），并且是引用传递方式（相当于编译器自动为我们按引用传递了所有局部变量）
this	函数体内可以使用 Lambda 所在类中的成员变量
a	将 a 按值进行传递。按值进行传递时，函数体内不能修改传递进来的 a 的拷贝，因为默认情况下函数是 const 的。要修改传递进来的 a 的拷贝，可以在花括号前添加 mutable 修饰符修改函数为可以修改值传递拷贝的局部变量
&a	将 a 按引用进行传递
a,&b	将 a 按值进行传递，b 按引用进行传递
=,&a,&b	除 a 和 b 按引用进行传递外，其他参数都按值进行传递
&,a,b	除 a 和 b 按值进行传递外，其他参数都按引用进行传递

int x = 0;
int y = 42;
auto ff = [x, &y] { //也可以写为 [=,&y]或者[&,x]
    cout << "x :" << x << endl;
    cout << "y :" << y << endl;
    y++;
    //x++; 报错因为 x 是按值传递只读访问不可修改
};

/*
auto ff = [x, &y] mutable{
    cout << "x :" << x << endl;
    cout << "y :" << y << endl;
    y++;
    x++; 对的因为mutable修改了值传递的只可读性
};
*/

ff();
x = y = 77;
ff();
ff();

/*
0 43
0 77
0 78
*/

定义 ff 后捕获的 x 是外部 x 的拷贝，捕获的 y 是外部 y 的引用，执行 x = y = 77 后 ff 内的 x 仍然是 0，而 y 改变为 77

对应的匿名函数对象类

实际上 Lambda 表达式生成的就是一个对象类，类中有一个重载的函数调用运算符，所以说他相当于是函数对象

class Temp {
   private:
    const int x;
    int& y;

   public:
    Temp(int xx, int& yy) : x(xx), y(yy) {}
    void operator() {
        cout <<“x :”<< x << endl;
        cout <<“y :”<< y << endl;
        y++;
    }
};

int x = 0;
int y = 42;
Temp ff(x, y);
x = y = 77;
ff();
ff();

• 外部的 x 以值传递给 ff 内部的 x，初始化完成后两个 x 便脱离的关系且 ff 内部的 x 不能修改
• 外部的 y 以引用传递给 ff 内部的 y，对外部或内部的 y 修改后都互相影响，实际上就是同一个数据

示例

• 示例一
• 示例二
• 示例三
• 示例四

int main() {
    vector<int> vec{1, 3, 5, 2, 6, 9};
    int value = 3;
    int cnt = count_if(vec.begin(), vec.end(), [=](int i) { return i > value; });
    cout << cnt << endl;
    return 0;
}

遍历容器统计大于 3 的元素个数，前两个参数指定迭代器区间，第三个参数通过 Lambda 表达式指定规则，i 为遍历过程中传入的当前元素的拷贝，符合 i>value 的返回 true 并进行计数

int main() {
    vector<int>(10);
    int value = 1;
    generate(vec.begin(), vec.end(), 
    [&value]{
        value *= 2;
        return value;
    };
    cout << cnt << endl;
    return 0;
}

generate 实现按照 2 4 8 ... 填充容器，前两个参数指定迭代器的区间，第三个参数通过 Lambda 表达式指定填充的内容，value 是引用捕获，倍增 value 的值并且以 value 作为填充当前元素的结果

vector<int> myVector;
...
vector<int>::iterator it = find_if(myVector.begin(), myVector.end(),[](int i) { return i >= 100; });

查找第一个大于等于 100 的元素，前两个参数指定查找的区间范围，遍历区间时每次只能得到一个整数，通过 Lambda 表达式指定查找规则，i 为当前遍历元素的拷贝，当该正数符合 i>=100 是返回 true

vector<string> myVector;
... 
vector<string>::iterator it = find_if(myVector.begin(), myVector.end(),[](const string& s) { return s.empty(); });

查找第一个空串，前两个参数指定查找的区间范围，遍历区间时每次只能得到一个整数，通过 Lambda 表达式指定查找规则，s 为当前遍历的字符串常引用时调用字符串的 empty() 判断是否为空串

常用算法

非修改类算法

包括区间内查找、统计计数、遍历处理、比较等运算

查找算法

非排序容器的查找算法

线性时间的复杂度

算法	作用
find()、find_if()	查找满足条件的第一个元素并返还迭代器
adjacent_find()	查找连续的连个相同的元素并返还首个元素的迭代器
find_first_of()	查找第二个序列中任意一个元素在第一个序列中的匹配的位置并返还迭代器
search()	查找第二个序列中元素在第一个序列中出现的第一个位置并返还迭代器，不像 find() 只能查找一个元素
find_end()	search() 的逆序版本
search_n()	查找连续多个元素在第一个序列中匹配的位置并返还匹配的一个元素的迭代器
min_element	查找序列内最小值并返还迭代器
max_element	查找序列内最大值并返还迭代器

C++ 扩展算法

算法	作用
find_if_not()	查找不符合条件的第一个元素并返还迭代器
minmax_element()	返回最大和最小值的迭代器的 pair
all_of()	是否所有元素都符合条件并返还 bool 结果
any_of()	是否任意元素符合条件并返还 bool 结果
none_of()	是否任意元素都不符合条件并返还 bool 结果

非排序容器查找算法示例

int main() {
    int elems[] = {5, 6, 9, 8, 8, 3};
    vector<int> myVector(elems, elems + 6);  //借助数组初始化
    vector<int>::const_iterator it, it2;
    it = min_element(myVector.begin(), myVector.end());
    it2 = max_element(myVector.begin(), myVector.end());
    it = adjacent_find(myVector.begin(), myVector.end());
    if (it != myVector.end())
        cout << *it << endl;
    int targets[] = {8, 9};
    it = find_first_of(myVector.begin(), myVector.end(), targets, targets + 2);  //普通数组的指针可以当做迭代器使用
    if (it != myVector.end())
        cout << "Found one of 8 or 9 : " << *it << endl;
    return 0;
}

find_first_of() 前两个参数指定搜索范围，后两个参数指定匹配的范围，查找位于匹配范围的且在搜索范围的首个元素，那匹配区间的单个元素去匹配，任意一个匹配即可

已排序容器的查找算法

binary_search() 用于折半查找，对数时间复杂度

lower_bound()、upper_bound()、equal_range() 可确定指定元素的区间范围

如果容器自身提供了查找算法那么应该优先使用，使用 STL 通用的查找算法效率不高

已排序容器的查找算法示例

vector<int> myVector{0, 0, 1, 0, 2, 9};

auto begin = myVector.begin();
auto end = myVector.end();

auto it=find_if_not( begin,  end, [](int i){return i == 0; }};

if (all_of(begin, end, [](int i) { return i == 0; })) {
    ...
}

• find_if_not 查找第一个不为 0 的元素
• all_of 算法判断是否所有元素均为 0

统计类算法

算法	作用
accumulate()	累计计算
count()、count_if()	对指定区间按照元素计数，count 统计指定区间等于某个值的元素次数，count_if 统计指定区间符合条件（函数对象）的元素次数

比较类算法

相同容器类型的比较

使用 == < 两个运算符实现各种比较，方式是逐个元素进行比较

不同容器类型之间的比较

两个迭代器区间逐个元素顺序比较

算法	作用
equal()	判断所有对应元素是否相同并返还 bool 结果
mismatch()	返还第二个序列在第一个序列中元素不匹配的元素的迭代器
lexicographical_compare()	判断第一个区间所有元素按照字典顺序是否小于第二个区间对应元素的值并返还bool 结果

遍历算法 for_each()

遍历 myMap 中的每个元素 （pair），对每个 pair 调用自定义的处理函数 printPair

#include <algorithm>
#include <iostream>
#include <map>
using namespace std;

void printPair(const pair<int, int>& elem) {  //输出pair的辅助函数，遍历容器时会逐个元素调用
    cout << elem.first << "->" << elem.second << endl;
}

int main() {
    map<int, int> myMap;
    myMap.insert(make_pair(4, 40));
    myMap.insert(make_pair(5, 50));
    myMap.insert(make_pair(6, 60));
    myMap.insert(make_pair(7, 70));
    myMap.insert(make_pair(8, 80));
    for_each(myMap.begin(), myMap.end(), &printPair);
    return 0;
}

遍历 myMap 中的每个元素 （pair），对每个 pair 通过 Lambda 表达式进行处理

int main() {
    map<int, int> myMap;
    ...
    for_each(myMap.begin(), myMap.end(),[](const pair<int, int>& p) { 
        cout << p.first <<“->”<< p.second << endl; 
    });
    return 0;
}

修改类算法

• 修改类算法从一个区间拷贝数据到另一个区间、移除元素、逆序元素等等
• 都有源区间和目标区间的概念，从源区间读取数据，写入或者修改目标区间
• 源区间和目标区间是可以相同的已实现就地修改
• 对于 map、multimap、set、multiset 容器不作为目标容器区间，因为他们被修改会破坏有序性

transform() 修改算法

transform() 遍历指定的源区间，针对每个元素调用传入的调用函数，产生新的元素并写入目标元素

如果将源区间和目标区间设置为相同的则实现了就地修改的效果

int main() {
    vector<int> myVector;
    ...
    for (auto i : myVector) cout << i << endl;
    transform(myVector.begin(), myVector.end(), myVector.begin(), [](int i) { return i + 100; });
    for (auto i : myVector) cout << i << endl;
    return 0;
}

transform() 前两个参数指定源区间，第三个参数指定目标区间的起始位置，Lambda 通过传入 i，遍历源区间的元素，对每个元素增加 100 后写回目标区间

copy() 和 copy_if() 复制算法

• copy() 算法从一个区间拷贝元素到另一个区间，两个区间不能相同但是可以交叉

• copy() 不是插入元素，只是将源区间元素覆盖目标区间的对应元素

int main() {
    vector<int> vec1, vec2;
    ... 
    vec2.resize(vec1.size());
    copy(vec1.begin(), vec1.end(),vec2.begin());
    for (auto i : vec2) cout << i << endl;
    return 0;
}

resize() 重置 vec2 的大小，以接受 vec1 的数据

copy() 前两个参数指定源区间，目标区间只指定起始位置

int main() {
    vector<int> vec1, vec2;
    ...
    vec2.resize(vec1.size());  //先开一个足够大的空间
    auto end = copy_if(vec1.begin(), vec1.end, vec2.begin(),[](int i) { 
        return i % 2 == 0; 
    });
    vec2.erase(end, vec2.end());  //最后再清除没用到的空间
    for (auto i : vec2) cout << i << endl;
    return 0;
}

将 vec1 中的偶数复制到 vec2 中，前两个参数指定源区间，第三个参数指定目标区间，第四个参数指定判定规则。最后一定要清除 end 和 vec2.end 之间的数据，否则遍历的时候就会出现未知元素

move() 移动算法

int main() {
    vector<Element> vec1, vec2;
    ... 
    vec2.resize(vec1.size());
    move(vec1.begin(), vec1.end(),
         vec2.begin());
    for (auto i : vec2) cout << i << endl;
    return 0;
}

move 将源区间的元素移动到目标区间，源区间不再有效

要求元素必须支持移动赋值运算

replace() 和 replace_if() 替换算法

• 替换算法将指定区间的匹配或者函数对象调用返还 true 的值替换为指定的值
• replace_copy() 和 replace_copy_if() 是它们的变体，不实现就地替换而是将处理结果复制到指定的目标中，不直接修改源中的元素

int main() {
    vector<int> myVector;
    ...
    replace_if(myVector.begin(), myVector.end(), [](int i) { return i < 0; }, 0);
    replace_if(myVector.begin(), myVector.end(), [](int i) { return i > 100; }, 100);
    for_each(myVector.begin(), myVector.end(),[](int i) { cout << i << endl; });
    return 0;
}

replace_if() 前两个参数指定区间，Lambda 指定匹配规则，即小于 0 的，最后一个参数指定替换的新值

实现将小于 0 的替换为 0，将大于 100 的替换为 100

remove() 和 remove_if() 移除算法

• 移除算法用于删除掉指定区间内匹配特定值或函数对象调用返回 true 的元素，remove 类算法并没有真正的删除元素而是将数据拷贝到区间的尾部并返回新的区间尾部的迭代器
• 想要真正的删除数据需要配合 使用erase()
• 其变化形式 remove_copy() 和 remov_copy_if() 组合 copy() 和 remove() 的功能，将源区间满足条件的元素（remove() 指定元素后）复制到目的区间

void removeEmptyStrings(vector<string>& strings) {
    auto it = remove_if(strings.begin(), strings.end(),[](const string& s) { 
        return s.empty(); 
    });
    strings.erase(it, strings.end());
}

remove_if() 前两个参数指定处理范围，Lambda 表达式指定符合移除条件的规则

remove_if() 返回移除后的最新 end() 位置

erase() 删除 it 和容器真正 end() 之间的所有元素

unique() 去重算法

• unique() 删除连续的重复元素只保留一个
• unique() 算法的基本形式，实现就地去重，变化的版本 unique_copy 去重后将结果拷贝到目标区间
• list 容器自身提供了 unique() 算法优先使用

reverse() 翻转算法

• reverse() 算法将区间内的元素逆转顺序
• reverse() 算法的基本版本就是就地翻转，改变当前区间，其变化版本 reverse_copy() 算法将翻转后的结果复制到目标区间

排序类算法

之前的博客有详细的使用讲解，这里不再赘述。见博客链接的 STL 排序

跳转链接，走你

有一个算法没有讲就是用于合并两个有序容器的元素并仍保持有序的算法—— merge()

int main() {
    vector<int> vec1, vec2, vecMerged;
    ... 
    sort(vec1.begin(), vec1.end());
    sort(vec2.begin(), vec2.end());
    vecMerged.resize(vec1.size() + vec2.size());
    merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vecMerged.begin());
}

通过调用 resize() 确保 vecMerged 足够保存合并结束

merge() 前两个参数指定第一个区间（有序），三、四参数指定第二个区间，第五个参数指定目标区间的起始位置

还有逆排序算法 random_shuffle() 用于随机重排区间内的元素实现类似“洗牌”的功能

集合算法

• includes() 判断一个区间是否另一个区间的子集，使用前要求容器必须有序

• set_union、set_interesection()、set_difference()、set_symmetric_difference() 实现标准的并、交、差和异或集合运算，也是在使用前要求容器必须有序

  操作	作用
  并	存在一个任意的区间
  交	存在两个区间，公共部分
  差	存在于第一个区间但是不存在于第二个区间
  异或	只存在一个区间，排除两个区间共存的

• 不能用关联容器保存集合运算结果

int main() {
    vector<int> set1, set2, set3;
    ... 
    sort(set1.begin(), set1.end());
    sort(set2.begin(), set2.end());
    if (includes(set1.begin(), set1.end(),set2.begin(), set2.end()))
        cout << “The second set is a subset of the first\n”;
    ...
}

includes() 前两个参数指定一个区间，后两个参数指定一个区间，判断 set2 是否为 set1 的子集，返回值类型为 bool

int main() {
    ... 
    set3.resize(set1.size() + set2.size());
    vector<int>::iterator newEnd;
    newEnd = set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), set3.begin());
    cout << "The union is : ";
    for (auto i : set3)
        cout << i << endl;
}

resize() 确保 set3 足够存储集合运算结果

set_union() 的前两个参数指定集合 1，三、四参数指定集合 2，最后一个参数指定目标容器的起始位置

迭代器适配器

基本概念

基本迭代器

iterator 和 const_iterator 是遍历容器最基本的迭代器

const_iterator 迭代器虽然很少用但是某些情况下必须使用，例如某个类的常函数要遍历自身的常数据成员容器，此时函数传入的 this 指针是 const 类型，其所有的成员都要求不能被更改，如果我们用普通的 iterator 编译器会报错，所以我们这时候只能用到 const_iterator 去遍历。但是返还时编译器不会检查指针类型，也就是说常函数只要求自身内部没有更改成员的可能就行

迭代器适配器

• STL 还提供了基于基本迭代器之上的适配器，以实现特殊的遍历功能
• reverse_iterator 逆向迭代器
• ostream_iterator、istream_iterator 输入输出流迭代器，将输入输出流当做容器
• insert_iterator 插入迭代器

reverse_iterator

• 通过 reverser_iterator 可实现反向移动遍历，比如执行反向迭代器的 ++ 运算，将会调用底层迭代器的运算
• 容器通常会提供 rbegin() 和 rend() 方法，返回用于逆向迭代器的起始位置和结束位置的下一个位置
  • rbegin() 引用最后一个元素，rend() 引用第一个元素的前一个位置
• 头文件 <iterator>
• 用途：将反向迭代器传给 find() 可以查找最后一个满足条件的元素

int main() {
    vector<int> myVector;
    int num;
    ... vector<int>::iterator it1;
    vector<int>::reverse_iterator it2;
    it1 = find(myVector.begin(), myVector.end(), num);
    it2 = find(myVector.rbegin(), myVector.rend(), num);
    ...
}

it1 为找到的第一个匹配元素，未找到返回 end()，it2 为找到最后一个匹配元素，未找到返回 rend()

ostream_iterator

int main() {
    vector<int> myVector;
    for (int i = 0; i < 10; i++)
        myVector.push_back(i);
    copy(myVector.begin(), myVector.end(),
         ostream_iterator<int>(cout, " "));
    cout << endl;
}

ostream_iterator 的模板参数为 int 表示处理整数，构造函数第一个参数传入 cout表示输出到 cout，第二个参数为字符串表示输出项之间输出的分隔内容

copy() 将容器内元素复制到目标容器（ostream_iterator)，相当于向 cout 输出

insert_iterator

• 使用基本的迭代器，copy 算法只能将源区间元素复制到目标区间，覆盖数据但不能插入

• 通过 insert_iterator ，copy 算法可以实现插入元素功能

• 三种插入迭代器

迭代器类型	作用
insert_iterator	向指定位置插入元素
back_insert_iterator	执行容器的 push_back
front_insert_iterator	执行容器的 push_front

int main() {
    vector<int> vec1, vec2;
    ...
    back_insert_iterator<vector<int> > inserter(vec2);
    remove_copy_if(vec1.begin(), vec1.end(), inserter, [](int i) { return i == 100; });
    copy(vec2.begin(), vec2.end(), ostream_iterator<int>(cout, " "));
    return 0;
}