STL常用算法

目录

1 概述

2 常用遍历算法

2.1 for_each

2.2 transform

3 常用查找算法

3.1 find

3.2 find_if

3.3 adjacent_find

3.4 binary_search

3.5 count

3.6 count_if

4 常用排序算法

4.1 sort

4.2 random_shuffle

4.3 merge

4.4 reverse

5 常用拷贝和替换算法

5.1 copy

5.2 replace

5.3 replace_if

5.4 swap

6 常用算术生成算法

6.1 accumulate

6.2 fill

7 常用集合算法

7.1 set_intersection

7.2 set_union

7.3 set_difference

1 概述

算法主要由头文件<algorithm>、<functional>、<numeric>组成

• <algorithm>：所有STL头文件中最大的，包括但不限于比较、交换、查找、遍历、复制、修改等

• <functional>：定义了一些模板类，以声明函数对象

• <numeric>：体积较小，只包括几个在序列上面进行简单数学运算的模板函数

2 常用遍历算法

目的：掌握常用的遍历算法

算法

 for_each     遍历容器
 ​
 transform    搬运容器到另一个容器中

2.1 for_each

功能： 遍历算法，遍历容器元素

 for_each(iterator begin,iterator end,func)       
 begin        起始迭代器
 end          终止迭代器
 func         函数或函数对象

根据func的不同，有不同的实现方式：

 // 1.使用普通函数
 void print1(int val)
 {
   cout << val << " ";
 }
 ​
 // 2.使用仿函数
 class print2
 {
 public:
   void operator()(int val)
   {
     cout << val << " ";
   }
 };
 int main()
 {
   vector<int> v1;
   for (int i = 0; i < 10; i++)
   {
     v1.push_back(i);
   }
   for_each(v1.begin(), v1.end(), print1);  // 传入普通函数
   cout << endl;
   for_each(v1.begin(), v1.end(), print2());// 传入匿名的函数对象
   return 0;
 }

2.2 transform

功能： 搬运容器到另一个容器中

 transform(iterator begin1,iterator end1,iterator begin2,func)
 begin1        原容器起始迭代器
 end1          原容器终止迭代器
 begin2        新容器起始迭代器
 func          函数或仿函数

根据func的不同，有不同的实现方式：

 // ①.使用普通函数
 int trans(int val)
 {
   return val;
 }
 // ②.使用仿函数
 class trans2
 {
 public:
   int operator()(int val)
   {
     return val;
   }
 };
 void test02()
 {
   vector<int> v1;
   for (int i = 0; i < 10; i++)
   {
     v1.push_back(i);
   }
   vector<int >v2; // 目标容器
   v2.resize(v1.size()); // 提前开辟空间
   transform(v1.begin(), v1.end(), v2.begin(), trans);  // 1
   transform(v1.begin(), v1.end(), v2.begin(), trans2()); // 2
   for_each(v2.begin(), v2.end(), print1);  // 传入普通函数
 }

注意：使用transform搬运容器时，一定要先确定目标容器有足够的空间，没有则要开辟

3 常用查找算法

目的：掌握常用的查找算法

算法

 find      查找目标元素
 find_if     按条件查找目标元素
 adjacent_find 查找相邻重复元素
 binary_search 二分查找法
 count     统计元素个数
 count_if    按条件统计元素个数

3.1 find

功能：查找目标元素，找到返回指定元素的迭代器，找不到返回终止迭代器end()；

 find(iterator begin.iterator end,val);
 begin    起始迭代器
 end      终止迭代器
 val      目标元素

根据查找的数据类型的不同，可以分为2类：

• ①查找内置数据类型

 void test03()
 {
   vector<int> v1;
   for (int i = 0; i < 10; i++)
   {
     v1.push_back(i);
   }
   // 查找内置数据类型
   vector<int>::iterator it = find(v1.begin(), v1.end(), 1);
   if (it == v1.end())
     cout << "没有" << endl;
   else
     cout << "有了：" << *it << endl;
 }

