c++ primer 笔记第十章泛型算法

第十章 泛型算法

梗概：介绍了c++标准库里面对顺序容器的很多算法，并且进一步加深的迭代器的讲解。

10.1 概述

算法大多数定义在algorithm头文件中，算法并不直接操作容器而是遍历一个迭代器范围。

迭代器可以让算法不依赖于容器，而是直接通过迭代器操作每个元素。因此依赖于元素类型的操作如< == 等等。

算法本身永远不会改变底层容器的大小，即不会添加删除元素。但是通过操作插入器迭代器可以完成。

 

10.2 初识泛型算法

除了少数例外，标准库算法都是对一个范围内的元素进行操作。

10.2.1 只读算法

只读算法只会读取输入范围内的元素而不改变元素，如find算法。

accumulate算法在numeric中，第三个元素决定了使用的加法类型和返回值类型。迭代器范围内的元素与第三个相容。

equal函数操作两个序列，第三个参数是另一个序列的初始迭代器。假设第二个序列至少和第一个一样长。

 

10.2.2 写容器元素的算法

算法操作的对象大小至少等于写入元素的个数。fill函数。

fill_n函数假定写入操作安全，即容器长度大于等于写入的元素个数，fill_n(dest, n, val)。

back_inserter是插入迭代器，对该迭代器赋值等同于调用push_back。如fill_n(back_inserter(vec), 10,0)。

拷贝算法copy接受三个参数，前两个是个迭代器范围，第三个是目标。假定第二个容器长度不小于第一个。

拷贝函数返回目标位置迭代器递增后的值，如尾后迭代器等。

很多其它函数提供拷贝版本，如replace_copy, remove_copy。

 

10.2.3 重排容器元素的算法

unique函数可以消除连续重复的元素，将不重复的元素集中在容器前部，返回第一个重复元素的迭代器。

一般将sort  unique  和erase配合使用。

 

10.3 定制操作

很多函数隐式调用了元素的一些操作如< == 等，我们可以输入自己编写的类似函数。

10.3.1 向算法传递函数

谓词是一个可以调用的表达式，返回一个能用做条件的值如bool。分为一元谓词和二元谓词。

sort函数默认调用元素的<操作，可以将定制的二元谓词作为第三个参数，如sort(v.begin(), v.end(), compare)。

stable_sort使相等的元素保持原先的顺序。

 

10.3.2 lambda表达式

lambda表达式可以解决谓词不能使用的参数如多于2个参数或者是需要更变的外部变量参数。

lambda即匿名函数，格式[capture list](parameter list) -> return type{function body}。

lambda函数若只含有return语句则可以隐式推断出返回类型，否则需要显式指定。

lambda函数可以接受正常的参数传递，但是不能有默认参数。

捕获列表可以捕获局部变量作为其内部使用，如[sz](const string& a) {return a.size()>sz;}。

find_if类似于find，只是第三个参数从元素值变为一个返回bool型的函数。

for_each函数可以遍历前两个参数范围内的元素并调用第三个函数参数使用元素值。

捕获列表只使用与局部非static变量，lambda可以直接使用局部static变量和所在函数外声明的变量。

 

10.3.3 lambda捕获和返回

lambda函数可以接受值捕获和引用捕获，默认值捕获。

引用捕获必须保证被捕获的变量在函数执行的时候存在。当函数返回lambda 类型对象时尤其注意。

可以使用&和=代表引用捕获和值捕获进行隐式捕获。

lambda函数创建过程可以理解为定义了一个类并返回了该类的一个对象。捕捉列表的值作为数据成员进行初始化。

初始化在函数定义的时候进行，若需要改变捕捉列表的值可以使用引用捕获。

默认情况lambada不改变捕获的值，在函数内改变可以使用mutable声明。在参数列表后。

lambada函数有非return语句时必须指定尾置返回值类型。

 

10.3.4 参数绑定

在一个地方的少数操作使用lambada操作，操作多或者重复使用定义函数更好。

标准库函数bind可以绑定函数参数列表中的部分参数，返回一个新的可调用类型。auto newCallable = bind(callable, arg_list)。

在arg_list中包含_n参数，代表newCallable中的第几个输入，定义在命名空间std::placeholders中，头文件functional中。

bind可以改变参数输入顺序，如 auto g=bind(f, a, b, _2, c, _1)情况下g(x,y)等于调用f(a,b,y,c,x)。

绑定的参数也可以是引用类型，但需要使用一个特殊函数ref， 如bind(print, ref(os), _1, ' ')。绑定os的引用。

 

