第10章 泛型算法

accumulate函数

accumulate(b, e, val)   返回一对迭代器范围内元素的“和”，第三个参数指定“和”的初值；返回类型与第三个实参的类型一致，而与容器内的元素类型无关

例如：

vector<double> v{1.1, 2, 3, 4};
accumulate(v.cbegin(), v.cend(), 0); //返回值是int类型的10
accumulate(v.cbegin(), v.cend(), 0.0); //返回值是double类型的10.1

PS：容器中元素类型不一定是数值类型，只要元素类型定义了+运算符即可；例如：string sum = accumulate(v.cbegin(), v.cend(), string("")) 做的事是将[b,e)范围的string依次连接起来并返回

 

equal函数

equal(b1, e1, b2) //c1中[b1,e1)范围的元素依次与c2中[b2, +∞)范围的元素比较

可以用来比较不同容器类型中的元素，且元素类型也不必一样。只要能用==比较两个元素类型即可。

PS：equal的一个重要假设：第二个序列至少和第一个序列一样长

 

fill函数

fill(b, e, val)   将val赋值给[b,e)范围的元素

fill_n(b, n, val)   将val赋值给[b,b+n)范围的n个元素

注意：写操作需保证目标位置足够大，能容纳要写入的元素。特殊地，不要在空容器上调用写操作的函数。

 

back_inserter函数

back_inserter函数返回一个与容器绑定的插入迭代器（insert iterator），定义在头文件iterator中。

通过插入迭代器赋值时，会调用push_back将一个具有给定值的元素添加到容器中。

例如：

　　vector<int> vec;

　　auto it = back_inserter(vec); //it是一个插入迭代器

　　*it = 10; //相当于vec.push_back(10)

再例如：

　　fill_n(back_inserter(vec),  5, 0); //在vec的末尾添加5各元素，每个元素的值都为0

 

拷贝算法

copy(b, e, dest)   将[b,e)范围的元素拷贝至dest指向的位置；返回插入到目的位置中的最后一个元素的后一个位置的迭代器

例如：可以用copy实现内置数组的拷贝

　　int a1[] = {0,1,2};

　　int a2[sizeof(a1)/sizeof(*a1)]; //保证a2与a1的空间（至少）一样大

　　auto ret = copy(begin(a1), end(a1), a2); //ret指向拷贝到a2的尾元素之后的位置

 

repalce与replace函数（略）

 

重排容器元素的算法

sort(b,e)   依据元素类型的<运算符来排序

unique(b,e)   “删除”（覆盖）相邻重复元素；unique函数不改变容器大小；返回的迭代器指向最后一个不重复元素之后的位置

PS：若要删除靠后的无用元素，可以这样

　　c.erase(unique(c.begin(),c.end()), c.end());

 

定制操作

find_if算法

find_if函数接受一对迭代器，表示一个范围；find_if的第三个参数是一个一元谓词，find_if对输入序列中的每个元素调用给定的这个谓词，返回第一个使谓词返回非0值的元素的迭代器；如果不存在这样的元素，则返回尾后迭代器。
例子：查找第一个小于5的元素
bool is(const int &i)
{
    if(i<5) return 1;
    return 0;
}

auto it = find_if(c.begin(), c.end(), is);
if(it==v.end())
    cout<<"not found"<<endl;
else
    cout<<*it<<endl;

 

lambda表达式

一个lambda表达式表示一个可调用的代码单元，可以将其理解为一个未命名的内联函数。
[captrue list] (parameter list) -> return type { function body }
captrue list：捕获列表；是一个lambda所在函数中定义的局部变量的列表，通常为空。
parameter list、return type、function body：与普通函数一样，分别表示参数类型、返回列表、函数体；不同的是，lambda必须使用尾置返回。

例子：编写一个lambda，接受两个int，返回它们的和

　　auto sum = [](int &a, int &b) -> int {return a+b;};
　　int x,y;
　　cout<<sum(x,y)<<endl;

注意：可以忽略参数列表和返回类型，但必须包含捕获列表和函数体。
注意：如果lambda函数体包含任何单一return语句之外的内容，且未指定return type，则返回void；否则，若函数体只是一个return语句，由return的表达式的类型推断返回类型。

向lambda传递参数
与普通函数不同，lambda表达式不能有默认参数。

使用捕获列表
若lambda要使用它所在函数的（非static）局部变量，则必须在捕获列表中指明该局部变量，多个局部变量以逗号分隔。
空的捕获列表：表明此lambda不使用它所在函数中的任何（非static）局部变量。
捕获列表只用于局部非static变量，lambda可以直接使用局部static变量和它所在函数之外声明的名字。

值捕获

与参数不同，被捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝。

引用捕获

在捕获列表中的变量名前加上&，指出该变量以引用方式捕获。

 

lambda捕获列表的不同形式

[ ]   空捕获列表；不使用所在函数中的（非static）变量
[names]   names是以逗号分隔的名字列表，名字前如果使用了&，则采用引用捕获方式，否则采用值捕获方式
[&]   隐式捕获列表，采用引用捕获方式
[=]   隐式捕获列表，采用值捕获方式
[&, identifer_list]   identifer_list是一个逗号分隔的列表，包含0个或多个来自所在函数的变量，这些变量都采用值捕获方式，而任何隐式捕获的变量都采用引用方式捕获。identifer_list中的名字前不能使用&。
[=, identifer_list]   identifer_list中的变量都采用引用方式捕获，而任何隐式捕获的变量都采用值捕获方式。identifer_list中的名字不能包含this，且这些名字前必须使用&。

 

