alin的学习之路（STL篇：三）(仿函数，常见算法)

1. 函数对象（仿函数）

函数对象 超出了普通函数的概念，可以拥有自己的状态

class myPrint { public: void operator()(int num) { cout << num << endl; m_Count++; } int m_Count = 0; }; void test01() { myPrint p; p(10); p(20); p(30); p(40); //函数对象 超出了普通函数的概念，可以拥有自己的状态 cout << "打印次数：" << p.m_Count << endl; }

函数对象可以做函数参数

class myPrint { public: void operator()(int num) { cout << num << endl; m_Count++; } int m_Count = 0; }; void print(myPrint p, int num) { p(num); } int main() { print(myPrint(), 10); system("pause"); return EXIT_SUCCESS; }

2.谓词

概念：返回值为bool的仿函数或者回调函数被称为谓词

一元谓词：函数参数只有一个

//返回值为bool的仿函数称为谓词 class GreaterThen20 { public: bool operator()(int val) { return val > 20; } }; //一元谓词 void test01() { vector<int> v; v.push_back(10); v.push_back(20); v.push_back(30); v.push_back(40); //找到第一个大于20的迭代器 //pred需要填入谓词 vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterThen20()); if (it == v.end()) { cout << "未找到" << endl; } else { cout << "找到了元素：" << *it << endl; } }

二元谓词：函数参数有两个

class myCompare { public: bool operator()(int val1, int val2) { return val1 > val2; } }; //二元谓词 void test02() { vector<int> v; v.push_back(10); v.push_back(20); v.push_back(30); v.push_back(40); //降序排序 sort(v.begin(), v.end(), myCompare()); for_each(v.begin(), v.end(), [](int val) {cout << val << endl; }); }

3.内建函数对象

template T negate 取反仿函数

//template<class T> T negate<T>//取反仿函数 void test01() { negate<int> n; cout << n(10) << endl; }

template T plus 加法仿函数

//template<class T> T plus<T>//加法仿函数 void test02() { plus<int> pl; cout << pl(10, 20) << endl; }

template bool greater 大于

//template<class T> bool greater<T>//大于 void test03() { vector<int>v; v.push_back(10); v.push_back(20); v.push_back(40); v.push_back(30); v.push_back(50); //降序 sort(v.begin(), v.end(), greater<int>()); for_each(v.begin(), v.end(), [](int val) {cout << val << " "; }); cout << endl; }

template bool logical_not 逻辑非

//template<class T> bool logical_not<T>//逻辑非 void test04() { vector<bool>v; v.push_back(true); v.push_back(false); v.push_back(true); v.push_back(false); for_each(v.begin(), v.end(), [](int val) {cout << val << " "; }); cout << endl; //使用transform函数搬移时，需要先做扩容，用resize vector<bool>v2; v2.resize(v.size()); //参数：源开始，源结束，目标开始，进行的操作(仿函数) transform(v.begin(), v.end(), v2.begin(), logical_not<bool>()); for_each(v2.begin(), v2.end(), [](int val) {cout << val << " "; }); cout << endl; }

4.适配器

绑定函数对象和参数

bind2nd 将函数对象与值绑定继承public binary_function<int, int, void>operator函数加const class myPrint : public binary_function<int, int, void> //<中的参数分别是operator的参数和operator的返回值> { public: void operator()(int val, int start) const { cout << val + start << endl; } }; void test01() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } int start = 0; cout << "请输入数据起始值:" << endl; cin >> start; for_each(v.begin(), v.end(), bind2nd(myPrint(),start)); } //1.bind2nd 将函数对象与值绑定 //2.继承public binary_function<int, int, void> //3.operator函数加const

取反适配器

not1继承public unary_function<int,bool>加constunary_function<>是一个参数的继承类，binary_function<>是两个参数的 class GreaterThanFive : public unary_function<int,bool> { public: bool operator()(int val) const { return val > 5; } }; //取反适配器 void test02() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } //vector<int>::iterator pos = find_if(v.begin(), v.end(), not1(GreaterThanFive())); vector<int>::iterator pos = find_if(v.begin(), v.end(), not1(bind2nd(greater<int>(),5))); if (pos == v.end()) { cout << "未找到" << endl; } else { cout << "找到了小于5的数字： " << *pos << endl; } //二元取反 sort(v.begin(), v.end(), not2(less<int>())); for_each(v.begin(), v.end(), [](int val) {cout << val << " "; }); cout << endl; }

函数指针适配器

将函数指针做适配 ptr_fun函数指针需要做绑定的话必须要先适配 //函数指针适配器 void myPrint2(int val, int start) { cout << val + start << endl; } void test03() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } cout << "请输入起始累加的值： " << endl; int start = 0; cin >> start; //将函数指针做适配 ptr_fun //函数指针需要做绑定的话必须要先适配 for_each(v.begin(), v.end(), bind2nd(ptr_fun(myPrint2),start)); }

成员函数适配器

使用成员函数，要使用成员函数适配器 //成员函数适配器 class Person { public: Person(string name, int age) { this->m_Name = name; this->m_Age = age; } void show() { cout << "姓名：" << this->m_Name << " 年龄：" << this->m_Age << endl; } void addAge() { this->m_Age++; } int m_Age; string m_Name; }; void myPrint04(Person&p) { cout << "姓名： " << p.m_Name << " 年龄： " << p.m_Age << endl; } void test04() { vector<Person>v; Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); //使用全局的回调函数 //for_each(v.begin(), v.end(), myPrint04); //使用成员函数，要使用成员函数适配器 for_each(v.begin(), v.end(), mem_fun_ref(&Person::show)); for_each(v.begin(), v.end(), mem_fun_ref(&Person::addAge)); for_each(v.begin(), v.end(), mem_fun_ref(&Person::show)); }

4.常用遍历算法

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

void myPrint(int val) { cout << val << " " ; } class MyPrint { public: void operator()(int val) { cout << val << " "; } }; void test01() { vector<int> v; for (int i = 0; i < 10; ++i) { v.push_back(i); } for_each(v.begin(), v.end(), myPrint); cout << endl; for_each(v.begin(), v.end(), MyPrint()); cout << endl; } class MyPrint2 { public: void operator()(int val) { cout << val << " "; this->m_Count++; } int m_Count; }; void test02() { vector<int> v; for (int i = 0; i < 10; ++i) { v.push_back(i); } //for_each如果用函数对象的方法，返回值是操作后的原对象 MyPrint2 mp = for_each(v.begin(), v.end(), MyPrint2()); cout << endl; cout << "打印次数：" << mp.m_Count << endl; } class MyPrint3 : public binary_function<int ,int ,void> { public: void operator()(int val,int start) const { cout << val + start << " "; } }; void test03() { vector<int> v; for (int i = 0; i < 10; ++i) { v.push_back(i); } for_each(v.begin(), v.end(), bind2nd(MyPrint3(),100)); cout << endl; }

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

class MyTransform { public: int operator()(int val) { return val + 100; } }; void test04() { vector<int> v; for (int i = 0; i < 10; ++i) { v.push_back(i); } vector<int> vTarget; vTarget.resize(10); //必须先扩容 transform(v.begin(), v.end(), vTarget.begin(), MyTransform()); for_each(vTarget.begin(), vTarget.end(), [](int val) {cout << val << " "; }); cout << endl; }

5.常用查找算法

find算法 查找元素 @param beg 容器开始迭代器 @param end 容器结束迭代器 @param value 查找的元素 @return 返回查找元素的位置

void test01() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i + 1); } vector<int>::iterator ret = find(v.begin(), v.end(), 5); if (ret == v.end()) { cout << "未找到" << endl; } else { cout << "找到了元素： " << *ret << endl; } } class Person { public: Person(string name,int age) { this->m_Name = name; this->m_Age = age; } bool operator==(const Person& p) const //注意要加上const { return p.m_Age == this->m_Age && p.m_Name == this->m_Name; } string m_Name; int m_Age; }; void test02() { vector<Person>v; Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); Person p("bbb", 20); vector<Person>::iterator ret = find(v.begin(), v.end(), p); if (ret == v.end()) { cout << "未找到" << endl; } else { cout << "找到了元素 - 姓名： " << (*ret).m_Name << " 年龄： " << ret->m_Age << endl; } }

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

class MyFindIf : public binary_function<Person*,Person*,bool> { public: bool operator()(Person* p,Person* p2) const { return p->m_Age == p2->m_Age && p->m_Name == p2->m_Name; } }; void test03() { vector<Person*>v; Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); v.push_back(&p1); v.push_back(&p2); v.push_back(&p3); v.push_back(&p4); Person* p = new Person("bbb", 20); //使用find_if确定对比的条件,可用来对比指针指向的内容 vector<Person*>::iterator ret = find_if(v.begin(), v.end(), bind2nd(MyFindIf(), p)); if (ret == v.end()) { cout << "未找到" << endl; } else { cout << "找到了元素 - 姓名：" << (*ret)->m_Name << " 年龄： " << (*ret)->m_Age << endl; } }

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

void test04() { vector<int>v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(3); v.push_back(2); vector<int>::iterator ret = adjacent_find(v.begin(), v.end()); if (ret == v.end()) { cout << "未找到" << endl; } else { cout << "找到了元素：" << *ret << endl; } }

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

void test05() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i + 1); } //使用时必须注意搜索序列是有序序列,否则会出现问题 bool ret = binary_search(v.begin(), v.end(), 2); if (ret) { cout << "找到了" << endl; } else { cout << "未找到" << endl; } }

