首页 > 编程语言 >22_STL之算法

22_STL之算法

时间：2023-10-15 14:57:14浏览次数：48  
标签：容器 end 22 iterator STL param v1 算法 迭代

STL之算法

函数对象

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

注意：

​ 1.函数对象(仿函数)是一个类，不是一个函数。

​ 2.函数对象(仿函数)重载了"()"操作符使得它可以像函数一样调用。

分类：

​ 如果函数对象 有一个参数 叫：一元函数对象

​ 如果函数对象 有二个参数 叫：二元函数对象

​ 如果函数对象 有三个参数 叫： 多元函数对象

#include <iostream>

using namespace std;

//函数对象(仿函数)
class Print
{
public:
    void operator()(char *str)
    {
        cout << str << endl;
    }
};

int main()
{
    Print p;
    p("hello world");
    return 0;
}

谓词

返回值为bool类型的普通函数或仿函数 都叫谓词。

如果谓词 有一个参数 叫：一元谓词

如果谓词 有二个参数 叫：二元谓词

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class GreaterThan30
{
public:
    bool operator()(int value)
    {
        return value>20;
    }
};

int main()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    //find_if条件查找
    vector<int>::iterator ret;
    ret = find_if(v.begin(), v.end(), GreaterThan30());
    if(ret != v.end())
    {
        cout << "查找结果: " << *ret << endl;
    }
    return 0;
}

image-20231014124826765

image-20231014125130464

二元谓词

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class MyGreaterInt
{
public:
    bool operator()(int v1, int v2)
    {
        return v1>v2;
    }
};

int main()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    
    sort(v.begin(), v.end(), MyGreaterInt());
    return 0;
}

内建函数对象

STL内建了一些函数对象。分为:算数类函数对象,关系运算类函数对象,逻辑运算类仿函数。这些仿函数所产生的对象,用法和一般函数完全相同，当然我们还可以产生无名的临时对象来履行函数功能。

6 个算数类函数对象,除了 negate 是一元运算，其他都是二元运算。

template<class T> T plus<T>//加法仿函数
template<class T> T minus<T>//减法仿函数
template<class T> T multiplies<T>//乘法仿函数
template<class T> T divides<T>//除法仿函数
template<class T> T modulus<T>//取模仿函数
template<class T> T negate<T>//取反仿函数

6个关系运算类函数对象，每一种都是二元运算。

template<class T> bool equal_to<T>//等于
template<class T> bool not_equal_to<T>//不等于
template<class T> bool greater<T>//大于
template<class T> bool greater_equal<T>//大于等于
template<class T> bool less<T>//小于
template<class T> bool less_equa <T>//小于等于

逻辑运算类运算函数 not为一元运算，其余为二元运算。

template<class T> bool logical_and<T>//逻辑与
template<class T> bool logical_or<T>//逻辑或
template<class T> bool logical_not<T>//逻辑非

案例:

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

int main()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    vector<int>::iterator ret;
    //内建函数对象
    ret = find_if(v.begin(), v.end(), bind2nd(greater<int>(), 10)); //bind2nd()将后面两个参数绑定成一个
    if(ret != v.end())
    {
        while(ret != v.end())
        {
            cout << *ret++ << endl;
        }
    }
    return 0;
}

适配器

适配器 为算法 提供接口

函数对象适配器

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

//第二步: 公共继承binary_function 参数萃取
class PrintInt: public binary_function<int, int, void>
{
public:
    //第三步: const修饰operator()
    void operator()(int val, int tmp) const
    {
//        cout << val+tmp << " ";
        cout << "val = " << val << ", " << "tmp = " << tmp << endl;
    }
};

int main()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    //第一步: bind2nd或bind1st绑定参数
    for_each(v.begin(), v.end(), bind2nd(PrintInt(), 200)); //bind2nd将200绑定到第二个参数
    for_each(v.begin(), v.end(), bind1st(PrintInt(), 200)); //bind1st将200绑定到第一个参数
    cout << endl;
    return 0;
}

image-20231014132350057

函数指针适配器 ptr_fun

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

void myPrintInt(int value, int tmp)
{
    cout << "value = " << value << ", tmp = " << tmp << endl;
}

int main()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(70);
    v1.push_back(90);
    //myPrintInt是函数名在C++中不能作为函数入口地址, 需要ptr_fun转换
    for_each(v1.begin(), v1.end(), bind2nd(ptr_fun(myPrintInt), 100));
    cout << endl;
    return 0;
}

成员函数 作为适配器 mem_fun_ref

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class Data
{
public:
    int data;
public:
    Data(){}
    Data(int d)
    {
        data = d;
    }
    void printInt(int tmp)
    {
        cout << "value = " << data+tmp << endl;
    }
};

