STL-常用算法

目录

5.1常用遍历算法

5.1.1 for_each

5.1.2 transform

5.2常用查找算法

5.2.1 find

5.2.2 find if

5.2.3 adjacent_find

5.2.4 binary_search

5.2.5 count

5.2.6 count_if

5.3常用排序算法

5.3.1 sort

5.3.2 random shuffle

5.3.3 merge

5.3.4 reverse

5.4常用拷贝和替换算法

5.4.1 copy

5.4.2 replace

5.4.3 replace_if

5.4.4 sap

5.5常用算术生成算法

5.5.1 aumulate

5.5.2 fill

5.6 常用集合算法

5.6.1 set intersection

5.6.2 set_union

5.6.3 set difference

---

 

概述:

算法主要是由头文件 组成

是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历操作、复制、修改等等

体积很小，只包括几个在序列上面进行简单数学运算的模板函数

定义了一些模板类,用以声明函数对象

5.1常用遍历算法

学习目标:

掌握常用的遍历算法

算法简介:

for_each //遍历容器

transform //搬运容器到另一个容器中

5.1.1 for_each

功能描述:

实现遍历容器

函数原型:

for_each(iterator beg, iterator end,_func);

//遍历算法 遍历容器元素

//beg开始迭代器

//end结束迭代器

//_func 函数或者函数对象

示例:

for_each在实际开发中是最常用遍历算法,需要熟练掌握

5.1.2 transform

功能描述:

搬运容器到另一个容器中

函数原型:

transform(iterator beg1, iterator end1, iterator beg2,_func);

//beg1 源容器开始迭代器

//end1 源容器结束迭代器

//beg2 目标容器开始迭代器

//_func 函数或者函数对象

示例

 

搬运的目标容器必须要提前开辟空间,否则无法正常搬运

5.2常用查找算法

学习目标:

掌握常用的查找算法

算法简介:

find //查找元素

find_if //按条件查找元素

adjacent_find //查找相邻重复元素

binary_search //二分查找法

count //统计元素个数

count if //按条件统计元素个数

5.2.1 find

功能描述:

查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()

函数原型:

find(iterator beg, iterator end, value);

// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

//beg开始迭代器

//end 结束迭代器

//value 查找的元素

示例

 

利用find可以在容器中找指定的元素,返回值是迭代器

5.2.2 find if

功能描述:

按条件查找元素

函数原型:

find if(iterator beg, iterator end,_Pred);

// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

//beg开始迭代器

//end结束迭代器

//_Pred函数或者谓词(返回bool类型的仿函数)

示例:

 

5.2.3 adjacent_find

功能描述:

查找相邻重复元素

函数原型:

adjacent _find(iterator beg, iterator end);

//查找相邻重复元素,返回相邻元素的第一个位置的迭代器

//beg开始迭代器

//end结束迭代器

示例:

面试题中如果出现查找相邻重复元素,记得用STL中的adjacent_find算法

5.2.4 binary_search

功能描述:

查找指定元素是否存在

函数原型:

bool binary_search(iterator beg, iterator end, value);

//查找指定的元素,查到返回true否则false

//注意:在无序序列中不可用

//beg开始迭代器

//end 结束迭代器

//value查找的元素

示例

二分查找法查找效率很高,值得注意的是查找的容器中元素必须是有序序列

5.2.5 count

功能描述:

统计元素个数

函数原型:

count(iterator beg, iterator end, value);

//统计元素出现次数

//beg开始迭代器

// end 结束迭代器

//vajue统计的元素

示例

 

 统计自定义数据类型时候，需要配合重载 operator==

5.2.6 count_if

功能描述

按条件统计元素个数

函数原型

count_if(iterator beg, iterator end, Pred);

//按条件统计元素出现次数

//beg开始迭代器

//end结束迭代器

//_Pred谓词

示例

 

 

 

5.3常用排序算法

学习目标:

掌握常用的排序算法

算法简介:

sort //对容器内元素进行排序

random shuffle //洗牌指定范围内的元素随机调整次序

merge //容器元素合并，并存储到另一容器中

reverse // 反转指定范围的元素

5.3.1 sort

功能描述:

对容器内元素进行排序

函数原型:

sort(iterator beg, iterator end,_Pred);

//按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

// beg 开始迭代器

// end 结束迭代器

// _Pred 谓词

示例

sort属于开发中最常用的算法之一,需熟练掌握

5.3.2 random shuffle

功能描述:

洗牌 指定范围内的元素随机调整次序

函数原型:

random _shuffle(iterator beg, iterator end);

//指定范围内的元素随机调整次序

// beg开始迭代器

//end结束迭代器

示例:

 

 

:random_shuffle洗牌算法比较实用,使用时记得加随机数种子

5.3.3 merge

功能描述:

两个容器元素合并，并存储到另一容器中

