C++STL标准库学习笔记(十三)算法(上)

2022/2/1 17:42:03

本文主要是介绍C++STL标准库学习笔记(十三)算法(上),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前言:

  在这个笔记中,我把大多数代码都加了注释,我的一些想法和注解用蓝色字体标记了出来,重点和需要关注的地方用红色字体标记了出来。

  在这一篇文章中,我们主要对STL中的算法进行简单的介绍。

正文:

1. STL算法分类

  STL中的算法大致可以分为以下七类:

  不变序列算法

  变值算法

  删除算法

  变序算法

  排序算法

  有序区间算法

  数值算法

2. STL算法

  大多数重载算法都是有两个版本的

    用“==”判断元素是否相等,或用“<”来比较大小

    多出一个类型参数“pred”和函数形参“pred op”:

    通过判断表达式“op(x,y)”的返回值:true/false

  来判断x是否“等于”y,或者x是否“小于”y

  如有下列两个版本的min_element:
  iterator min_element(iterator first, iterator last);

  iterator min_element(iterator first, iterator last, Pred op);

  (其实不就是多了一个要传入的比较规则嘛)

2.1. 不变序列算法

  该类算法不会修改算法所作用的容器或对象

  适用于顺序容器和关联容器

  时间复杂度都是O(n)

  min:求两个对象中较小的(可自定义比较器)

  max:求两个对象中较大的(可自定义比较器)

  min_element: 求区间中的最小值(可自定义比较器)

  max_element: 求区间中的最大值(可自定义比较器)

  for_each: 对区间中的每个元素都做某种操作

  count: 计算区间中等于某值的元素个数

  count_if: 计算区间中符合某种条件的元素个数

  find: 在区间中查找等于某值的元素

  find_if: 在区间中查找符合某条件的元素

  find_end: 在区间中查找另一个区间最后一次出现的位置(可自定义比较器)

  find_first_of: 在区间中查找第一个出现在另一个区间中的元素(可自定义比较器)

  adjacent_find: 在区间中寻找第一次出现连续两个相等元素的位置(可自定义比较器)

  search: 在区间中查找另一个区间第一次出现的位置(可自定义比较器)

  search_n: 在区间中查找第一次出现等于某值的连续n个元素(可自定义比较器)

  equal: 判断两区间是否相等(可自定义比较器)

  mismatch: 逐个比较两个区间的元素,返回第一次发生不相等的两个元素的位置(可自定义比较器)

  lexicographical_compare: 按字典序比较两个区间的大小(可自定义比较器)

  find:

  template<class init, class T>

  init find(init first, init last, const T& val);

  返回[first,last)中的迭代器i,使得*i==val

  find_if:

  templast<class init, class Pred>

  init find_if(init first, init last, pred pr);

  返回区间[first, last)中的迭代器i,使得pr(*i)==true

  (所以说传进来的pr是个函数?查了一下,传入的是一个一元谓词,即只带一个参数且返回值限定为bool的函数对象)

  for_each:

  template<class init, class Fun>

  Fun for_each(init first, init last, Fun f);

  对[first, last)中的每个元素e,执行f(e),要求f(e)不能改变e

  count:

  template<class init, class T>

  size_t count(init first, init last, const T& val);

  计算[first, last)中等于val的元素个数(x==y为true算等于)

  count_if:

  template<class init, class Pred>

  size_t count_if(init first, init last, Pred pr);

  计算[first, last)中符合pr(e)==true的元素e的个数

  (用法感觉和find_if差不多)

  min_element:

  template<class Fwdlt>

  Fwdlt min_element(Fwdlt first, Fwdlt last);

  返回[first, last)中最小元素的迭代器,以“<”作比较器

  最小指没有元素比它小,而不是它比别的不同元素都小

  因为即使a!=b,a<b和b<a有可能都不成立

  max_element:

  template<class Fwdlt>

  Fwdlt max_element(Fwdlt first, Fwdlt last);

  返回[first, last)中最大元素(不小于任何其他元素)的迭代器

  也是以“<”作比较器

  样例:

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 class A
 5 {
 6 public:
 7     int n;
 8     A(int i):n(i){}
 9 };
