前言

本节就来分析一下 rotate 的实现。为什么前言就一句话！

rotate

rotate 的作用为将 [first,middle) 内的元素和 [middle,last) 内的元素互换。middle 所指的元素会成为容器的第个元素。如果有个数字序列 { 1,2,3,4,5,6,7}，对元素 3 做旋转操作，会形成 {3,4,5,6,7,1,2}。rotate() 可以交换两个长度不同的区间，如下所示。

1.png

做过力扣189. 轮转数组 的人都知道，实现这种效果最简单的方法就是分别在前半段，后半段以及整个区间上各翻转一次，这里的前后段以 middle 分界，这样就可以达到 rotate 的效果，并且代码也最好理解。

当然，STL 中的 rotate 函数仍然不是简单地这样实现的，按照《STL 源码剖析》，rotate 函数的全貌如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/// @brief rotate 的 ForwardIterator 版本 
template  <class ForwardIterator, class Distance>
ForwardIterator rotate_dsipatch(ForwardIterator first, ForwardIterator middle, ForwardIterator last, 
    Distance*, forward_iterator_tag) {
    for (ForwardIterator i = middle;;) {
        tinystl::iter_swap(first, i);  // 前段、后段的元素一一交换
        ++first;                      
        ++i;                                // 双双前进 1
        // 以下判断是前段 [first, middle) 先结束还是后段 [middle, last) 先结束
        if (first == middle) {              // 前段先结束
            if (i == last) return;          // 后段也结束，结束整个循环
            else middle = i;                // 否则调整，对新的前、后段再做交换
        }
        else if (i == last) {               // 后段先结束
            i == middle;                    // 调整前段的区间范围
        }
    }
}

/// @brief rotate 的 BidirectionalIterator 版本
template <class BidirectionalIterator, class Distance>
void rotate_dsipatch(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, 
    Distance*, bidirectional_iterator_tag) {
    tinystl::reverse(first, middle);
    tinystl::reverse(middle, last);
    tinystl::reverse(first, last);
}

/// @brief 辗转相除法求最大公因子
template <class EuclideanRingElement>
EuclideanRingElement gcd(EuclideanRingElement m, EuclideanRingElement n) {
    while (n != 0) {
        auto t = m % n;
        m = n;
        n = t;
    }
    return m;
}

/// @brief 对 [first, last) 内的元素进行循环移位
/// @param first  区间起始位置
/// @param last   区间结束位置
/// @param initial  移动的起始位置
/// @param shift  移动的位数
/// @param T*  用于指定元素类型
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;
}

/// @brief rotate 的 RandomAccessIterator 版本
template <class RandomAccessIterator, class Distance>
void rotate_dispatch(RandomAccessIterator first, RandomAccessIterator middle, 
    RandomAccessIterator last, Distance*, random_access_iterator_tag) {
    // 以下迭代器的相减操作，只适用于 RandomAccessIterator
    // 取全长和前段长度的最大公因子
    Distance n = gcd(last - first, middle - first);
    while (n--) {
        tinystl::rotate_cycle(first, last, first + n, middle - first, value_type(first));
    }
}

/// @brief 将[first, middle)内的元素和 [middle, last)内的元素互换，可以交换两个长度不同的区间
template <class ForwardIterator>
void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last) {
    if (first == middle || middle == last) return;
    tinystl::rotate_dispatch(first, middle, last, distance_type(first), iterator_category(first));
}

总体来说还是根据不同的迭代器类型都实现了各自的版本，其中 BidirectionalIterator 的版本就是反转三次的实现，直接调用 reverse 就行，十分方便。ForwardIterator 版本的实现比较神奇，会辗转移位直到前后区间长度相同，主要适用于与链表类似的结构。RandomAccessIterator 的实现就和 力扣题解 中的环状替换思路相同了，先计算需要循环移位的次数，再逐次调用 rotate_cycle 函数，该函数的作用就是以 initial 为起点，在区间中进行 shift 个单位的移位（实际上是左移）。