for_each算法

for_each(b,e,pred)   对迭代器范围[b,e)的元素依次调用一元谓词函数pred

 

可变lambda

对于一个值捕获的变量，lambda不会改变 其值；若希望改变其值，就必须在参数列表后加上关键字mutable。

 

参数绑定：bind函数

（略）

 

再探迭代器

插入迭代器

插入迭代器实际上是一种迭代器适配器，它接受一个容器，生成一个迭代器，能实现向给定容器添加元素。

插入迭代器有三种：back_inserter、front_inserter、inserter

 

插入迭代器的操作

it = t   在it指定的当前位置插入值t；假定c是it绑定的容器，依赖于插入迭代器的不同种类，此赋值操作分别调用c.push_back(t)、c.push_front(t)、c.insert(t,p)，其中p是传递给inserter的迭代器位置

*it   ++it   it++   虽然这些操作存在，但不会对插入迭代器it做任何事情；每个操作都返回it

 

一个例子：

　　vector<int> v;
　　auto inst_it = inserter(v, v.begin());
　　*inst_it = 1;
　　*inst_it = 2;
　　*inst_it = 3;

最终v中含有三个元素1,2,3

　　*inst_it = val;

其效果相当于

　　it = v.insert(it, val); //it指向新加入的元素

　　++it; //递增it使它指向原来的元素

 

 

iostream迭代器

istream_iterator操作

istream_iterator<T> in(is)   in从输入流is读取类型为T的值

istream_iterator<T> eof   eof被定义为空的istream_iterator，可以当做尾后迭代器来使用；对于一个关联到流的迭代器，一旦其关联的流遇到文件尾或IO错误（例如读到非T类型的值），迭代器的值就与尾后迭代器相等

in1 == in2    in1 != in2   in1和in2必须读取相同的类型才能进行比较；若它们都是尾后迭代器，或者绑定到相同的输入，则两者相等

*in   返回从流中读取的值

in->mem   相当于(*in).mem

++in   in++   使用绑定的元素类型所定义的>>运算符从输入流读取下一个值；前置版本返回指向递增后迭代器的引用，后置版本返回旧值

 

ostream_iterator操作

创建一个ostream_iterator时，可以提供（可选的）第二参数，它是一个C风格字符串（字符串字面值常量、指向字符数组的指针），在输出每个元素后都将打印此字符串。

必须将ostream_iterator绑定到一个指定的流，不允许空的或表示尾后位置的ostream_iterator。

ostream_iterator<T> out(os)   out将类型为T的值写到输出流os中

ostream_iterator<T> out(os, d)   out将类型为T的值写到输出流os中，每个值后面都输出一个d；d是一个C风格字符串

out = val   用<<运算符将val写入到out所绑定的ostream中；val的类型需要与out可写的类型兼容

*out   ++out   out++   这些运算符存在，但不对out做任何事情；每个运算符都返回out

 

泛型算法结构

泛型算法形参模式

alg(beg, end, other args)

alg(beg, end, dest, other args)   dest参数是一个表示算法可以写入的目的位置的迭代器；dest可能是一个直接指向容器的迭代器，也可能被绑定到一个插入迭代器，或是一个ostream_iterator

alg(beg, end, beg2, other args)

alg(beg, end, beg2, end2, other args)

 

特定容器算法

与其它容器不同，链表类型 list 和 forward_list 定义了几个成员函数形式的算法。

对于 list 和 forward_list 应该优先使用其成员函数版本的算法而不是通用算法，以达到较低代价。例如：一个链表可以改变元素间的链接而不是真的交换它们的值来“交换”元素，因此这些链表版本的算法的性能优于对应的通用版本。

 

list、forward_list成员函数版本的算法

lst.merge(lst2)   lst.merge(lst2, comp)   将来自lst2的元素合并入lst；lst和lst2都必须是有序的；元素将从lst2中删除，merge操作之后，lst2为空；第一个版本使用<运算符、第二个版本使用给定的比较操作

lst.remove(val)    lst.remove_if(pred)    调用erase删除掉与给定值val相等或令一元谓词pred为真的每个元素

lst.reverse()   反转lst中元素的顺序

lst.sort()   lst.sort(comp)   使用<或给定的比较操作排序元素

lst.unique()   lst.unique(pred)   调用erase删除相邻重复值；第一个版本使用==、第二个版本使用给定的二元谓词pred

 

splice成员

链表类型还定义了splice算法。

list、forward_list的splice成员函数的参数

lst.splice(args) 或 flst.splice_after(args)

args可以是如下形式：

(p, lst2)   p是指向lst中元素的迭代器，或者是指向flst首前位置的迭代器；函数将lst2的所有元素移动到lst中p之前的位置或是flst中p之后的位置；将元素从lst2中删除；lst2的类型必须与lst或flst相同，且不能是同一个链表

(p, lst2, p2)   p2是一个指向lst2中位置的有效的迭代器；将p2指向的元素移动到lst中，或将p2之后的元素移动到flst中；lst2可以是与lst或flst相同的链表

(p, lst2, b, e)   b、e必须表示lst2中的合法范围；将给定范围中的元素从lst2移动到lst或flst；lst2可以是与lst或flst相同的链表，但p不能指向[b,e)范围的元素

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有