STL相关算法

🕗 发布于 2024-07-24 09:23 算法 c++ java c语言

STL相关算法

算法基础
- 算法概述
- STL中算法分类
算法中函数对象和谓词
- 函数对象
- 谓词
空间配置器
算法概述

算法基础

算法概述

算法部分主要由头文件，和组成。
是所有STL头文件中最大的一个，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、反转、排序、合并等等。
体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。
中则定义了一些模板类，用以声明函数对象。
STL提供了大量实现算法的模版函数，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能，从而大大地提升效率。

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、

排序算法包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作
数值算法对容器内容进行数值计算

算法中函数对象和谓词

函数对象

重载函数调用操作符的类，其对象常称为函数对象（function object），即它们是行为类似函数的对象，也叫仿函数(functor),其实就是重载“()”操作符，使得类对象可以像函数那样调用。

注意:

函数对象(仿函数)是一个类，不是一个函数。
函数对象(仿函数)重载了”() ”操作符使得它可以像函数一样调用。

分类:假定某个类有一个重载的operator()，而且重载的operator()要求获取一个参数，我们就将这个类称为“一元仿函数”（unary functor）；
相反，如果重载的operator()要求获取两个参数，就将这个类称为“二元仿函数”（binary functor）。

函数对象的作用主要是什么？ STL提供的算法往往都有两个版本，其中一个版本表现出最常用的某种运算，另一版本则允许用户通过template参数的形式来指定所要采取的策略。

//函数对象是重载了函数调用符号的类
struct MyPrint{
voidoperator()(int val){
cout << val << endl;
}
};

void test01(){

//如何使用
MyPrint print01;
print01(10);//重载了()操作符的类实例化的对象，可以像普通函数那样调用,可以有参数 ，可以有返回值
}

//函数对象超出了普通函数的概念，可以保存函数的调用状态
struct HePrint{
HePrint(){
mCount =0;
}
voidoperator()(int val){
cout << val << endl;
mCount++;
}
int mCount;
};
void test02(){

HePrint print;
print(10);
print(20);
print(30);
print(40);
cout << print.mCount << endl;
}

//函数对象可以做参数和返回值
struct OurPrint{
voidoperator()(int val){
cout << val << endl;
}
};

void doBusiness(OurPrint print){
print(20);
}

void test03(){
//函数对象做参数
doBusiness(OurPrint());
}

谓词

谓词是指普通函数或重载的operator()返回值是bool类型的函数对象(仿函数)。如果operator接受一个参数，那么叫做一元谓词,如果接受两个参数，那么叫做二元谓词，谓词可作为一个判断式。

struct GreaterThanFive{
booloperator()(int v){
return v >5;
}
};

//一元谓词
void test01(){

vector<int> v;
for(int i =0; i <10;i++){
v.push_back(i);
}

vector<int>::iterator ret = find_if(v.begin(), v.end(), GreaterThanFive());
if(ret == v.end()){
cout <<"没有找到!"<< endl;
}
else{
cout <<"找到:"<<*ret << endl;
}

}

//二元谓词
struct MyCompare{
booloperator()(int v1,int v2){
return v1 > v2;
}
};

void test02(){

vector<int> v;
srand((unsignedint)time(NULL));
for(int i =0; i <10; i++){
v.push_back(rand()%100);
}

for(vector<int>::iterator it = v.begin(); it != v.end(); it ++){
cout <<*it <<" ";
}
cout << endl;
//排序算法
sort(v.begin(), v.end(), MyCompare());

for(vector<int>::iterator it = v.begin(); it != v.end(); it++){
cout <<*it <<" ";
}
cout << endl;
}

空间配置器

在软件开发，程序设计中，我们不免因为程序需求，使用很多的小块内存（基本类型以及小内存的自定义类型）。在程序中动态申请，释放。
　　
这个过程过程并不是一定能够控制好的，于是乎，
问题1：就出现了内存碎片问题。
问题2：一直在因为小块内存而进行内存申请，调用malloc，系统调用产生性能问题。

策略：如果申请的内存大小超过128，那么空间配置器就自动调用一级空间配置器。反之调用二级空间配置器。

一级空间配置器，STL源码中的一级空间配置器命名为class __malloc_alloc_template ，它很简单，就是对malloc，free，realloc等系统分配函数的一层封装。

二级空间配置器，由一个内存池和自由链表配合实现的。

算法概述

算法主要是由头文件<algorithm><functional><numeric>组成。
<algorithm>是所有STL头文件中最大的一个,其中常用的功能涉及到比较，交换，查找,遍历，复制，修改，反转，排序，合并等…
<numeric>体积很小，只包括在几个序列容器上进行的简单运算的模板函数.
<functional> 定义了一些模板类,用以声明函数对象。

常用遍历算法

