（9）STL算法之逆转旋转

1、逆转是指将容器或序列中的元素按逆向顺序翻转。STL算法提供了几个实现逆转功能的算法reverse()和reverse_copy()。先来看看reverse()的底层实现。

template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last);

template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last)
{
    while ((first!=last)&&(first!=--last)) 
    {
        std::iter_swap (first,last);
        ++first;
    }
}

 再来看看reverse_copy()，逆转并复制...

template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy (BidirectionalIterator first,BidirectionalIterator last, OutputIterator result);

template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy (BidirectionalIterator first,BidirectionalIterator last, OutputIterator result)
{
    while (first!=last) 
    {
        --last;
        *result = *last;
        ++result;
    }
    return result;
}

用法示例：

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

void Print(int& elem)
{
	cout << elem << " ";
}

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9 };
	vector<int> v;
	v.assign(arr, arr + 9);
	for (auto it = v.begin(); it != v.end(); it++)
		cout << *it << " ";              // 1 2 3 4 5 6 7 8 9
	cout << endl;
	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), Print);     // 9 8 7 6 5 4 3 2 1
	cout << endl;
	list<int> l1,l2;
	copy(v.rbegin(), v.rend(), back_inserter(l1));
	for (int val : l1)
		cout << val << " ";              // 1 2 3 4 5 6 7 8 9
	cout << endl;
	list<int>::iterator l = l1.begin();
	list<int>::iterator r = l1.end();
	advance(l, 2); 
	advance(r, -2);
	reverse_copy(l, r, back_inserter(l2));
	for (int val : l2)
		cout << val << " ";              // 7 6 5 4 3
	cout << endl;
	return 0;
}

可以看到程序中使用到了advance()，advance()可以很方便的实现容器迭代器的前进与后退，那为什么要用advance实现迭代器的前进与后退，而不像vector容器那样直接写成v.begin()+2呢？原因在于list容器与vector容器的迭代器的移动方式上，vector的迭代器可以使用加法运算，而list容器的迭代器必须使用advance()。

2、旋转

STL提供了对于容器的旋转算法，即rotate()和rotate_copy()，将[first,middle]的元素移动到序列最后边。函数rotate将容器序列看做一个环，来进行旋转并非简单的左移。rotate_copy()在旋转后会复制参加旋转的元素。先来看看它们的底层实现与示例。

template <class ForwardIterator>
ForwardIterator rotate (ForwardIterator first, ForwardIterator middle,ForwardIterator last);

template <class ForwardIterator>
void rotate (ForwardIterator first, ForwardIterator middle,ForwardIterator last)
{
    ForwardIterator next = middle;
    while (first!=next)
    {
        swap (*first++,*next++);
        if (next==last) 
            next=middle;
        else if (first==middle) 
            middle=next;
    }
}

用法示例

#include <iostream>   
#include <algorithm>   
#include <vector> 
using namespace std;

int main() {
    vector<int> v;
    for (int i = 1; i < 10; ++i) 
        v.push_back(i); // 1 2 3 4 5 6 7 8 9
    rotate(v.begin(), v.begin() + 3, v.end());
    // 4 5 6 7 8 9 1 2 3
    for (auto it = v.begin(); it != v.end(); ++it)
        cout << *it <<" ";  // 4 5 6 7 8 9 1 2 3
    cout << endl;
    return 0;
}

rotate_copy()

template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy (ForwardIterator first, ForwardIterator middle,ForwardIterator last, OutputIterator result);

template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy (ForwardIterator first, ForwardIterator middle,ForwardIterator last, OutputIterator result)
{
    result=std::copy (middle,last,result);
    return std::copy (first,middle,result);
}

#include <iostream>     
#include <algorithm>    
#include <vector>   
using namespace std;

int main() {
    int arr[] = { 1,2,3,4,5,6,7,8,9};
    vector<int> v(9);
    rotate_copy(arr, arr + 3, arr + 9, v.begin());
    for (auto it = v.begin(); it != v.end(); ++it)
        cout << *it <<" ";   // 4 5 6 7 8 9 1 2 3
    cout << endl;
    return 0;
}