首页 > 编程语言 >STL中的算法

STL中的算法

时间：2022-08-28 17:55:31浏览次数：54  
标签：last 函数 STL RanIt 算法 template FwdIt first

参考：传智播客C++课程讲义 传智扫地僧

前言

算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。

<algorithm>是所有STL头文件中最大的一个，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、反转、排序、合并等等。

<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。

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

STL提供了大量实现算法的模版函数，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能，从而大大地提升效率。

#include <algorithm>

#include <numeric>

#include <functional>

STL中算法分类

  • 操作对象
    • 直接改变容器的内容
    • 将原容器的内容复制一份,修改其副本,然后传回该副本
  • 功能:
    • 非可变序列算法 指不直接修改其所操作的容器内容的算法
      • 计数算法        count、count_if
      • 搜索算法        search、find、find_if、find_first_of、…
      • 比较算法        equal、mismatch、lexicographical_compare
    • 可变序列算法 指可以修改它们所操作的容器内容的算法
      • 删除算法        remove、remove_if、remove_copy、…
      • 修改算法        for_each、transform
      • 排序算法        sort、stable_sort、partial_sort、
    • 排序算法 包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作
    • 数值算法 对容器内容进行数值计算

查找算法(13个)：判断容器中是否包含某个值

函数名

头文件

函数功能

adjacent_find

<algorithm>

在iterator对标识元素范围内,查找一对相邻重复元素,找到则返回指向这对元素的第一个元素的ForwardIterator .否则返回last.重载版本使用输入的二元操作符代替相等的判断

函数原形

template<class FwdIt> FwdIt adjacent_find(FwdIt first, FwdIt last);

template<class FwdIt, class Pred> FwdIt adjacent_find(FwdIt first, FwdIt last, Pred pr);

binary_search

<algorithm>

在有序序列中查找value,找到返回true.重载的版本实用指定的比较函数对象或函数指针来判断相等

函数原形

template<class FwdIt, class T> bool binary_search(FwdIt first, FwdIt last, const T& val);

template<class FwdIt, class T, class Pred> bool binary_search(FwdIt first, FwdIt last, const T& val,Pred pr);

count

<algorithm>

利用等于操作符,把标志范围内的元素与输入值比较,返回相等元素个数

函数原形

template<class InIt, class Dist> size_t count(InIt first, InIt last,const T& val, Dist& n);

count_if

<algorithm>

利用输入的操作符,对标志范围内的元素进行操作,返回结果为true的个数

函数原形

template<class InIt, class Pred, class Dist> size_t count_if(InIt first, InIt last, Pred pr);

equal_range

<algorithm>

功能类似equal，返回一对iterator，第一个表示lower_bound，第二个表示upper_bound

函数原形

template<class FwdIt, class T> pair<FwdIt, FwdIt> equal_range(FwdIt first, FwdIt last,const T& val);

template<class FwdIt, class T, class Pred> pair<FwdIt, FwdIt> equal_range(FwdIt first, FwdIt last,const T& val, Pred pr);

find

<algorithm>

利用底层元素的等于操作符,对指定范围内的元素与输入值进行比较.当匹配时,结束搜索,返回该元素的一个InputIterator

函数原形

template<class InIt, class T> InIt find(InIt first, InIt last, const T& val);

find_end

<algorithm>

在指定范围内查找"由输入的另外一对iterator标志的第二个序列"的最后一次出现.找到则返回最后一对的第一个ForwardIterator,否则返回输入的"另外一对"的第一个ForwardIterator.重载版本使用用户输入的操作符代替等于操作

函数原形

template<class FwdIt1, class FwdIt2> FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,FwdIt2 first2, FwdIt2 last2);

template<class FwdIt1, class FwdIt2, class Pred> FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,FwdIt2 first2, FwdIt2 last2, Pred pr);

find_first_of

<algorithm>

在指定范围内查找"由输入的另外一对iterator标志的第二个序列"中任意一个元素的第一次出现。重载版本中使用了用户自定义操作符

函数原形

template<class FwdIt1, class FwdIt2> FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,FwdIt2 first2, FwdIt2 last2);

template<class FwdIt1, class FwdIt2, class Pred> FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,FwdIt2 first2, FwdIt2 last2, Pred pr);

find_if

<algorithm>

使用输入的函数代替等于操作符执行find

 

template<class InIt, class Pred> InIt find_if(InIt first, InIt last, Pred pr);

lower_bound

<algorithm>

返回一个ForwardIterator，指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置.重载函数使用自定义比较操作

函数原形

template<class FwdIt, class T> FwdIt lower_bound(FwdIt first, FwdIt last, const T& val);

template<class FwdIt, class T, class Pred> FwdIt lower_bound(FwdIt first, FwdIt last, const T& val, Pred pr);