• ②查找自定义数据类型

自定义数据类型person

 class person
 {
 public:
   person(string name, int age)
   {
     this->m_name = name;
     this->m_age = age;
   }
   // 重载== 使find底层知道如何对比自定义数据类型
   bool operator == (const person &p)
   {
     if (p.m_name == this->m_name && p.m_age == this->m_age)
       return true;
     else
       return false;
   }
   string m_name;
   int m_age;
 };

测试

 void test04()
 {
   vector<person> v;
   person p1("Joyce", 21); person p2("Tatina", 20);
   person p3("Nna", 3);  person p4("knnz", 40);
 ​
   v.push_back(p1); v.push_back(p2);
   v.push_back(p3); v.push_back(p4);
 ​
   person p5("Nna", 3);
   vector<person>::iterator it = find(v.begin(), v.end(), p5);
   if (it == v.end())
     cout << "没有" << endl;
   else
     cout << "有了：" << it->m_name << it->m_age << endl;
 }

注意：自定义数据类型的对比，要先实现==的重载，否则编译器不知道如何对比

3.2 find_if

功能：按条件查找元素，找到返回所在位置迭代器，否则返回终止迭代器end()；

 find_if(iterator begin,iterator end,_Pred);
 begin    起始迭代器
 end      终止迭代器
 _Pred    函数或谓词(返回bool类型的仿函数)

根据查找的数据类型的不同，可以分为2类：

• ①查找内置数据类型

 // 内置数据类型
 class GreaterSix // 内置数据类型 val大于6即可
 {
 public:
   bool operator()(int val)
   {
     return val > 6;
   }
 };
 void test05()
 {
   vector<int> v;
   for (int i = 0; i < 10; i++)
   {
     v.push_back(i);
   }
   vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterSix());
   cout << *it << endl;
 }

• ②自定义数据类型

自定义数据类型person1

 class person1
 {
 public:
   person1(string name, int age)
   {
     this->m_name = name;
     this->m_age = age;
   }
   string m_name;
   int m_age;
 };

测试函数与对比函数：

 class AgeGreateTwenty // 年龄大于33即可
 {
 public:
   bool operator()(person1& p)
   {
     return p.m_age > 33;
   }
 };
 void test05_2()
 {
   vector<person1>v;
   person1 p1("Joyce", 21);person1 p2("Tatina", 20);
   person1 p3("Nna", 3); person1 p4("knnz", 40);
 ​
   v.push_back(p1); v.push_back(p2);
   v.push_back(p3); v.push_back(p4);
   vector<person1>::iterator it = find_if(v.begin(), v.end(), AgeGreateTwenty());
   if (it == v.end())
     cout << "没有" << endl;
   else
     cout << it->m_name <<it->m_age<< endl;
 }

3.3 adjacent_find

功能：查找相邻重复元素，找到返回所在位置迭代器，否则返回终止迭代器end()；

 adjacent_find(iterator begin,iterator end);
 begin    起始迭代器
 end      终止迭代器

测试：

 void test06()
 {
   vector<int> v;
   v.push_back(1); v.push_back(3); v.push_back(1);
   v.push_back(33);  v.push_back(53);  v.push_back(23);
   v.push_back(3); v.push_back(3); v.push_back(8);
   vector<int>::iterator it = adjacent_find(v.begin(), v.end());
   if (it == v.end())
     cout << "没有" << endl;
   else
     cout << *it;
 }

注意：如果是不相邻的元素，则无法查找到，必须2个挨着才行

3.4 binary_search

功能：查找指定元素是否存在，存在返回true，否则返回false

 binary_search(iterator begin,iterator end,val);
 begin    起始迭代器
 end      终止迭代器
 val      目标元素

示例：从实现从0-9找到5

 void test07()
 {
   vector<int> v;
   int i = 0;
   while (i++ < 10)
   {
     v.push_back(i);
   }
 ​
   bool it = binary_search(v.begin(), v.end(), 5);
   if (it)
     cout << "有了" << endl;
   else
     cout << "没有" << endl;
 }

