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! 的可能排列中随机选择一种.
- 使用rand函数作为随机函数
- 使用自定义随机数生成函数
partition
基于_Prad,将区域划分成两部分. 前半部分满足_Pred(it)==true,后半部分_Pred(it)==false