count算法 统计元素出现次数 @param beg 容器开始迭代器 @param end 容器结束迭代器 @param value 统计的元素 @return int返回元素个数

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

class MyCount:public binary_function<int,int,bool> { public: bool operator()(int val, int n) const { return val >= n; } }; void test06() { vector<int>v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(3); v.push_back(3); v.push_back(2); v.push_back(3); int cnt = count(v.begin(), v.end(), 3); cout << cnt << endl; //int cnt2 = count_if(v.begin(), v.end(), bind2nd(greater_equal<int>(), 3)); int cnt2 = count_if(v.begin(), v.end(), bind2nd(MyCount(), 3)); cout << cnt2 << endl; }

6.常用排序算法

merge算法 容器元素合并，并存储到另一容器中 注意:两个容器必须是有序的 @param beg1 容器1开始迭代器 @param end1 容器1结束迭代器 @param beg2 容器2开始迭代器 @param end2 容器2结束迭代器 @param dest 目标容器开始迭代器

void test01() { vector<int>v1; vector<int>v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 1); } vector<int> vTarget; vTarget.resize(v1.size() + v2.size()); //注意是将两个有序序列合并成一个有序序列，前提是都有序 merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin()); for_each(vTarget.begin(), vTarget.end(), [](int val) {cout << val << " "; }); cout << endl; }

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

