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 做平滑切换
下一篇：后端开发刷题 | 笔试

关于单片机的【汇编指令系统】
计算机程序设计语言，经历了从机器语言、汇编语言到高级语言的进程。机器语言只是0 和1 的序列，运算效率最高，对编程者最不友好；早起的汇编语言，会有一些简单的英文和符号串作为助记符号，但需要人们打孔，
阅读更多2024-09-20
Thymeleaf模版引擎
Thymeleaf是面向Web和独立环境的现代服务器端Java模版引擎，能够处理HTML、XML、JavaScript、CSS甚至纯文本。Thymeleaf旨在提供一个优雅的、高度可维护的创建模版的方
阅读更多2024-09-20
数据结构—(java)反射，枚举，lambda表达式
java的反射机制是指，在程序的运行状态中，对于任意一个类，可以获取这个类的全部信息（包括，类加载器（后面会学到），构造方法，成员属性，成员方法等。对于任意一个对象，我们也能够调用其属性与方法进行修改
阅读更多2024-09-20
算法打卡：第十一章图论part02
代码随想录打卡第51天
阅读更多2024-09-20
AIGC数智化课程内容生产与服务平台 | OPENAIGC开发者大赛企业组AI创新之星奖
它为企业培训、院校教育、中小学课程、政府培训、教育机构、出版社及IP知识博主提供全面的解决方案，助力各类用户高效、便捷地生成和管理教学内容。通过AI技术，AI智课能够自动化创建丰富多样的课程材料，提升
阅读更多2024-09-20
【Kubernetes知识点】HPA如何控制不同的资源实现自动扩缩容？
❤️ 摘要：Kubernetes 作为当前最流行的容器编排平台，提供了 Horizontal Pod Autoscaler (HPA) 以便根据资源利用情况自动调整 Pod 副本数。本文将深入探讨 H
阅读更多2024-09-20
arm和riscv系统调用对比(笔记)
相似之处: ecall 和 SVC 都是用于从用户模式切换到内核模式，执行系统调用。它们的作用和使用方式非常相似，都是触发内核级别的处理，以处理用户请求的特权操作。不同之处: PendSV 是一个用于
阅读更多2024-09-20
完全背包问题(优化版二维)
有 NN 种物品和一个容量是 VV 的背包，每种物品都有无限件可用。第 ii 种物品的体积是 vivi，价值是 wiwi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出
阅读更多2024-09-20
6.C_数据结构_查询_哈希表
哈希表的查询是通过计算的方式获取数据的地址，而不是依次比较。在哈希表中，有一个键值key，通过一些函数转换为哈希表的索引值。其中：这个函数被称为哈希函数、散列函数、杂凑函数，记为：H(key)直接地址
阅读更多2024-09-20
行业革新，数据先行：智源研究院数据与行业应用 Workshop第三期
9月25日周三下午14点，智源人工智能研究院将在北京海淀区智源大厦举办“数据与行业应用 Workshop”第三期，与大家共话数据新基建和行业应用的未来。欢迎查看议程，扫码报名参加。
阅读更多2024-09-20

STL相关算法

STL相关算法

算法基础

算法概述

STL中算法分类

算法中函数对象和谓词

函数对象

谓词

空间配置器

算法概述

常用遍历算法

常用查找算法

常用排序算法

常用拷贝和替换算法

常用算数生成算法

常用集合算法

相关文章