reverse算法扩充
内容来源:TCPL和TCPL题解
在TCPL中的19.1习题,有对reverse算法的设计。
template<typename Bi> void reverse(Bi begin, Bi end)
从STL的定义来看,参数输入的迭代器是双向迭代器(Bidirectional iterator)。设计起来也是比较容易的。
namespace{
template<typename Bi>
inline void reverse(Bi begin, Bi end){
while(begin != end)
iter_swap(begin++, --end);
}
}
而在TCPL的题解里面提到了输入参数是向前迭代器的情况(Forward iterator)。这样reverse算法得重新设计。
算法概述:
1.反转一个向前序列,可以首先将序列分成大致一样长的两半。然后用std::swap_ranges算法交换着两个半长序列。
2.递归地反转这个两个半长序列。
[注意一下序列元素的个数(奇偶数)]
template<typename For>
void forward_reverse(For begin1, int len)
{
if(len > 1){
int half_len = len / 2;
For end1 = begin1;
advance(end1, hal_len);
For begin2 = end1;
if(len % 2 != 0) //序列个数为奇数
++begin2;
std::swap_ranges(begin1, end1, begin2);
forward_reverse(begin1, half_len);
forward_reverse(begin2, half_len);
}
}
再为forward_reverse函数和reverse(bidirection)函数提供一个统一的借口。
template<typename It>
inline void flex_reverse(It begin, It end)
{
using std::iterator_traits;
tagged_reverse(begin, end, iterator_traits<It>::iterator_category());
}
tagged_reverse()函数是通过函数重载和迭代器特征类(萃取技术)的结合来完成下面两个函数的自动选择。
template<typename For> //forward_reverse封装
inline void tagged_reverse(For begin, For end, std::forward_iterator_tag)
{
forward_reverse(begin, distance(begin, end));
}
template<typename For> //reverse封装
inline void tagged_reverse(For begin, For end, std::bidirectional_iterator_tag)
{
reverse(begin, end);
}
后来我发现好像把Forward_iterator的容器并不多见。
STL容器:1、双向迭代器(Bidirectional iterator)
list、set、multiset、map、multimap
2、随机存取迭代器(Random access iterator)
vector、deque、string
附:iterator_traits模板类中的一组声明描述:
template<class Iter> struct iterator_traits
{
typedef typename Iter::iterator_category iterator_category;
typedef typename Iter::value_type value_type;
typedef typename Iter::difference_type difference_type;
typedef typename Iter::pointer pointer;
typedef typename Iter::reference reference;
};