-
Day 21：C++STL算法篇(2/2)
目录
3.lexicographical_compare:比较两个序列(类似于string的比较。)
set_symmetric_difference:对称差集（^）
一、STL排列组合算法
1.什么是上(下一个排序组合)？
2.两个方法：(会改变原容器的顺序！)
①next_permutation
下一个排序序列的组合(返回值：bool类型，有就返回true，无则返回false)->(有序组合后的)数字越来越大
②prev_permutation
上一个排序序列的组合->数字越来越小
- array<int, 3> data = { 1,2,3 };//123
- next_permutation(data.begin(), data.end());//变大一次->132
- for (auto v : data)
- {
- cout << v;
- }
- cout << endl;
- prev_permutation(data.begin(), data.end());//变小一次->123
- for (auto v : data)
- {
- cout << v;
- }
输出：
132
1233.实际应用库举例：
做算法题的时候，4个数的不重复的组合的all情况(用next则起始数字用1234，用prev则起始数字为4321)
- vector<int> vecData = { 1,2,3,4 };
- int i = 0;
- do
- {
- cout << "第 " << i + 1 << " 组合结果:";
- for (auto v : vecData)
- {
- cout << v;
- }
- cout << endl;
- i++;
- } while (next_permutation(vecData.begin(), vecData.end()));
输出：
第 1 组合结果:1234
第 2 组合结果:1243
第 3 组合结果:1324
第 4 组合结果:1342
第 5 组合结果:1423
第 6 组合结果:1432
第 7 组合结果:2134
第 8 组合结果:2143
第 9 组合结果:2314
第 10 组合结果:2341
第 11 组合结果:2413
第 12 组合结果:2431
第 13 组合结果:3124
第 14 组合结果:3142
第 15 组合结果:3214
第 16 组合结果:3241
第 17 组合结果:3412
第 18 组合结果:3421
第 19 组合结果:4123
第 20 组合结果:4132
第 21 组合结果:4213
第 22 组合结果:4231
第 23 组合结果:4312
第 24 组合结果:4321二、STL 算术算法
注：做数字操作的头文件<numeric> 以及<iterator>
1.accumulate:区间求和
三个参数->前两个参数:区间的起末，第三个是sum的初值(常为0)
- //1.求和
- vector<int> data = { 1,2,3,4,5,6,7,8,9 };
- int sum = 0;
- for (auto v : data)
- {
- sum += v;
- }
- cout << sum << endl;
- sum = 0;
- sum = accumulate(data.begin(), data.end(), 0);
- cout << sum << endl;
- sum = accumulate(data.begin(), data.end(), 100);
- cout << sum << endl;
输出：
45
45
145 //第三个参数的起始值改为了1002.partial_sum:相邻元素的和，逐步求和。
- //2.逐步求和
- vector<int> data = { 1,2,3,4,5,6,7,8,9 };
- vector<int> result(data.size());
- partial_sum(data.begin(), data.end(), result.begin());
- for (auto v : result)
- {
- cout << v<<" ";
- }
- cout << endl;
输出：1 3 6 10 15 21 28 36 45
3.inner_product:序列内积运算
注：必须要满足矩阵的乘法规则，否则会直接报错
- //3.求内积运算:矩阵乘法
- vector<int> first(4);
- vector<int> second(4);
- for (int i = 0; i < 4; i++)
- {
- first[i] = i + 1; //1 2 3 4
- second[i] = i + 1; //1 2 3 4
- }
- cout << inner_product(first.begin(), first.end(), second.begin(), 0) << endl;
输出：30 //本处用的是两个向量的内积。
4.adjacent_difference: 求相邻元素
运算方法：当前位置和前一个位置的差值
- //4.求差值
- vector<int> test = { 2,2,3,4,5,6,7,8,9 };
- adjacent_difference(test.begin(), test.end(),
- ostream_iterator<int>(cout, "\t"));
- cout << endl;
- //ostream_iterator<int>(cout, "\t") 新容器开始位置替换这个参数
输出：2 0 1 1 1 1 1 1 1
注意：本处的第三个参数应该是迭代器(正常情况保存的话，可以开一个容器vecData，那么第三个参数可写 vecData.begin()来保存)
->本处（采用流型迭代器！->也是迭代器）是为了直接打印到屏幕上！
三、STL 生成异变算法
1.for_each:迭代访问
->三个参数：起+末+子函数指针（每个元素遍历都分别按子函数进行操作）(三种写法)
- //1.for_each遍历
- vector<int> testData = { 1,2,3,4,5,6,7,8,9 };
- for_each(testData.begin(), testData.end(),
- [](int x) {cout << x << "\t"; });
- cout << endl;
- for_each(testData.begin(), testData.end(),print);
- cout << endl;
- for_each(testData.begin(), testData.end(),
- [](int& x) {x *= 2; cout << x <<"\t"; });
- cout << endl;
输出：
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
2 4 6 8 10 12 14 16 18注：此处提供了打印容器的新写法 +函数指针的处理
（不一定要是打印，也可以进行其他的操作）
2.有关fill
①fill:填充方式初始容器
区间填充 参数:起+末+需要填充的元素
- //2.fill
- vector<int> fillData(3);
- fill(fillData.begin()+2, fillData.end(), 10);
- for_each(fillData.begin(), fillData.end(),
- [](int x) {cout << x << "\t"; });/*打印容器*/
输出： 0 0 10
②fill_n:指定长度填充容器
区间填充 参数:起+填充个数num+需要填充的元素(更加灵活一点)
- //3.fill_n
- vector<int> fData(4);
- fill_n(fData.begin()+2, 2, 100);
- //开始位置，填充几个， 填的元素是什么
- for_each(fData.begin(), fData.end(),[](int x){ cout<<x<<"\t";});
输出：0 0 100 100
3.有关generate
①generate：填充容器
通过函数去复制 参数：起+末+函数指针
- vector<int> gData(4);
- generate(gData.begin(), gData.end(),[]() {return 222; });
- for_each(gData.begin(), gData.end(),[](int x) {cout << x << "\t"; });
- cout << endl;
输出： 222 222 222 222
②generate_n:填充前n个位置
通过函数去复制 参数：起+操作个数num+函数指针
- vector<int> gData(4);
- generate_n(gData.begin(),2, []() {return 111; });
- for_each(gData.begin(), gData.end(), [](int x) {cout << x << "\t"; });
输出： 111 111 0 0
4.transform：一元转换和二元转换
注：(相对于generate的区别，就是其不会改变原容器的，而是将结果进行另存)
参数：起+末+存储容器的起始+处理方式的函数指针
- //5.transform
- vector<int> testTrans = { 1,2,3,4,5,6,7,8,9 };
- vector<int> resultTrans(testTrans.size());
- transform(testTrans.begin(), testTrans.end(),
- resultTrans.begin(),[](int data) {return -data; });
- for_each(resultTrans.begin(), resultTrans.end(), [](int x) {cout << x << "\t"; });
- cout << endl;
输出： -1 -2 -3 -4 -5 -6 -7 -8 -9
四、STL 关系算法
1.equal:两容器元素是否都相同(顺序也要是相同的)
- //1.比较
- vector<int> one = { 1,2,3,4,5,6,7 };
- vector<int> two = { 1,2,3,4,5,7,6 };
- cout << boolalpha << equal(one.begin(), one.end(), two.begin()) << endl;
输出： false //vector中元素顺序不同，则两个容器的元素不相同
2.includes:是否是包含关系(必须要是有序容器)
（四个参数，两个容器的起末区间即可。）
- //2.包含关系要是有序
- vector<int> one = { 1,2,3,4,5,6,7 };
- vector<int> thrid = { 1,2,3};
- cout << boolalpha << includes(one.begin(), one.end(),
- thrid.begin(),thrid.end()) <<endl;
输出： true
若该容器不是有序的，则会报错！！
3.lexicographical_compare:比较两个序列(类似于string的比较。)
- //3.比较 第一个小于第二个就返回true
- vector<int> one = { 1,2,3,4,5,6,7 };
- vector<int> two = { 1,2,3,4,5,7,6 };
- cout << boolalpha << lexicographical_compare(one.begin(), one.end(),
- two.begin(), two.end()) << endl;
输出：true //比较 第一个小于第二个就返回true
4.求max
①max:求最大值
此地无银三百两->此函数不是给iterator设计的，不是区间内的最大值，而是比较两个参数的max值
②max_element:返回最大值的iterator
专门用于迭代器->找出这个可迭代容器的中最大值(区间内的最大值)
5.求min,原理同max，在此不过多赘述
- //test for "min" and "max"
- vector<int> one = { 1,2,3,4,5,6,7 };
- vector<int> two = { 1,2,3,4,5,7,6 };
- cout << "max:" << max(1,3) << endl;
- cout << "min:" << min(1, 2) << endl;
- cout << "Max:" << *max_element(two.begin(), two.end()) << endl;
- cout << "Min:" << *min_element(one.begin(), one.end()) << endl;
输出：
max:3
min:1
Max:7
Min:16.mismatch：找到第一个不同的位置
返回值：一个指向pair数对类型的迭代器iterator
参数：两个容器的起止位置(共四个参数)
- //4.找第一个不同地方
- vector<int> one = { 1,2,3,4,5,6,7 };
- vector<int> two = { 1,2,3,4,5,7,6 };
- cout << *mismatch(one.begin(), one.end(), two.begin(), two.end()).first << endl;
- cout << *mismatch(one.begin(), one.end(), two.begin(), two.end()).second << endl;
- //first: 第一容器不同的元素的位置
- //second: 第二个容器不同的元素的位置
输出：
6
7注：
//first: 第一容器不同的元素的位置
//second: 第二个容器不同的元素的位置五、STL集合算法
说明：参数均为5个，两个容器的起止位置(前4个)，最后一个位置是存储的位置的迭代器(当你不想保存到某个容器中的时候，可采用下面的流型迭代器写法，直接输出到屏幕上。)
- #include <iostream>
- #include <algorithm>
- #include <functional>
- #include <iterator>
- #include <vector>
- using namespace std;
- int main()
- {
- vector<int> one = { 1,2,3,4,5,6 };
- vector<int> two = { 4,5,6,7,8,9 };
- vector<int> result(one.size() + two.size());
- //1.并集
- set_union(one.begin(), one.end(), two.begin(), two.end(),
- result.begin());
- for_each(result.begin(), result.end(),
- [](int x) {if (x != 0) { cout << x << "\t"; }});
- cout << endl;
- //2.交集
- set_intersection(one.begin(), one.end(), two.begin(), two.end(),
- ostream_iterator<int>(cout, "\t")
- );
- cout << endl;
- //3.求差集
- set_difference(one.begin(), one.end(), two.begin(), two.end(),
- ostream_iterator<int>(cout, "\t"));
- cout << endl;
- //4.对称差集
- set_symmetric_difference(one.begin(), one.end(), two.begin(), two.end(),
- ostream_iterator<int>(cout, "\t"));
- cout << endl;
- return 0;
- }
输出：
1 2 3 4 5 6 7 8 9
4 5 6
1 2 3
1 2 3 7 8 9六、STL堆算法
1.是什么堆？：
(一堆数据)一定是一个完全二叉树，放在数组中是无序的，在二叉树中是有序的。2.大顶堆:
父亲节点要大于子节点(向上渗透)->出堆一定是有序的(大顶堆的出堆方式，从大到小出来。小顶堆相反)
3常用函数.
①make_heap:生成一个堆
(默认是大顶堆，默认的第三参数是计算准则less<int>->可缺省）->所以greater<int>是小顶堆
注：此处准则一定要和sort_heap的堆排序准则一致！！！！否则报错。
注：make_heap之后容器中元素的顺序就会改变(按照二叉树的方式进行排序！)
②pop_heap:出堆
把要出堆的元素放到容器的绒面，并没有真正的删除，需要手动调用容器的删除函数进行删除
③push_heap:入堆
④sort_heap:堆排序
->改变存储的容器中元素顺序 (但更常用的是popheap结合vector的pop_back方法)
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <vector>
- #include <functional>
- using namespace std;
- int main()
- {
- vector<int> data = { 1,3,19,9,4,7 };
- make_heap(data.begin(), data.end()); //默认形式是大顶堆
- for (auto v : data)
- {
- cout << v << "\t";
- }
- cout << endl;
- cout << "出堆：" << endl;
- while (!data.empty())
- {
- pop_heap(data.begin(), data.end()); //要出去的元素放到最后面
- cout << data.back() << "\t";
- data.pop_back(); //真正的删除元素
- }
- cout << endl;
- vector<int> data2 = { 1,3,19,9,4,7 };
- //less方式是大顶堆，和默认是一样的
- make_heap(data2.begin(), data2.end(), less<int>());
- //sort_heap(data2.begin(), data2.end(), greater<int>());
- //上面一句 会报错，堆排序准则一定要和生成准则一致
- vector<int> data3 = { 1,3,19,9,4,7 };
- make_heap(data3.begin(), data3.end(), greater<int>());
- sort_heap(data3.begin(), data3.end(), greater<int>());
- for (auto v : data3)
- {
- cout << v << "\t";
- }
- cout << endl;
- return 0;
- }
输出：
19 9 7 3 4 1
出堆：
19 9 7 4 3 1
19 9 7 4 3 1 -
相关阅读:
Linux下路由表的转发流程
el-table的一些样式总结
关于CLR GC调优的一些问题
初探 Vue3 新特性
Java分库分表配置
你写过的最蠢的代码是？
NIO知识总结三
【计算机网络】子网掩码、子网划分
AM@由极限的两个存在准则(定理)推导的两个重要极限
【暑期每日一题】洛谷 P7257 [COCI2009-2010#3] FILIP
- 原文地址：https://blog.csdn.net/zjjaibc/article/details/125557642
