10.泛型算法

标准库容器定义的操作集合惊人得小。标准库并未给每个容器添加大量功能,而是提供了一组算法,这些算法中的大多数都独立于任何特定的容器。这些算法是通用的(generic,或称泛型的):它们可用于不同类型的容器和不同类型的元素。

10.1概述

大多数算法都定义在头文件$algorithm$中。标准库还在头文件$numric$中定义了一系列的数值泛型算法.

迭代器令算法不依赖于容器

算法依赖于容器类型

int a[8]={1,2,3,1,2,3,4,1};
//计算索引0-8中1出现的次数，结果为3
cout<<count(begin(a),end(a),1)<<endl;
//计算0-6中1出现的次数。结果2，因为它是左闭右开的区间
cout<<count(a,a+7,1)<<endl;

10.2初识泛型算法

理解算法的最基本的方法就是了解他们是否读取元素，改变元素或者重排序元素

10.2.1只读算法

一些算法只会读取范围内的值而不改变值。比如$find$函数，$accumulate$函数,$equal$函数。这些函数有个有意思的参数，就是BinaryOperation binary_op，这个可以允许定义自己的函数。

bool myequal(int a,int b){
    return a!=b;
}
int main(int argc, const char * argv[]) {
    int a[8]={1,2,3,1,2,3,4,1};
    vector<int>b={1,2,3,1,2,3,4,1};
    cout<<equal(begin(a), end(a), begin(b),myequal)<<endl;//输出0
    cout<<equal(begin(a), end(a)c begin(b))<<endl;//输出1
    vector<string>c={"hello","word"};
    cout<<accumulate(c.begin(), c.end(), ""); //会报错，因为“”默认为const char*类型
    cout<<accumulate(c.begin(), c.end(), string(""));//输出helloword
    return 0;
}

10.2.2写容器的算法

算法不检查写操作

比如$fill$函数，接受一对迭代器和初始值，$fill_{n}$接受初始迭代器，一个计数值和一个值。

不知道是不是编译器的问题，下面展示一个很奇怪的东西,当你只要初始化了$a$,$*first$有地址之后，无论怎么赋值，都不报错。

int main(int argc, const char * argv[]) {
    vector<int>a(10);
    //记住左闭右开
    // fill(a.begin(), a.end(), 0); 
    //fill_n(a.begin(),10,1);
    cout<<*(a.begin()+100)<<endl;//输出一个随机数，测试的时候是-1885063384
    fill_n(a.begin(),121111,1);//当超过了初始化的大小，并不会报错。
  	cout<<*(a.begin()+100)<<endl;//输出1
    return 0;
}

但是没有帮$*first$赋值的话，就会报错

template <class _ForwardIterator, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
void
__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
{
    for (; __first != __last; ++__first)
        *__first = __value_;
}
int main(int argc, const char * argv[]) {
    vector<int>a;
    fill(a.begin(),a.end(),0);//不报错，和源代码有关，first和end相等，所以不会for循环
    fill_n(a.begin(),10,0);//报错
}

介绍back_inserter

$back_inserter$接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。可以这样子理解，申请了一个新的空间。

int main(int argc, const char * argv[]) {
    vector<int>a;
    back_insert_iterator<vector<int>>it=back_inserter(a);
    *it=10;//添加了一个10
    cout<<a[0]<<endl;
    //添加10个0
    fill_n(back_inserter(a),10,0);
}

拷贝算法

使用迭代器一定要注意大小一致，它不检查大小，根据源码实现不同，它会把需要写入的值，全部写进去。

int main(int argc, const char * argv[]) {
    vector<int>a={1,2,3,4};
    vector<int>b(3);
    vector<int>::iterator it=copy(begin(a), end(a), begin(b));
    cout<<*(it-1)<<endl; //输出4，因为copy返回的是最后一个元素的后一个位置，理解成a的end可以
    cout<<b[0]<<b[1]<<b[2]<<b[3]<<endl;//输出1 2 3 4
    cout<<b.size()<<endl;//输出3
    cout<<*b.end()<<endl;//输出4，正常来说应该是随机数，但是copy我们多复制了一个，把end赋值了。
    return 0;
}