10 bool operator<(const A & a1, const A & a2)
11 {
12     cout<<"< called"<<endl;
13     if (a1.n==3&&a2.n==7)
14     {
15         return true;
16     }
17     return false;
18 }
19 int main(int argc, char const *argv[])
20 {
21     A aa[] = {3,5,7,2,1};
22     cout<<min_element(aa,aa+5)->n<<endl;
23     cout<<max_element(aa,aa+5)->n<<endl;
24     return 0;
25 }
26 /*
27 输出:
28 < called
29 < called
30 < called
31 < called
32 3
33 < called
34 < called
35 < called
36 < called
37 7
38 */

  (这里假设第一个元素是最小值,然后逐个比较,发现第一个在定义的“<”下真是最小值,结果就是3,第二种情况就是发现3<7,结果就是7)

2.2. 变值算法

  此类算法会修改源区间或目标区间元素的值

  值被修改的那个区间,不可以是属于关联容器的(因为若修改了的话,关联容器的有序性就被打破了)

  for_each:对区间中的每个元素都做某种操作(与前面的不同就是传入的函数参数是不是const的)

  copy:复制一个区间到别处

  copy_backward:复制一个区间到别处,但目标区间是从后往前被修改的

  transform:将一个区间的元素变形后拷贝到另一个区间

  swap_ranges:交换两个区间内容

  fill:用某个值填充区间

  fill_n:用某个值替换区间中的n个元素

  generate:用某个操作的结果填充区间

  generate_n:用某个操作的结果替换区间中的n个元素

  replace:将区间中的某个值替换成另一个值

  replace_if:将区间中符合某种条件的值替换成另一个值

  replace_copy:将一个区间拷贝到另一个区间,拷贝时某个值要换成新值拷过去

  replace_copy_if:将一个区间拷贝到另一个区间,拷贝时符合某条件的值要换成新值拷过去

transform:

  template<class init, class Outit, class Unop>

  Outit transform(init first, init last, outit x, Unop uop);

  对[first, last)中的每个迭代器l,

    执行uop(*i);并将结果依次放入从x开始的地方

    要求uop(*i)不得改变*i的值

  本模板返回值是个迭代器,即x+(last-first)

    x可以和first相等

  样例:(包含了前面和没说的一些东西)

 1 #include<vector>
 2 #include<iostream>
 3 #include<numeric>
 4 #include<list>
 5 #include<algorithm>
 6 #include<iterator>
 7 using namespace std;
 8 class CLessThen9
 9 {
10 public:
11     bool operator()(int n){return n < 9;}
12 };
13 void outputSquare(int value){cout<<value*value<<" ";}
14 int calculateCube(int value){return value*value*value;}
15 
16 int main(int argc, char const *argv[])
17 {
18     const int SIZE = 10;
19     int a1[] = {1,2,3,4,5,6,7,8,9,10};
20     int a2[] = {100,2,8,1,50,3,8,9,10,2};
21     vector<int> v(a1,a1+SIZE);
22     ostream_iterator<int> output(cout," ");
23     random_shuffle(v.begin(),v.end());//随机打乱区间的值
24     cout<<endl<<"1)";//输出:1)9 2 10 3 1 6 8 4 5 7(这里是随机的)
25     copy(v.begin(),v.end(),output);
26     copy(a2,a2+SIZE,v.begin());
27     cout<<endl<<"2)";//输出:2)2
28     cout<<count(v.begin(),v.end(),8);
29     cout<<endl<<"3)";//输出:3)6
30     cout<<count_if(v.begin(),v.end(),CLessThen9());//这里就调用了对象
31     cout<<endl<<"4)";//输出:4)1
32     cout<<*(min_element(v.begin(),v.end()));
33     cout<<endl<<"5)";//输出:5)100
34     cout<<*(max_element(v.begin(),v.end()));
35     cout<<endl<<"6)";//输出:6)193
36     cout<<accumulate(v.begin(),v.end(),0);//求和,累加到0上面
37     cout<<endl<<"7)";//输出:10000 4 64 1 2500 9 64 81 100 4
38     for_each(v.begin(),v.end(),outputSquare);
39     vector<int> cubes(SIZE);
40     transform(a1,a1+SIZE,cubes.begin(),calculateCube);//a1的立方放到了cubes里面
41     cout<<endl<<"8)";//输出:1 8 27 64 125 216 343 512 729 1000
42     copy(cubes.begin(),cubes.end(),output);
43     
44     return 0;
45 }

  其中:

  ostream_iterator<int> output(cout," ");

  定义了一个ostream_iterator<int>对象,可以通过cout输出以“ ”(空格)分割的一个个整数

  copy(v.begin(),v.end(),output);

  导致v的内容在cout上输出

  (老师讲到这里的时候放起了慷慨激昂的音乐)

  copy:

  template<class init, class outit>

  outit copy(init first, init last, outit x);

  本函数对每个在区间[0,last-first)中的N执行一次*(x+N) = *(first+N),返回x+N

  对于copy(v.begin(),v.end(),output);

  first和last的类型是vector<int>::const_iterator

  output的类型是ostream_iterator<int>

  copy的源码