就结论而言，STL 中针对每种迭代器实现的 rotate 都是该类型迭代器最高效的实现方式，时间复杂度都是 O(n)O(n) 并且不需要使用额外空间，这也体现了 STL 对于性能极致的优化。

性能测试

来做一下测试，看看我们实现的版本与 STL 的差距，这里只测试了 RandomAccessIterator 的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define TEST_ROTATE(mode, len, count) do { \
  srand((int)time(0)); \
  clock_t start, end; \
  mode::vector<int> v(len); \
  mode::iota(v.begin(), v.end(), 1); \
  start = clock(); \
  for (int i = 0; i < count; ++i) { \
    int middle = rand() % len + 1; \
    mode::rotate(v.begin(), v.begin() + middle, v.end()); \
  } \
  end = clock(); \
  int n = static_cast<int>(static_cast<double>(end - start) \
      / CLOCKS_PER_SEC * 1000); \
  std::cout << "Total time: " << n << " ms\n"; \
} while (0)

TEST(rotate_pk) {
    std::cout << "|    std    |" << std::endl;
    TEST_ROTATE(std, 10000, 10000);
    std::cout << "|  tinystl  |" << std::endl;
    TEST_ROTATE(tinystl, 10000, 10000);
}

结果十分出人意料，按照上述实现的算法和 STL 中的运行效率差别巨大。慢了整整六倍，令人百思不得其解。博主简单查看了一下 stl_algo.h，发现 STL 中真实的实现和《STL源码剖析》中所介绍的差别还是挺大的，比如 RandomAccessIterator 其实并没有调用类似于 rotate_cycle() 的函数，甚至并没有调用 gcd()，而是在函数内部自己实现了类似的功能，同时还使用了在别处定义的大量宏，或许就是这些导致的性能差距吧。

1
2
3
4
5
// Run TestCase:rotate_pk
// |    std    |
// Total time: 14 ms
// |  tinystl  |
// Total time: 86 ms

值得一提的是，最初博主并没有按照《STL源码剖析》中的实现来写 rotate，而是简单地对所有类型迭代器均翻转三次，同样进行测试居然发现这样还稍微快些。

可以参考《编程珠玑》2.3节的内容，翻转三次的方式无论是空间还是时间上都比较优秀，算是既高效又不容易出错的一种实现了。

1
2
3
4
5
6
7
8
9
10
/// @brief 将[first, middle)内的元素和 [middle, last)内的元素互换，可以交换两个长度不同的区间
template <class ForwardIterator>
ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last) {
    auto new_middle = first;
    tinystl::advance(new_middle, last - middle);
    tinystl::reverse(first, last);
    tinystl::reverse(first, new_middle);
    tinystl::reverse(new_middle, last);
    return new_middle;
}

仔细想想的话，上述对 vector 的测试最终其实会调用 RandomAccessIterator 版本的 rotate，翻转三次的做法实际上相当于对整个区间处理了两遍，但理想状态下的 STL 中 RandomAccessIterator 版本的 rotate 做法，只会处理一遍整个区间，因此几乎会快一倍；但实际运行来看并不能达到一倍，这和中间的其他计算有关，如最大公因数的计算等。

1
2
3
4
5
6
7
8
9
10
11
12
// Run TestCase:rotate_pk
// |    std    |
// Total time: 14 ms
// |  tinystl  |
// Total time: 22 ms

// 扩大数量级
//  Run TestCase:rotate_pk
// |    std    |
// Total time: 1686 ms
// |  tinystl  |
// Total time: 2525 ms

总结

这一节分析了 rotate 函数的实现，可以看出 STL 仍然是针对每种迭代器类型都做了优化，使得运行时的效率最佳，但实现的版本与 STL 还是有很大差距，可能与 STL 内部的其他优化有关，留个坑等有空了再填吧咕咕。