c++泛型算法

发表于

一、概述

大多数算法都定义在头文件algorithm中，numeric中定义了一组数值范型算法。
一般情况下，算法不直接操作容器，而是遍历由两个迭代器指定的一个元素范围来进行操作。
通常情况下，算法遍历范围，对其中每个元素进行一些处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int val = 42;

auto result = find(vec.cbegin(), vec.cend(), val);

cout<<"The value "<<val<<(result ==vec.cend() ? "is not present":"is presnet")<<endl;

string val = "a value";

auto result = find(lst.cbegin(),lst.cend(),val);

//在数组上

int ia[] = {24,12,100,109,23,58};
int val = 58;
int *reult = find(begin(ia), end(ia), val);

auto result = find(ia+1, ia+4, val);
算法永远不会执行容器的操作。

它只会运行于迭代器之上，执行迭代器的操作。算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器中移动元素，但永远不会直接添加或删除元素。

标准库定义了一类特殊的迭代器，称为插入器(inserter)。与普通迭代器只能遍历所绑定的容器相比，插入器能在底层的容器上执行插入操作。因此，当一个算法操作一个这样的迭代器时，迭代器可以完成向容器添加元素的效果，但算法自身永远不会做这样的操作。

二、初识泛型算法

大多数标准库算法都对一个范围内的元素进行操作。此元素范围称为“输入范围”。接受输入范围的算法总是使用前两个参数来表示此范围，两个参数分别是指向要处理的第一个元素和尾元素后位置的迭代器。

理解算法的最基本的方法是了解它们是否读取元素、改变元素或是重排元素顺序。

2.1 只读算法

只会读取其输入范围内的元素，而从不改变元素。

accumulate，定义在头文件numeric中。前两个指出需要求和的元素的范围，第三个参数是和的初值。

1
int sum = accumulate(vec.begin(), vec.end(), 0);

第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型。

1
2
3
4
5
6
7
8
string sum = accumulate(v.cbegin(), v.cend(), string(""));

string sum = accumulate(v.cbegin(), v.cend(), "");//错误，用于保存和的对象的类型将是const char*。const char*上没有定义+运算符

std::vector<double> d{1.1, 0.3, 3.4};
std::cout<<std::accumulate(d.cbegin(), d.cend(), 0)<<std::endl;

输出：4，而不是4.8。因为0为int，决定了加法运算符和返回值类型。

对于只读取而不改变元素的算法，通常使用cbegin()和cend()。但是，如果你计划使用算法返回的迭代器改变元素的值，就需要使用begin()和end()。

操作两个序列的算法。

equal，用于确定两个序列是否保存相同的值。如果所有对应元素都相等，则返回true，否则返回false。
此方法接受三个迭代器：前两个表示第一个序列中的元素范围，第三个表示第二个序列中的首元素。

1
2
3
4
5
6
7
8
9
10
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());
//roster2的元素数目至少与roster1一样多

如果roster1:[1,1,2]
roster2:[1,1,2,1]
返回true

如果roster1:[1,1,2]
roster2:[1,1]
返回false

元素类型不必一样，只要能用==来比较两个元素类型即可。roster1可以是vector，roster2是list。

那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长。

2.2写容器元素的算法

将新值赋予序列中的元素。确保序列原大小至少不小于算法写入的元素数目。

1
2
fill(vec.begin(), vec.end(), 0);	
fill(vec.begin(), vec.begin()+vec.size()/2, 10);
迭代器参数：一些算法从两个序列中读取元素。两个序列的元素可以来自于不同类型的容器。类型也不要求严格匹配。

算法不检查写操作

1
2
3
4
5
vector<int> vec;

fill_n(vec.begin(), vec.size(), 0);	//将所有元素置0

fill_n(vec.begin(), 10, 0);	//灾难：修改vec中的10个不存在元素
1
2
3
vector<int> vec;
vec.reserve(10);
fill_n(vec.begin(),10,0);	//此时：vec.size()为0，大小并未改变.可使用back_inserter.
向目的位置迭代器写入数据的算法假定目的位置足够大，能容纳要写入的元素。

介绍back_inserter

头文件。接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中。

1
2
3
vector<int> vec;
auto it = back_inserter(vec);
*it = 42;

常常使用back_inserter来创建一个迭代器，作为算法的目的位置来使用。