upper_bound

<algorithm>

返回一个ForwardIterator,指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置，该位置标志一个大于value的值.重载函数使用自定义比较操作

函数原形

template<class FwdIt, class T> FwdIt upper_bound(FwdIt first, FwdIt last, const T& val);

template<class FwdIt, class T, class Pred> FwdIt upper_bound(FwdIt first, FwdIt last, const T& val, Pred pr);

search

<algorithm>

给出两个范围，返回一个ForwardIterator,查找成功指向第一个范围内第一次出现子序列(第二个范围)的位置，查找失败指向last1,重载版本使用自定义的比较操作

函数原形

template<class FwdIt1, class FwdIt2> FwdIt1 search(FwdIt1 first1, FwdIt1 last1,FwdIt2 first2, FwdIt2 last2);

template<class FwdIt1, class FwdIt2, class Pred> FwdIt1 search(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2, Pred pr);

search_n

<algorithm>

在指定范围内查找val出现n次的子序列。重载版本使用自定义的比较操作

函数原形

template<class FwdIt, class Dist, class T> FwdIt search_n(FwdIt first, FwdIt last,Dist n, const T& val);

template<class FwdIt, class Dist, class T, class Pred> FwdIt search_n(FwdIt first, FwdIt last,Dist n, const T& val, Pred pr);

堆算法(4个)

函数名

头文件

函数功能

make_heap

<algorithm>

把指定范围内的元素生成一个堆。重载版本使用自定义比较操作

函数原形

template<class RanIt> void make_heap(RanIt first, RanIt last);

template<class RanIt, class Pred> void make_heap(RanIt first, RanIt last, Pred pr);

pop_heap

<algorithm>

并不真正把最大元素从堆中弹出，而是重新排序堆。它把first和last-1交换，然后重新生成一个堆。可使用容器的back来访问被"弹出"的元素或者使用pop_back进行真正的删除。重载版本使用自定义的比较操作

函数原形

template<class RanIt> void pop_heap(RanIt first, RanIt last);

template<class RanIt, class Pred> void pop_heap(RanIt first, RanIt last, Pred pr);

push_heap

<algorithm>

假设first到last-1是一个有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向该函数前，必须先把元素插入容器后。重载版本使用指定的比较操作

函数原形

template<class RanIt>void push_heap(RanIt first, RanIt last);

template<class RanIt, class Pred> void push_heap(RanIt first, RanIt last, Pred pr);

sort_heap

<algorithm>

对指定范围内的序列重新排序，它假设该序列是个有序堆。重载版本使用自定义比较操作

函数原形

template<class RanIt> void sort_heap(RanIt first, RanIt last);

template<class RanIt, class Pred> void sort_heap(RanIt first, RanIt last, Pred pr);

排序和通用算法(14个)：提供元素排序策略

函数名

头文件

函数功能

inplace_merge

<algorithm>

合并两个有序序列，结果序列覆盖两端范围。重载版本使用输入的操作进行排序

函数原形

template<class BidIt> void inplace_merge(BidIt first, BidIt middle, BidIt last);

template<class BidIt, class Pred> void inplace_merge(BidIt first, BidIt middle, BidIt last, Pred pr);

merge

<algorithm>

合并两个有序序列，存放到另一个序列。重载版本使用自定义的比较

函数原形

template<class InIt1, class InIt2, class OutIt> OutIt merge(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x);

template<class InIt1, class InIt2, class OutIt, class Pred> OutIt merge(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x, Pred pr);

nth_element

<algorithm>

将范围内的序列重新排序，使所有小于第n个元素的元素都出现在它前面，而大于它的都出现在后面。重载版本使用自定义的比较操作

函数原形

template<class RanIt> void nth_element(RanIt first, RanIt nth, RanIt last);

template<class RanIt, class Pred> void nth_element(RanIt first, RanIt nth, RanIt last, Pred pr);

partial_sort

<algorithm>

对序列做部分排序，被排序元素个数正好可以被放到范围内。重载版本使用自定义的比较操作

函数原形

template<class RanIt> void partial_sort(RanIt first, RanIt middle, RanIt last);

template<class RanIt, class Pred> void partial_sort(RanIt first, RanIt middle, RanIt last, Pred pr);

partial_sort_copy

<algorithm>

与partial_sort类似，不过将经过排序的序列复制到另一个容器

函数原形

template<class InIt, class RanIt> RanIt partial_sort_copy(InIt first1, InIt last1,RanIt first2, RanIt last2);

template<class InIt, class RanIt, class Pred> RanIt partial_sort_copy(InIt first1, InIt last1,RanIt first2, RanIt last2, Pred pr);

partition

<algorithm>

对指定范围内元素重新排序，使用输入的函数，把结果为true的元素放在结果为false的元素之前