10.4 再探迭代器

迭代器除了每个容器定义的普通迭代器还包括：

• 插入迭代器：绑定到容器上用来向容器插入元素。
• 流迭代器：绑定到输入输出流上，用来关联相关的IO流。
• 反向迭代器：与普通迭代器移动方向相反，forward_list没有。
• 移动迭代器：专门移动容器中的函数而不是拷贝。

10.4.1 插入迭代器

• back_inserter  每次赋值调用push_back。
• front_inserter 每次赋值调用push_front且返回新插入的首元素的迭代器，因此连续插入会使序列反向。
• inserter  接受两个参数，在第二个参数指定位置之前插入元素，返回原来的第二个参数。

 

10.4.2 iostream迭代器

迭代器把对应的流当成一个特定类型的序列来处理。

istream_iterator使用>>读取流，因此元素必须定义了>>运算符。支持解引用，自增和->。

istream_iterator绑定在一个istream对象，且必须定义类型，如 ifstream in("afile");  istream_iterator<string> str_in(in);

当istream_iterator定义但未绑定时，默认初始化为可以当做尾后值的迭代器。

算法和定义都可以直接操作istream_iterator。如vector<int> vec(in_iter, eof);或 accumulate(in, eof, 0)。

istream_iterator 使用惰性求值，在调用时才读取数据而非定义时。

ostream_iterator使用<<运算符，赋值即输出。

解引用和自增对ostream_iterator对象不做任何操作返回原值，但是有益于格式统一。

copy(v.begin(), v.end(), out_iter）

int main() 
{
	// iterators that can read and write Sales_items
	istream_iterator<Sales_item> item_iter(cin), eof;
	ostream_iterator<Sales_item> out_iter(cout, "\n");

	// store the first transaction in sum and read the next record
	Sales_item sum = *item_iter++; 

	while (item_iter != eof) {
		// if the current transaction (which is in item_iter) 
		// has the same ISBN
	    if (item_iter->isbn() == sum.isbn())
	        sum += *item_iter++; // add it to sum 
		                         // and read the next transaction
	    else {
	        out_iter = sum;      // write the current sum
	        sum = *item_iter++;  // read the next transaction
	    }
	}
	out_iter = sum;  // remember to print the last set of records

	return 0;
}

 

10.4.3 反向迭代器

反向迭代器从尾元素向首元素移动，递增递减操作与普通迭代器反向，forward_list不支持。

只能从即支持++又支持--的迭代器来定义，因此流迭代器不支持。

反向迭代器和迭代器之间的关系:   v.end() 和v.rbegin() 不是指向同一个迭代器，v.end()是尾后，v.rbegin()是尾元素。

同理v.begin()是首元素而 v.rend()是首元素前一个位置，vbegin()和v.rend().base()相同。

 

10.4 泛型算法结构

10.5.1 5类迭代器

迭代器定义了一组公共操作，所有的迭代器都支持，如自加，解引用和赋值。

• 输入迭代器：只读不写，只能自增和单遍顺序扫描算法。递增可能导致其它迭代器失效。
• 输出迭代器：只写不读，只支持自增和解引用。只能向一个迭代器赋值一次。
• 前向迭代器：可读写，只能向前移动。如forward_list的迭代器。
• 双向迭代器：可以读写和双向移动。普通容器的迭代器均为双向迭代器。
• 随机访问迭代器：支持随机访问，< += + - -= <= > >= [n]等等操作。sort需要。string，vector，array和deque的迭代器支持。

 

10.5.2 算法形参模式

算法一般具有如下四种之一的形式：alg(beg,end,other args)  alg(beg,end,dest,other args)  alg(beg, end, beg2, other args) 和alg(beg, end, beg2, end2, other args)。

接收单个目标dest的算法一般假设dest可以写入任意数量的元素，如inserter和ostream_iterator。

接收一个beg2的算法要求第二个容器至少和第一个一样大。

 

10.5.3 算法命名规范

当算法参数可以明显区别时一般直接重载。

否则有_if形式，第三个参数为一个谓词。

_copy形式可以将结果写到新的内存中而不改变原参数。

 

10.6 特定容器算法

链表类型list和forward_list有一些单独定义的算法，sort、merge、remove、reverse和unique。

因为链表的实现方式和其它容器有所区别因此优先使用成员函数算法。

merge合并两个有序链表，第二个链表被删除。

unique直接删除重复元素。

特有的splice函数，根据指定迭代器拼合两个链表。

链表特有的操作会改变容器，如remove和unique都是直接删除。