1
2
vector<int> vec;
fill_n(back_inserter(vec), 10, 0);	//传递了back_inserter返回的迭代器，每次赋值都会在vec上调用push_back。

拷贝算法

将输入范围中的元素拷贝到目的序列中。传递给copy的目的序列至少要包含与输入序列一样多的元素。

1
2
3
4
5
int a1[] = {0,1,2,3,4,5,6,7,8,9};

int a2[sizeof(a1) / sizeof(*a1)];

auto ret = copy(begin(a1), end(a1), a2);

copy返回的是其目的位置迭代器(递增后)的值。ret恰好指向拷贝到a2的尾元素之后的位置。

replace算法

1
2
3
4
replace(ilst.begin(), ilst.end(), 0, 42);

//使用back_inserter按需要增长目标序列
replace_copy(ilst.begin(), ilst.end(), back_inserter(ivec), 0, 42);

2.3重排容器元素的算法

sort重排输入序列中的元素，利用元素类型的<运算符来实现排序。

1
2
3
4
5
6
void elimDups(vector<string> &words)
{
	sort(words.begin(), words.end());
	auto end_unique = unique(words.begin(), words.end());//返回指向不重复区域之后一个位置的迭代器
	words.erase(end_unique, words.end());//使用容器操作删除元素
}
标准库算法对迭代器而不是容器进行操作。因此算法不能添加或删除元素。

三、定制操作

3.1 向算法传递函数

谓词(predicate)

可调用的表达式，返回结果是一个能用作条件的值。一元谓词，只接受单一参数；二元谓词，有两个参数。

1
2
3
4
5
6
bool isShorter(const string &lhs, const string &rhs)
{
	return lhs.size() < rhs.size();
}

sort(words.begin(), words.end(), isShorter);

排序算法

stable_sort，维持相等元素的原有顺序。

1
2
3
4
5
6
7
elimDups(words);

stable_sort(words.begin(), words.end(), isShorter);

for(const auto &s : words)
	cout<<s<<" ";
cout<<endl;

3.2 lambda表达式

使用标准库find_if算法来查找第一个具有特定大小的元素。find_if第三个参数是一个谓词，接受一个参数，以便能用输入序列的元素调用它，那么就没有办法把长度作为第二个参数传进去了。

介绍lambda

可调用对象：函数、函数指针、重载了函数调用运算符的类、lambda表达式
lambda表达式可以理解为一个未命名的内联函数。

capture list -> return type{function body}

可以忽略参数列表和返回类型，但必须永远包含捕获列表和函数体

auto f = []{return 42;};
cout<<f()<<endl;

如果lambda的函数体包含任何单一return语句之外的内容，且未指定返回类型，则返回void

lambda不能有默认参数，因此一个lambda调用的实参数目永远与形参数目相等。

1
stable_sort(words.begin(), words.end(),[](const string &a, const string &b){return a.size() < b.size();});

使用捕获列表

一个lambda通过将局部变量包含在其捕获列表中来指出将会使用这些变量。只有在捕获列表中，才能在函数题里使用。

1
2
3
4
5
size_t sz =5;

auto wc = find_if(words.begin(), words.end(),[sz](const string&a){return a.size() >= sz;});

for_each(wc,words.end(),[](const string &s){cout<<s<<" ";});
捕获列表只用于所在函数的局部非static变量；可以直接使用局部static变量和函数体之外声明的名字。

3.3 lambda捕获和返回

当定义一个lambda时，编译器生成一个与lambda对应的新的类类型。

值捕获

1
2
3
4
5
6
7
void fcn1()
{
	size_t v1 = 42;	
	auto f = [v1]{return v1;}
	v1 = 0;
	auto j = f();		//j为42；f保存了我们创建它时v1的拷贝
}

引用捕获

当以引用方式捕获一个变量时，必须保证在lambda执行时变量是存在的。

1
2
3
4
5
6
7
8
9
10
11
12
void fcn2()
{
	size_t v1 = 42;
	auto f2 = [&v1]{return v1;};
	v1 = 0;
	auto j = f2();	//j为0；f2保存v1的引用
}

