现在的位置: 首页 > 综合 > 正文

算法和函数对象

2013年08月28日 ⁄ 综合 ⁄ 共 2302字 ⁄ 字号 评论关闭

算法

在算法描述中,模板参数的名称很重要。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()并不删除重复的元素,他不过是把不重复的元素移向序列的前部(头部),返回指向这段

无重复子序列末端的迭代器。

 

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.......

抱歉!评论已关闭.