C++ 算法包和源码简析
2021-04-04 本文已影响0人
zcwfeng
C++ 函数适配器
STL中定义了大量的函数对象，但是有时候需要对函数返回值进行进一步的简单计算，或者填上多余的参数，不能直接代入算法，函数适配器实现了这一功能，将一种函数对象转化为另一种符合要求的函数对象，函数适配器可以分为4大类，绑定适配器，组合适配器，指针函数适配器和成员函数适配器
标准适配器.png
直接构造STL中的函数适配器通常会导致冗长的类型声明。为简化适配器的构造，STL还提供了函数适配器辅助函数，借助于泛型自动推断技术，无须显式的类型声明便可实现函数适配器的构造
辅助函数.png
常用函数适配器
bind1st(op,value)
bind2nd(op,value)
not1(op)
not2(op)
mem_fun_ref(op)
mem_fun(op) ptr_fun(op)
1 绑定器（binder）:binder 通过把二元函数对象的一个实参绑定到一个特殊的值上，将其转 换成一元函数对象。C＋＋标准库提供两种预定义的 binder 适配器：bind1st 和 bind2nd，前 者把值绑定到二元函数对象的第一个实参上，后者绑定在第二个实参上。
2 取反器(negator):negator 是一个将函数对象的值翻转的函数适配器。标准库提供两个预定 义的 ngeator 适配器：not1 翻转一元预定义函数对象的真值,而 not2 翻转二元谓词函数的真 值。
bind2nd
bind2nd 会调用 binder2nd
所以我们这两句是等价的
bind2nd(equal_to<string>(),"CCC"));
binder2nd<equal_to<string>>(equal_to<string>(),"CCC"));
equal_to 需要两个参数，比较内容没有, 所以我们采用函数适配器传入
equals_to.jpg
现在的问题是： 没有办法把 CCC 传递给 const _Tp& __y，就没法去比较
find_if(setVar.begin(), setVar.end(), equal_to<string>("CCC"), "CCC");
使用函数适配器后，就能够 CCCC 传递给了 const _Tp& __y，
setVar.begin(), setVar.end() 会把这些元素取出来 const _Tp& __x
x == y 的比较
#include <iostream>
#include <set>
#include<algorithm>
using namespace std;
int main() {
set<string, less<string>> setVal;
setVal.insert("AAA");
setVal.insert("BBB");
setVal.insert("CCC");
for (auto it = setVal.begin(); it != setVal.end();it++) {
cout << *it << endl;
}
// find_if 查看源码
// equal_to 需要两个参数，比较内容没有，使用函数适配器解决
set<string, less<string>>::iterator iteratorResult
= find_if(setVal.begin(), setVal.end(),
// bind2nd(equal_to<string>(),"CCC"));
binder2nd<equal_to<string>>(equal_to<string>(),"CCC"));
if(iteratorResult != setVal.end()){
cout << "success" << endl;
} else {
cout << "fail" << endl;
}
return 0;
}
取反适配器
一元取反适配器 not1
继承unary_fuction<类型1，返回值类型>
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;
class MyPrint:public binary_function<int,int,void>{
public:
void operator()(int v,int start) const{
cout << "v=" << v << "start=" << start << "v+start=" << v + start << endl;
}
};
// 取反适配器
class CreateThenFive:public unary_function<int,bool>{
public:
bool operator()(int v)const{
return v > 5;
}
};
int main() {
//一元取反
vector<int>v;
for (int i = 0; i < 10; i++)
{
v.push_back(i);
}
//查找大于5的数字
//需求改为找小于5的数字
vector<int>::iterator pos1 = find_if(v.begin(),v.end(),CreateThenFive());
auto pos2 = find_if(v.begin(),v.end(),not1(CreateThenFive()));
auto pos = find_if(v.begin(),v.end(),not1(bind2nd(less<int>(),5)));
if (pos != v.end())
{
cout << "找到大于5的数字为：" <<*pos<< endl;
}
else
{
cout << "未找到" << endl;
}
return 0;
}
函数指针适配器ptr_fun
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;
void myprint(int v, int start) {
cout << v + start << endl;
}
int main() {
vector<int> v;
for (int i = 0; i < 10; i++) {
v.push_back(i);
}
//将函数指针 适配为函数对象
//ptr_fun
for_each(v.begin(), v.end(), bind2nd(ptr_fun(myprint), 100));
return 0;
}
成员函数适配器mem_fun_ref
//成员函数适配器
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Person {
public:
Person(string name, int age) {
this->m_Name = name;
this->m_Age = age;
}
void showPerson() {
cout << "成员函数中姓名：" << m_Name << "年龄：" << m_Age << endl;
}
void plusAge() {
this->m_Age += 100;
}
string m_Name;
int m_Age;
};
void MyPrintPerson(Person &p) {
cout << "姓名：" << p.m_Name << "年龄：" << p.m_Age << endl;
}
int main() {
vector <Person> v;
Person p1("aaa", 10);
Person p2("bbb", 15);
Person p3("ccc", 18);
Person p4("ddd", 40);
v.push_back(p1);
v.push_back(p2);
v.push_back(p3);
v.push_back(p4);
//成员函数适配器
//mem_fun_ref
for_each(v.begin(),v.end(),mem_fun_ref(&Person::showPerson));
for_each(v.begin(),v.end(),mem_fun_ref(&Person::plusAge));
for_each(v.begin(),v.end(),mem_fun_ref(&Person::showPerson));
for_each(v.begin(),v.end(),ptr_fun(MyPrintPerson));
return 0;
}
C++ 算法包内置源码
2.jpg
前几篇使用过for_each 并简单分析了源码，再看一个例子
STL 算法之 for_each
查看源码，根据源码自定义仿函数__F
for_eqch.jpg
#include <iostream>
#include <set>
#include<algorithm>
#include <vector>
using namespace std;
class __F{
public:
void operator()(int __first){
cout << "自定义一元谓词" << __first << endl;
}
};
int main() {
vector<int> vectorVar;
vectorVar.insert(vectorVar.begin(),1000);
vectorVar.insert(vectorVar.begin(),2000);
vectorVar.insert(vectorVar.begin(),3000);
//for_each 源码 __f 自定义反函数
for_each(vectorVar.begin(),vectorVar.end(),__F());
return 0;
}
STL 算法之 transform
先写demo，使用的时候点进transform看一眼源码，写仿函数__UnaryOperation
transform.jpg
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class __UnaryOperation{
public:
int operator()(const int __first){
cout << "自定义一元谓词" << __first << endl;
return __first + 9;
}
};
int main(){
vector<int> vectorVar;
vectorVar.insert(vectorVar.begin(),1000);
vectorVar.insert(vectorVar.begin(),2000);
vectorVar.insert(vectorVar.begin(),3000);
//for_each 源码 __f 自定义反函数
// 第三个参数接收值
transform(vectorVar.begin(),vectorVar.end(),vectorVar.begin(),__UnaryOperation());
for(auto it = vectorVar.begin();it != vectorVar.end();it++){
cout << *it << endl;
}
// 标准外部写法
vector<int> vr;
vr.resize(vectorVar.size());
transform(vectorVar.begin(),vectorVar.end(),vr.begin(),__UnaryOperation());
for(auto it = vr.begin();it != vr.end();it++){
cout << *it << endl;
}
return 0;
}
STL 算法之 find 与 find_if:查找容器内容
find 没有自定义仿函数
int main() {
vector<int> vectorVar;
vectorVar.insert(vectorVar.begin(), 10000);
vectorVar.insert(vectorVar.begin(), 20000);
vectorVar.insert(vectorVar.begin(), 30000);
vectorVar.insert(vectorVar.begin(), 40000);
// find 没有自定义仿函数
auto iteratorVar = find(vectorVar.begin(), vectorVar.end(), 40000);
if (iteratorVar != vectorVar.end()) {
cout << "查找到了" << endl;
} else {
cout << "没有找到" << endl;
}
return 0;
}
find_if 有自定义仿函数
查看源码，find和find_if. 区别在于源码的__pred 访函数
// find_if 有自定义仿函数
class __pred {
public:
int number;
__pred(int number) : number(number) {}
bool operator() (const int value) {
return number == value;
}
};
int main() {
vector<int> vectorVar;
vectorVar.insert(vectorVar.begin(), 10000);
vectorVar.insert(vectorVar.begin(), 20000);
vectorVar.insert(vectorVar.begin(), 30000);
vectorVar.insert(vectorVar.begin(), 40000);
auto it = find_if(vectorVar.begin(), vectorVar.end(), __pred(30000));
if (it != vectorVar.end()) {
cout << "查找到了" << endl;
} else {
cout << "没有找到" << endl;
}
return 0;
STL 算法之 count 与 count_if:统一该值在容器中出现的个数
看源码也是很简单
template <class _InputIterator, class _Predicate>
_LIBCPP_NODISCARD_EXT inline
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
typename iterator_traits<_InputIterator>::difference_type
count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
typename iterator_traits<_InputIterator>::difference_type __r(0);
for (; __first != __last; ++__first)
if (__pred(*__first))
++__r;
return __r;
}
示例demo:
#include <iostream>
#include <vector> // stl包
#include <algorithm> // 算法包
using namespace std;
// count 没有自定义仿函数
int main() {
vector<int> vectorVar;
vectorVar.push_back(1);
vectorVar.push_back(2);
vectorVar.push_back(3);
vectorVar.push_back(2);
vectorVar.push_back(4);
vectorVar.push_back(6);
vectorVar.push_back(8);
vectorVar.push_back(1);
int number = count(vectorVar.begin(), vectorVar.end(), 2);
cout << "等于2的个数是:" << number << endl;
// C++ 源码 函数适配器
number = count_if(vectorVar.begin(), vectorVar.end(), bind2nd(less<int>(), 2)); // 函数适配器 配合 less <
cout << "等于2的个数是:" << number << endl;
number = count_if(vectorVar.begin(), vectorVar.end(), bind2nd(greater<int>(), 2)); // 函数适配器 配合 less >
cout << "等于2的个数是:" << number << endl;
number = count_if(vectorVar.begin(), vectorVar.end(), bind2nd(equal_to<int>(), 2)); // 函数适配器 配合 less =
cout << "等于2的个数是:" << number << endl;
return 0;
}
STL 算法之 merge:把两个有序数组进行合并
#include <iostream>
#include <set>
#include<algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> vectorVar;
vectorVar.insert(vectorVar.begin(), 1000);
vectorVar.insert(vectorVar.begin(), 2000);
vectorVar.insert(vectorVar.begin(), 3000);
vector<int> vectorVar2;
vectorVar2.insert(vectorVar2.begin(), 1000);
vectorVar2.insert(vectorVar2.begin(), 2000);
vectorVar2.insert(vectorVar2.begin(), 3000);
vector<int> result;
result.resize(vectorVar.size() + vectorVar2.size());
merge(vectorVar.begin(), vectorVar.end(), vectorVar2.begin(), vectorVar2.end(), result.begin());
for (auto it = result.begin(); it != result.end(); it++) {
cout << "it = " << *it << endl;
}
return 0;
}
源码简单看一眼：
template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
merge(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
{
typedef typename iterator_traits<_InputIterator1>::value_type __v1;
typedef typename iterator_traits<_InputIterator2>::value_type __v2;
return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
}
---------------------------
merge 方法
template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
_OutputIterator
__merge(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
{
for (; __first1 != __last1; ++__result)
{
if (__first2 == __last2)
return _VSTD::copy(__first1, __last1, __result);
if (__comp(*__first2, *__first1))
{
*__result = *__first2;
++__first2;
}
else
{
*__result = *__first1;
++__first1;
}
}
return _VSTD::copy(__first2, __last2, __result);
}
最终是经过算法后，调用了copy到_result
STL 算法之 sort:排序
#include <iostream>
#include <set>
#include<algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> vectorVar;
vectorVar.push_back(1000);
vectorVar.push_back(2000);
vectorVar.push_back(3000);
vectorVar.push_back(4000);
vectorVar.push_back(3000);
sort(vectorVar.begin(), vectorVar.end(), greater<int>());
random_shuffle(vectorVar.begin(), vectorVar.end());
for (auto it = vectorVar.begin(); it != vectorVar.end(); it++) {
cout << "it = " << *it << endl;
}
return 0;
}
STL 算法之 random_shuffle:随机打乱元素的顺序
#include <iostream>
#include <vector> // stl包
#include <algorithm> // 算法包
using namespace std;
int main() {
vector<int> vectorVar; // vector默认是没有排序功能的
vectorVar.push_back(65);
vectorVar.push_back(53);
vectorVar.push_back(84);
vectorVar.push_back(11);
vectorVar.push_back(22);
vectorVar.push_back(33);
vectorVar.push_back(44);
sort(vectorVar.begin(), vectorVar.end(), less<int>());
random_shuffle(vectorVar.begin(), vectorVar.end());
// 直接打印 vectorVar容器 此时 是不是就已经排序了
for (auto itVar = vectorVar.begin(); itVar != vectorVar.end() ; itVar++) {
cout << *itVar << "\t";
}
return 0;
}
STL 算法之 copy:copy 容器 1 的元素 到 容器 2
#include <iostream>
#include <set>
#include<algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> vectorVar;
vectorVar.push_back(1000);
vectorVar.push_back(2000);
vectorVar.push_back(3000);
vectorVar.push_back(4000);
vectorVar.push_back(5000);
vector<int> result;
result.resize(vectorVar.size());
copy(vectorVar.begin(), vectorVar.end(), result.begin());
for (auto it = vectorVar.begin(); it != vectorVar.end(); it++) {
cout << "it = " << *it << endl;
}
return 0;
}
STL 算法之 replace，替换元素内容
#include <iostream>
#include <set>
#include<algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> vectorVar;
vectorVar.push_back(1000);
vectorVar.push_back(2000);
vectorVar.push_back(3000);
vectorVar.push_back(4000);
vectorVar.push_back(5000);
replace(vectorVar.begin(), vectorVar.end(), 1000,1111);
for (auto it = vectorVar.begin(); it != vectorVar.end(); it++) {
cout << "it = " << *it << endl;
}
return 0;
}