void biggies(vector<int> &words, vector<string>::size_type sz, ostream &os = cout, char c=' ')
{
	for_each(words.begin(), words.end(), [&os,c](const string &s){os<<s<<c;});
}
捕获普通变量，如int string，通常可以用值捕获。如果捕获一个指针或迭代器，或采用引用捕获，必须确保lambda执行时，绑定到迭代器、指针、引用的对象存在。

隐式捕获：&告诉编译器采用引用捕获，=告诉编译器采用值捕获。混合使用时，第一个元素必须为&或＝.

1
2
3
for_each(words.begin(), words.end(), [&,c](const string &s){os<<s<<c;});

for_each(words.begin(), words.end(), [=,&os](const string &s){os<<s<<c;});

可变lambda

值被拷贝的变量，如果希望改变它的值，必须在参数列表后加上mutable。

1
2
3
4
5
6
7
void fcn3()
{
	size_t v1 = 42;
	auto f = [v1]()mutable(return ++v1;);	//不添加mutable，会报错
	v1 = 0;
	auto j = f();		//j为43
}

引用捕获变量是否可修改，依赖于引用的变量是否为const

1
2
3
4
5
6
7
void fcn4()
{
	size_t v1 = 42;
	suto f2 = [&v1]{return ++v1;};
	v1 = 0;
	auto j = f2();	//j为1
}

指定lambda返回值

1
2
3
4
5
transform(vi.begin(), vi.end(), vi.begin(),[](int i){if(i < 0) return -i; else return i;});	//错误：不能推断lambda的返回类型

transform(vi.begin(), vi.end(), vi.begin(),[](int i){return i < 0 ? -i:i;});

transform(vi.begin(), vi.end(), vi.begin(),[](int i) -> int {if(i < 0) return -i; else return i;});

3.4 参数绑定

只在一两个地方使用的简单操作，lambda表达式是最有用的。如果我们需要在很多地方使用相同的操作，通常定义一个函数。

如果lambda的捕获列表为空，通常可以用函数来代替它。

对于捕获局部变量的lambda，用函数来替换它就不容易了。
例如，find_if调用的lambda比较一个string和一个给定大小。

1
2
3
4
bool check_size(const string &s, string::size_type sz)
{
	return s.size() >= sz;
}

但我们不能用这个函数作为find_if的一个参数。find_if接受一个一元谓词。

标准库bind函数
头文件functional，可以看作一个通用的函数适配器，接受一个可调用对象，生成一个新的可调用对象来“适应”源对象的参数列表。

auto newCallable = bind(callable, arg_list);

newCallable本身是一个可调用对象，arg_list是一个逗号分隔的参数列表，对应给定的callable的参数。即，当我们调用newCallable时，newCallable会调用callalbe，并传递给它arg_list中的参数。
arg_list中可能包含“占位符”，形如_n。

_1为newCallable的第一个参数，_2为第二个参数。没有_1，不可能有_2。

绑定check_size的sz参数

1
2
3
4
5
auto check6 = bind(check_size, _1, 6);

string s = "hello";

bool b1 = check6(s);	//check6(s)会调用check_size(s, 6)

使用bind，可以替换原来的lambda。

1
2
3
auto wc = find_if(words.begin(), words.end(), [sz](const string &a) {return a.size() > sz;});

auto wc = find_if(words.begin(), words.end(), bind(check_size, _1, sz));

使用placeholders名字
名字_n都定义在一个名为placeholders的命名空间，这个命名空间定义在std命名空间中。

using std::placeholders::_1;
或者
using namespace std::placeholders;

bind的参数

auto g = bind(f, a, b, _2, c, _1);

g(_1,_2)
映射为
f(a,b,_2,c,_1)
g的第一个参数映射到f的第三个参数，g的第二个参数映射到f的第五个参数

调用g(X,Y)
会调用
f(a,b,Y,c,X)

用bind重排参数顺序

1
2
3
sort(words.begin(), words.end(), isShorter);//由短到长

sort(words.begin(), words.end(), bind(isShorter,_2,_1));//由长到短

绑定引用参数

1
2
3
4
5
6
7
8
9
for_each(words.begin(), words.end(),[&os, c](const string &s){os<<s<<c;});

ostream &print(ostream &os, const string &s, char c)
{
	return os<<s<<c;
}
for_each(words.begin(), words.end(), bind(print, os, _1, ' '));//错误：os不能拷贝

for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));

标准库ref函数返回一个对象，包含给定的引用。还有一个cref函数，生成一个保存const引用的类。ref和cref都定义在functional中。

