Tips for C++ Primer Chapter 10 泛型算法

2018-06-17 21:40:16来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

第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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Easy Game LightOJ - 1031

下一篇:洛谷P1306 斐波那契公约数