第10章 泛型算法(下)

10.3 定制操作

很多算法都会比较输入序列中的元素。默认情况下,这类算法使用元素类型的<或==运算符完成比较。标准库还为这些算法定义了额外的版本,允许我们提供自己定义的
操作来代替默认运算符。例如sort算法默认使用元素类型的<运算符。

  • 向算法传递函数:
  1. 谓词:谓词是一个可调用的表达式,其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类:一元谓词(unary predicate,意味着它们只接受单一参数)和二元谓词(binary predicate,意味中它们有两个参数)。接受谓词参数的算法对输入序列中的元素调用谓词。因此,元素类型必须能转换为谓词的参数类型。接受一个二元谓词参数的sort版本用这个谓词代替<来比较元素。
  2. 排序算法:当我们将words按大小重排的同时,还希望具有相同长度的元素按字典序排列,可以使用stable_sort算法。这种稳定排序算法维持相等元素的原有顺序。

    假定再次调用前words是按字典序排列的,则调用之后,words会按元素大小排序,而长度相同的单词会保持字典序。
  • 10.3.2 lambda表达式
  1. 介绍lambda:我们可以向一个算法传递任何类别的可调用对象(callable object)。对于一个对象或一个表达式,如果可以对其使用调用运算符,则称它为可调用的。到目前为止,我们使用过的仅有的两种可调用对象是函数和函数指针。还有其他两种可调用对象:重载了函数调用运算符的类,以及lambda表达式(lambda expression)。一个lambda表达式表示可调用的代码单元。我们可以将其理解为一个未命名的内联函数。与任何函数类似,一个lambda具有一个返回类型、一个参数列表和一个函数体。但与函数不同,lambda可能定义在函数内部。一个lambda表达式具有如下形式:

    其中,capture list是一个lambda所在函数中定义的局部变量的列表(通常为空);return type、parameter list和function body与任何普通函数一样,分别表示返回类型、参数列表和函数体。但是与普通函数不同的是,lambda必须使用尾置返回来指定返回类型。我们可以忽略参数列表和返回类型,但必须永远包含捕获列表函数体

    在lambda中忽略括号和参数列表等价于指定一个空参数列表;如果忽略返回类型,lambda根据函数体中的代码推断出返回类型。如果函数体只是一个return语句,则返回类型从返回的表达式的类型推断而来。否则,返回类型为void。
    NOTE:如果lambda的函数体包含任何单一return语句之外的内容,且未指定返回类型,则返回void。(同函数一样若类型是void,则不能返回值!)
  2. 向lambda传递参数
    与一个普通函数调用类似,调用一个lambda时给定的实参被用来初始化lambda的形参。通常,实参和形参的类型必须匹配。但以普通函数不同,lambda不能有默认参数。因此,一个lambda调用的实参数目永远与形参数目相等。一旦形参初始化完毕,就可以执行函数体了。
  3. 使用捕获列表
    虽然lambda可以出现在一个函数中,使用其局部变量,但它只能使用那些明确指明的变量。一个lambda通过将局部变量包含在其捕获列表中来指出将会使用这些变量。
  4. 调用find_if
    使用此lambda,我们就可以查找第一个长度大于等于sz的元素:

    这里对find_if的调用返回一个迭代器,指向第一个长度不小于给定参数sz的元素。如果这样的元素不存在,则返回words.end()的一个拷贝。
    我们可以使用find_if返回的迭代器来计算从它开始到words的末尾一共有多少个元素:

    我们的输出语句调用make_plural来输出“word”或”words”,具体输出哪个取决于大小是否等于1。
  5. for_each算法
    问题的最后一部分是打印words中长度大于等于sz的元素。为了达到这一目的,我们可以使用for_each算法。此算法接受一个可调用对象,并对输入序列中每个元素调用此对象:

    NOTE:捕获列表只用于局部非static变量,lambda可以直接使用局部static变量和它所在函数之外声明的名字。
  6. 完整的biggies
  • lambda捕获和返回
    当定义一个lambda时,编译器生成一个与lambda对应的新的(未命名的)类类型。目前,我们可以这么理解,当向一个函数传递一个lambda时,同时定义了一个新类型和该类型的一个对象:传递的参数就是此编译器生成的类类型的未命名对象。
  1. 值捕获:类似于参数传递,变量的捕获方式也可以是值或引用。目前为止,我们的lambda采用值捕获的方式。与传值参数类似,采用值捕获的前提是变量可以拷贝。与参数不同,被捕获的变量的值是在lambda创建时拷贝,而不是调用时拷贝。
  2. 引用捕获:我们定义lambda时可以采用引用方式捕获变量。例如:

    WARNING:当以引用方式捕获一个变量时,必须保证在lambda执行时变量是存在的。
  3. 隐式捕获:为了指示编译器推断捕获列表,应在捕获列表中写一个&(引用捕获)=(值捕获)。如果我们希望对一部分变量采用值捕获,对其他变量采用引用捕获,可以混合使用隐式捕获和显示捕获。

    当我们混合使用隐式捕获和显示捕获时,捕获列表中第一个元素必须是一个&或=。此符号指定了默认方式为引用或值。并且,显示捕获的变量必须使用与隐式捕获不同的方式。
  4. 指定lambda返回类型:默认情况下,如果一个lambda体包含return之外的任何语句,则编译器假定此lambda返回void。当我们需要为一个lambda定义返回类型时,必须使用尾置返回类型:

    函数transfrom接受三个迭代器和一个可调用对象。前两个迭代器表示输入序列,第三个迭代器表示目的位置。第四个参数是一个lambda,它的捕获列表是空的,接受单一int参数,返回一个int值。
  • 参数绑定(P354)
    对于那种只在一两个地方使用的简单操作,lambda表达式是最有用的。如果我们需要在很多地方使用相同的操作,通常应该定义一个函数,而不是多次编写相同的lambda表达式。
    如果lambda的捕获列表为空,通常可以用函数来代替它。但是对于捕获局部变量的lambda,用函数来替换它就不是那么容易了。
    标准库bind函数:可以将bind函数看作一个通用的函数适配器,它接受一个可调用对象,生成一个新的可调用对象来“适应”原对象的参数列表。