/*
    遍历算法 遍历容器元素
@param beg 开始迭代器
@param end 结束迭代器
@param _callback  函数回调或者函数对象
@return 函数对象
*/
for_each(iterator beg, iterator end, _callback);
/*
transform算法 将指定容器区间元素搬运到另一容器中
注意 : transform 不会给目标容器分配内存，所以需要我们提前分配好内存
@param beg1 源容器开始迭代器
@param end1 源容器结束迭代器
@param beg2 目标容器开始迭代器
@param _cakkback 回调函数或者函数对象
@return 返回目标容器迭代器
*/
transform(iterator beg1, iterator end1, iterator beg2, _callbakc)

for_each:

/*

template<class _InIt,class _Fn1> inline
void for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
{
for (; _First != _Last; ++_First)
_Func(*_First);
}

*/

//普通函数
void print01(int val){
cout << val <<" ";
}
//函数对象
struct print001{
void operator()(int val){
cout << val <<" ";
}
};

//for_each算法基本用法
void test01(){

vector<int> v;
for(int i =0; i <10;i++){
v.push_back(i);
}

//遍历算法
for_each(v.begin(), v.end(), print01);
cout << endl;

for_each(v.begin(), v.end(), print001());
cout << endl;

}

struct print02{
print02(){
mCount =0;
}
void operator()(int val){
cout << val <<" ";
mCount++;
}
int mCount;
};

//for_each返回值
void test02(){

vector<int> v;
for(int i =0; i <10; i++){
v.push_back(i);
}

print02& p = for_each(v.begin(), v.end(), print02());
cout << endl;
cout << p.mCount << endl;
}

struct print03 :public binary_function<int,int,void>{
voidoperator()(int val,int bindParam)const{
cout << val + bindParam <<" ";
}
};

//for_each绑定参数输出
void test03(){

vector<int> v;
for(int i =0; i <10; i++){
v.push_back(i);
}

for_each(v.begin(), v.end(), bind2nd(print03(),100));
}

transform:

//transform 将一个容器中的值搬运到另一个容器中
/*
template<class _InIt, class _OutIt, class _Fn1> inline 
_OutIt _Transform(_InIt _First, _InIt _Last,_OutIt _Dest, _Fn1 _Func)
{

for (; _First != _Last; ++_First, ++_Dest)
*_Dest = _Func(*_First);
return (_Dest);
}

template<class _InIt1,class _InIt2,class _OutIt,class _Fn2> inline
_OutIt _Transform(_InIt1 _First1, _InIt1 _Last1,_InIt2 _First2, _OutIt _Dest, _Fn2 _Func)
{
for (; _First1 != _Last1; ++_First1, ++_First2, ++_Dest)
*_Dest = _Func(*_First1, *_First2);
return (_Dest);
}
*/

struct transformTest01{
int operator()(int val){
return val +100;
}
};
struct print01{
void operator()(int val){
cout << val <<" ";
}
};
void test01(){

vector<int> vSource;
for(int i =0; i <10;i ++){
vSource.push_back(i +1);
}

//目标容器
vector<int> vTarget;
//给vTarget开辟空间
vTarget.resize(vSource.size());
//将vSource中的元素搬运到vTarget
vector<int>::iterator it = transform(vSource.begin(), vSource.end(), vTarget.begin(), transformTest01());
//打印
for_each(vTarget.begin(), vTarget.end(), print01()); cout << endl;

}

//将容器1和容器2中的元素相加放入到第三个容器中
struct transformTest02{
intoperator()(int v1,int v2){
return v1 + v2;
}
};
void test02(){

vector<int> vSource1;
vector<int> vSource2;
for(int i =0; i <10; i++){
vSource1.push_back(i +1);
}

//目标容器
vector<int> vTarget;
//给vTarget开辟空间
vTarget.resize(vSource1.size());
transform(vSource1.begin(), vSource1.end(), vSource2.begin(),vTarget.begin(), transformTest02());
//打印
for_each(vTarget.begin(), vTarget.end(), print01()); cout << endl;
}

常用查找算法

/*
find算法 查找元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@return 返回查找元素的位置
*/
find(iterator beg, iterator end, value)
/*
adjacent_find算法 查找相邻重复元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  _callback 回调函数或者谓词(返回bool类型的函数对象)
@return 返回相邻元素的第一个位置的迭代器
*/
adjacent_find(iterator beg, iterator end, _callback);
/*
binary_search算法 二分查找法
注意: 在无序序列中不可用
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@return bool 查找返回true 否则false
*/
bool binary_search(iterator beg, iterator end, value);
/*
find_if算法 条件查找
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  callback 回调函数或者谓词(返回bool类型的函数对象)
@return bool 查找返回true 否则false
*/
find_if(iterator beg, iterator end, _callback);
/*
count算法 统计元素出现次数
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  value回调函数或者谓词(返回bool类型的函数对象)
@return int返回元素个数
*/
count(iterator beg, iterator end, value);
/*
count算法 统计元素出现次数
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  callback 回调函数或者谓词(返回bool类型的函数对象)
@return int返回元素个数
*/
count_if(iterator beg, iterator end, _callback);

