c++ 泛型算法

1：c++的算法库中有超过100个算法，这些算法均不会直接操作底层的元素，他们是通过操作迭代器规定的范围来实现的。

3：只读算法,操作两个序列的算法，写容器的算法,插入迭代器，拷贝算法

(1)：只读算法如”std::find”,”std::count”之类的算法，不会改变元素的值。对于只读取而不改变元素的算法，通常最好使用cbegin()和cend(),但是如果计划了使用算法返回的迭代器来改变元素的值，就需要使用begin()和end()的结果作为参数。

std::find(vec.cbegin(),vec.cend(),val);  //返回下标的迭代器
std::count(vec.cbegin(),vec.cend(),val); //返回val在vec中的个数

(2)：操作两个序列的算法规定：至少第二个要和第一个一样长。

std::accumulate(vec.cbegin(),vec.cend(),0); //将vec中的数字加起来
std::euqal(vec1.cbegin(),vec1.cend(),vec2.cend()); //将第一个vec1和vec2每个元素逐个比较，要是vec1长度大于vec2，那么在vec1中超过vec2的部分，结果将是未定义的。

(3)：写容器的算法要求容器的最小数目不能小于我们要求算法写入的元素数目,但是这个大小是由我们自己保证的。

auto it = std::back_inserter(vec);    //通过插入迭代器给原来vec增加元素。
*it = 42;
//back_inserter接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器
std::fill_n(back_inserter(vec),10,0); //将10个0添加到vec中

(4)：拷贝算法

#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<iterator>

using std::cout;
using std::cin;
using std::endl;

int main(int argc,char *argv[])
{
    std::vector<int> v1 = {1,2,3,4,5,6,7};
    int a1[] = {0,1,2,3,4,5,6,7};
    int a2[sizeof(a1)/sizeof(*a1)];
    //将a1的内容拷贝到a2当中,ret是a2的尾后迭代器
    auto ret = std::copy(std::begin(a1),std::end(a1),a2);
    for(auto u:a2) cout << u << " ";cout << endl;
    //replace将v1中的数字1替换成100
    std::replace(v1.begin(),v1.end(),1,100);
    for(auto u:v1) cout << u << " ";cout << endl;
    //如果我们希望原始序列不变，可以使用replace_copy
    //v2是v1的拷贝,并且修改了1成为了100
    std::vector<int> v2;
    std::replace_copy(v1.cbegin(),v1.cend(),back_inserter(v2),1,100);
    for(auto u:v2) cout << u << " ";cout << endl;
    return 0;
}

有关空间问题

泛型算法不会进行容器操作，因此有关删除和插入元素都是通过erase和back_inserter进行的

int main(int argc,char *argv[])
{
    std::vector<int> vec;
    std::list<int> lst;
    int i;
    while(cin >> i) {
        lst.push_back(i);
    }
    vec.resize(lst.size()); //用resize可以重新设置大小
    //错误,因为reserve不改变容器中元素的个数，只是保证空间的大小
    //vec.reserve(lst.size());
    cout << vec.capacity() << endl;
    std::copy(lst.cbegin(),lst.cend(),vec.begin());
    for(auto u:vec) cout << u << " ";cout << endl;
    return 0;
}

(5)：剔除重复和重新排序

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<iterator>
using std::cout;
using std::cin;
using std::endl;

void elimDups(std::vector<int> &v1)
{
    std::sort(v1.begin(),v1.end());   //排序操作，不改变容器大小
    for(auto u:v1) cout << u << " ";cout << endl;
    auto end_unique = std::unique(v1.begin(),v1.end());  //剔除重复，不会改变容器的大小
    for(auto u:v1) cout << u << " ";cout << endl;
    v1.erase(end_unique,v1.end());   //容器操作，真正删除重复的元素
    for(auto u:v1) cout << u << " ";cout << endl;
}

int main(int argc,char *argv[])
{
    std::vector<int> v1 = {1,2,2,3,4,5,5,5,4,4,2};
    elimDups(v1);
    return 0;
}

4：谓词

谓词是一个可调用的表达式，其返回结果是一个能作为条件的值。标准库算法使用的谓词分为两类：一元谓词和二元谓词。
分别对应一个和两个条件，就是给我们的普通排序增加了别的自己定义的条件。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using std::cout;
using std::cin;
using std::endl;

bool isLongerFive(const std::string &str)  //一元谓词
{
    return str.size() >= 5;
}

int main(int argc,char *argv[])
{
    std::vector<std::string> v1 = {"the","quick","red","fox","jumps","over","the","slow","red","turtle"};  
    auto it = std::partition(v1.begin(),v1.end(),isLongerFive); //第三个参数就是一元谓词
    for(auto it1 = v1.begin();it1 != it;++it1) {
        cout << *it1 << endl;
    }
    return 0;
}

5：lambda表达式

c++中可以被调用形式有4种：函数，函数指针，重载了函数调用运算符的类，lambda表达式
一个lambda表达式表示一个可以调用的代码单元。我们可以将其理解为一个未命名的内联函数，具有一个返回类型，一个参数列表和一个函数体。
与函数不同，lambda表达式可以定义在函数内部。基本形式如下:

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

(1)：向lambda传递参数

[](const std::string &a,const std::string &b){ return a.size() > b.size();} 
//空捕获列表表明此lambda不使用它所在函数中的任何局部变量。
//那我们就可以像下面这样调用
std::stable_sort(vec.begin(),vec.end(),[](const std::string &a,const std::string &b){ return a.size() > b.size();});

