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

Posted on In Symbols count in article: 2.3k Reading time ≈ 2 mins.

先来看一段十分简单的使用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 下的测试结果。不同版本编译器结果会有不同。