int main()
{
    vector<Data> v1;
    v1.push_back (Data(10));
    v1.push_back (Data(30));
    v1.push_back (Data(50));
    v1.push_back (Data(70));
    v1.push_back (Data(90));
    //mem_fun_ref 成员函数指针 &Data::printInt 成员函数入口地址
    for_each(v1.begin(), v1.end(), bind2nd(mem_fun_ref(&Data::printInt), 100));
    return 0;
}

取反适配器

not1 一元取反

image-20231014134020121

not2 二元取反

image-20231014134117458

算法概述

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

常用遍历算法

for_each 遍历算法

/*
遍历算法 遍历容器元素
@param beg 开始迭代器
@param end 结束迭代器
@param _callback函数回调或者函数对象
@return 函数对象
*/
for_each(iterator beg, iterator end, _callback);

transform 算法

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

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int myTransform(int value)
{
    return value;
}

int main()
{
    vector<int> v1;
    v1.push_back (10);
    v1.push_back (30);
    v1.push_back (50);
    v1.push_back (70);
    v1.push_back (90);

    vector<int> v2;
    v2.resize(v1.size());

    transform(v1.begin(), v1.end(), v2.begin(), myTransform);

    for_each(v2.begin(), v2.end(), [=](int value){
        cout << value << endl;
    });
    return 0;
}

常用查找算法

find 算法

/*
find 算法 查找元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@return 返回查找元素的位置
*/
find(iterator beg, iterator end, value);

image-20231014140122633

find_if 算法

/*
find_if 算法 条件查找
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param callback回调函数或者谓词(返回bool类型的函数对象)
@return bool 查找返回true 否则 false
*/
find_if(iterator beg, iterator end, _callback);

image-20231014140243277

adjacent_find 算法

/*
adjacent_find 算法 查找相邻重复元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param -callback回调函数或者谓词(返回bool类型的函数对象)
@return 返回相邻元素的第一个位置的迭代器
*/
adjacent_find(iterator beg, iterator end, _callback);

binary_search 算法

/*
binary_search 算法 二分查找法
注意：在无序序列中不可用
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@return bool 查找返回 true 否则 false
*/
bool binary_search(iterator beg, iterator end, value);

image-20231014140737178

count 算法

/*
统计元素出现次数
@param beg 容器开始迭代器
@param end容器结束迭代器
@param value回调函数或者谓词(返回boo1类型的函数对象)
@return int 返回元素个数
*/
count(iterator beg, iterator end, value);

image-20231014140856114

count_if 算法

/*
count_if 算法 统计元素出现次数
@param beg容器开始迭代器
@param end 容器结束迭代器
@param callback回调函数或者谓词(返回 bool类型的函数对象)
@return int 返回元素个数
*/
count_if(iterator beg, iterator end, _callback);

image-20231014141121978

常用排序算法

merge算法

/*
merge 算法 容器元素合并，并存储到另一容器中
注意：两个容器必须是有序的
@param beg1 容器 1 开始迭代器
@param end1 容器 1 结束迭代器
@param beg2 容器 2 开始迭代器
@param end2 容器 2 结束迭代器
@param beg3 目标容器开始迭代器
*/
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator beg3);

sort 算法

/*
sort 算法 容器元素排序
@param beg 容器 1 开始迭代器
@param end 容器 1 结束迭代器
@param -callback回调函数或者谓词(返回bool类型的函数对象)
*/
sort(iterator beg, iterator end, _callback)

random_shuffle 算法

/*
random_shuffle 算法 对指定范围内的元素随机调整次序
@param beg 容器开始迭代器
@param end 容器结束迭代器
*/
random_shuffle(iteratorIbeg, iterator end);

image-20231015132704171

reverse 算法

/*
reverse 算法 反转指定范围的元素
@param beg容器开始迭代器
@param end容器结束迭代器
*/
reverse(iterator beg, iterator end)

image-20231015132940514

常用拷贝替换算法

copy算法

/*
copy算法将容器内指定范围的元素拷贝到另一容器中
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param dest 目标起始迭代器
*/
copy(iterator beg, iterator end, iterator dest)

image-20231015133300610

终端迭代器输出:

image-20231015133706344

replace算法

/*
replace 算法 将容器内指定范围的旧元素修改为新元素
@param beg 容器开始迭代器
@param end容器结束迭代器
@param oldvalue 旧元素
@param oldvalue新元素
*/
replace(iterator beg, iterator end, oldvalue, newval)

image-20231015133746279

replace_if 算法

/*
replace_if 算法 将容器内指定范围满足条件的元素替换为新元素
@param beg 容器开始迭代器
@param end容器结束迭代器
@param callback函数回调或者谓词(返回Boo1类型的函数对象)
@param oldvalue 新元素
*/
replace_if(iterator beg, iterator end, _callback, newvalue)

image-20231015134151541

swap 算法

/*
swap算法互换两个容器的元素
@param c1 容器 1
@param c2 容器 2
*/
swap(container c1,Tcontainer c2)

image-20231015134323475

image-20231015134332673

常用算法生成算法

accumulate 算法

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

fill 算法

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

