???????????????????????????????? ?
reverse算法擴(kuò)充
???????????????????????? 內(nèi)容來(lái)源：TCPL和TCPL題解
在TCPL中的19.1習(xí)題，有對(duì)reverse算法的設(shè)計(jì)。
template<typename Bi> void reverse(Bi begin, Bi end)
從STL的定義來(lái)看，參數(shù)輸入的迭代器是雙向迭代器(Bidirectional iterator)。設(shè)計(jì)起來(lái)也是比較容易的。
namespace{
?template<typename Bi>
?inline void reverse(Bi begin, Bi end){
??while(begin != end)
???iter_swap(begin++, --end);
?}
}
而在TCPL的題解里面提到了輸入?yún)?shù)是向前迭代器的情況（Forward iterator）。這樣reverse算法得重新設(shè)計(jì)。
算法概述：
??? 1.反轉(zhuǎn)一個(gè)向前序列，可以首先將序列分成大致一樣長(zhǎng)的兩半。然后用std::swap_ranges算法交換著兩個(gè)半長(zhǎng)序列。
??? 2.遞歸地反轉(zhuǎn)這個(gè)兩個(gè)半長(zhǎng)序列。
[注意一下序列元素的個(gè)數(shù)（奇偶數(shù)）]
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) //序列個(gè)數(shù)為奇數(shù)
???++begin2;
??std::swap_ranges(begin1, end1, begin2);
??forward_reverse(begin1, half_len);
??forward_reverse(begin2, half_len);
?}
}
再為forward_reverse函數(shù)和reverse（bidirection）函數(shù)提供一個(gè)統(tǒng)一的借口。
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()函數(shù)是通過(guò)函數(shù)重載和迭代器特征類(lèi)（萃取技術(shù)）的結(jié)合來(lái)完成下面兩個(gè)函數(shù)的自動(dòng)選擇。
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);
}
后來(lái)我發(fā)現(xiàn)好像把Forward_iterator的容器并不多見(jiàn)。
STL容器：1、雙向迭代器（Bidirectional iterator）
??????????? list、set、multiset、map、multimap
??????? 2、隨機(jī)存取迭代器（Random access iterator）
??????????? vector、deque、string
附：iterator_traits模板類(lèi)中的一組聲明描述：
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;
};
?