网站导航
> 文章列表 > c++常见算法

c++常见算法

网友: 文章列表 2024-03-21 23:19:13

c++常见算法

目录

1、常见遍历算法

1.1、for_each遍历算法

1.2、、transform算法

 2、常见的查找算法

2.1、find 算法查找元素

2.1.1、find 算法查找基本类型

2.1.2、find 算法查找自定义类型

2.2、find_if 按照条件查找

2.3、adjacent_find算法 查找相邻重复元素

2.4、binary_search算法 二分查找法

2.5、count算法 统计元素出现次数

​编辑 

2.6、count_if算法 统计元素出现次数

3、常用的排序算法

3.1、merge算法 容器元素合并

3.2、sort算法 容器元素排序  

3.3、random_shuffle算法 对指定范围内的元素随机调整次序

​编辑

3.4、reverse算法 反转指定范围的元素

4、常见拷贝替换算法

4.1、copy算法

4.2、copy算法升级

4.3、replace算法  

​编辑

4.4、 replace_if算法

4.4.1、使用标准模板库中的内建函数对象

4.4.2、使用自定义函数对象（仿函数）

4.5、swap算法 

5、常见算数生成算法

5.1、accumulate算法 计算容器元素累计总和

5.2、fill算法 向容器中添加元素

6、常见的集合操作

6.1、set_intersection求两个set集合的交集

6. 2、 set_union算法 求两个set集合的并集

6.3、set_difference算法 求两个set集合的差集 

7、总结

1、常见遍历算法

1.1、for_each遍历算法 

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

其中 回调函数 _callback 可以使用  普通函数 或者 函数对象 实现

1.2、、transform算法

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

其中 回调函数 _callback 可以使用  普通函数 或者 函数对象 实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printVectorInt(vector<int> &v)
{vector<int>::iterator it;for(it=v.begin(); it!=v.end(); it++){cout<<*it<<" ";}cout<<endl;
}//回调函数 使用 普通函数完成，也可以使用函数对象完成
//回调函数中对 数据 进行需要的处理
int myTransInt01(int val)
{return val;
}void test01()
{vector<int> v1;v1.push_back(10);v1.push_back(70);v1.push_back(30);v1.push_back(50);v1.push_back(90);vector<int> v2;v2.resize(v1.size());transform(v1.begin(), v1.end(), v2.begin(), myTransInt01);printVectorInt(v2);
}int main(int argc, char *argv[])
{test01();return 0;
}

 2、常见的查找算法

2.1、find 算法查找元素


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

2.1.1、find 算法查找基本类型


void test02()
{vector<int> v1;v1.push_back(10);v1.push_back(70);v1.push_back(30);v1.push_back(50);v1.push_back(90);vector<int>::iterator ret;ret = find(v1.begin(), v1.end(), 30);if(ret != v1.end()){cout<<"查找的数据:"<<*ret<<endl;}
}int main(int argc, char *argv[])
{test02();return 0;
}

2.1.2、find 算法查找自定义类型

find 查找自定义数据类型  需要重载==


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;#include<string>
class Person
{friend void test03();
private:int num;string name;
public:Person(){}Person(int num, string name){this->num = num;this->name = name;}bool operator==(const Person &ob){return ((this->num == ob.num) && (this->name == ob.name));}
};void test03()
{vector<Person> v1;v1.push_back(Person(100,"lucy"));v1.push_back(Person(101,"bob"));v1.push_back(Person(102,"tom"));vector<Person>::iterator ret;//find 查找自定义数据类型  需要重载==ret = find(v1.begin(), v1.end(), Person(101,"bob"));if(ret != v1.end()){cout<<"查找的数据:"<<(*ret).num<<" "<<(*ret).name<<endl;}
}int main(int argc, char *argv[])
{test03();return 0;
}

如果没有重载 相等（==）运算符，则编译会报错

 也即是 find 函数查找自定义类型数据的时候，是从开始迭代器到末尾迭代器中依次将容器中的元素从头到尾取出来，然后和当前需要查找的元素一一对比，但是由于是自定义类型的数据，所以必须要重 相等（==）运算符，否则编译会报错

bool operator==(const Person &ob){return ((this->num == ob.num) && (this->name == ob.name));}

2.2、find_if 按照条件查找

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

从容器中查找出大于 30 的元素

oid test04()
{vector<int> v1;v1.push_back(10);v1.push_back(70);v1.push_back(30);v1.push_back(50);v1.push_back(90);vector<int>::iterator ret;ret = find_if(v1.begin(), v1.end(),  bind2nd(greater<int>(),30)  );if(ret != v1.end()){cout<<"查找的数据:"<<*ret<<endl;}
}int main(int argc, char *argv[])
{test04();return 0;
}

2.3、adjacent_find算法 查找相邻重复元素 


void test05()
{vector<int> v1;v1.push_back(10);v1.push_back(20);v1.push_back(20);v1.push_back(30);v1.push_back(30);vector<int>::iterator ret;ret = adjacent_find(v1.begin(),v1.end());if(ret != v1.end()){cout<<"第一个相邻重复的元素:"<<*ret<<endl;}
}int main(int argc, char *argv[])
{test05();return 0;
}

