STL算法学习

一   函数对象： 因为很多的算法中多使用了函数对象

二元函数对象，V1和V2为输入，V3为结果

plus:
  transform(V1.begin(), V1.end(), V2.begin(), V3.begin(),plus());

其他的二元函数对象：minus,multiples,divieds,modulus.

二元断言函数对象，使用时需要bind2nd（）或bind1st（）来绑定比较对象。

less:
  find_if(L.begin(), L.end(), bind2nd(less(), 0));

其他的二元断言函 数：equal_to,notequal_to,greater,greater_equal,less_equal,logical_and,logical_or

二元逻辑函数

binary_negate:
const char* wptr = find_if(str, str + MAXLEN,
                           compose2(not2(logical_or()),
                                    bind2nd(equal_to(), ' '),
                                    bind2nd(equal_to(), '\n')));

一元函数对象

negate：
transform(V1.begin(), V1.end(), V2.begin(),
          negate());

一元断定函数对象

logical_not:
  transform(V.begin(), V.end(), V.begin(), logical_not());

一元逻辑函数

unary_negate:

二   函数对象发生器：主要用来填充序列。


产生不重复的随机数：
// Generate unique random numbers from 0 to mod:
class URandGen {
  std::set used;
  int limit;
public:
  URandGen(int lim) : limit(lim) {
    srand(time(0));
  }
  int operator()() {
    while(true) {
      int i = int(rand()) % limit;
      if(used.find(i) == used.end()) {
        used.insert(i);
        return i;
      }
    }
  }
};

const int sz = 10;
const int max = 50;
vector x(sz), y(sz), r(sz);
//An integer random number generator:
URandGen urg(max);
generate_n(x.begin(), sz, urg);

三 函数对象适配器 ： 将函数转化为函数对象

ptr_fun:一般函数适配器

一元实例：
transform(first, last, first,
          compose1(negate, ptr_fun(fabs)));

二元实例：
list::iterator item =
              find_if(L.begin(), L.end(),
                      not1(binder2nd(ptr_fun(strcmp), "OK")));

not1：对一元的断定函数对象取反的适配器。

not2: 对二元的断定函数对象取反的适配器。

mem_fun与mem_fun_ref：类成员函数的适配器,区别是一个需要指针，而另一个仅需要一般对象。如下：
shape 是一个指针变量，则foreach(v.begin(),v.end(),mem_fun(&shape::draw));
但如果 shape是一般的变量，不是指针，则 foreach（v.begin(),v.end(),mem_fun_ref(&shape::draw)）；

四   算法：

拷贝：
copy（）
reverse_copy()
rotate_copy()
remove_copy()  拷贝不等于某值的元素到另一个序列。
remove_copy_if() 拷贝符合条件的到另一个序列。

填充和生成：
fill()
fill_n() 填充序列中的n个元素。
generate（）为序 列中的每个元素调用gen（）函数。

排列：
next_permuttion() 后一个排列。
prev_permutation()

partition() 划分，将满足条件的元素移动到序列的前面。
stable_partition()

查找和替换：
find（）
binary_search() 在一个已经有顺序的序列上查找。
find_if()
search() 检查第二个序列是否在第一个序列中出现，且顺序相同。

删除：注意必须调用erase（）来真正删除
remove（）
unique（）删除相邻重复元素，最好 现排序。

合并序列：
merge（）

数值算法：
accumulate（） 对序列的每个元素进行运算后求和。
transform（） 也可以对每个元素进行运算。
计数：
size（）总个数。
count（）等于某值的元素个数。

adjacent_difference 序列中的后一个减前与他相邻的前一个得到新的序列。

adiacent_find

-----------------------------------------------------------------------------------------------------------------------------------------------------------
                

算法部分主要由头文件， 和组成。
是所有STL头文件中最大的一个，它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到 的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。
体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。
中则定义了一些模板类，用以声明函数对象。

一、查找算法
adjacent_find()      //搜索相等或满足条件的邻近元素
binary_search()     //对一个范围的中的元素进行测试，是否与指定数相等或满足一个二元断言
count_if()       //得到容器内满足条件的元素个数。
equal_range()
find_end()  //从末尾开始找与指定范围相等的位置，
find_first_of()
find_if()
lower_bound()  //在一有序元素组得到第一个不小于指定元素的位置
upper_bound()
search()         //在范围内搜索与目标范围相同或满足二元断言
search_n()

二、排序(sorting)和通用(ordering)算法
inplace_merge()  //把两组元素合并成一组，新组成的元素将以指定的方法排序
merge()                //合成两组有序元素范围到出口
nth_element()      //以第n个元素为基准，前面的元素都不大于它，后面的元素都大于它 ，但结果非有序
partial_sort()       //部分排序，形如找出最小的5个元素
partial_sort_copy()     //上面的副本版
partition()             //以某个一元断言把指定数组分成两部分，但两部分是在一起的
random_shuffle()  //随机洗
reverse()                //逆序
reverse_copy()       
rotate()                 //滚动，集体逆序
rotate_copy()
sort()               
stable_sort()        //保证相等元素的原来顺序不变。
stable_partition()  //把一组元素分成两部分，左边（begin边）满足条件,右边不满足条件

三、删除和替换算法
copy()                      //把一个范围内的元素以正方向复制到OutIterator
copy_backwards() //只不过是反方向复制，从屁股复制到屁股
iter_swap()              //交换两指定元素
remove()        //移除干扰的元素，返回的new_end与原end间为移除的元素
remove_copy()  //复制不包括指定元素的范围到新的迭代器
remove_if()         /移除所有满足条件的元素
remove_copy_if()
replace()        //把指定范围的指定元素替换成指定元素
replace_copy()
replace_if()      //把指定范围内的满足条件元素替换成指定元素
replace_copy_if()       
swap()       
swap_range()  //范围交换
unique()       //在相邻一定范围内移除重复的原素
unique_copy()

四、排列组合，生成和异变，堆算法
   next_permutation()  //返回排列组合的下一个原素（字典排序）
  prev_permutation()  //排列组合倒推
  fill()                    //以某一元素为样板在一定范围内清一色填充
   fill_n()                //n表示填充个数
  for_each()         //对每个元素以正方向用某个函数对其操作一遍
   generate()       //对一个范围内的元素以发生器的结果赋值
   generate_n()     // n表示填充个数
   transform()         //换条件变化一组元素到输出
   make_heap()  //把最大的元素放在首位，创建堆
   pop_heap()        //往堆中增加一个原素
   push_heap()      //把最大的元素从堆顶移到最后，并从余下堆中取出最大的数放在最前
  sort_heap()      //堆的排序

五、关系算法，集合算法
equal()                       //两组元素进行二元比较，判断是否相等
includes()                   //判断一个范围的元素是不是另一范围的子集
lexicographical_compare()
max()                      //比较两个元素返回找大的
max_element()       //上面的范围版
min()                  
min_element()
mismatch()           //比较两个范围，返回第一个不同位置
set_union()              //合并2个集合
set_intersection()              //取交集
set_difference()             //取第一个集合减去第二个集合
set_symmetric_difference()        //取只在一个集合中存在的元素集合