常用排序算法

/*
merge算法 容器元素合并，并存储到另一容器中
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest  目标容器开始迭代器
*/
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
/*
sort算法 容器元素排序
注意:两个容器必须是有序的
@param beg 容器1开始迭代器
@param end 容器1结束迭代器
@param _callback 回调函数或者谓词(返回bool类型的函数对象)
*/
sort(iterator beg, iterator end, _callback)
/*
random_shuffle算法 对指定范围内的元素随机调整次序
@param beg 容器开始迭代器
@param end 容器结束迭代器
*/
random_shuffle(iterator beg, iterator end)
/*
reverse算法 反转指定范围的元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
*/
reverse(iterator beg, iterator end)

常用拷贝和替换算法

/*
copy算法 将容器内指定范围的元素拷贝到另一容器中
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param dest 目标容器结束迭代器
*/
copy(iterator beg, iterator end, iterator dest)
/*
replace算法 将容器内指定范围的旧元素修改为新元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param oldvalue 旧元素
@param oldvalue 新元素
*/
replace(iterator beg, iterator end, oldvalue, newvalue)
/*
replace_if算法 将容器内指定范围满足条件的元素替换为新元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param callback函数回调或者谓词(返回Bool类型的函数对象)
@param oldvalue 新元素
*/
replace_if(iterator beg, iterator end, _callback, newvalue)
/*
swap算法 互换两个容器的元素
@param c1容器1
@param c2容器2
*/
swap(container c1, container c2)

常用算数生成算法

/*
accumulate算法 计算容器元素累计总和
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value累加值
*/
accumulate(iterator beg, iterator end, value)
/*
fill算法 向容器中添加元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value t填充元素
*/
fill(iterator beg, iterator end, value)

常用集合算法

/*
set_intersection算法 求两个set集合的交集
注意:两个集合必须是有序序列
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest  目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
*/
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
/*
set_union算法 求两个set集合的并集
注意:两个集合必须是有序序列
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest  目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
*/
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
/*
set_difference算法 求两个set集合的差集
注意:两个集合必须是有序序列
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest  目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
*/
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

原文地址：https://blog.csdn.net/2401_83614570/article/details/140556162

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【办公软件】Office 2019以上版本PPT 做平滑切换
下一篇：后端开发刷题 | 笔试

大数据机器学习算法与计算机视觉应用02：线性规划
在零和博弈中，是概率和对应收益乘积的总和（收益给定），在最大流问题中，是通往终点所有流量的总和。卡马卡方法又被称作内部点方法，它寻找最优解的方法并非从可行域边界的一个顶点出发，而是从可行域内部的一个点
阅读更多2024-11-15
Python学习------第八天
num = int (input("请输入您想存入多少钱：请输入："))print(f"{name},你好，你的余额剩余:{money}元")num = in
阅读更多2024-11-15
【qt】控件
frameGeometry是开始从红圈开始算，Geometry从黑圈算程序证明：使用一个按键，当按键按下,qdebug打印各自左上角的坐标（相当于屏幕左上角），以及窗口大小视频演示：frameGeom
阅读更多2024-11-15
Jupyter notebook如何加载torch环境
Jupyter notebook如何加载torch环境
阅读更多2024-11-15
「QT」文件类之 QDataStream 数据流类
QDataStream是Qt框架中的一个类，它提供了基于Qt数据类型的二进制流接口。通过QDataStream，可以方便地将Qt的基本数据类型（如整型、浮点型、字符串等）以及自定义的Qt对象序列化（即
阅读更多2024-11-15
在vue项目中使用SM4加密登录
在 utils 文件夹中创建 sm4Util.js 文件。
阅读更多2024-11-15
力扣654：最大二叉树
力扣654：最大二叉树。C语言
阅读更多2024-11-15
Linux各种解压命令汇总
最常用的是.tar.gz，原因：linux各种版本标准压缩方式，几乎各大版本可以直接用；【注意】：.tar不是压缩的格式，tar只是按照一定的格式将所有的文件打包在一起。压缩目录tar cf - te
阅读更多2024-11-15
命令行打包Java工程
表示跳过测试可用于指定本地maven仓库路径。
阅读更多2024-11-15
web服务器
web 服务器提供的这些数据大部分都是文件，那么我们需要在服务器端先将数据文件写好，并且放置在某个特殊的目录下面，这个目录就是我们整个网站的首页，在nginx 中，这个目录默认在浏览器是通过你在地址栏
阅读更多2024-11-15

STL相关算法

STL相关算法

算法基础

算法概述

STL中算法分类

算法中函数对象和谓词

函数对象

谓词

空间配置器

算法概述

常用遍历算法

常用查找算法

常用排序算法

常用拷贝和替换算法

常用算数生成算法

常用集合算法

相关文章