[What] c++ 泛型算法

学习书籍:

这是我第一次接触泛型算法,既羞愧又激动……

标准库容器所提供的操作集合很小,因为有泛型算法可用于不同类型的容器和不同类型的元素。

泛型算法:

  • 算法:实现了经典算法的公共接口
  • 泛型:用于不同类型的元素和多种容器类型

概述

大多数算法都定义在头文件 algorithm 中,标准库还在头文件 numeric 中定义了一组数值泛型算法。

这些算法的操作接口并不是容器,而是由两个迭代器指定的一个元素的范围来操作。

  • 因为使用迭代器相关的操作可以抽象化元素的类型
  • 由于仅使用迭代器,所以 算法可能改变容器中保存的元素的值,也可能在容器内移动元素,但永远不会直接添加或删除元素

比如使用 find 来寻找容器中是否包含某个特定的值:

//con 可以是 vector<int> 类型,也可以是 vector<string> 、string 等等
auto result = find(con.cbegin(), con.cend(), val);

由于内置数组的指针和容器中迭代器的使用一样,所以也可以用于内置数组:

int *result = find(begin(ia), end(ia), val);
//在 ia[1] 到 ia[3] 中查找是否包含 val
int *result2 = find(ia + 1, ia + 4, val);

初识泛型算法

大部分情况下,标准库提供的算法都是对一个范围内的元素(输入范围)进行操作。

  • 一般前两个参数分别是指向要处理的第一个元素和尾元素之后位置的迭代器

只读算法

只读算法是指:只会读取输入范围内的元素,但不改变元素。

算法的匹配参数决定了序列中元素的类型必须与输入参数匹配,或者能够进行转换:

//使用 accumulate 算法将输入范围内的元素与第三个参数相加

//第三个参数设定了输入范围内的参数为整型,或者可以转换为整型
int sum = accumulate(vec.cbegin(), vec.cend(), 0);

//将 string 相加,这是因为 string 定义了 + 运算符
string sum = accumulate(v.cbegin(), v.cend(), string(""));
//如果第三个参数不显示创建 string,那么类型就是 const char *,但此类型并没有 + 运算,所以会报错
string sum = accumulate(v.cbegin(), v.cend(), "");

写容器元素的算法

如果算法要修改序列中的元素,那么需要确保序列原大小至少不小于算法写的元素数目。

  • 这就如同保证内存不能越界一样

需要理解上面这句话,因为算法操作的是迭代器,也就是指针, 它并没有调用容器的方法来扩展容器的容量

back_inserter

插入迭代器(insert iterator)保证算法有足够的元素空间来容纳输出数据,它是一种向容器中 添加元素 的迭代器。

vector<int> vec;
//使用函数 back_inserter 通过输入的容器创建一个插入迭代器
auto it = back_inserter(vec);
//使用此插入迭代器赋值时,会调用 push_back 将元素值 42 添加到 vec 中
*it = 42;

拷贝算法

拷贝(copy)算法将输入范围中的元素拷贝到目的序列中:

int a1[] = {0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1) / sizeof(*a1)];
//将 a1 的内容拷贝给 a2,返回 a2 尾元素之后的位置
auto ret = copy(begin(a1), end(a1), a2);

重排容器元素的算法

算法库提供了很多排序算法函数便于调用。

定制操作

Last Updated 2020-03-29 日 23:05.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.1.14)