一 算法。
在算法描述中,模板参数的名称很重要。In、Out、For、Bi、Ran分别表示输入,输出,前向,双向和随即访问迭代器。Pred表示一元谓词,BinPred表示二元谓词,Cmp表示比较操作,Op表示一元操作,BinOp表示二元操作。如果传递一个为提供所需操作的 类型,就将在模板实例化的时候产生一个错误。
二 函数对象 谓词 约束器 适配器 否定器
2.1谓词综述,
在<functional>里,标准库提供了一些常用谓词:
equal_to, not_equal_to m,greater,less,greater_equal,less_equal,logical_and,logical_or,logical_not.
2.2 约束器 适配器 和否定器
这些适配器具有统一的结构,他们都依赖于函数对象基类 unary_function 和binary_function。
三 非修改性序列算法。
1 比较常见的 for_each
2 查找 find find_if. find()可以看成find_if的一个==作为谓词的版本。
3 计数.count ,count_if.
4 equal, mismatch().
5 search() , search_n(), find_end()... 这个find_end()相当于反向的search(),但是为什么用find的名字呢。
四 修改性序列算法。
借助迭代器的操作都不能改变容器的大小,除了无法插入或删除元素以外,这些算法可以修改元素的值,交换元素,复制元素等。
甚至remove的操作也是通过腹泻掉一些元素的的方式完成的。
1 copy
2 transform
3 unique.
unique()并不删除重复的元素,他不过是把不重复的元素移向序列的前部(头部),返回指向这段
无重复子序列末端的迭代器。
//或者精简如下
template<class For> For unique(For first,For last)
{
first = adjacent_find(first,last);
return unique_copy(first,last,first);
}
unique其实只删除了相邻是重复的。为了清除所有的重复的,输入序列首先先排序,然后再如此。应该确认在排序和删除重复时使用的是同一个准则。
4 replace replace_copy.
template<class In,class Out,class T>
Out replace_copy(In first,In last,Out res,const T& val,const T& new_val)
{
while(first != last)
{
*rest++ = (*first == val)?new_val:*first;
++first;
}
}
5 remove remove_copy remove_copy_if
6 fill generate. fill 不过是generate的一个特殊情况,其中的函数反复给出同样的值。
7 reverse rotate random_shuffle ..and so on.
四 排序。
1 sort()算法需要随机访问迭代器。他们最好用在vector中。
stable_sort能保持其相对顺序的不改变,而sort则不行。
partial_sort.
nth_element.
2 二分检索。binary_search()
3 merge inplace_merge.
4 划分。partition.
5 序列上的集合运算。
确保这些容器都是已排序的。
includes() set_union set_intersection set_difference set_symmetric_difference
10 排列。
对于元素的顺序,每种组合都是一种排列。
可以获取排列的算法: next_permutation prev_permutation.
continue tomorrow.......