首页 > 编程语言 >STL- 常用算法

STL- 常用算法

时间:2023-08-29 22:23:09浏览次数:55  
标签:容器 常用 end 迭代 iterator STL 元素 beg 算法

5 STL- 常用算法

概述:

  • 算法主要是由头文件<algorithm> <functional> <numeric>组成。

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

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

  • <functional>定义了一些模板类,用以声明函数对象。

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类型的仿函数)

总结:find_if按条件查找使查找更加灵活,提供的仿函数可以改变不同的策略

5.2.3 adjacent_find

功能描述:

  • 查找相邻重复元素

函数原型:

  • adjacent_find(iterator beg, iterator end);

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

    // beg 开始迭代器

    // end 结束迭代器

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

功能描述:

  • 查找指定元素是否存在

函数原型:

  • 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 结束迭代器

    // value 统计的元素

总结: 统计自定义数据类型时候,需要配合重载 operator==

5.2.6 count_if

功能描述:

  • 按条件统计元素个数

函数原型:

  • count_if(iterator beg, iterator end, _Pred);

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

    // beg 开始迭代器

    // end 结束迭代器

    // _Pred 谓词

总结:按值统计用count,按条件统计用count_if

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 // 容器内指定范围满足条件的元素替换为新元素
  • swap // 互换两个容器的元素

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, newvalue);

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

    // beg 开始迭代器

    // end 结束迭代器

    // oldvalue 旧元素

    // newvalue 新元素

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

5.4.3 replace_if

功能描述:

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

函数原型:

  • replace_if(iterator beg, iterator end, _pred, newvalue);

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

    // beg 开始迭代器

    // end 结束迭代器

    // _pred 谓词

    // newvalue 替换的新元素

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

5.4.4 swap

功能描述:

  • 互换两个容器的元素

函数原型:

  • swap(container c1, container c2);

    // 互换两个容器的元素

    // c1容器1

    // c2容器2

总结:swap交换容器时,注意交换的容器要同种类型

5.5 常用算术生成算法

注意:

  • 算术生成算法属于小型算法,使用时包含的头文件为 #include <numeric>

算法简介:

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

  • fill // 向容器中添加元素

5.5.1 accumulate

功能描述:

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

函数原型:

  • accumulate(iterator beg, iterator end, value);

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

    // beg 开始迭代器

    // end 结束迭代器

    // value 起始值

总结:accumulate使用时头文件注意是 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返回值既是差集中最后一个元素的位置

标签:容器,常用,end,迭代,iterator,STL,元素,beg,算法
From: https://www.cnblogs.com/ljh2487/p/17665994.html

相关文章

  • STL- 常用容器
    3STL-常用容器3.1string容器3.1.1string基本概念本质:string是C++风格的字符串,而string本质上是一个类string和char*区别:char*是一个指针string是一个类,类内部封装了char*,管理这个字符串,是一个char*型的容器。特点:string类内部封装了很多成员方法例如:查找fi......
  • STL- 函数对象
    4STL-函数对象4.1函数对象4.1.1函数对象概念概念:重载函数调用操作符的类,其对象常称为函数对象函数对象使用重载的()时,行为类似函数调用,也叫仿函数本质:函数对象(仿函数)是一个类,不是一个函数4.1.2函数对象使用特点:函数对象在使用时,可以像普通函数那样调用,可以......
  • STL初识
    2STL初识2.1STL的诞生长久以来,软件界一直希望建立一种可重复利用的东西C++的面向对象和泛型编程思想,目的就是复用性的提升大多情况下,数据结构和算法都未能有一套标准,导致被迫从事大量重复工作为了建立数据结构和算法的一套标准,诞生了STL2.2STL基本概念STL(......
  • js 常用链接
    nodeguide:TheNode.jsEventLoop,Timers,andprocess.nextTick()vuexvue3vitevitest......
  • ESP32 idf常用脚本命令及git命令
    一、Linux环境1.下载并安装相关的工具./install.sh2.添加ESP-IDF工具到PATH中../export.sh3.打开配置界面idf.pymenuconfig4.设置编译的芯片型号idf.pyset-targetesp32c35.编译工程idf.pybuild6.指定串口和波特率烧录程序并打开串口监视器idf.pyflash-b1500......
  • Python 中一些常用的
    对变量类型转换的内置函数int():将一个数值或字符串转换成整数,可以指定进制。float():将一个字符串转换成浮点数。str():将指定的对象转换成字符串形式,可以指定编码。chr():将整数转换成该编码对应的字符串(一个字符)。ord():将字符串(一个字符)转换成对应的编码(整数)。这个经常用。......
  • 国密算法SM2的优势、原理和应用场景
    在数字化时代,信息安全成为关注的焦点。密码算法是信息安全的核心,而国密算法SM2是一种国产密码算法,已经广泛应用于电子认证、电子签名、数据加密等领域。本文将深入介绍SM2算法的优势、原理和应用场景,并探讨如何利用FuncGPT(慧函数)生成的SM2库构建安全的应用程序。 一、国密算法S......
  • Git 常用命令 --- git add命令
    Gitadd的一般形式为:gitadd[参数] [--]<路径>表示将需要提交的代码从工作区添加到暂存区。为了方便,一般都用.来标识路径,.表示当前目录。 1.gitadd.网上普遍的说法是:将修改操作的文件和未跟踪且为新添加的文件添加到git系统的暂存区,但不包括删除的文件。但实际测试,git......
  • Git常用操作
    Git基本理解git的工作就是创建和保存项目的快照以及之后的快照进行对比。常用命令: gitclone-拷贝一份远程仓库,就是下载一个项目gitpush-上传远程代码并合并gitadd-添加文件到仓库(实际到暂存区)gitcommit-提交暂存区到本地仓库gitcheckoutgitpull-下载远......
  • Git常用命令
    1.状态1.1文件状态  2.分支2.1分支常用命令gitbranchxxx:新建分支gitcheckoutxxx:切换分支gitcheckout-bxxx:新建分支并切换到该分支(相当于上面两条命令)gitbranch-dxxx:删除分支gitbranch:查看分支列表gitpushorigin--deletexxx:删除远程分支gitfet......