注意：二分查找法要求序列必须有序且默认是升序才能用，且返回的是ture或false不是迭代器

3.5 count

功能：统计元素个数

 count(iterator begin,iterator end,val);
 begin    起始迭代器
 end      终止迭代器
 val      目标元素

根据统计的数据类型的不同，可以分为2类：

• ①内置数据类型

 void test08()
 {
   vector<int> v;
   v.push_back(1); v.push_back(3); v.push_back(1);
   v.push_back(33);  v.push_back(53);  v.push_back(23);
   v.push_back(3); v.push_back(3); v.push_back(8);
 ​
   int ret = count(v.begin(), v.end(), 3);
   cout << ret << endl;
 }

• ②自定义数据类型

自定义数据类型，要加上==的重载使编译器知道如何对比

 class person
 {
 public:
   person(string name, int age)
   {
     this->m_name = name;
     this->m_age = age;
   }
   // 重载== 使find底层知道如何对比自定义数据类型
   bool operator == (const person &p)
   {
     if (p.m_name == this->m_name && p.m_age == this->m_age)
       return true;
     else
       return false;
   }
   string m_name;
   int m_age;
 };

测试 

 void test08_2()
 {
   vector<person> v;
   person p1("Joyce", 21); person p2("Tatina", 20);
   person p3("Nna", 3);  person p4("knnz", 40);
   person p6("Nna", 3);
   v.push_back(p1); v.push_back(p2);
   v.push_back(p3); v.push_back(p4); v.push_back(p6);
   person p5("Nna", 3);
   int ret = count(v.begin(), v.end(), p5);
   cout <<"与p5同名同姓的人员个数为："<< ret << endl;
 }

3.6 count_if

功能：按条件统计元素个数

 count_if(iterator begin,iterator end,_Pred);
 begin    起始迭代器
 end      终止迭代器
 _Pred    谓词（条件）

根据统计的数据类型的不同，可以分为2类：

• ①内置数据类型

 class GreaterFive // 大于5的谓词
 {
 public:
   bool operator()(int val)
   {
     return val > 5;
   }
 };
 void test09_1()
 {
   vector<int> v;
   v.push_back(1); v.push_back(3); v.push_back(1);
   v.push_back(33);v.push_back(53);  v.push_back(23);
   v.push_back(3); v.push_back(3); v.push_back(8);
 ​
   int ret = count_if(v.begin(), v.end(), GreaterFive());
   cout << "大于5的数字有 " << ret << " 个" << endl;
 }

• ②自定义数据类型

自定义数据类型person，以及大于20岁的谓词

 class person
 {
 public:
   person(string name, int age)
   {
     this->m_name = name;
     this->m_age = age;
   }
   // 重载== 使find底层知道如何对比自定义数据类型
   bool operator == (const person &p)
   {
     if (p.m_name == this->m_name && p.m_age == this->m_age)
       return true;
     else
       return false;
   }
   string m_name;
   int m_age;
 };

 class Greater20 // 年龄大于20
 {
 public:
   bool operator()(const person& p)
   {
     if (p.m_age > 20)
       return true;
     else
       return false;
   }
 };
 void test09_2()
 {
   vector<person> v;
   person p1("Joyce", 21); person p2("Tatina", 20);
   person p3("Nna", 3);  person p4("knnz", 40);
   person p5("Bbyeaz", 33);
   v.push_back(p1); v.push_back(p2);
   v.push_back(p3); v.push_back(p4); v.push_back(p5);
 ​
   int ret = count_if(v.begin(), v.end(),Greater20());
   cout << "大于20岁的人员个数为：" << ret << endl;
 }

4 常用排序算法

目的：掌握常用的排序算法

算法

 sort      对容器内元素进行排序
 random_shuffle  洗牌，对指定范围内元素随即调整次序
 merge     容器元素合并，并存储至另一容器中
 reverse     反转指定范围内元素

