网站导航
> 文章列表 > 【STL】常用算法

【STL】常用算法

网友: 文章列表 2024-03-22 02:32:13

【STL】常用算法

  • STL算法主要包含在头文件
  • 是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历、复制、修改等
  • 体积很小，只包括几个在序列上面进行简单数学运算的模板函数
  • 定义了一些模板类，用以生命函数对象

1、常用遍历算法

  • for_each //遍历容器
  • transform //在遍历的过程中可以将元素搬运到另一个容器
    for_each(first,last,function)
	vector<int>v;v.push_back(14);v.push_back(4);v.push_back(0);v.push_back(15);for_each(v.begin(),v.end(),printVal); // 利用普通函数for_each(v.begin(),v.end(),Print());  // 仿函数

transform(first,last,function)

	vector<int>v1;v1.resize(v.size());transform(v.begin(), v.end(),v1.begin(),Print());

2、常用查找算法

  • find() 查找元素
  • find_if 按照条件查找元素
  • adjacent_find 查找相邻重复元素
  • binary_search 二分查找法
  • count 统计元素个数
  • count_if 按条件统计元素个数
    1、find 查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()
class Person {
public:string name;int age;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;}}
};
void test() {Person p1("曹操",43);Person p2("曹丕",23);Person p3("曹植",4);Person p4("曹冲",13);vector<Person>v;v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);vector<Person>::iterator it = find(v.begin(), v.end(), Person("曹操",43));// 查找自定义数据类型if (it != v.end()) {cout << it->age<<" " << it->name;}else {cout << "没找到";}
}

2、find_if()，按值查找，存在返回迭代器，不存在返回结束迭代器位置

class Person {
public:string name;int age;Person(string name,int age) {this->name = name;this->age = age;}bool operator()(const Person &p) {return p.age > 120;}
};
void test04() {vector<int>v;v.push_back(23);v.push_back(3);v.push_back(2);v.push_back(32);vector<int>::iterator it = find_if(v.begin(), v.end(), CompareFive());if (it != v.end()) {cout << *it;}else {cout << "没找到";}
}
void test() {Person p1("曹操",3);Person p2("曹丕",23);Person p3("曹植",4);Person p4("曹冲",123);vector<Person>v;v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);vector<Person>::iterator it = find_if(v.begin(), v.end(), Person("你",002));// 查找自定义数据类型if (it != v.end()) {cout << it->age<<" " << it->name;}else {cout << "没找到";}
}

3、adjacent_find(first,last) 查找相邻重复元素

	vector<int>v;v.push_back(23);v.push_back(3);//v.push_back(32);v.push_back(3);v.push_back(32);vector<int>::iterator it = adjacent_find(v.begin(), v.end());if (it != v.end()) {cout << *it;  //3}else {cout << "没找到";}

4、binary_search(first,last，val) 查找指定元素，返回true或false
必须在有序序列中使用

	vector<int>v;v.push_back(23);v.push_back(3);v.push_back(22);v.push_back(3);v.push_back(32);v.push_back(5);v.push_back(9);sort(v.begin(), v.end());bool re = binary_search(v.begin(), v.end(), 5);cout << re;

5、count(first,end,val) 统计元素出现次数

void test04() {  //内置数据统计vector<int>v;v.push_back(23);v.push_back(3);v.push_back(22);v.push_back(3);v.push_back(32);v.push_back(5);v.push_back(9);int re = count(v.begin(), v.end(), 54);cout << re;
}
void test() { //自定义数据类型统计Person p1("曹操",3);Person p2("曹丕",23);Person p3("曹植",4);Person p4("曹冲",123);Person p5("曹冲",123);vector<Person>v;v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);v.push_back(p5);int re = count(v.begin(),v.end(),Person("曹冲", 123));re = count(v.begin(),v.end(),Person("曹昂", 123));cout << re;
}

6、count_if（beg,end,_pred(谓词)）按条件统计

bool compareFive(int val) {return val > 5;
}
bool compareSix(int val) {return val < 6;
}
void printVal(const Person& p) {cout << p.age<< " ";
}
class Greaterthirteen {
public:bool operator()(const Person&p) {if (p.age > 13) {return true;}else{return false;}}
};
void test04() {vector<int>v;v.push_back(23);v.push_back(3);v.push_back(22);v.push_back(3);v.push_back(32);v.push_back(5);v.push_back(9);int re = count_if(v.begin(), v.end(), compareFive);  // 大于5cout << re;re = count_if(v.begin(), v.end(), compareSix);  //小于6cout << re;
}
void test() {Person p1("曹操",3);Person p2("曹丕",23);Person p3("曹植",4);Person p4("曹冲",123);Person p5("曹冲",123);vector<Person>v;v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);v.push_back(p5);int re = count_if(v.begin(),v.end(), Greaterthirteen());for_each(v.begin(), v.end(), printVal);//re = count(v.begin(),v.end(),Person("曹昂", 123));cout << re;
}