10.2.3重排容器算法

bool isbig(int i,int j){
    return i>j;
}
int main(int argc, const char * argv[]) {
    vector<int>a={1,4,5,3,7,8,1,3};
    //从大到小排序
    sort(a.begin(),a.end(),isbig);
    //8 7 5 4 3 3 1 1
    //将相邻重复元素放到最后，返回指向最后一个不重复的元素的后一个值
    vector<int>::iterator it=unique(a.begin(), a.end());
    //变为了 8 7 5 4 3 1 ? ?这个问号不确定是什么值
    cout<<*it<<endl;//输出3
    a.erase(it, a.end());
    //a变为了 8 7 5 4 3 1
    return 0;
}

10.3定制操作

比如$sort$函数，默认是从小到大排序，但是我们希望他由大到小排序，这时候就需要定制操作了，一般这些函数有个参数$predicate$

10.3.1向算法传递函数

bool isbig(string i,string j){
    return i.length()<j.length();
}
int main(int argc, const char * argv[]) {
    //string按照长度排序，长度相同的按照字典序排序·
    vector<string>a={"z","a","abc","zb"};
    sort(a.begin(),a.end());
    stable_sort(a.begin(), a.end(),isbig);
    return 0;
}

10.3.2lambda表达式

介绍lambda $lambda$表达式的声明方法为，返回类型是尾置类型

\[[capture\ list](parameter\ list)->return\ type \{function\ body\}\]

$capture\ list$:捕获列表，是一个$lambda$所在函数中定义的局部变量的列表
$parameter\ list$表示参数列表
$return\ type$表示返回类型
$function\ body$表示函数体

一般可以忽略参数列表和返回类型，但必须包含捕获列表和函数体

如果lambda的函数体包含任何单一return语句之外的内容,且未指定返回类型,则返回void.

auto f=[]{return 32}
cout<<f()<<endl;//输出32

像lamdba传递参数

这里继续拿$stable_sort$做为例子

stable_sort(a.begin.a.end,[](string i,string j){return i.length()<j.length()});

使用捕获列表

现在要使用$find_if$函数查找第一个大于长度为$sz$的字符串

bool isbig(string i,string j){
    return i.length()<j.length();
}
int main(int argc, const char * argv[]) {
    string a[4]={"a","b","cd","abcd"};
    int sz=2;
    string*it=find_if(begin(a), end(a), [sz](string i)->bool{
        return i.length()>=sz;
    });
    cout<<*it<<endl;
    return 0;
}

10.3.3lambda捕获和返回

值捕获

int main(int argc, const char * argv[]) {
    size_t v1 =42; //局部变量//将v1拷贝到名为f的可调用对象
    auto f = [v1] { return v1; };
    v1 = 0;
    auto j =f(); // j为42; f保存了我们创建它时v1的拷贝
    return 0;
}

引用捕获

int main(int argc, const char * argv[]) {
    size_t v1 =42; //局部变量//将v1拷贝到名为f的可调用对象
    auto f = [&v1] { return v1; };
    v1 = 0;
    auto j =f(); // j为0; f保存了我们创建它时v1的引用而非拷贝
    return 0;
}

隐式捕获

可变lambda

对于值被拷贝的变量，$lamba$不会改变其值，如果我们希望能改变一个被捕获的变量的值，可以通过关键字mutable从而改变

int main(int argc, const char * argv[]) {
    size_t v1 =42; //局部变量//将v1拷贝到名为f的可调用对象
    auto f = [v1] ()mutable { return ++v1; };//不加mutable会报错
    cout<<v1;//结果是42
    v1=0;//结果是0
    auto j =f();
    cout<<j;//结果43
    return 0;
}

对于引用拷贝的变量是否可以修改依赖于此引用指向的是一个$const$类型，还是一个非$const$类型。

10.3.4参数绑定

主要讲$bind$函数的使用，它的头文件为$functional$,命名空间为$using\ namespace\ std::placeholders$.当需要传递多个数值，或者$lambda$函数太过复杂的话，可以使用。

