前言
本节将会分析 merge 与 inplace_merge 的实现，二者的作用都是合并两个有序的区间，不同之处在于 inplace_merge 是原地合并，会更加复杂。
merge
merge() 的作用为将 [first1, last1)、[first2, last2) 两个有序区间的元素合并到以 result 为起始的空间中，重载版本接受一个仿函数 comp 来比较元素的大小，原理十分简单，这里就直接附上代码。
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
|
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result) {
while (first1 != last1 && first2 != last2) {
if (*first2 < *first1) *result++ = *first2++;
else *result++ = *first1++;
}
return tinystl::copy(first2, last2, tinystl::copy(first1, last1, result));
}
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp) {
while (first1 != last1 && first2 != last2) {
if (comp(*first2, *first1)) *result++ = *first2++;
else *result++ = *first1++;
}
return tinystl::copy(first2, last2, tinystl::copy(first1, last1, result));
}
|
inplace_merge
inplace_merge 的作用为，将两个连接在一起的有序序列 [first, middle)、[middle, last) 合并为一个有序序列，该算法会申请额外的缓冲空间（buffer），但在没有申请成功的情况下也能原地的进行合并，但是效率会差些。同样的，这个函数也提供一个可以输入仿函数的版本。
temporary_buffer
其中，inplace_merge 在申请缓冲区时用到了一个特殊的数据结构 —— temporary_buffer，这是个比较简单的类模板，主要就是负责缓冲区的管理，这个类被定义在了 stl_tembuf.h 中，TinySTL 中将其放在了 memory.h 里。
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
|
template <class ForwardIterator, class T>
class temporary_buffer {
private:
ptrdiff_t original_len;
ptrdiff_t len;
T* buffer;
public:
temporary_buffer(ForwardIterator first, ForwardIterator last);
~temporary_buffer() {
tinystl::destroy(buffer, buffer + len);
free(buffer);
}
public:
ptrdiff_t size() const noexcept { return len; }
ptrdiff_t requested_size() const noexcept { return original_len; }
T* begin() const noexcept { return buffer; }
T* end() const noexcept { return buffer + len; }
private:
void allocate_buffer();
void initialize_buffer(const T&, std::true_type) {}
void initialize_buffer(const T& value, std::false_type) {
tinystl::uninitialized_fill_n(buffer, len, value);
}
private:
temporary_buffer(const temporary_buffer&) = delete;
void operator=(const temporary_buffer&) = delete;
};
template <class ForwardIterator, class T>
temporary_buffer<ForwardIterator, T>::
temporary_buffer(ForwardIterator first, ForwardIterator last) {
try {
len = tinystl::distance(first, last);
allocate_buffer();
if (len > 0) {
initialize_buffer(*first, std::is_trivially_default_constructible<T>());
}
} catch (...) {
free(buffer);
buffer = nullptr;
len = 0;
}
}
template <class ForwardIterator, class T>
void temporary_buffer<ForwardIterator, T>::allocate_buffer() {
original_len = len;
if (len > static_cast<ptrdiff_t>(INT_MAX / sizeof(T))) {
len = INT_MAX / sizeof(T);
}
while (len > 0) {
buffer = static_cast<T*>(malloc(len * sizeof(T)));
if (buffer) break;
len /= 2;
}
}
|
temporary_buffer 这个类就是简单地调用 malloc 申请空间并维护缓冲区，不使用 STL 自带的 alloc 等空间配置器，也没有提供更多的操作，这样设计是为了使一些算法在申请缓冲区时代价尽量小。另外，在 alloc_buffer 中可以看到，在申请缓冲区时会尽量满足大小的要求，如果申请不到这么多的空间就会将目标大小减半继续申请，直到申请到空间或减小到 0，因此返回的缓冲区大小可能会与需求的大小不一致。
inplace_merge
由于这个函数比较复杂，因此这里我们拆看一步一步地来分析：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last) {
if (first == middle || middle == last) return;
tinystl::inplace_merge_aux(first, middle, last, value_type(first));
}
template <class BidirectionalIterator, class T>
void inplace_merge_aux(BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last, T*) {
auto len1 = tinystl::distance(first, middle);
auto len2 = tinystl::distance(middle, last);
temporary_buffer<BidirectionalIterator, T> buf(first, last);
if (buf.begin() == nullptr) {
tinystl::merge_without_buffer(first, middle, last, len1, len2);
}
else {
tinystl::merge_adaptive(first, middle, last, len1, len2, buf.begin(), buf.size());
}
}
|
首先需要注意的是 inplace_merge 接受的最低迭代器类型为 BidirectionalIterator，这一点与 merge 不同， merge 只需要顺序地处理两个区间即可，因此接受的是最低的 InputIterator 类型。
inplace_merge 在简单地去除不需要合并的情况后就直接转调用了 inplace_merge_aux；inplace_merge_aux 会先计算两个区间的长度并维护，毕竟除了 RandomAccessIterator 外计算迭代器之间的距离也不是这么容易的，此外会申请缓冲区并根据是否申请到了缓冲区调用不同的函数。
merge_without_buffer
首先先来看看 merge_without_buffer 的实现：
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
|
template <class BidirectionalIterator, class Distance>
void merge_without_buffer(BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last, Distance len1, Distance len2) {
if (len1 == 0 || len2 == 0) return;
if (len1 + len2 == 2) {
if (*middle < *first) tinystl::iter_swap(first, middle);
return;
}
auto first_cut = first;
auto second_cut = middle;
Distance len11 = 0;
Distance len22 = 0;
if (len1 > len2) {
len11 = len1 >> 1;
tinystl::advance(first_cut, len11);
second_cut = tinystl::lower_bound(middle, last, *first_cut);
len22 = tinystl::distance(middle, second_cut);
}
else {
len22 = len2 >> 1;
tinystl::advance(second_cut, len22);
first_cut = tinystl::upper_bound(first, middle, *second_cut);
len11 = tinystl::distance(first, first_cut);
}
auto new_middle = tinystl::rotate(first_cut, middle, second_cut);
tinystl::merge_without_buffer(first, first_cut, new_middle, len11, len22);
tinystl::merge_without_buffer(new_middle, second_cut, last, len1 - len11, len2 - len22);
}
|
这个函数的实现十分巧妙，通过递归的方式不断将区间划分为更小的区间再处理，是一种“分治”的思想。
具体来说，每一次 merge_without_buffer 会将 [first, middle) 中较大的部分旋转到区间后半段，[middle, last) 中较小的部分旋转到区间前半段，这样前后两部分就变得有序了，只需分别处理前后两部分即可，有点类似于快排，毕竟都是分治。
最终交换元素是通过 iter_swap 与 rotate 实现的，rotate 就是前面分析过的那个函数，rotate。
至于为什么每次都要选择较长的那个区间进行分割，这是出于效率的考虑，把区间切割成长度差不多的两个区间才能保证 O(logn) 的时间复杂度，否则性能就会逐渐向 O(n) 退化。
merge_adaptive
接下来再来分析一下 merge_adaptive。
首先需要介绍两个辅助函数：
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
|
template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator1 merge_backward(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
BidirectionalIterator2 first2, BidirectionalIterator2 last2,
BidirectionalIterator1 result) {
if (first1 == last1) return tinystl::copy_backward(first2, last2, result);
if (first2 == last2) return tinystl::copy_backward(first1, last1, result);
--last1;
--last2;
while (true) {
if (*last2 < *last1) {
*--result = *last1;
if (first1 == last1) return tinystl::copy_backward(first2, ++last2, result);
--last1;
}
else {
*--result = *last2;
if (first2 == last2) return tinystl::copy_backward(first1, ++last1, result);
--last2;
}
}
}
template <class BidirectionalIterator1, class BidirectionalIterator2, class Distance>
BidirectionalIterator1 rotate_adaptive(BidirectionalIterator1 first, BidirectionalIterator1 middle,
BidirectionalIterator1 last, Distance len1, Distance len2,
BidirectionalIterator2 buffer, Distance buffer_size) {
BidirectionalIterator2 buffer_end;
if (len1 > len2 && len2 <= buffer_size) {
buffer_end = tinystl::copy(middle, last, buffer);
tinystl::copy_backward(first, middle, last);
return tinystl::copy(buffer, buffer_end, first);
}
else if (len1 <= buffer_size) {
buffer_end = tinystl::copy(first, middle, buffer);
tinystl::copy(middle, last, first);
return tinystl::copy_backward(buffer, buffer_end, last);
}
else {
return tinystl::rotate(first, middle, last);
}
}
|
merge_backward 主要用于缓冲区能够装下第二个序列时直接进行反向合并，这也是为什么 inplace_merge 一定要接受 BidirectionalIterator 的原因，rotate_adaptive 则是根据缓冲区的情况来决定如何旋转两个序列；值得一提的是，虽然 rotate 的实现已经足够高效，但能够直接使用 memset 的 copy() 无疑要更快些。
接下来就是 merge_adaptive 了，该函数的逻辑其实与 merge_without_buffer 类似，在缓冲区不够大时依然会分治然后递归调用，缓冲区足够大时当然就直接合并了。
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
|
template <class BidirectionalIterator, class Distance, class Pointer>
void merge_adaptive(BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last, Distance len1, Distance len2,
Pointer buffer, Distance buffer_size) {
if (len1 <= len2 && len1 <= buffer_size) {
Pointer buffer_end = tinystl::copy(first, middle, buffer);
tinystl::merge(buffer, buffer_end, middle, last, first);
}
else if (len2 <= buffer_size) {
Pointer buffer_end = tinystl::copy(middle, last, buffer);
tinystl::merge_backward(first, middle, buffer, buffer_end, last);
}
else {
auto first_cut = first;
auto second_cut = middle;
Distance len11 = 0;
Distance len22 = 0;
if (len1 > len2) {
len11 = len1 >> 1;
tinystl::advance(first_cut, len11);
second_cut = tinystl::lower_bound(middle, last, *first_cut);
len22 = tinystl::distance(middle, second_cut);
}
else {
len22 = len2 >> 1;
tinystl::advance(second_cut, len22);
first_cut = tinystl::upper_bound(first, middle, *second_cut);
len11 = tinystl::distance(first, first_cut);
}
auto new_middle = tinystl::rotate_adaptive(first_cut, middle, second_cut, len1 - len11, len22,
buffer, buffer_size);
tinystl::merge_adaptive(first, first_cut, new_middle, len11, len22, buffer, buffer_size);
tinystl::merge_adaptive(new_middle, second_cut, last, len1 - len11, len2 - len22, buffer, buffer_size);
}
}
|
这就是 inplace_merge 的全貌了，总的来说该函数会根据申请缓冲区的情况来采取最高效的实现，另外辅助函数的方方面面也都体现着 STL 对于效率的优化。
总结
本节分析了合并有序区间的两个函数 merge 与 inplace_merge，这两个函数的不同之处主要在两方面：
merge 接受的最低迭代器为 InputIterator 而 inplace_merge 则需要 BidirectionalIterator 类型的迭代器。merge 需要将结果存在以 result 为首的另一个位置，而 inplace_merge 则是原地操作，且在没有额外缓冲区的情况下也能正常执行。
这两个函数都利用“分治”的手段来递归处理区间，是十分经典的算法。
