The Coder

I am a humble coder.

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  4 随笔 :: 4 文章 :: 9 评论 :: 0 Trackbacks

                                   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;
};

 

posted on 2006-06-05 19:38 TH 阅读(400) 评论(0)  编辑 收藏 引用 所属分类: STL和标准函数库

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理