泛型算法

generic algorithm

1. 标准库容器定义的操作集合比较小, 容器的功能比较少
   
   标准库提供了一组算法，这些算法是通用的，或称作泛型，可用于不同类型的容器和不同类型的元素
   
2. 算法并不直接操作容器，而是遍历给定范围的元素
   
3. 算法永远不会执行容器的操作
   
4. 算法运行在迭代器之上，执行迭代器的操作
   
   或者执行与迭代器操作兼容的指针操作
   
5. 算法永远不会改变底层容器的大小
   
6. 算法可能改变容器中保存的元素的值，也可能移动元素，但永远不会直接添加或删除元素
   
   因此, 容器本身只提供较少的功能; 而这些功能中包含了增删元素的操作
   
7. 大多数算法提供了一种方法，允许我们使用自定义的操作来代替默认的运算符
   

泛型算法与迭代器

标准库定义了大约100个类型无关的、对序列进行操作的算法

任何算法的最基本的特性是它要求其迭代器提供哪些操作

C++标准指明了泛型算法每个迭代器参数的最小类别

序列可以由标准库容器的元素组成，可以是一个内置数组, 或者通过读写一个流来生成

算法通过迭代器操作序列, 实现无关元素类型

多数算法的前两个形参是使用迭代器表示的输入序列; 额外的迭代器参数可以是一个表示输出范围的输出迭代器, 或者表示第二个输入序列的两个迭代器, 或者指向第二个输入序列首元素的迭代器

泛型算法形参模板

1. 接受一个输入序列
   

   Copy1alg(beg, end, other_args);

2. 接受一个输入序列和一个输出序列
   

   Copy1alg(beg, end, dest, other_args);

3. 接受两个输入序列: 第二个输入序列使用迭代器范围给出
   

   Copy1alg(beg, end, beg2, other_args);

4. 接受两个输入序列: 第二个输入序列只给出指向首元素的迭代器
   

   Copy1alg(beg, end, beg2, end2, other_args);

接受一个输入序列的算法

find算法接受一对输入迭代器

查找与给定值相等的(第一个)元素. 如果存在, 返回指向该元素的迭代器; 返回e

Copy1find(b, e, val);

使用了元素类型的相等运算符

要求通过迭代器访问元素，递增迭代器，比较两个迭代器是否相等

示例

Copy1int val = 42;
2
3auto result = find(vec.cbegin(), vec.cend(), val);
4
5cout << "The value " << val << (result == vec.cend()) ? " is not present" : " is present") << endl;

Copy1string val = "a value";
2
3auto result = find(lst.cbegin(), lst.cend(), val);

sort算法接受一对随机访问迭代器

要求读、写和随机访问元素的能力

链表不支持sort算法

accumulate算法接受一对输入迭代器

replace算法接受一对前向迭代器

使用输出迭代器表示输出序列的算法

假定目的容器空间足够容纳将要写入的元素

• 如果dest指向容器中的元素, 假定元素存在, 对其进行覆写
  
• 如果dest是插入迭代器, 无论如何容器空间都是足够的; 往容器中添加元素
  
• 如果dest是输出流迭代器, 同样不用担心空间是否足够, 可以往输出流写入任意多个元素
  

Copy1alg(beg, end, dest, other_args);

copy的第三个参数是输出迭代器

replace_copy接受一对前向迭代器表示输入序列, 接受一个输出迭代器表示输出序列

接受第二个输入序列的算法

1. 第二个输入序列使用迭代器范围给出
   
2. 第二个输入序列只给出指向首元素的迭代器: 假定第二个输入序列元素个数不小于第一个输入序列