STL学习笔记(变序性算法)
变序性算法改变元素的次序,但不改变元素值。
这些算法不能用于关联式容器,因为在关联式容器中,元素有一定的次序,不能随意变动。
逆转元素次序
void
reverse(BidirectionalIterator beg,BidirectionalIterator end)
OutputIterator
reverse_copy(BidirectionalIterator sourceBeg,BidirectionalIterator sourceEnd,
OutputIterator destBeg)
1.reverce()会将区间[beg,end)内的元素全部逆序
2.reverse_copy()是reverse()跟copy()的组合
下面这个程序展示reverse()和reverse_copy()的用法
#include <iterator>
#include "algostuff.hpp"
using namespace std; int main()
{
vector<int> coll;
INSERT_ELEMENTS(coll,,);
PRINT_ELEMENTS(coll,"coll: ");
reverse(coll.begin(),coll.end());
PRINT_ELEMENTS(coll,"coll: ");
reverse(coll.begin()+,coll.end()-);
PRINT_ELEMENTS(coll,"coll: ");
reverse_copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
cout<<endl;
}
旋转(Rotating)元素次序
1.旋转序列内的元素
void
rotate(ForwardIterator beg,ForwardIterator newBeg,
ForwardIterator end)
1.将区间[beg,end)内的元素进行旋转,执行后*newBeg成为新的第一元素
2.调用者必须确保newBeg是[beg,end)内的一个有效位置,否则会引发未定义的行为
以下程序示范如何使用rotate()
#include "algostuff.hpp"
using namespace std; int main()
{
vector<int> coll;
INSERT_ELEMENTS(coll,,);
PRINT_ELEMENTS(coll,"coll: ");
rotate(coll.begin(),coll.begin()+,coll.end());
PRINT_ELEMENTS(coll,"one left: ");
rotate(coll.begin(),coll.end()-,coll.end());
PRINT_ELEMENTS(coll,"two right: ");
rotate(coll.begin(),find(coll.begin(),coll.end(),),coll.end());
PRINT_ELEMENTS(coll,"4 first: ");
}
2.复制并同时旋转元素
OutputIterator
rotate_copy(ForwardIterator sourceBeg,ForwardIterator newBeg,
ForwardIterator sourceEnd,
OutputIterator destBeg)
这是copy()和rotate()的组合
以下程序示范rotate_copy()的用法
#include <iterator>
#include "algostuff.hpp"
using namespace std; int main()
{
set<int> coll;
INSERT_ELEMENTS(coll,,);
PRINT_ELEMENTS(coll);
set<int>::iterator pos=coll.begin();
advance(pos,);
rotate_copy(coll.begin(),pos,coll.end(),ostream_iterator<int>(cout," "));
cout<<endl;
pos=coll.end();
advance(pos,-);
rotate_copy(coll.begin(),pos,coll.end(),ostream_iterator<int>(cout," "));
cout<<endl;
rotate_copy(coll.begin(),coll.find(),coll.end(),ostream_iterator<int>(cout," "));
cout<<endl;
}
排列元素(Permuting)元素
bool
next_permutation(BidirectionalIterator beg,
BidirectionalIterator end)
bool
prev_permutation(BidirectionalIterator beg,
BidirectionalIterator end)
1.next_permutation()会改变区间[beg,end)内的元素次序,使他们符合“下一个排列次序”
2.prev_permutation()会改变区间[beg,end)内的元素次序,是他们符合“上一个排列次序”
下面这个例子展示利用next_permutation()和prev_permutation()将所有元素的所有可能排列的过程
#include "algostuff.hpp"
using namespace std; int main()
{
vector<int> coll;
INSERT_ELEMENTS(coll,,);
PRINT_ELEMENTS(coll,"on entry: ");
while(next_permutation(coll.begin(),coll.end()))
PRINT_ELEMENTS(coll," ");
PRINT_ELEMENTS(coll,"afterward: ");
while(prev_permutation(coll.begin(),coll.end()))
PRINT_ELEMENTS(coll," ");
PRINT_ELEMENTS(coll,"now: ");
while(prev_permutation(coll.begin(),coll.end()))
PRINT_ELEMENTS(coll," ");
PRINT_ELEMENTS(coll,"afterward: ");
}
重排元素(Shuffling,搅乱次序)
void
random_shuffle(RandomAccessIterator beg,RandomAccessIterator end)
void
random_shuffle(RandomAccessIterator beg,RandomAccessIterator end,
RandomFunc& op)
1.第一形式使用一个均匀分布随机数产生器来打乱区间[beg,end)内的元素次序
2.第二形式使用op打乱区间[beg,end)内的元素次序。
以下程序示范如何调用random_shuffle()来打乱元素次序
#include <cstdlib>
#include "algostuff.hpp"
using namespace std; class MyRandom
{
public:
ptrdiff_t operator()(ptrdiff_t max)
{
double tmp;
tmp=static_cast<double>(rand())/static_cast<double>(RAND_MAX);
return static_cast<ptrdiff_t>(tmp * max);
}
}; int main()
{
vector<int> coll;
INSERT_ELEMENTS(coll,,);
PRINT_ELEMENTS(coll,"coll: ");
random_shuffle(coll.begin(),coll.end());
PRINT_ELEMENTS(coll,"shuffled: ");
sort(coll.begin(),coll.end());
PRINT_ELEMENTS(coll,"sorted: ");
MyRandom rd;
random_shuffle(coll.begin(),coll.end(),rd);
PRINT_ELEMENTS(coll,"shuffled: ");
}
将元素向前搬移
BidirectionalIterator
partition(BidirectionalIterator beg,
BidirectionalIterator end,
UnaryPredicate op)
BidirectionalIterator
stable_partition(BidirectionalIterator beg,
BidirectionalIterator end,
UnaryPredicate op)
1.这两种算法将区间[beg,end)中造成以下一元判断式:op(elem)结果为true的元素向前端移动
2.stable_partition()会保持元素之间的相对次序。
以下程序示范partition()和stable_partition()的用法以及两者的区别
#include "algostuff.hpp"
using namespace std; int main()
{
vector<int> coll1;
vector<int> coll2;
INSERT_ELEMENTS(coll1,,);
INSERT_ELEMENTS(coll2,,);
PRINT_ELEMENTS(coll1,"coll1: ");
PRINT_ELEMENTS(coll2,"coll2: ");
cout<<endl;
vector<int>::iterator pos1,pos2;
pos1=partition(coll1.begin(),coll1.end(),not1(bind2nd(modulus<int>(),)));
pos2=stable_partition(coll2.begin(),coll2.end(),not1(bind2nd(modulus<int>(),)));
PRINT_ELEMENTS(coll1,"coll1: ");
cout<<"first odd element: "<<*pos1<<endl;
PRINT_ELEMENTS(coll2,"coll1: ");
cout<<"first odd elements: "<<*pos2<<endl;
PRINT_ELEMENTS(coll2,"coll2: ");
}
最新文章
- Android中editText使用报错
- Prism中使用MEF的例子
- git 查看、创建、删除 本地,远程 分支
- hdu 2579 Dating with girls(2)
- Sql 执行删除修改之前添加备份
- left join 过滤条件写在on后面和写在where 后面的区别
- Android的SoundPool
- WordPress Videowall插件‘page_id’参数跨站脚本漏洞
- Codeforces Round #335 (Div. 1)--C. Freelancer&#39;s Dreams 线性规划对偶问题+三分
- 虚拟机设备直通的两种方式(Working in Progress)
- jQuery来源学习笔记:扩展的实用功能
- OpenLayers.Map的一些特殊事件
- springmvc框架原理分析和简单入门程序
- 最简单的设计模式——单例模式的演进和推荐写法(Java 版)
- Error - SqlDateTime overflow. Must be between 1/1/1753 12:00:00 AM and 12/31/9999 11:59:59 PM
- oracle 数据库密码过期
- elasticsearch权威指南
- PX Deq: Execution Msg 等待事件
- Cocos 开发笔记
- js检测密码强度
热门文章
- [LeetCode] Binary Tree Inorder Traversal 中序排序
- Synthesis of memory barriers
- CString::GetLength()获得字节数
- read 系统调用剖析【转】
- Windows环境Vim编辑器如何执行Ruby代码
- Flex与51单片机socket通信 策略问题
- springBoot 微服务
- 二十六个月Android学习工作总结【转】
- UVA 10369 - Arctic NetWork (求最小生成树)
- FZU-2270 Two Triangles(两个三角形全等)