//对于有的lambda表达式，我们需要使用函数中的局部变量，这时候就必须要使用lambda表达式的捕获列表  
[sz](const std::string &a) { return a.size() >= sz; }; //注意，此时只有捕获列表中有sz，我们才可以使用它
//捕获列表只使用局部非static变量，lambda可以使用局部static变量和它所在函数之外的名字。

stable_sort和find_if以及partition

stable_sort(vec.begin(),vec.end(),isShorter);    //stable_sort 保证长度相等的单词之间字典序。

find_if(vec.begin(),vec.end(),谓词); //find_if算法对输入序列中每个元素调用给定的谓词。它返回第一个使谓词返回非0值的元素。

//partition将区分true和false，将true放到前面,将false放到后面，返回第一个指向false的迭代器。

auto wc = std::partition(v1.begin(),v1.end(),[val](const std::string &b){ return b.size() <= val;});

（2）：lambda值捕获和返回
1：捕获

• 值捕获：auto f = [v1]{return v1;}前提是变量可以拷贝，与参数不同的是被捕获的变量值在lambda创建时拷贝，一旦创建完成之后对原值再修改不会影响。
• 引用捕获：auto f = [&v1]{ return v1;}引用捕获的值原值修改之后引用的值也会变化，注意引用的是局部变量，在函数结束之后局部变量会被释放。
• 隐式捕获：[=](const std::string &s){ return s.size() >= sz;}=表示采用值捕获的方式，&采用表示引用捕获的方式。
• 混合显式和隐式捕获：[&,c](const std::string &s){ os << s << c;}os：隐式捕获，引用捕获 c：显式捕获，值捕获
• 可变lambda：必须使用关键字mutable，auto f = [v1] () mutable { return ++v1; }

2：返回：如果lambda表达式中包含return之外的任何语句，编译器假定lambda返回void。当我们需要给lambda表达式定义返回类型时，必须使用
尾置返回类型。

//使用尾置返回类型
std::transform(vec.begin(),vec.end(),vec.begin(),[](int i)->int { if(i < 0) return -i;else return i;});

//使用bind还可以重排参数顺序
std::sort(words.begin(),words.end(),isShorter);             //相当于调用isShorter(A,B)
std::sort(words.begin(),words.end(),bind(isShorter,_2,_1)); //相当于调用isShorter(B,A)

//ref函数和cref函数  
//由于bind函数绑定的时候会拷贝，由于ostream是无法拷贝的，所以我们使用ref(os)，函数返回一个对象，包含给定的引用，此对象是可以拷贝的。

6：c++迭代器

1：插入迭代器:负责在容器操作层面插入元素

名称	功能
back_inserter()	创建一个使用push_back()的迭代器
front_inserter()	创建一个使用push_front()的迭代器
inserter()	创建一个使用insert的迭代器,此函数接受第二个参数，指向给定容器的迭代器

2：iostream流操作
(1)：istream_iterator的操作
istream_iterator用>>来读取流，我们可以循环从cin读取值，下面注意它的用法

#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>

using std::cout;
using std::cin;
using std::endl;

int main(int argc,char *argv[])
{
    //定义流的类型为cin
    std::istream_iterator<int> in_iter(cin);
    //eof表示文件尾或者IO错误
    std::istream_iterator<int> eof;
    //用读入的数据构建一个vector
    std::vector<int> vec(in_iter,eof);
    for(auto u:vec) cout << u << " ";cout << endl;
    //我们也可以调用标准库中的算法使用accumulate
    cout << std::accumulate(in_iter,eof,0) << endl;
    return 0;
}

(2)：ostream_iterator的操作
我们可以对任何具有输出运算符的类型定义ostream_iterator。特殊的是，它的第二个参数可以再输出的东西后面加上一个我们指定的c风格的字符串。

3:反向迭代器

除了forward_list之外的容器都支持反向迭代器。支持反向迭代器的容器也需要支持--运算符。

//注意几个迭代器的位置 vec.begin() vec.end() vec.rbegin() vec.rend() iter.base()
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>

using std::cout;
using std::cin;
using std::endl;

int main(int argc,char *argv[])
{
    std::string line = "yang,bo,dong";
    //输出"yang"
    auto comma = std::find(line.begin(),line.end(),',');
    cout << std::string(line.begin(),comma) << endl;
    //本想输出"dong"，结果却成了"gnod"，原因就是因为rbegin是按照反向处理容器元素的
    auto rcomma = std::find(line.rbegin(),line.rend(),',');
    cout << std::string(line.rbegin(),rcomma) << endl;
    //我们可以用rcomma.base()来将反向迭代器转换成普通迭代器
    cout << std::string(rcomma.base(),line.end()) << endl;
    return 0;
}

4：迭代器的几种类别

名称	支持的操作	对应容器或算法
输入迭代器	==,!=,++,*,->,只能用于顺序访问	find,accumulate,copy前两个参数,istream_iterator
输出迭代器	++,*,修改目的位置的值	copy的第三个参数,ostream_iterator
前向迭代器	可以读写元素，这类迭代器在一个序列中移动，前向迭代器支持所有输入和输出迭代器的操作	unique
双向迭代器	可以正向和反向读写序列中的元素	reverse,list
随机访问迭代器	提供在常量时间内访问序列中任意元素的能力。支持算术操作和下标运算符	vector

5:算法的命名规范

• _if的版本一般会接受一个谓词，find_if(beg,end,pred)查找的是第一个使pred为真的元素。
• _copy需要写入额外空间的版本，都会在之后加copy,比如重新排序并且将他们赋值到其他的空间,就用remove_copy_if。