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)中最大元素（不小于任何其他元素）的迭代器

        也是以“<”作比较器

        样例：

#include<iostream>
#include<algorithm>
using namespace std;
class A
{
public:
    int n;
    A(int i):n(i){}
};
bool operator<(const A & a1, const A & a2)
{
    cout<<"< called"<<endl;
    if (a1.n==3&&a2.n==7)
    {
        return true;
    }
    return false;
}
int main(int argc, char const *argv[])
{
    A aa[] = {3,5,7,2,1};
    cout<<min_element(aa,aa+5)->n<<endl;
    cout<<max_element(aa,aa+5)->n<<endl;
    return 0;
}
/*
输出：
< called
< called
< called
< called
3
< called
< called
< called
< called
7
*/

        （这里假设第一个元素是最小值，然后逐个比较，发现第一个在定义的“<”下真是最小值，结果就是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相等

        样例：（包含了前面和没说的一些东西）

#include<vector>
#include<iostream>
#include<numeric>
#include<list>
#include<algorithm>
#include<iterator>
using namespace std;
class CLessThen9
{
public:
    bool operator()(int n){return n < 9;}
};
void outputSquare(int value){cout<<value*value<<" ";}
int calculateCube(int value){return value*value*value;}

int main(int argc, char const *argv[])
{
    const int SIZE = 10;
    int a1[] = {1,2,3,4,5,6,7,8,9,10};
    int a2[] = {100,2,8,1,50,3,8,9,10,2};
    vector<int> v(a1,a1+SIZE);
    ostream_iterator<int> output(cout," ");
    random_shuffle(v.begin(),v.end());//随机打乱区间的值
    cout<<endl<<"1)";//输出：1)9 2 10 3 1 6 8 4 5 7（这里是随机的）
    copy(v.begin(),v.end(),output);
    copy(a2,a2+SIZE,v.begin());
    cout<<endl<<"2)";//输出：2)2
    cout<<count(v.begin(),v.end(),8);
    cout<<endl<<"3)";//输出：3)6
    cout<<count_if(v.begin(),v.end(),CLessThen9());//这里就调用了对象
    cout<<endl<<"4)";//输出：4)1
    cout<<*(min_element(v.begin(),v.end()));
    cout<<endl<<"5)";//输出：5)100
    cout<<*(max_element(v.begin(),v.end()));
    cout<<endl<<"6)";//输出：6)193
    cout<<accumulate(v.begin(),v.end(),0);//求和，累加到0上面
    cout<<endl<<"7)";//输出：10000 4 64 1 2500 9 64 81 100 4
    for_each(v.begin(),v.end(),outputSquare);
    vector<int> cubes(SIZE);
    transform(a1,a1+SIZE,cubes.begin(),calculateCube);//a1的立方放到了cubes里面
    cout<<endl<<"8)";//输出：1 8 27 64 125 216 343 512 729 1000
    copy(cubes.begin(),cubes.end(),output);
    
    return 0;
}

        其中：

        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的源码

template<class _ll, class _ol>
inline _ol copy(_ll _F,_ll _L,_ol _X)
{
    for (;_F != _L; ++_X,++_F)
        *_X = *_F;
    return(_X);
}

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

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

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

template<class _ll, class _ol>
inline My_ostream_iterator<int> copy(int _F,int _L,My_ostream_iterator<int> _X)
{
    for (;_F != _L; ++_X,++_F)
        *_X = *_F;
    return(_X);
}

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

        “=”也应该被重载

#include<iterator>
#include<iostream>
#include<string>
template<class T>
class My_ostream_iterator:public iterator<output_iterator_tag, T>
{
    private:
    string sep;//分隔符
    ostream & os;
    public:
    My_ostream_iterator(ostream & o,string s):sep(s),os(o){}
    void operator++(){};//++只需要有定义即可，不需要做什么
    My_ostream_iterator & operator*(){return *this;}
    My_ostream_iterator & operator=(const T & val)
    { os<<val<<sep;return *this;}
};

        （io流给我整晕了555）

后记：

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