4.1 sort

功能：对容器内元素进行排序

 sort(iterator begin,iterator end,_Pred);
 begin    起始迭代器
 end      终止迭代器
 _Pred    谓词（条件，不填则是升序）

测试

 void test10()
 {
   vector<int> v;
   v.push_back(1); v.push_back(3); v.push_back(2);
   v.push_back(33); v.push_back(53); v.push_back(23);
   v.push_back(5); v.push_back(4); v.push_back(8);
   
   // 升序-默认
   sort(v.begin(), v.end());
   for_each(v.begin(), v.end(), print2());
   cout << endl;
   // 降序-重载
   sort(v.begin(), v.end(), greater<int>()); // greater 内建函数对象
   for_each(v.begin(), v.end(), print2());
 }

4.2 random_shuffle

功能：洗牌，指定范围内元素随机调整次序

 random_shuffle(iterator begin,iterator end);
 begin    起始迭代器
 end      终止迭代器

只需提供起始迭代器与终止迭代器即可

 void test11()
 {
   srand((unsigned)time(NULL)); // 随机数种子
   vector<int> v;
   int i = 0;
   while (i++ < 10)
   {
     v.push_back(i);
   }
   for_each(v.begin(), v.end(), print2());
   cout << endl;
   random_shuffle(v.begin(), v.end()); // 洗牌
   for_each(v.begin(), v.end(), print2());
 }

4.3 merge

功能：将两个容器元素合并，并存储到另一个容器中

 merge(iterator begin1,iterator end1,iterator begin2,iterator end2,iterator dest);
 begin1    容器1起始迭代器
 end1      容器1终止迭代器
 begin2    容器2起始迭代器
 end2      容器2终止迭代器
 dest      目标存储迭代器

一共需要3个容器

 void test12()
 {
   vector<int> v;
   vector<int> v2;
   int i = 0;
   while (i++ < 5)
   {
     v.push_back(i);
     v2.push_back(i+6);
   }
 ​
   vector<int>v3;
   v3.resize(v.size() + v2.size()); // 给目标容器开辟空间
   merge(v.begin(), v.end(), v2.begin(), v2.end(), v3.begin());
   for_each(v3.begin(), v3.end(), print2());
 }

注意：

• 原始的2个容器必须是有序的

• 使用merge前必须给目标容器开辟足够的空间

4.4 reverse

功能：将范围内元素反转

 reverse(iterator begin,iterator end);
 begin    起始迭代器
 end      终止迭代器

测试

 void test13()
 {
   vector<int> v;
   int i = 0;
   while (i++ < 10)
   {
     v.push_back(i);
   }
   for_each(v.begin(), v.end(), print2());
   cout << endl;
   reverse(v.begin(), v.end());
   for_each(v.begin(), v.end(), print2());
 }

5 常用拷贝和替换算法

目的：掌握常用的拷贝和替换算法

算法

 copy        容器内指定范围内的元素拷贝到另一容器中
 replace     将容器中指定范围内的元素替换为新的元素
 replace_if  容器内指定范围内满足条件的元素替换为新的元素
 swap        交换2个相同类型容器的元素

5.1 copy

功能：将容器指定范围内元素拷贝到另一容器中

 copy(iterator begin1,iterator end1,iterator dest);
 begin1    容器1起始迭代器
 end1      容器1终止迭代器
 dest      目标存储迭代器

测试

 void test14()
 {
   vector<int> v;
   int i = 0;
   while (i++ < 10)
   {
     v.push_back(i);
   }
   vector<int> v2;
   v2.resize(v.size());
   copy(v.begin(), v.end(), v2.begin());
   for_each(v2.begin(), v2.end(), print2());
 }

注意：提前给目标容器开辟空间

5.2 replace

功能：将容器中指定范围内的所有指定元素替换为新的元素

 replace(iterator begin,iterator end,oldval,newval);
 begin     起始迭代器
 end       终止迭代器
 oldval    旧元素
 newval    新元素