常用集合算法

image-20231015140326499

set_intersection 算法

/*
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)

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main()
{
    vector<int> v1;
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(50);

    vector<int> v2;
    v2.push_back(20);
    v2.push_back(40);
    v2.push_back(60);

    vector<int> v3; //存交集
    v3.resize(min(v2.size(), v1.size()));
    vector<int>::iterator ret =  set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    copy(v3.begin(), ret, ostream_iterator<int>(cout, " "));
    return 0;
}

set_union 算法

/*
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)

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> v1;
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(50);

    vector<int> v2;
    v2.push_back(20);
    v2.push_back(40);
    v2.push_back(60);

    vector<int> v3; //存并集
    v3.resize(v2.size()+v1.size());
    vector<int>::iterator ret =  set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    copy(v3.begin(), ret, ostream_iterator<int>(cout, " "));
    return 0;
}

set_difference 算法

/*
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)

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main()
{
    vector<int> v1;
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(50);

    vector<int> v2;
    v2.push_back(20);
    v2.push_back(40);
    v2.push_back(60);

    vector<int> v3; //存差集
    v3.resize(v1.size());
    vector<int>::iterator ret =  set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    copy(v3.begin(), ret, ostream_iterator<int>(cout, " "));
    return 0;
}

标签：容器,end,22,iterator,STL,param,v1,算法,迭代
From： https://www.cnblogs.com/mzx233/p/17765630.html

相关文章

  • 《算法学习专栏》—— DP问题之状态机模型
    2023年10月13日更新于2023年10月13日一、前言本栏，为状态机模型，题目主要来源日常，目前主要来源于Acwing的提高课。希望以后做到状态机的题目，也能加进来，不断完善。使用的分析方法均为闫式DP分析法。字臭。。。希望能用手写板慢慢写的好看。二、状态机模型2.1对于状态机的考虑......
  • 算法第2章实践报告1
    7-1Cablemaster(切割绳子）有N条绳子，它们的长度分别为x。如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长能有多长？输入格式：第一行两个整数n和k（1<=n<=10000;1<=k<=10000）。接下来n行，描述了每条绳子的长度x，x也是整数。输出格式:切割后每条绳子的最大长度。完整代码：......
  • VTK 判断一个 点 是否在一个模型 stl 内部 vtk 点是否在内部 表面 寻找最近点
    判断一个点,判断是否在风格stl模型内部，或表面：目录1.方案一：使用vtkCellLocator  FindClosestPoint找到模型上距离给定点最近的一点，计算两点的距离，小于某一阈值则认为此点在模型上；2.方案二使用vtkKdTreePointLocator3.方案三使用vtkSelectEnclosedPoints1.方案一：使用vtk......
  • 【算法题】6939. 数组中的最大数对和
    题目：给你一个下标从0开始的整数数组nums。请你从nums中找出和最大的一对数，且这两个数数位上最大的数字相等。返回最大和，如果不存在满足题意的数字对，返回-1。示例1：输入：nums=[51,71,17,24,42]输出：88解释：i=1和j=2，nums[i]和nums[j]数位上最大的数字相等，且这......
  • 【算法题】88. 合并两个有序数组
    题目：给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。注意：最终，合并后数组不应由函数返回，而是存储在数组nums1中。为了应对这种情况，nums1的......
  • Python 练习实例22
    题目：两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队赛手的名单。程序源代码：实例#!/usr/bin/python#-*-coding:UTF-8-*-foriinrange(ord('x'),ord('z')+1):......
  • RaftPaper：寻一个可被理解的共识算法
    周末躺不平，摆不烂，卷不动，随便读一篇paper吧原文：InSearchofanUnderstandableConsensusAlgorithm作者：DiegoOngaro/JohnOusterhout——StanfordUniversity摘要Raft是一个用于管理一份被复制的日志的共识算法，它和（multi-）Paxos产出的结果等价，和Paxos一样高效，但它的结......
  • 代码随想录算法训练营-动态规划-3-(0-1背包问题）|416. 分割等和子集、1049. 最后一块石
    416.分割等和子集01背包的递推公式为：dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);如果dp[j]==j说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。1classSolution:2defcanPartition(self,nums:List[int])->bool:3_sum=......
  • 10.15算法
    最小栈设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。实现MinStack类:MinStack()初始化堆栈对象。voidpush(intval)将元素val推入堆栈。voidpop()删除堆栈顶部的元素。inttop()获取堆栈顶部的元素。intgetMin()获取堆栈中的最小元素。 示例......
  • 一个vuepress配置问题，引发的js递归算法思考
    前言这两天在尝试用语雀＋vuepress＋github搭建个人博客。小破站地址：王天的web进阶之路语雀作为编辑器，发布文档推送github，再自动打包部署，大概流程如下。问题我使用的elog插件批量导出语雀文档。elog采用的配置是所有文章平铺导出，没有按照语雀知识库目录生成markdown，这导......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99