江苏省建设工程施工安全网站,公司网站集资网站开发人员犯法么,广告设计与制作就业方向是什么,网络推广培训有哪些课程概述#xff1a;
算法主要是由头文件 algorithm functional numeric 组成。algorithm 是所有 STL 头文件中最大的一个#xff0c;范围涉及是比较、交换、查找、遍历操作、复制、修改等等。functional 定义了一些模板类#xff0c;…概述
算法主要是由头文件 algorithm functional numeric 组成。algorithm 是所有 STL 头文件中最大的一个范围涉及是比较、交换、查找、遍历操作、复制、修改等等。functional 定义了一些模板类用以声明函数对象numeric 体积很小只包括几个在序列上面进行简单数学运算的模板函数
1. 常用的遍历算法
学习目标
掌握常用的遍历算法
算法简介
for_each // 遍历容器transform // 搬运容器到另一个容器中
1.1 for_each
功能描述
实现遍历容器
函数原型
for_each(iterator beg, iterator end, _func); // 遍历算法 遍历容器元素 // beg 开始迭代器 // end 结束迭代器 // _func 函数或者函数对象
示例
#include iostream
#include vector
#include algorithm
using namespace std;//1.普通函数
void print01(int val) {cout val ;
}//2.仿函数
class print02
{
public:void operator()(int val) {cout val ;}
};int main() {vectorint 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(), print02());//仿函数的函数对象cout endl;return 0;
}总结for_each 在实际开发中是最常用的遍历算法需要熟练掌握
1.2 transform
功能描述
搬运容器到另一个容器中
函数原型
transform(iterator beg1, iterator end1, iterator beg2, _func); // beg1 源容器开始迭代器 // end1 源容器结束迭代器 // beg2 目标容器开始迭代器 // _func 函数或者函数对象可以在搬运过程中对源容器中的元素做一些逻辑运算等操作
示例
#include iostream
#include vector
#include algorithm
using namespace std;//仿函数
class Transform
{
public:int operator()(int val) {//搬运过程中需要把元素返回回去所以返回类型为搬运的元素类型return val;}
};class MyPrint
{
public:void operator()(int val) {cout val ;}
};int main() {vectorint v;for (int i 0; i 10; i) {v.push_back(i);}vectorint vTarget;vTarget.resize(v.size());//目标容器需要提前开辟预定大小的空间transform(v.begin(), v.end(), vTarget.begin(), Transform());for_each(vTarget.begin(), vTarget.end(), MyPrint());cout endl;return 0;
}总结
搬运的目标容器必须要提前开辟预定大小的空间否则无法正常搬运搬运过程中需要把元素返回回去所以仿函数的返回类型为 搬运的元素的类型
2. 常用查找算法
学习目标
掌握常用的查找算法
算法简介
find // 查找元素find_if // 按条件查找元素adjacent_find // 查找相邻重复元素binary_search // 二分查找法count // 统计元素个数count_if // 按条件统计元素个数
2.1 find
功能描述
查找指定元素找到返回指定元素的迭代器找不到返回结束迭代器end
函数原型
find(iterator beg, iterator end, value); // 以迭代器的方式按值查找元素找到返回指定位置迭代器找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // value 查找的元素
示例
#include iostream
#include vector
#include algorithm
using namespace std;class Person {
public:Person(string name, int age) {this-name name;this-age age;}bool operator(const Person p) {if (this-name p.name this-age p.age) {return true;} else {return false;}}public:string name;int age;
};int main() {
//查找内置数据类型vectorint v;for (int i 0; i 10; i) {v.push_back(i);}vectorint::iterator it find(v.begin(), v.end(), 5);if (it v.end()) {cout 没有找到 endl;}else {cout 找到: *it endl;}//查找自定义数据类型vectorPerson vp;Person p1(aaa, 10);Person p2(bbb, 20);Person p3(ccc, 30);Person p4(ddd, 40);vp.push_back(p1);vp.push_back(p2);vp.push_back(p3);vp.push_back(p4);Person pp(bbb, 20);//当使用 find 查找自定义数据类型时要在自定义数据类型内部重载 运算符让底层 find 知道如何对比自定义数据类型vectorPerson::iterator it find(vp.begin(), vp.end(), pp);if (it vp.end()) {cout 没有找到 endl;}else {cout 找到 it-name it.age endl;}return 0;
}总结
利用 find 可以在容器中找指定的元素返回值是迭代器当使用 find 查找自定义数据类型时要在自定义数据类型内部重载 运算符让底层 find 知道如何对比自定义数据类型
2.2 find_if
功能描述
按条件查找元素
函数原型
find_if(iterator beg, iterator end, _Pred); // 按值查找元素找到返回指定元素迭代器位置找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // _Pred 函数或者谓词返回 bool 类型的仿函数
示例
#include iostream
#include vector
#include algorithm
using namespace std;//内置数据类型仿函数
class GreaterFive
{
public:bool operator()(int val) {return val 5;}
};class Person {
public:Person(string name, int age) {this-name name;this-age age;}bool operator(const Person p) {if (this-name p.name this-age p.age) {return true;} else {return false;}}public:string name;int age;
};//自定义数据类型仿函数
class Greater20
{
public:bool operator()(Person p) {return p.age 20;}
};int main() {
//查找内置数据类型vectorint v;for (int i 0; i 10; i) {v.push_back(i);}vectorint::iterator it find_if(v.begin(), v.end(), GreaterFive());if (it v.end()) {cout 没有找到 endl;}else {cout 找到大于 5 的数字为: *it endl;}//查找自定义数据类型vectorPerson vp;Person p1(aaa, 10);Person p2(bbb, 20);Person p3(ccc, 30);Person p4(ddd, 40);vp.push_back(p1);vp.push_back(p2);vp.push_back(p3);vp.push_back(p4);Person pp(bbb, 20);vectorPerson::iterator it find(vp.begin(), vp.end(), Greater20());if (it vp.end()) {cout 没有找到 endl;}else {cout 找到 it-name it.age endl;}return 0;
}2.3 adjacent_find
功能描述
查找相邻重复元素
函数原型
adjacent_find(iterator beg, iterator end); // 查找相邻重复元素返回相邻元素的第一个位置的迭代器找不到返回结束迭代器位置。 // beg 开始迭代器 // end 结束迭代器
示例
#include iostream
#include vector
#include algorithm
using namespace std;int main() {
//查找内置数据类型vectorint v;v.push_back(0);v.push_back(2);v.push_back(0);v.push_back(3);v.push_back(1);v.push_back(4);v.push_back(3);v.push_back(3);vectorint::iterator it adjacent_find(v.begin(), v.end());if (it v.end()) {cout 没有找到相邻重复元素 endl;}else {cout 找到相邻重复元素: *it endl;}return 0;
}2.4 binary_search
功能描述
查找指定元素是否存在
函数原型
bool binary_search(iterator beg, iterator end, val); // 查找指定的元素查到返回 true否则 false // beg 开始迭代器 // end 结束迭代器 // value 查找的元素 注意容器必须是有序的序列在无序序列中不可用。如果是无序的序列结果未知 示例
#include iostream
#include vector
#include algorithm
using namespace std;int main() {
//查找内置数据类型vectorint v;for (int i 0; i 10; i) {v.push_back(i);}bool ret binary_search(v.begin(), v.end(), 9);if (ret) {cout 找到了元素! endl;}else {cout 未找到! endl;}return 0;
}总结虽然二分查找法查找效率很高但是值得注意的是查找的容器中元素必须是有序序列。
2.5 count
功能描述
统计元素个数
函数原型
count(iterator beg, iterator end, val); // 统计元素出现次数 // beg 开始迭代器 // end 结束迭代器 // value 统计的元素
示例
#include iostream
#include vector
#include algorithm
using namespace std;class Person {
public:Person(string name, int age) {this-name name;this-age age;}bool operator(const Person p) {//底层要求必须加上 const否则会报错if (this-age p.age) {return true;} else {return false;}}public:string name;int age;
};int main() {
//统计内置数据类型vectorint v;v.push_back(0);v.push_back(2);v.push_back(0);v.push_back(3);v.push_back(1);v.push_back(4);v.push_back(3);v.push_back(3);int num count(v.begin(), v.end(), 3);cout 3 的元素个数为 num endl;//统计自定义数据类型vectorPerson vp;Person p1(aaa, 10);Person p2(bbb, 20);Person p3(ccc, 20);Person p4(ddd, 40);vp.push_back(p1);vp.push_back(p2);vp.push_back(p3);vp.push_back(p4);Person pp(eee, 20);//当使用 count 查找自定义数据类型时要在自定义数据类型内部重载 运算符让底层 count 知道如何对比自定义数据类型num count(vp.begin(), vp.end(), pp);cout 和 eee 的年龄相同 的元素个数为 num endl;return 0;
}总结统计自定义数据类型的时候需要配合重载 operator
2.5 count_if
功能描述
按条件统计元素个数
函数原型
count_if(iterator beg, iterator end, _Pred); // 按条件统计元素出现次数 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词
示例
#include iostream
#include vector
#include algorithm
using namespace std;class Greater2
{
public:bool operator()(int val) {return val 2;}
};class Person {
public:Person(string name, int age) {this-name name;this-age age;}bool operator(const Person p) {//底层要求必须加上 const否则会报错if (this-age p.age) {return true;} else {return false;}}public:string name;int age;
};class AgeGreater20
{
public:bool operator()(const Person p) {return p.age 20;}
};int main() {
//统计内置数据类型vectorint v;v.push_back(0);v.push_back(2);v.push_back(0);v.push_back(3);v.push_back(1);v.push_back(4);v.push_back(3);v.push_back(3);int num count_if(v.begin(), v.end(), Greater2());cout 大于 2 的元素个数为 num endl;//统计自定义数据类型vectorPerson vp;Person p1(aaa, 10);Person p2(bbb, 20);Person p3(ccc, 20);Person p4(ddd, 40);vp.push_back(p1);vp.push_back(p2);vp.push_back(p3);vp.push_back(p4);num count(vp.begin(), vp.end(), AgeGreater20());cout age 20 的元素个数为 num endl;return 0;
}3. 常用排序算法
学习目标
掌握常用的排序算法
算法简介
sort //对容器中元素进行排序random_shuffle //洗牌 指定范围内的元素随机调整次序merge //容器元素合并并存储在另一个容器中reverse //反转指定范围内的元素
3.1 sort
功能描述
对容器内元素进行排序
函数原型
sort(iterator beg, iterator end, _Pred); // 按值查找元素找到返回指定位置迭代器找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词可以选择填或不填不填的话默认是一个从小到大的排序如果填的话会按照指定的排序规则进行排序 // 返回值是 bool 类型
示例
#include iostream
#include vector
#include algorithm
#include functional
using namespace std;class Greater2
{
public:bool operator()(int val) {return val 2;}
};//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v;v.push_back(0);v.push_back(2);v.push_back(3);v.push_back(1);v.push_back(4);sort(v.begin(), v.end());//1.默认升序排列for_each(v.begin(), v.end(), myPrint);cout endl;sort(v.begin(), v.end(), greaterint());//2.使用内建函数对象降序排列for_each(v.begin(), v.end(), myPrint);cout endl;return 0;
}总结sort 属于开发中最常用的算法之一需熟练掌握
3.2 random_shuffle
功能描述
洗牌对指定范围内的元素随机调整次序
函数原型
random_shuffle(iterator beg, iterator end); // 按值查找元素找到返回指定位置迭代器找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器
示例
#include iostream
#include vector
#include algorithm
#include ctime
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v;for (int i 0 ; i 10; i) {v.push_back(i);}//1.利用洗牌算法打乱顺序但每次打乱顺序是一样的//random_shuffle(v.begin(), v.end());//2.利用洗牌算法打乱顺序加入随机种子真实打乱srand((unsigned int)time(NULL));random_shuffle(v.begin(), v.end());for_each(v.begin(), v.end(), myPrint);cout endl;return 0;
}总结random_shuffle 洗牌算法比较实用使用时记得加随机数种子
3.3 merge
功能描述
两个容器元素合并并存储到另一个容器中
函数原型
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器 注意默认情况下两个容器必须都是升序序列合并后依然是一个升序序列如果都是降序序列的话需要在参数列表中第 6 个形参的位置填写 谓词参数 指定规则。 示例
#include iostream
#include vector
#include algorithm
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v1;for (int i 0 ; i 10; i) {v1.push_back(i);}vectorint v2;for (int i 0 ; i 10; i) {v2.push_back(i3);}vectorint vTarget;vTarget.resize(v1.size() v2.size());//提前给目标容器分配空间merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());for_each(vTarget.begin(), vTarget.end(), myPrint);cout endl;return 0;
}总结
默认情况下 merge 合并的两个容器必须都是升序序列合并后依然是一个升序序列。必须提前给目标容器分配空间
3.3 reverse
功能描述
将容器内元素进行反转
函数原型
reverse(iterator beg, iterator end); // 反转指定范围内的元素 // beg 开始迭代器 // end 结束迭代器
示例
#include iostream
#include vector
#include algorithm
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v;v.push_back(10);v.push_back(30);v.push_back(50);v.push_back(20);v.push_back(40);cout 反转前 endl;for_each(v.begin(), v.end(), myPrint);cout endl;cout 反转后 endl;reverse(v.begin(), v.end());//1.for_each(v.begin(), v.end(), myPrint);cout endl;return 0;
}总结
reverse 反转区间内元素面试题可能涉及到
4. 常用拷贝和替换算法
学习目标
掌握常用的拷贝和替换算法
算法简介
copy // 容器内指定范围的元素拷贝到另一个容器中replace // 将容器内指定范围的旧元素修改为新元素replace_if // 容器内指定范围满足条件的元素替换为新元素swap // 互换两个容器的元素
4.1 copy
功能描述
容器内指定范围的元素拷贝到另一个容器中
函数原型
copy(iterator beg, iterator end, iterator dest); // 将源容器中的数据拷贝到目标容器中 // beg 源容器的起始迭代器 // end 源容器的结束迭代器 // dest 目标容器的起始迭代器
示例
#include iostream
#include vector
#include algorithm
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v;v.push_back(10);v.push_back(30);v.push_back(50);v.push_back(20);v.push_back(40);for_each(v.begin(), v.end(), myPrint);cout endl;vectorint v2;v2.resize(v.size());//提前开辟空间copy(v.begin(), v.end(), v2.begin());//1.for_each(v2.begin(), v2.end(), myPrint);cout endl;return 0;
}总结
利用 copy 算法在拷贝时目标容器记得提前开辟空间。在实际工程中以容器直接赋值为主copy 算法拷贝使用较少。
4.2 replace
功能描述
容器内指定范围的旧元素修改为新元素
函数原型
replace(iterator beg, iterator end, oldvalue, newvalue); // 将区间内旧元素替换成新元素 // beg 开始迭代器 // end 结束迭代器 // oldvalue 旧元素 // newvalue 新元素
示例
#include iostream
#include vector
#include algorithm
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v;v.push_back(10);v.push_back(30);v.push_back(50);v.push_back(20);v.push_back(40);v.push_back(30);v.push_back(50);v.push_back(20);v.push_back(40);for_each(v.begin(), v.end(), myPrint);cout endl;replace(v.begin(), v.end(), 20, 2000);//1.for_each(v2.begin(), v2.end(), myPrint);cout endl;return 0;
}总结
replace 会替换区间内满足条件的元素
4.3 replace_if
功能描述
将区间内满足条件的元素替换成指定元素
函数原型
replace_if(iterator beg, iterator end, _pred, newvalue); // 按条件替换元素将区间内满足条件的旧元素替换成新元素 // beg 开始迭代器 // end 结束迭代器 // _pred 谓词 // newvalue 替换的新元素
示例
#include iostream
#include vector
#include algorithm
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}class Greater30 {
public:bool operator()(int val) {return val 30;}
};int main() {vectorint v;v.push_back(10);v.push_back(30);v.push_back(50);v.push_back(20);v.push_back(40);v.push_back(30);v.push_back(50);v.push_back(20);v.push_back(40);for_each(v.begin(), v.end(), myPrint);cout endl;replace_if(v.begin(), v.end(), Greater30(), 3000);//1.for_each(v2.begin(), v2.end(), myPrint);cout endl;return 0;
}总结
replace_if 按条件查找可以利用仿函数灵活筛选满足的条件
4.4 swap
功能描述
互换两个容器
函数原型
swap(container c1, container c2); // 互换两个容器 // c1容器 1 // c2容器 2 同种类型的容器才可以做交换。 示例
#include iostream
#include vector
#include algorithm
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v1;v1.push_back(10);v1.push_back(30);v1.push_back(50);v1.push_back(20);v1.push_back(40);vectorint v2;v2.push_back(300);v2.push_back(500);v2.push_back(200);v2.push_back(400);for_each(v1.begin(), v1.end(), myPrint);cout endl;for_each(v2.begin(), v2.end(), myPrint);cout endl;swap(v1, v2);//1.for_each(v1.begin(), v1.end(), myPrint);cout endl;for_each(v2.begin(), v2.end(), myPrint);cout endl;return 0;
}总结
swap 交换容器时注意交换的容器要同种类型
5. 常用的算术生成算法
学习目标
掌握常用的算术生成算法
注意
算术生成算法属于小型算法使用是包含的头文件为 #include numeric
算法简介
accumulate // 计算容器元素累积总和fill // 往容器中添加元素
5.1 accumulate
功能描述
计算区间内的容器元素累计总和
函数原型
accumulate(iterator beg, iterator end, value); // 计算容器元素累积总和 // beg 开始迭代器 // end 结束迭代器 // value 初始的累加值
示例
#include iostream
#include vector
#include algorithm
#include numeric
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v;for (int i 0; i 100; i) {v.push_back(i);}for_each(v.begin(), v.end(), myPrint);cout endl;int total accumulate(v.begin(), v.end(), 0);//1.cout total total endl;return 0;
}总结
accumulate 使用时头文件注意是 numeric这个算法很实用
5.2 fill
功能描述
向容器中填充指定的元素
函数原型
fill(iterator beg, iterator end, value); // 向容器中填充元素 // beg 开始迭代器 // end 结束迭代器 // value 填充的值
示例
#include iostream
#include vector
#include algorithm
#include numeric
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v;v.resize(10);fill(v.begin(), v.end(), 100);for_each(v.begin(), v.end(), myPrint);cout endl;return 0;
}总结
利用 fill 可以将容器区间内元素填充为 指定的值。
6. 常用集合算法
学习目标
掌握常用的集合算法
算法简介
set_intersection //求两个容器的交集set_union //求两个容器的并集set_difference //求两个容器的差集
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 目标容器开始迭代器 // 返回目标容器中交集结束的迭代器 注意两个集合两个源容器必须是有序序列默认升序降序谓词。 示例
#include iostream
#include vector
#include algorithm
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v1;for (int i 0 ; i 10; i) {v1.push_back(i);}vectorint v2;for (int i 0 ; i 10; i) {v2.push_back(i3);}vectorint vTarget;vTarget.resize(min(v1.size(), v2.size()));//提前给目标容器分配空间vectorint::iterator itEnd set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());//1.返回值是目标容器中交集结束的迭代器for_each(vTarget.begin(), itEnd, myPrint);cout endl;return 0;
}总结
求交集的两个集合两个源容器必须是有序序列默认升序降序谓词。目标容器开辟空间需要从两个容器中取小值set_intersection 返回值 是交集中最后一个元素的下一个位置在遍历交集的时候使用返回值的迭代器。
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 目标容器开始迭代器 // 返回目标容器中并集结束的迭代器 注意两个集合两个源容器必须是有序序列默认升序降序谓词。 示例
#include iostream
#include vector
#include algorithm
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v1;for (int i 0 ; i 10; i) {v1.push_back(i);}vectorint v2;for (int i 0 ; i 10; i) {v2.push_back(i3);}vectorint vTarget;vTarget.resize(v1.size() v2.size());//提前给目标容器分配空间vectorint::iterator itEnd set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());//1.返回值是目标容器中并集结束的迭代器for_each(vTarget.begin(), itEnd, myPrint);cout endl;return 0;
}总结
求并集的两个集合两个源容器必须是有序序列默认升序降序谓词。目标容器开辟空间需要两个容器相加set_union 返回值 是并集中最后一个元素的下一个位置在遍历并集的时候使用返回值的迭代器。
6.3 set_difference
功能描述
求两个容器的差集 v1 和 v2 容器的差集v1 - v1 ∩ v2 v2 和 v1 容器的差集v2 - v1 ∩ v2 函数原型
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 求两个容器的差集 // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器 // 返回目标容器中差集结束的迭代器 注意两个集合两个源容器必须是有序序列默认升序降序谓词。 示例
#include iostream
#include vector
#include algorithm
using namespace std;//普通函数遍历
void myPrint(int val) {cout val ;
}int main() {vectorint v1;for (int i 0 ; i 10; i) {v1.push_back(i);}vectorint v2;for (int i 0 ; i 10; i) {v2.push_back(i3);}vectorint vTarget;vTarget.resize(max(v1.size(), v2.size()));//提前给目标容器分配空间cout v1 和 v2 的差集是 endl;vectorint::iterator itEnd set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());//1.返回值是目标容器中差集结束的迭代器for_each(vTarget.begin(), itEnd, myPrint);cout endl;cout v2 和 v1 的差集是 endl;vectorint::iterator itEnd set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());//2.返回值是目标容器中差集结束的迭代器for_each(vTarget.begin(), itEnd, myPrint);cout endl;return 0;
}总结
求差集的两个集合两个源容器必须是有序序列默认升序降序谓词。目标容器开辟空间需要从两个容器中取较大值set_difference 返回值 是差集中最后一个元素的下一个位置在遍历差集的时候使用返回值的迭代器。