函数原型:

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

//容器元素合并，并存储到另一容器中

//注意:两个容器必须是有序的

//beg1 容器1开始迭代器

//end1 容器1结束迭代器

//beg2 容器2开始迭代器

//end2 容器2结束迭代器

//dest 目标容器开始迭代器

示例:

merge合并的两个容器必须是有序序列

5.3.4 reverse

功能描述:

将容器内元素进行反转

函数原型:

reverse(iterator beg, iterator end);

//反转指定范围的元素

// beg开始迭代器

//end结束迭代器

示例

reverse反转区间内元素，面试题可能涉及到

5.4常用拷贝和替换算法

学习目标:

掌握常用的拷贝和替换算法

算法简介:

copy //容器内指定范围的元素拷贝到另一容器中

replace //将容器内指定范围的旧元素修改为新元素

replace if //容器内指定范围满足条件的元素替换为新元素

sap //互换两个容器的元素

5.4.1 copy

功能描述:

容器内指定范围的元素拷贝到另一容器中

函数原型:

copy(iterator beg, iterator end, iterator dest);

//按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

// beg开始迭代器

// end结束迭代器

// dest 目标起始迭代器

示例

利用copy算法在拷贝时，目标容器记得提前开辟空间

5.4.2 replace

功能描述:

将容器内指定范围的旧元素修改为新元素

函数原型:

replace(iterator beg, iterator end, oldvalue, nevalue);

// 将区间内旧元素替换成新元素

// beg开始迭代器

// end 结束迭代器

// oldvalue 旧元素

// nevalue新元素

示例:

replace会替换区间内满足条件的元素

5.4.3 replace_if

功能描述:

将区间内满足条件的元素，替换成指定元素

函数原型:

replace if(iterator beg, iterator end, _pred, nevalue);

//按条件替换元素，满足条件的替换成指定元素

//beg开始迭代器

//end结束迭代器

//_pred 谓词

//nevalue替换的新元素

示例:

replace_if按条件查找，可以利用仿函数灵活筛选满足的条件

5.4.4 sap

功能描述

互换两个容器的元素

函数原型:

sap(container c1, container c2);

//互换两个容器的元素

//c1容器1

//c2容器2

示例:

sap交换容器时，注意交换的容器是同种类型

5.5常用算术生成算法

学习目标:

掌握常用的算术生成算法

注意:

算术生成算法属于小型算法，使用时包含的头文件为#include

算法简介:

aumulate //计算容器元素累计总和

fill //向容器中添加元素

5.5.1 aumulate

功能描述:

计算区间内 容器元素累计总和

函数原型:

aumulate(iterator beg, iterator end, value);

//计算容器元素累计总和

//beg开始迭代器

//end结束迭代器

//value 起始值

示例

aumulate使用时头文件注意是 numeric，这个算法很实用

5.5.2 fill

功能描述:

向容器中填充指定的元素

函数原型:

fill(iterator beg, iterator end, value);

//向容器中填充元素

//beg开始迭代器

//end结束迭代器

//value填充的值

示例

利用fill可以将容器区间内元素填充为指定的值

5.6 常用集合算法

学习目标:

掌握常用的集合算法

算法简介:

set intersection //求两个容器的交集

set_union //求两个容器的并集

set difference //求两个容器的差集

5.6.1 set intersection

功能描述:

求两个容器的交集

函数原型:

set intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

//求两个集合的交集

//注意两个集合必须是有序序列

//beg1 容器1开始迭代器

//end1 容器1结束迭代器

//beg2 容器2开始迭代器

//end2 容器2结束迭代器

//dest 目标容器开始迭代器

示例

 

求交集的两个集合必须是有序序列

目标容器开辟空间需要从两个容器中取小值

set_intersection返回值即是交集中一个元素的位置

5.6.2 set_union

功能描述:

求两个集合的并集

函数原型

set union(iterator beg1, iterator end1 iterator beg2, iterator end2, iterator dest):

//求两个集合的并集

//注意:两个集合必须是有序序列

//beg1 容器1开始迭代器

//end1 容器1结束迭代器

// beg2 容器2开始迭代器

//end2 容器2结束迭代器

// dest 目标容器开始迭代器

示例:

求并集的两个集合必须是有序序列

目标容器开辞空间需要两个容器相加

set_union返回值即是并集中一个元素的位置

5.6.3 set difference

功能描述:

求两个集合的差集

函数原型:

set difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

//求两个集合的差集

//注意:两个集合必须是有序序列

//beg1 容器1开始迭代器

//end1 容器1结束迭代器

//beg2 容器2开始迭代器

//end2 容器2结束迭代器

// dest目标容器开始迭代器

示例

求差集的两个集合必须是有序序列

目标容器开辟空间需要从两个容器取较大值

set_difference返回值即是差集中一个元素的位置