四、再探迭代器

标准库在头文件iterator中还定义了几种：插入迭代器(insert iterator)、流迭代器(stream iterator)、反向迭代器(reverse iterator)、移动迭代器(move iterator)。

4.1 插入迭代器

是一种迭代器适配器，接受一个容器，生成一个迭代器，能实现向给定容器添加元素。
有三种:

back_inserter：创建一个使用push_back的迭代器，只有容器支持push_back才可以使用

front_inserter：创建一个使用push_front的迭代器，只有容器支持push_front才可以使用

inserter：创建一个使用inserter的迭代器。此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。

理解插入器：当调用inserter(c,iter)时，我们得到一个迭代器，接下来使用它，会将元素插入到iter原来所指向的元素之前的位置。

*it = val;

等价于：

it = c.insert(it, val);        //it指向新加入的元素
++it;    //递增it使它指向原来的元素

1
2
3
4
5
6
7
8
9
10
11

list<int> lst = {1,2,3,4};
list<int> lst2, lst3, lst4(lst);
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
copy(lst.cbegin(), lst.cend(), inserter(lst3,lst3.begin()));
copy(lst.cbegin(), lst.cend(), inserter(lst4,lst4.begin()));

输出分别为：
4 3 2 1
1 2 3 4
1 2 3 4 1 2 3 4

4.2 iostream迭代器

istream_iterator读取输入流，ostream_iterator向一个输出流写数据。

istream_iterator操作

当创建一个流迭代器时，必须指定迭代器将要读写的对象类型。一个istream_iterator使用>>来读取流。因此，istream_iterator要读取的类型必须定义了输入运算符。

语法 解释
istream_iteraotr in(is) in从输入流is读取类型为T的流
istream_iteraotr end 读取类型为T的值的istream_iterator迭代器，表示尾后位置
in1 == in2 in1和in2必须读取相同类型。如果它们都是尾后迭代器或绑定到相同的输入，则相等
in1 != in2
*in 返回从流中读取的值
in->mem 与(*in).mem的含义相同
++in, in++ 使用元素类型所定义的>>运算符从输入流中读取下一个值 
1
2
3
4
istream_iterator<int> int_it(cin);	//从cin读取int
istream_iterator<int> int_eof;		//尾后迭代器
ifstream in("afile");
istream_iterator<string>	str_it(in);	//从"afile"中读取字符串

从输入读取数据，存入一个vector的例子。

1
2
3
4
5
6
istream_iterator<int> in_iter(cin);	//从cin读取int
istream_iterator<int> eof;				//istream尾后迭代器
while(in_iter != eof)	//当有数据可供读取时
{
	vec.push_back(*in_iter++);
}

等价于

1
2
istream_iterator<int> in_iter(cin), eof;//从cin读取int
vector<int> vec(in_iter, eof);	//从迭代器范围构造vec

使用算法操作流迭代

1
2
istream_iterator<int> in_iter(cin), eof;
cout<<accumulate(in,eof,0)<<endl;

ostream_iterator操作

可以对任何具有输出运算符(<<)的类型定义ostream_iteraotr。当创建一个ostream_iterator时，可以提供(可选的)第二参数，是一个字符串，在输出每个元素后都会打印此字符串。必须是C风格字符串(即，一个字符串字面常量或一个指向以空字符串结尾的字符数组的指针)。必须将一个ostream_iterator绑定到一个指定的流，不允许空的或表示尾后位置的ostream_iterator。

语法 解释
ostream_iterator out(os) out将类型为T的值写到输出流os中
ostream_iterator out(os,d) out将类型为T的值写到输出流os中，每个值后面都输出d。d指向一个空字符结尾的字符数组
out = val 用<<运算符将val写入到out绑定的ostream中。val的类型必须与out可写的类型兼容
*out,++out,out++ 这些运算符存在，但部队out做任何事情。每个运算符都返回out 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ostream_iterator<int> out_iter(cout, " ");
for(auto e:vec)
	*out_iter++ = e;
cout<<endl;

可以忽略解引用和递增运算，等价于

for(auto e:vec)
	out_iter = e;
cout<<endl;