2.4、binary_search算法 二分查找法

binary_search 查找的结果和前面的查找算法的返回值不一样，前面的查找算法是迭代器，但是binary_search 查找的结果是 bool 类型

1 /*
2 注意: 在无序序列中不可用
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param value 查找的元素
6 @return bool 查找返回true 否则false
7 */
bool binary_search(iterator beg, iterator end, value);
void test06()
{vector<int> v1;v1.push_back(10);v1.push_back(70);v1.push_back(30);v1.push_back(50);v1.push_back(90);sort(v1.begin(), v1.end());bool ret;ret = binary_search(v1.begin(), v1.end(),  30);if(ret){cout<<"存在该数据"<<endl;}
}

2.5、count算法 统计元素出现次数

/*
2 @param beg 容器开始迭代器
3 @param end 容器结束迭代器
4 @param value
5 @return int返回元素个数
6 */
count(iterator beg, iterator end, value);

void test07()
{vector<int> v1;v1.push_back(10);v1.push_back(30);v1.push_back(70);v1.push_back(30);v1.push_back(90);cout<<count(v1.begin(), v1.end(), 30)<<endl;
}int main(int argc, char *argv[])
{test07();return 0;
}

2.6、count_if算法 统计元素出现次数

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

void test08()
{vector<int> v1;v1.push_back(10);v1.push_back(30);v1.push_back(70);v1.push_back(30);v1.push_back(90);cout<<count_if(v1.begin(), v1.end(), bind2nd(greater<int>(), 10) )<<endl;
}int main(int argc, char *argv[])
{test08();return 0;
}

3、常用的排序算法

3.1、merge算法 容器元素合并

merge算法 容器元素合并，并存储到另一容器中
注意:两个容器必须是有序的 
/*
2 merge算法 容器元素合并，并存储到另一容器中
3 注意:两个容器必须是有序的
4 @param beg1 容器1开始迭代器
5 @param end1 容器1结束迭代器
6 @param beg2 容器2开始迭代器
7 @param end2 容器2结束迭代器
8 @param dest 目标容器开始迭代器
9 */
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterat
or dest)
void test10()
{vector<int> v1;v1.push_back(10);v1.push_back(30);v1.push_back(50);vector<int> v2;v2.push_back(20);v2.push_back(40);v2.push_back(60);v2.push_back(70);v2.push_back(80);vector<int> v3;v3.resize(v1.size() + v2.size());merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());printVectorInt(v3);
}int main(int argc, char *argv[])
{test10();return 0;
}

3.2、sort算法 容器元素排序  

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

3.3、random_shuffle算法 对指定范围内的元素随机调整次序

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

通过随机数种子调整元素顺序

#include<stdlib.h>
#include<time.h>
void test11()
{vector<int> v1;v1.push_back(10);v1.push_back(30);v1.push_back(50);v1.push_back(70);v1.push_back(90);printVectorInt(v1);//设置随机数种子srand(time(NULL));//洗牌random_shuffle(v1.begin(), v1.end());printVectorInt(v1);
}

3.4、reverse算法 反转指定范围的元素

不管容器中的元素有没有顺序，都可以反转

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

void test12()
{vector<int> v1;v1.push_back(10);v1.push_back(30);v1.push_back(50);v1.push_back(70);v1.push_back(90);printVectorInt(v1);//洗牌reverse(v1.begin(), v1.end());printVectorInt(v1);
}int main(int argc, char *argv[])
{test12();return 0;
}

4、常见拷贝替换算法

4.1、copy算法

copy算法 将容器内指定范围的元素拷贝到另一容器中 

/*
2 copy算法 将容器内指定范围的元素拷贝到另一容器中
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param dest 目标起始迭代器
6 */
copy(iterator beg, iterator end, iterator dest)
void test13()
{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());copy(v1.begin(), v1.end(), v2.begin());printVectorInt(v2);
}int main(int argc, char *argv[])
{test13();return 0;
}

4.2、copy算法升级

#include<iterator>
void test14()
{vector<int> v1;v1.push_back(10);v1.push_back(30);v1.push_back(50);v1.push_back(70);v1.push_back(90);//第二个迭代器可以是控制台 ostream_iterator<int>(cout, " ") copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );cout<<endl;
}int main(int argc, char *argv[])
{test14();return 0;
}

4.3、replace算法  

replace算法 将容器内指定范围的旧元素修改为新元素 
/*
2 replace算法 将容器内指定范围的旧元素修改为新元素
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param oldvalue 旧元素
6 @param oldvalue 新元素
*/
replace(iterator beg, iterator end, oldvalue, newvalue)
void test15()
{vector<int> v1;v1.push_back(10);v1.push_back(30);v1.push_back(50);v1.push_back(70);v1.push_back(90);copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );cout<<endl;replace(v1.begin(), v1.end(), 30, 3000);copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );cout<<endl;
}int main(int argc, char *argv[])
{test15();}

4.4、 replace_if算法

replace_if算法 将容器内指定范围满足条件的元素替换为新元素

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

4.4.1、使用标准模板库中的内建函数对象