bool isbig(string i,int j){
    return i.length()<j;
}
ostream&print(ostream&s,const string&ss,char c){
    return s<<ss<<c<<endl;
}
int main(int argc, const char * argv[]) {
    string i="1122";
    auto f=bind(isbig,std::placeholders::_1,1);
    cout<<f(i)<<endl;//false
    vector<string>ss={"1","2",""};
    int sz=1;
    //bind(function,arglist)，其中arglist对应于function的函数列表，其中默认为拷贝形式
    cout<<*find_if(ss.begin(), ss.end(), bind(isbig,std::placeholders::_1, sz));
    //绑定引用参数
    ostream&os=cout;
    char c='1';
    //for_each(ss.begin(), ss.end(), [&os,c](const string&s){os<<s<<c<<endl;});
    //改写
    //bind中参数默认为拷贝，如果对于有些参数想要引用传递或者绑定的参数无法拷贝，那么就使用关键字ref，cref是const类型
    for_each(ss.begin(), ss.end(), bind(print, ref(os), _1,c));
    return 0;
}

10.4再探迭代器

插入迭代器:用来插入元素
流迭代器:用来遍历元素
反向迭代器:迭代器向后移动
移动迭代器:用来移动元素

10.4.1插入迭代器

插入迭代器有以下三个类型

$back$_$inserter$:在容器最后的位置插入数值,对应函数$push$_$back$
$front$_$inserter$:在容器最前面插入数值,都应函数$push$_$front$

$inserter$:在容器的指定位置前面插入数值,对应函数$insert(it,val)$

int main(int argc, const char * argv[]) {
    vector<int>nums={1,2,3,4};
    //it是nums的插入迭代器
    back_insert_iterator<vector<int>>it=back_inserter(nums);
    *it=5;//相当于插入5，it指向5
    cout<<nums[4]<<endl;//数组为1，2，3，4，5输出5
    //vector没有push_front方法
    list<int>num={1,2,3,4,5};
    front_insert_iterator<list<int>>it1=front_inserter(num);
    *it1=0;//在前面插入0，输出0 ，1，2，3，4，5
    cout<<num.front()<<endl;
    insert_iterator<vector<int>>it2=inserter(nums,nums.begin());
    *it2=3;//变成了3，1，2，3，4，5
    cout<<nums[0]<<nums[1]<<nums[2]<<nums[3]<<nums[4]<<nums[5]<<endl;
    return 0;
}

10.4.2iostream迭代器

主要包括输入输出的流的迭代器·

下面看代码展示用处

int main(int argc, const char * argv[]) {
    istream_iterator<int>in(cin),end;
    vector<int>aa;
    while (in!=end) {
        aa.push_back(*in++);
    }
  	//copy(in,end,back_inserter(aa))也是一种打印方式，不同的是比如输入1234，while循环*in代表的是4，后者代表的是1
  	//但是此时in==end
    //将a数组打印出来
    ostream_iterator<int>out(cout);
    for(int a:aa){
        *out=a;
        out++;
    }
    //同样是输出
    copy(aa.begin(),aa.end(),out);
    cout<<endl;
    return 0;
}

10.4.3反向迭代器

这里主要主义反向迭代器转为正向迭代器使用base函数即可

int main(int argc, const char * argv[]) {
    string a="abc,ddd";
    //将正向迭代器，转换为反向迭代器
    //如果本身就是反向的话，那么就不用改变
    string::reverse_iterator it(a.end());
    cout<<*it<<endl;//输出d
    cout<<string(a.cbegin(),a.cend())<<endl;//输出abc,ddd
    cout<<string(a.crbegin(),a.crend())<<endl;//输出ddd,cba
    cout<<string(a.crend().base(),a.crbegin().base())<<endl;//输出adc,ddd
    return 0;
}

10.5特定容器用法

对于list和forward_list来说有特定的用法。一般优先使用本容器的特定用法

int main(int argc, const char * argv[]) {
    list<int>a={1,2,3,4};
    list<int>b={5,6,7};
    //a.splice(a.begin(), b);a变为5 6 7 1 2 3 4，b为空
    //a.splice(a.begin(), b,b.begin());//a为5 1 2 3 4,b为6 7
    a.splice(a.begin(), b,b.begin(),--b.end());//a为5，6，1，2，3，4 b为7
    return 0;
}

C++