10.4 再探迭代器

除了为每个容器定义的迭代器之外,标准库在头文件iterator中还定义了额外几种迭代器。这些迭代器包括以下几种:

  1. 移动迭代器(move iterator):这些专用的迭代器不是拷贝其中的元素,而是移动它们。
  2. 反向迭代器(reverse iterator):这些迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器。
  3. 流迭代器(stream iterator):这些迭代器被绑定到输入或输出流上,可用来遍历所关联的IO流。
  4. 插入迭代器(insert iterator):这些迭代器被绑定到一个容器上,可用来向容器插入元素。
  • 插入迭代器
  1. 插入迭代器是一种迭代器适配器,它接受一个容器,生成一个迭代器,能实现向给定容器添加元素。当我们通过一个插入迭代器进行赋值时,该迭代器调用容器操作来向给定容器的指定位置插入一个元素。
  2. 插入迭代器有三种类型,差异在于元素插入的位置:(1)back_inserter:创建一个使用push_back的迭代器。(2)front_inserter:创建一个使用push_front的迭代器。(3)inserter:创建一个使用inserter的迭代器。此函数接受第二个参数,这个参数必须是一个指向给定容器的迭代器。
    NOTE:只有在容器支持push_front的情况下,我们才可以使用front_inserter。类似的,只有在容器支持push_back的情况下,我们才能使用back_inserter。
  3. 理解插入器的工作过程是很重要的:当调用inserter(c,iter)时,我们得到一个迭代器,接下来使用它时,会将元素插入到iter原来所指向的元素之前的位置。

    当调用front_inserter(c)时,我们得到一个插入迭代器,接下来会调用push_front。当每个元素被插入到容器c中时,它变为c的新的首元素。因此,front_inserter生成的迭代器会将插入的元素序列的顺去颠倒过来,而inserter和back_inserter则不会。
  • iostream迭代器(P359)

istream_iterator读取输入流,ostream_iterator向一个输出流写数据。这些迭代器将它们对于的流当做一个特定类型的元素序列来处理。通过使用流迭代器,我们可以用泛型算法从流对象读取数据以及向其写入数据。

  • 反向迭代器

反向迭代器就是在容器中从尾元素向首元素移动的迭代器。对于反向迭代器,递增(以及递减)操作的含义会颠倒过来。除了forward_list之外,其他容器都支持反向迭代器。

可以通过sort传递一对反向迭代器来将vector整理为递减序:

10.5  泛型算法结构

任何算法的最基本的特性是它要求其迭代器提供哪些操作。

  • 5类迭代器(P365)
    类似容器,迭代器也定义了一组公共操作。一些操作所有迭代器都支持,另外一些只有特定类别的迭代器才支持。例如,ostream_iterator只支持递增、解引用和赋值。vector、string和deque的迭代器除了这些操作外,还支持递减、关系和运算符。
  1. 输入迭代器(input iterator):可以读取序列中的元素。一个输入迭代器必须支持:(1)用于比较两个迭代器的相等和不相等运算符(==、!=)。(2)用于推进迭代器的前置和后置递增运算(++)。(3)用于读取元素的解引用运算符(*);解引用只会出现在赋值运算符的右侧。(4)箭头运算符(->),等价于(*it).member。
  2. 输出迭代器
  3. 前向迭代器
  4. 双向迭代器
  5. 随机方位迭代器
  • 算法形参模式
  1. alg(beg, end, other args);
  2. alg(beg, end, dest, other args);
  3. alg(beg, end, beg2, other args);
  4. alg(beg, end, beg2, end2, other args);
  • 算法命名规范
  1. 一些算法使用重载形式传递一个谓词:接受谓词参数来代替<或==运算符的算法,以及那些不接受额外参数的算法,通常都是重载的函数。
  2. _if版本的算法:接受一个元素值的算法通常有另一个不同名的版本,该版本接受一个谓词代替元素值。接受谓词参数的算法都有附加的_if前缀:
10.6 特定容器算法

与其他容器不同,链表类型list和forward_list定义了几个成员函数形式的算法。特别是,他们定义了独有的sort、merge、remove、reverse和unique。
NOTE:对于list和forward_list,应该优先使用成员函数版本的算法而不是通用算法。

表10.6

链表特有的操作会改变容器:多数链表特有的算法都与其通用版本很相似,但不完全相同。链表特有的版本与通用版本间的一个至关重要的区别是链表版本会改变底层的容器。例如,remove的链表版本会删除指定的元素。unique的链表版本会删除第二个后继的重复元素。
类似的,merge和splice会销毁其参数。

发表评论

电子邮件地址不会被公开。 必填项已用*标注