void test16()
{vector<int> v1;v1.push_back(10);v1.push_back(30);v1.push_back(50);v1.push_back(70);v1.push_back(90);copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );cout<<endl;replace_if(v1.begin(), v1.end(), bind2nd(greater<int>(),30), 3000);copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );cout<<endl;
}

4.4.2、使用自定义函数对象（仿函数）

class GreaterThan30
{
public:bool operator()(int value){return value>30;}
};void test16()
{vector<int> v1;v1.push_back(10);v1.push_back(30);v1.push_back(50);v1.push_back(70);v1.push_back(90);copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );cout<<endl;replace_if(v1.begin(), v1.end(), GreaterThan30() , 3000);copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );cout<<endl;
}int main(int argc, char *argv[])
{test16();return 0;
}

4.5、swap算法 

不用关心两个容器的大小

swap算法 互换两个容器的元素

/*
3 @param c1容器1
4 @param c2容器2
5 */
swap(container c1, container c2)

5、常见算数生成算法

5.1、accumulate算法 计算容器元素累计总和

accumulate算法 计算容器元素累计总和

/*
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param value累加值 （注意：求和完后 + value）
6 */
accumulate(iterator beg, iterator end, value)

5.2、fill算法 向容器中添加元素

fill算法 向容器中添加元素

/*
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param value t填充元素
6 */
fill(iterator beg, iterator end, value)
void test17()
{vector<int> v1;v1.resize(5);fill(v1.begin(), v1.end(), 10);copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );cout<<endl;
}int main(){test17();
}

6、常见的集合操作

6.1、set_intersection求两个set集合的交集

set_intersection算法 求两个set集合的交集
注意:两个集合必须是有序序列

/*
4 @param beg1 容器1开始迭代器
5 @param end1 容器1结束迭代器
6 @param beg2 容器2开始迭代器
7 @param end2 容器2结束迭代器
8 @param dest 目标容器开始迭代器
9 @return 目标容器的最后一个元素的迭代器地址
10 */
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator e
nd2,iterator dest)
void test18()
{vector<int> v1;v1.push_back(1);v1.push_back(3);v1.push_back(5);v1.push_back(7);v1.push_back(9);vector<int> v2;v2.push_back(7);v2.push_back(9);v2.push_back(11);v2.push_back(13);v2.push_back(15);vector<int> v3;    //存放交集v3.resize( min(v1.size(),v2.size()));vector<int>::iterator ret;ret = set_intersection(v1.begin(), v1.end(), v2.begin(),v2.end(), v3.begin());copy(v3.begin(), ret, ostream_iterator<int>(cout, " ") );cout<<endl;
}int main(){test18();return 0;
}

6. 2、 set_union算法 求两个set集合的并集

set_union算法 求两个set集合的并集
注意:两个集合必须是有序序列

 /*
4 @param beg1 容器1开始迭代器
5 @param end1 容器1结束迭代器
6 @param beg2 容器2开始迭代器
7 @param end2 容器2结束迭代器
8 @param dest 目标容器开始迭代器
9 @return 目标容器的最后一个元素的迭代器地址
10 */
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, it
erator dest)
void test18()
{vector<int> v1;v1.push_back(1);v1.push_back(3);v1.push_back(5);v1.push_back(7);v1.push_back(9);vector<int> v2;v2.push_back(7);v2.push_back(9);v2.push_back(11);v2.push_back(13);v2.push_back(15);vector<int> v3;    //存放并集v3.resize(v1.size()+v2.size());vector<int>::iterator ret;ret = set_union(v1.begin(), v1.end(), v2.begin(),v2.end(), v3.begin());copy(v3.begin(), ret, ostream_iterator<int>(cout, " ") );cout<<endl;
}int main(){test18();return 0;
}

6.3、set_difference算法 求两个set集合的差集 

set_difference算法 求两个set集合的差集
注意:两个集合必须是有序序列

 /*
4 @param beg1 容器1开始迭代器
5 @param end1 容器1结束迭代器
6 @param beg2 容器2开始迭代器
7 @param end2 容器2结束迭代器
8 @param dest 目标容器开始迭代器
9 @return 目标容器的最后一个元素的迭代器地址
10 */
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end
2, iterator dest)
void test18()
{vector<int> v1;v1.push_back(1);v1.push_back(3);v1.push_back(5);v1.push_back(7);v1.push_back(9);vector<int> v2;v2.push_back(7);v2.push_back(9);v2.push_back(11);v2.push_back(13);v2.push_back(15);vector<int> v3;    //存放差集v3.resize(v1.size());  //A - B ,则最大为 v1的容器大小vector<int>::iterator ret;ret = set_difference(v1.begin(), v1.end(), v2.begin(),v2.end(), v3.begin());copy(v3.begin(), ret, ostream_iterator<int>(cout, " ") );cout<<endl;
}int main(){test18();return 0;
}

7、总结

（1）、以后在 STL 中见到算法中的参数 _callback 可以使用  普通函数 或者 函数对象 实现

（2）、必须要注意 每一个 算法 的返回值的 类型

网络标签：

相关问题