11.1 概述1. 算法如何工作
每个泛型算法的实现都独立于单独的容器,这些算法还是大而不全的,并且不依赖于容器存储的元素。
2. 标准算法固有的独立于类型
算法只在一点上隐式的依赖元素类型,必须能够对元素作比较运算。
3. 迭代器将算法和容器绑定起来
算法从不执行容器提供的操作,只是单独以来迭代器和迭代器操作实现。
11.2 初窥算法
#include <algorithm> //常用算法
#include <numeric> //泛化的算术算法
11.2.1 只读算法
例如求vector<int> vec;中元素的和
int sum = accumulate(vec.begin() , vec.end(), 0) ;
//最后一个参数为累加初始值,该参数很有必要,告诉了该函数累加值得类型,或者可转化的类型
find_first_of的使用
//roster1、roster2为名字的list容器,求其相同名字个数
size_t cnt = 0;
list<string>::iterator it = roster1.begin() ;
while( (it = find_first_of(it, roster1.end(), roster2.begin(), roster2.end() ) ) != roster1.end() )
{
++cnt ;
++it ;
}
cout << "'found" << cnt << "names on both rosters."<<endl;
// roster1、roster2的类型不比精准匹配,只要这两个序列的元素可以相等操作符比较即可
11.2.2 写容器元素的算法
fill(iterator1, iterator2, iterator1,value)
fill_n(iterator1, num , value); //填充存在的元素,否则未定义
back_inserter //插入迭代器
fill_n(back_inserter(vec) , 10 , 0 ) ; //在末尾插入填充
copy(iter1, iter2, iter_dst) ; //^_^ 多明显需要解释么?
replace(iter1, iter2, 0 ,42) ; //这个是注释
replace_copy(iter1, iter2, iter_dest, 0 ,42) ;
//可能你都不想往这里看了,但是这次需要解释一下,这个算法功能类似于copy+replace的结合。并且iter_dest也可以使用插入迭代器,向空的容器中复制元素。
11.2.3 对容器中元素重新排序的算法
sort(iterator1, iterator2);
iterator end_unique = unique(iterator1, iterator2);
stable_sort(iterator1,iterator2, predicate);
count_if(iterator1, iterator2, predicate);
predicate 谓词,也就是做某些检测的函数
11.3 再谈迭代器
另外三种迭代器:
(1) 插入迭代器
(2) iostream迭代器
(3) 反向迭代器
11.3.1 插入迭代器
有三种插入迭代器
back_inserter 使用push_back插入的迭代器
front_inserter 使用push_front插入的迭代器
inserter 使用insert插入的迭代器
11.3.2 流迭代器
流迭代器的定义:
istream_iterator<T> in(strm);
istream_iterator<T> in;
ostream_iterator<T> out(strm);
ostream_iterator<T> out(strm, delima);
11.3.3 反向迭代器
反向迭代器和其他迭代器的关系:riterator.base(); 产生普通迭代器,其位置是反向迭代器的向后的一个位置,类似于rbegin() 和 end() 返回的迭代器之间的关系
11.3.4 const迭代器
PS:流使用迭代器等应包含iterator 头文件
11.4 泛型算法的结构
通用泛型算法和某些容器特有的算法