1 template<class _ll, class _ol>
2 inline _ol copy(_ll _F,_ll _L,_ol _X)
3 {
4     for (;_F != _L; ++_X,++_F)
5         *_X = *_F;
6     return(_X);
7 }

  一个问题,在下面的程序中如何编写My_ostream_iterator?

 1 #include<iostream>
 2 #include<fstream>
 3 #include<string>
 4 #include<algorithm>
 5 #include<iterator>
 6 using namespace std;
 7 int main(int argc, char const *argv[])
 8 {
 9     int a[4] = {1,2,3,4};
10     My_ostream_iterator<int> oit(cout,"*");
11     copy(a,a+4,oit);//输出 1*2*3*4*
12     ofstream oFile("test.txt",ios::out);
13     My_ostream_iterator<int> oitf(oFile,"*");
14     copy(a,a+4,oitf);//向text.txt文件中写入1*2*3*4
15     oFile.close();
16     return 0;
17 }//如何编写My_ostream_iterator???

  在上面程序中调用“copy(a,a+4,oit)”实例化后得到copy如下:

1 template<class _ll, class _ol>
2 inline My_ostream_iterator<int> copy(int _F,int _L,My_ostream_iterator<int> _X)
3 {
4     for (;_F != _L; ++_X,++_F)
5         *_X = *_F;
6     return(_X);
7 }

  My_ostream_iterator类应该重载“++”和“*”运算符

  “=”也应该被重载

 1 #include<iterator>
 2 #include<iostream>
 3 #include<string>
 4 template<class T>
 5 class My_ostream_iterator:public iterator<output_iterator_tag, T>
 6 {
 7     private:
 8     string sep;//分隔符
 9     ostream & os;
10     public:
11     My_ostream_iterator(ostream & o,string s):sep(s),os(o){}
12     void operator++(){};//++只需要有定义即可,不需要做什么
13     My_ostream_iterator & operator*(){return *this;}
14     My_ostream_iterator & operator=(const T & val)
15     { os<<val<<sep;return *this;}
16 };

(io流给我整晕了555)

后记:

  这节课好长啊,下次看见这么长的课,我就。。。。乖乖看完,总不能不学对不对,不说了,各位新年快乐,祝各位码运昌隆!



这篇关于C++STL标准库学习笔记(十三)算法(上)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程