范型编程_变易算法

---

title: 范型编程_变易算法
date: 2016-05-01 11:47:47
categories: 算法 #文章文类
tags: [范型编程,STL,变易算法,Geekband]

---

定义

指会改变容器中对象的操作

包括:

1. copy 
2. swap 
3. transform
4. replace
5. fill
6. generate
7. remove
8. unique
9. reserve
10. rotate
11. random_shuffle
12. partition

copy

将区域1中的元素全部拷贝到2中. copy可以实现将容器中的对象左移(left shifting)
e.g
std::copy(v.begin()+2, v.end(), v.begin() );

copy_n

将区域1中的前Count个元素拷贝到2中.

copy_backward

将区域1中的内容拷贝的区域2中, 2只给出最后一个元素(v.end()), 从1的最后一个元素开始向前拷贝.
该算法可以实现元素右移(right shifting)

copy_if

区域1中的元素满足 Pred(*it) == true 时,拷贝到区域2中

swap

交换对象

交换对象 _left 和 _right

swap_ranges

两个区域,区域1长度必须要>=区域2, 从第一个元素开始交换对象.

transform(1)

对区域1内的每个元素应用Func(*it) 并将Func执行的结果放入区域2中指定区域:
(dest+i) = Func((it+i))

tansform(2)

将区域1中的每个元素 ,区域2中的每个元素, 应用 Func( *it1, *it2), 然后将Func结果放入Dest中
*(Dest+i) = Func( (it1+i),(it2+i) )

replace(1)

对于区域内每个元素,如果满足 *it == _OldVal, 则执行: *it = _NewVal

replace_if

对区域内每个元素, 如果满足 _Pred(it) == true ,则执行 :it = _Val

replace_copy

将区域1中的元素全部拷贝到区域2中,并且当1中的元素满足*it==_OldVal时 替换为_NewVal

repalce_copy_if

将区域1中的元素拷贝到区域2中,并且当1中的元素满足_Pred(*it, _OldVal) == true时替换为_NewVal

fill

将_Val赋值给区域中的每个元素, 类似于初始化区域
类似于数组中:　double t[10] = {2};

generate

调用Func的结果赋值给区域中的每个元素.
e.g 使用随机数初始化
std::generate(v.begin(), v.end(), rand);

remove

返回一个迭代器it2(it2<=v1.end()),使得 [v1.begin(), it2)中没有与_Val相等的元素

remove_if

返回一个迭代器it2,使得 [v1.begin(), it2)中没有满足_Pred(*it)==true的元素

remove_copy

从区域1中拷贝不等于_Val的元素到_Dest中

unique

返回一个新的迭代器it2, 使得 [v1.begin(), it2)中没有重复出现的元素(只保留一份)

reverse

对区域内的元素进行头尾交换
e.g
v[] = {1,2,3,4,5,6}
After reverse:
v[] = {6,5,4,3,2,1}

rotate

交换区域 [_First, _Mid) <-->[_Mid,_Last)

e.g
v[]={1,2,3,4,5,6}
Mid指向3
After rotate:
v[]={3,4,5,6,1,2}

random_shuffle

对区域内元素进行洗牌. 算法可能性: N = v.size() 那么即从 N! 的可能排列中随机选择一种.

1. 使用rand函数作为随机函数
2. 使用自定义随机数生成函数

partition

基于_Prad,将区域划分成两部分. 前半部分满足_Pred(it)==true,后半部分_Pred(it)==false