void test02() { vector<int>v; v.push_back(10); v.push_back(30); v.push_back(40); v.push_back(20); v.push_back(50); sort(v.begin(), v.end()); for_each(v.begin(), v.end(), [](int val) {cout << val << " "; }); cout << endl; sort(v.begin(), v.end(),greater<int>()); for_each(v.begin(), v.end(), [](int val) {cout << val << " "; }); cout << endl; }

random_shuffle算法 对指定范围内的元素随机调整次序 @param beg 容器开始迭代器 @param end 容器结束迭代器

void test03() { srand((size_t)time(NULL)); vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } random_shuffle(v.begin(), v.end()); for_each(v.begin(), v.end(), [](int val) {cout << val << " "; }); cout << endl; }

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

void test04() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } reverse(v.begin(), v.end()); for_each(v.begin(), v.end(), [](int val) {cout << val << " "; }); cout << endl; }

7.常用拷贝和替换算法

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

void test01() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } vector<int>v2; v2.resize(v.size()); copy(v.begin(), v.end(), v2.begin()); //可以用copy算法代替for_each的遍历打印 copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " ")); cout << endl; }

replace算法 将容器内指定范围的旧元素修改为新元素 @param beg 容器开始迭代器 @param end 容器结束迭代器 @param oldvalue 旧元素 @param newvalue 新元素

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