函数原形

template<class BidIt, class Pred> BidIt partition(BidIt first, BidIt last, Pred pr);

random_shuffle

<algorithm>

对指定范围内的元素随机调整次序。重载版本输入一个随机数产生操作

函数原形

template<class RanIt> void random_shuffle(RanIt first, RanIt last);

template<class RanIt, class Fun> void random_shuffle(RanIt first, RanIt last, Fun& f);

reverse

<algorithm>

将指定范围内元素重新反序排序

函数原形

template<class BidIt> void reverse(BidIt first, BidIt last);

reverse_copy

<algorithm>

与reverse类似，不过将结果写入另一个容器

函数原形

template<class BidIt, class OutIt> OutIt reverse_copy(BidIt first, BidIt last, OutIt x);

rotate

<algorithm>

将指定范围内元素移到容器末尾，由middle指向的元素成为容器第一个元素

函数原形

template<class FwdIt> void rotate(FwdIt first, FwdIt middle, FwdIt last);

rotate_copy

<algorithm>

与rotate类似，不过将结果写入另一个容器

函数原形

template<class FwdIt, class OutIt> OutIt rotate_copy(FwdIt first, FwdIt middle, FwdIt last, OutIt x);

sort

<algorithm>

以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作

函数原形

template<class RanIt> void sort(RanIt first, RanIt last);

template<class RanIt, class Pred> void sort(RanIt first, RanIt last, Pred pr);

stable_sort

<algorithm>

与sort类似，不过保留相等元素之间的顺序关系

函数原形

template<class BidIt> void stable_sort(BidIt first, BidIt last);

template<class BidIt, class Pred> void stable_sort(BidIt first, BidIt last, Pred pr);

stable_partition

<algorithm>

与partition类似，不过不保证保留容器中的相对顺序

函数原形

template<class FwdIt, class Pred> FwdIt stable_partition(FwdIt first, FwdIt last, Pred pr);

 

。。。

常用算法汇总

常用算法汇总
    常用的查找算法：
adjacent_find()（ adjacent 是邻近的意思）,binary_search(),count(),
count_if(),equal_range(),find(),find_if()。
    常用的排序算法：
merge(),sort(),random_shuffle()（shuffle是洗牌的意思） ,reverse()。
    常用的拷贝和替换算法：
copy(), replace(),
replace_if(),swap()
    常用的算术和生成算法：
accumulate()（ accumulate 是求和的意思）,fill(),。
    常用的集合算法：
set_union(),set_intersection(),
set_difference()。
    常用的遍历算法：
for_each(), transform()（ transform 是变换的意思）


 

 

 

 

 

查找

 

排序

 

标签：last,函数,STL,RanIt,算法,template,FwdIt,first
From： https://www.cnblogs.com/htj10/p/16633241.html

相关文章

  • 【算法笔记】一文解决数组类型算法题（1）
    本文主要介绍数据结构中的数组，以及LeetCode题库下面相关题型的分类和解法套路。数组理论概述定义数组是存储在一块连续内存上的，由相同元素集合组成的数据结构。利用索......
  • 哈希算法
    目录什么是哈希算法？哈希算法的应用应用一：安全加密应用二：唯一标识应用三：数据校验应用四：散列函数什么是哈希算法？将任意长度的二进制值串映射为固定长度的二进制值串，这个映......
  • 21级数据结构与算法实验2——链表
    21级数据结构与算法实验2——链表28天7-1单链表的创建及遍历分数30作者陈晓梅单位广东外语外贸大学读入n值及n个整数，建立单链表并遍历输出。输入格式:读入n及......
  • LetCode算法--2.两数相加
    给你两个 非空的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和......
  • LetCode算法刷题-精选200题-1.两数之和
    给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是......
  • 加密算法学习之SM4
    pom引入:<!--SM国密加密--><dependency><groupId>org.bouncycastle</groupId><artifactId>bcprov-jdk15on</artifactId><version>1.56</version></dependen......
  • 决策树算法
    1.决策树在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表......
  • 算法总结
    1.二叉树的右侧视图给定一个二叉树的根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。题解：根之前二叉树解题类似，用广度优先搜索或......
  • 人物交互算法（HOI）学习笔记之 ——QPIC
    论文简介QPIC:Query-BasedPairwiseHuman-ObjectInteractionDetectionwithImage-WideContextualInformation[论文地址][https://arxiv.org/abs/2103.05399][代......
  • ZJU-199001 第三周练习 2 数字特征值 位运算算法
    题目对数字求特征值是常用的编码算法,奇偶特征是一种简单的特征值.对于一个整数,从个位开始对每一位数字编号,个位是\(1\)号,十位是\(2\)号,以此类推.这个整数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99