测试

 void test15()
 {
   vector<int> v;
   v.push_back(1); v.push_back(3); v.push_back(2);
   v.push_back(3); v.push_back(53);  v.push_back(23);
   v.push_back(3); v.push_back(4); v.push_back(8);
   for_each(v.begin(), v.end(), print2());
   cout << endl;
   replace(v.begin(), v.end(), 3, 888);
   for_each(v.begin(), v.end(), print2());
 }

5.3 replace_if

功能：容器内指定范围内满足条件的元素替换为新的元素

 replace_if(iterator begin,iterator end,_Pred,newval);
 begin     起始迭代器
 end       终止迭代器
 _Pred     谓词
 newval    新元素

示例：大于6的值替换为888

谓词GreaterSix

 class GreaterSix // 内置数据类型 val大于6即可
 {
 public:
   bool operator()(int val)
   {
     return val > 6;
   }
 };

测试

 void test16()
 {
   vector<int> v;
   v.push_back(1); v.push_back(3); v.push_back(2);
   v.push_back(3); v.push_back(53);  v.push_back(23);
   v.push_back(3); v.push_back(4); v.push_back(8);
   for_each(v.begin(), v.end(), print2());
   cout << endl;
   replace_if(v.begin(), v.end(), GreaterSix(), 888);
   for_each(v.begin(), v.end(), print2());
 }

5.4 swap

功能：交换2个相同类型容器的元素

 swap(container c1,container c2);
 c1    容器1
 c2    容器2

测试

 void test17()
 {
   vector<int> v;
   vector<int> v2;   int i = 0;
   while (i++ < 10)
   {
     v.push_back(i);
     v2.push_back(i+16);
   }
   cout << "交换前：" << endl;
   for_each(v.begin(), v.end(), print2()); cout << endl;
   for_each(v2.begin(), v2.end(), print2());
   cout << endl;  cout << "交换后：" << endl;
   swap(v, v2);
   for_each(v.begin(), v.end(), print2()); cout << endl;
   for_each(v2.begin(), v2.end(), print2());
 }

6 常用算术生成算法

目的：掌握常用的算术生成算法

算法

 accumulate    计算容器元素累计总和
 fill          向容器中添加指定元素

注意：该算法属于小型算法，要包含头文件<numeric>

6.1 accumulate

功能：将容器指定范围内元素拷贝到另一容器中

 accumulate(iterator begin,iterator end,val);
 begin     起始迭代器
 end       终止迭代器
 val       起始值

测试

 void test18()
 {
   vector<int> v;
   int i = 0;
   while (i++ < 100)
   {
     v.push_back(i);
   }
   int num = accumulate(v.begin(), v.end(),0);
   //  0是起始值，即num=总和+0；如果是1000，即num=总和+1000
   cout << num;
 }

6.2 fill

功能：向容器中添加指定元素

 fill(iterator begin,iterator end,val);
 begin     起始迭代器
 end       终止迭代器
 val       要填充的值

测试

 void test19()
 {
   vector<int> v;
   int i = 0;
   while (i++ < 10)
   {
     v.push_back(i);
   }
   for_each(v.begin(), v.end(), print1); cout << endl;
   fill(v.begin() + 1, v.end() - 1, 888);
   for_each(v.begin(), v.end(), print1);
 }

7 常用集合算法

目的：掌握常用的集合算法

算法

 set_intersection  求两个容器的交集
 set_union         求两个容器的并集
 set_difference    求两个容器的差集

注意：该算法属于小型算法，要包含头文件<numeric>

7.1 set_intersection

功能：求两个容器的交集

 set_intersection(iterator begin1,iterator end1,iterator begin2,iterator end2,iterator dest);
 begin1    容器1起始迭代器
 end1      容器1终止迭代器
 begin2    容器2起始迭代器
 end2      容器2终止迭代器
 dest      目标存储迭代器