copy(vec.begin(), vec.end(), out_iter);
cout<<endl;
```  

4.3 反向迭代器

除了forward_list之外，其他容器都支持反响迭代器。可以通过rbegin、rend、从日本给 i 呢、crend成员函数来获得。递增一个反向迭代器会移动到前一个元素；递减会移动到下一个元素。

vector vec = {0,1,2,3,4};
for(auto r_iter = vec.crbegin(); r_iter != vec.crend(); ++r_iter)
cout<< *r_iter<<endl;
//打印4 3 2 1 0

sort(vec.begin(),vec.end()); //按“正常顺序”排序
sort(vec.rbegin(),vec.rend()); //按“逆序”排序

1
2
3
4
5
6
7

反向迭代器需要递减运算符

调用base()可转换成普通迭代器。


![transform photo](http://o9kchgjar.bkt.clouddn.com/Snip20161211_1.png)

auto comma = find(line.cbegin(), line.cend(), ‘,’);
cout<<string(line.cbegin(),comma)<<endl;
输出:FIRST

auto rcomma = find(line.crbegin(), line.crend(), ‘,’);
cout<<string(line.crbegin(),rcomma)<<endl;
输出：TSAL

cout<<string(rcomma.base(), line.cend())<<endl;
输出LAST
```

五、泛型算法结构

5.1 5类迭代器

输入迭代器：只读不写；单遍扫描，只能递增。操作：== != ++ * ->

输出迭代器：只写不读；单遍扫描，只能递增。操作：++ *

前向迭代器：可读写；多遍扫描，只能递增。操作：== != ++ * ->

双向迭代器：可读写；多遍扫描，可递增递减。操作：== != ++ -- * ->

随机访问迭代器：可读写；多边扫描，支持全部迭代器运算。操作：== != < <= > >= ++ -- + += - -= - * -> iter[n] = *(iter+n)

vector    :    random access iterator
list    :    bidirectional iterator
map        :    bidirectional iterator
set        :    bidirectional iterator
forward_lsit: forward iterator

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参数是一个表示算法可以写入的目的位置的迭代器。按需要写入数据，不管写入多少个都是安全的。常见的：插入迭代器、ostream_iterator。

接受第二个输入序列的算法
单独接受beg2或是接受beg2和end2的算法。接受单独beg2的算法假定从beg2开始的序列与beg和end所表示的范围至少一样大

5.3算法命名规范

一些算法使用重载形式传递一个谓词

接受谓词参数来代替<或==运算符。

unique(beg,end);        //使用==运算符比较元素
unique(beg,end,comp);    //使用comp比较元素

_if 版本的算法
接受一个元素值的算法通常有另一个不同名的版本，该版本接受一个谓词代替元素值。接受谓词参数的算法都有附加的_if前缀。

find(beg, end, val);    //查找输入范围中val第一次出现的位置
find_if(beg, end, pred);    //查找第一个令pred为真的元素

区分拷贝元素的版本和不拷贝的版本
默认情况下，重排元素的算法将重排后的元素写回给定的输入序列中。这些算法还提供另一个版本，将元素写到一个指定的输出目的位置。写道额外目的空间的算法都在名字后面附加一个_copy。

reverse(beg, end);    //翻转输入范围中的元素的顺序
reverse_copy(beg, end);    //将元素按逆序拷贝到dest

一些算法同时提供_copy和_if版本。

remove_if(v1.begin(), v1.end(), [](int i){return i % 2;});

remove_copy_if(v1.begin(), v1.end(), back_inserter(v2),[](int i) {
return i % 2});

六、特定容器算法

list和forward_list定义了几个成员函数形式的算法。它们定义了独有的sort merge remove reverse unique。通用版本的sort要求随机访问迭代器，不能用于list和forward_list。

语法 解释
lst.merge(lst2) 将来自lst2的元素合并入lst。lst和lst2都必须是有序的。元素将从lst2中删除。在合并之后，lst2变为空。第一个版本使用<运算符；第二个版本使用给定的比较操作
lst.merge(lst2,comp)
lst.remove(val) 调用erase删除掉与val相等或令一元谓词为真的每一个元素
lst.remove_if(pred)
lst.reverse() 反转lst中元素的顺序
lst.sort() 使用<或给定比较操作排序元素
lst.sort(comp)
lst.unique() 调用erase删除同一个值的连续拷贝。使用==或谓词
lst.unique(pred)

链表特有的操作会改变容器