STL 源码剖析 算法 stl_algo.h -- rotate
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了STL 源码剖析 算法 stl_algo.h -- rotate，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2808字，纯文字阅读大概需要5分钟。
内容图文
本文为senlie原创，转载请保留此地址： http://blog.csdn.net/zhengsenlie
rotate
--------------------------------------------------------------
描述：将[first, middle) 内的元素和[middle, last) 内的元素互换。
图6-6g
/*------------------------------------------------------------
*分派函数(dispatch function)
*/
template <class ForwardIterator>
inline void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last){
if(first == middle || middle == last) return ;
__rotate(first, middle, last, distance_type(first), iterator_category(first));
}
下面根据不同的迭代器类型完成三个旋转操作
rotate 的 forward iterator 版
思路：
1.以短段为依据，对应元素逐一对调
2.调整，对新的前、后段再作交换
3.当两段都结束时，循环结束
图6-6h
复杂度：O(n)
template<class ForwardIterator, class Distance>
void __rotate(ForwardIterator first, ForwardIterator middle,
ForwardIterator last, Distance*, forward_iterator_tag){
for(ForwardIterator i = middle ; ; ){
iter_swap(first, i); //前段，后段的元素一一交换
++first; ++i; // 双双前进 1
// 以下判断是前段[first, middle)先结束还是后段 [middle, last) 后结束
if(first == middle){ //前段结束了
if(i == last) return; //如果后段同时也结束，整个就结束了
middle = i;
}
else if(i == last){ //后段先结束
i = middle; // 调整，准备对新的的前、后段再作交换
}
}
}rotate 的 bidirectional iterator 版
思路：
1.对前段逆转
2.对后段逆转
3.对整体逆转
复杂度：O(n)
图6-6i
template<class BidirectionalIterator, class Distance>
void __rotate(BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last, Distance *,
bidirectional_iterator_tag){
reverse(first, middle);
reverse(middle,last);
reverse(first, last);
}
rotate 的 random access iterator 版 --> ?? 看不太懂。。。
template<class RandomAccessIterator, class Distance>
void __rotate(RandomAccessIterator first, RandomAccessIterator middle，
RandomAccessIterator last, Distance *,
random_access_iterator_tag){
//取全长和前段长度的最大公因子
Distance n = __gcd(last - first, middle - first);
while(n--){
__rotate_cycle(first, last, first + n, middle - first, value_type(first));
}
}
template <class EuclideanRingElement>
EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n)
{
while (n != 0) {
EuclideanRingElement t = m % n;
m = n;
n = t;
}
return m;
}
template <class RandomAccessIterator, class Distance, class T>
void __rotate_cycle(RandomAccessIterator first, RandomAccessIterator last,
RandomAccessIterator initial, Distance shift, T*) {
T value = *initial;
RandomAccessIterator ptr1 = initial;
RandomAccessIterator ptr2 = ptr1 + shift;
while (ptr2 != initial) {
*ptr1 = *ptr2;
ptr1 = ptr2;
if (last - ptr2 > shift)
ptr2 += shift;
else
ptr2 = first + (shift - (last - ptr2));
}
*ptr1 = value;
}
示例：
char alpha[] = "abcdefghijklmnopqrstuvwxyz";
rotate(alpha, alpha + 13, alpha + 26);
printf("%s\n", alpha);
// The output is nopqrstuvwxyzabcdefghijklm
原文：http://blog.csdn.net/zhengsenlie/article/details/37932435
内容总结
以上是互联网集市为您收集整理的STL 源码剖析 算法 stl_algo.h -- rotate全部内容，希望文章能够帮你解决STL 源码剖析 算法 stl_algo.h -- rotate所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。