首先，容器交集有2种情况：

我们直接取全包的情况的大小为目标容器开辟空间，因为空间只能比他小，不会更大

 void test20()
 {
   vector<int> v;
   vector<int> v2;
   int i = 0;
   while (i++ < 8)
   {
     v.push_back(i);   // 1-8
     v2.push_back(i + 3);// 4-11
   }
   for_each(v.begin(), v.end(), print2()); cout << endl; for_each(v2.begin(), v2.end(), print2());
   vector<int>v3;
   v3.resize(min(v.size(), v2.size())); // 给目标容器开辟空间
   vector<int>::iterator itEnd = set_intersection(v.begin(), v.end(), v2.begin(), v2.end(), v3.begin());
   // 返回容器里最后一个数据的迭代器
   cout << endl;
   for_each(v3.begin(), itEnd, print2());
 }

注意：

• set_intersection函数返回的是目标容器插完数据后最后一个数据的迭代器

• 原2容器必须是有序的

• 新容器大小取原容器中较小的size

7.2 set_union

功能：求两个容器的并集

 set_union(iterator begin1,iterator end1,iterator begin2,iterator end2,iterator dest);
 begin1    容器1起始迭代器
 end1      容器1终止迭代器
 begin2    容器2起始迭代器
 end2      容器2终止迭代器
 dest      目标存储迭代器

首先，容器并集有2种情况：

 void test21()
 {
   vector<int> v;
   vector<int> v2;
   int i = 0;
   while (i++ < 8)
   {
     v.push_back(i);   // 1-8
     v2.push_back(i + 3);// 4-11
   }
   for_each(v.begin(), v.end(), print2()); cout << endl; for_each(v2.begin(), v2.end(), print2());
   vector<int>v3;
   v3.resize(v.size() + v2.size()); // 给目标容器开辟空间
   vector<int>::iterator itEnd = set_union(v.begin(), v.end(), v2.begin(), v2.end(), v3.begin());
   // 返回容器里最后一个数据的迭代器
   cout << endl;
   for_each(v3.begin(), itEnd, print2());
 }

注意：

• set_union函数返回的是目标容器插完数据后最后一个数据的迭代器

• 原2容器必须是有序的

• 新容器大小取原2容器size之和

7.3 set_difference

功能：求两个容器的差集

 set_difference(iterator begin1,iterator end1,iterator begin2,iterator end2,iterator dest);
 begin1    容器1起始迭代器
 end1      容器1终止迭代器
 begin2    容器2起始迭代器
 end2      容器2终止迭代器
 dest      目标存储迭代器

首先，容器差集有2种情况：

而根据v1和v2的相交程度的不同，大小也有不同的取值：

 void test22()
 {
   vector<int> v;
   vector<int> v2;
   int i = 0;
   while (i++ < 8)
   {
     v.push_back(i);   // 1-8
     v2.push_back(i + 3);// 4-11
   }
   for_each(v.begin(), v.end(), print2()); cout << endl; for_each(v2.begin(), v2.end(), print2());
   vector<int>v3;
   v3.resize(max(v.size(), v2.size())); // 给目标容器开辟空间
   cout << endl;
   vector<int>::iterator itEnd = set_difference(v.begin(), v.end(), v2.begin(), v2.end(), v3.begin());
   // 返回容器里最后一个数据的迭代器
   cout << "v1和v2的差集："<<endl;
   for_each(v3.begin(), itEnd, print2());  cout << endl;
   cout << "v2和v1的差集：" << endl;
   itEnd = set_difference(v2.begin(), v2.end(), v.begin(), v.end(), v3.begin());
   for_each(v3.begin(), itEnd, print2());  cout << endl;
 }

注意：

• set_difference函数返回的是目标容器插完数据后最后一个数据的迭代器

• 原2容器必须是有序的

• 新容器大小取原容器中较大的size文章来源地址https://www.toymoban.com/news/detail-478205.html

到了这里，关于STL常用算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！