stl make_heap在llvm和g++下的不同实现

先来看一段十分简单的使用stl的c++代码,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
using namespace std;

int main(void) {
vector<int> vec;
int len = 5;
for (int i = 1; i <= len; ++i)
vec.push_back(i);
make_heap(vec.begin(), vec.end());
for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
cout << *iter << " ";
}
cout << endl;
return 0;
}

发现在 xcode 中运行和在 mac terminal 中利用 g++ 编译运行结果不一样,分别为:

1
2
xcode-default : 5 4 2 1 3
terminal-g++ : 5 4 3 1 2

建堆产生不同结果的原因很简单,即两次编译代码所使用的编译器不同,xcode中默认使用”Apple LLVM compiler”,在g++中使用的是”LLVM GCC”。而这两种不同编译器选择的STL实现方法是不一样的,LLVM默认选择”libc++(LLVM C++ standard library)”,而g++默认使用的是”libstdc++(GNU C++ standard library)”。

libc++中的实现

在libc++中make_heap的实现如下所示,从代码中可以看出,通过 __last 这个随机访问的迭代器,从前向后遍历,调用 __push_heap_back 将数据依次插入到堆中。__push_heap_back 的实现是将新插入元素放在堆尾,然后针对这个元素使用 shift up 策略调整至合适位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class _Compare, class _RandomAccessIterator>
void
__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
difference_type __n = __last - __first;
if (__n > 1)
{
__last = __first;
++__last;
for (difference_type __i = 1; __i < __n;)
__push_heap_back<_Compare>(__first, ++__last, __comp, ++__i);
}
}

libstdc++中的实现

在 libstdc++ 中 make_heap 首先将所有元素按照原顺序放入堆的存储结构,然后从最大的非叶子节点开始调整元素位置,即调用 __adjust_heap 操作,__adjust_heap 会自上向下依次选择每个子节点中较大的元素上升。

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
template<typename _RandomAccessIterator>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;

// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);

if (__last - __first < 2)
return;

const _DistanceType __len = __last - __first;
_DistanceType __parent = (__len - 2) / 2;
while (true)
{
std::__adjust_heap(__first, __parent, __len,
_ValueType(*(__first + __parent)));
if (__parent == 0)
return;
__parent--;
}
}

注:以上结果是在 OS X 10.8.4,Xcode4 下的测试结果。不同版本编译器结果会有不同。