class MyReplace { public: bool operator()(int val) { return val > 3; } }; void test02() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } replace(v.begin(), v.end(), 3, 300); copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); cout << endl; //replace_if(v.begin(), v.end(), MyReplace(), 300); replace_if(v.begin(), v.end(), bind2nd(greater<int>(),3), 300); copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); cout << endl; }

swap算法 互换两个容器的元素 @param c1容器1 @param c2容器2

void test03() { vector<int>v1; vector<int>v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i*10); } cout << "交换前v1和v2：" << endl; copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ")); cout << endl; copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " ")); cout << endl; swap(v1, v2); cout << "交换后v1和v2：" << endl; copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ")); cout << endl; copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " ")); cout << endl; }

8.常用算术生成算法

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

void test01() { vector<int>v; for (int i = 1; i <= 100; i++) { v.push_back(i); } //最后一个参数是累加的初始值 int sum = accumulate(v.begin(), v.end(), 0); cout << "sum = " << sum << endl; }

fill算法 向容器中添加元素 @param beg 容器开始迭代器 @param end 容器结束迭代器 @param value 填充元素

void test02() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } fill(v.begin(), v.end(), 0); copy(v.begin(), v.end(), ostream_iterator<int>(cout," ")); cout << endl; }

9.常用集合算法

set_intersection算法 求两个set集合的交集 注意:两个集合必须是有序序列 @param beg1 容器1开始迭代器 @param end1 容器1结束迭代器 @param beg2 容器2开始迭代器 @param end2 容器2结束迭代器 @param dest 目标容器开始迭代器 @return 目标容器的最后一个元素的迭代器地址

void test01() { vector<int>v1; vector<int>v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 5); } vector<int>vTarget; //目标容器 vTarget.resize(min(v1.size(), v2.size())); vector<int>::iterator itEnd = set_intersection(v1.begin(),v1.end(), v2.begin(), v2.end(),vTarget.begin()); copy(vTarget.begin(), itEnd, ostream_iterator<int>(cout, " ")); cout << endl; }

set_union算法 求两个set集合的并集 注意:两个集合必须是有序序列 @param beg1 容器1开始迭代器 @param end1 容器1结束迭代器 @param beg2 容器2开始迭代器 @param end2 容器2结束迭代器 @param dest 目标容器开始迭代器 @return 目标容器的最后一个元素的迭代器地址

void test02() { vector<int>v1; vector<int>v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 5); } vector<int>vTarget; //目标容器 vTarget.resize(v1.size()+v2.size()); vector<int>::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin()); copy(vTarget.begin(), itEnd, ostream_iterator<int>(cout, " ")); cout << endl; }

set_difference算法 求两个set集合的差集 注意:两个集合必须是有序序列 @param beg1 容器1开始迭代器 @param end1 容器1结束迭代器 @param beg2 容器2开始迭代器 @param end2 容器2结束迭代器 @param dest 目标容器开始迭代器 @return 目标容器的最后一个元素的迭代器地址

void test03() { vector<int>v1; vector<int>v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 5); } vector<int>vTarget; //目标容器 vTarget.resize(max(v1.size() , v2.size())); vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin()); copy(vTarget.begin(), itEnd, ostream_iterator<int>(cout, " ")); cout << endl; }