3、常用排序算法

  • sort() 排序
  • random_shuffle() 随机调整顺序
  • merge() 合并
  • reverse() 反转容器元素
    1、sort(first,last,_Pred)
    2、random_shuffle(first,last)
	vector<int>v;v.push_back(23);v.push_back(3);v.push_back(22);v.push_back(3);v.push_back(32);v.push_back(5);v.push_back(9);sort(v.begin(), v.end());for_each(v.begin(), v.end(), printVal);random_shuffle(v.begin(),v.end());for_each(v.begin(), v.end(), printVal);

3、merge(beg1,end1,beg2,end2,dest) 将两个容器元素合并，两个容器元素必须有序（排列规则一致），且合并后仍然有序
dest为目标容器

	vector<int>v;v.push_back(23);v.push_back(3);v.push_back(22);v.push_back(3);v.push_back(32);v.push_back(5);v.push_back(9);vector<int>v1;v1.push_back(35);v1.push_back(33);v1.push_back(221);v1.push_back(3);v1.push_back(2);v1.push_back(56);v1.push_back(94);vector<int>v2;v2.resize(v1.size()+v.size());sort(v.begin(), v.end());sort(v1.begin(), v1.end());merge(v.begin(), v.end(), v1.begin(), v1.end(),v2.begin());for_each(v2.begin(), v2.end(), printVal);

4、reverse(first,last);

	sort(v.begin(), v.end());reverse(v.begin(), v.end());for_each(v.begin(), v.end(), printVal);

4、常用拷贝和替换算法

  • copy 将容器中指定元素拷贝 到另一容器中
  • replace 将容器中指定范围的旧元素修改为新元素
  • replace_if 指定条件的替换
  • swap 互换两个容器元素
    1、copy(beg,end,dest);
copy(++v.begin(), v.end(), v1.begin());

2、replace(beg,end,oldval,newval)

replace(v.begin(), v.end(), 3, 4);

3、replace(beg,end,_Pred,newval)

replace_if(v.begin(), v.end(), Greaterthirteen(), 13); // 大于13的替换为13
replace_if(v.begin(),v.end(), Greaterthirteen(),Person("曹冲",13));

4、swap(container c1,container c2)

vector<int>v1=v;
v1.push_back(43);
swap(v, v1);

5、常用算术生成算法

需要导入头文件

  • accumulate 计算容器元素累计总和
  • fill 向容器中添加元素
    1、accumulate(first,last,val) val为起始累加值
vector<int>v;
v.push_back(32);
v.push_back(3);
v.push_back(2);
v.push_back(-1);
int sum = accumulate(v.begin(),v.end(),100); // 4

2、fill(beg,end,val)

fill(v.begin(), v.end(), 1);

6、常用集合算法

  • set_intersection // 交集
  • set_union 求并集
  • set_difference 求差集
    1、set_intersection
    求两个容器的交集，两个容器必须为有序序列
vector<int>v2;
sort(v1.begin(), v1.end());
v2.resize(min(v.size(),v1.size()));
//返回值为交集的结束位置
vector<int>::iterator it = set_intersection(v.begin(),v.end(), v1.begin(),v1.end(), v2.begin());
for_each(v2.begin(),it,printVal);

2、set_union
求两个容器的并集，两个容器必须为有序序列

v2.resize(v.size()+v1.size());
vector<int>::iterator it = set_union(v.begin(),v.end(), v1.begin(),v1.end(), v2.begin());
for_each(v2.begin(),it, printVal);

3、set_difference
求两个容器的差集，两个容器必须为有序序列

v2.resize(max(v.size(),v1.size()));
vector<int>::iterator it = set_difference(v.begin(),v.end(), v1.begin(),v1.end(), v2.begin());  //求v 和 v1的差集
for_each(v2.begin(), it, printVal);
it = set_difference(v1.begin(),v1.end(), v.begin(),v.end(), v2.begin());  //求 v1和 v的差集
for_each(v2.begin(), it, printVal);
网络标签：

相关问题