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 下的测试结果。不同版本编译器结果会有不同。

C++, STL

Comments