1

我正在使用 c++ STL 堆算法,并且我围绕它编写了一个包装类,这样我就可以做一些其他的事情。当我尝试使用下面的代码时,例如:

//! Min-heap wrapper class.
class FMMHeap{
public:
    FMMHeap(Vector &phi) : _phi(phi) {}
    bool operator()(unsigned p1, unsigned p2) {return fabs(_phi(p1)) > fabs(_phi(p2)); }
    inline void pop(){ pop_heap(_heap.begin(),_heap.end(),*this); _heap.pop_back(); }
    [...lots of other stuff...]
    vectorU32 _heap;
    Vector &_phi;
}

它比我有这样一个单独的函数对象时要慢得多:

struct HeapSort{
public:
    HeapSort(Vector &phi) : _phi(phi) {}
    bool operator()(unsigned p1, unsigned p2) {return fabs(_phi(p1)) > fabs(_phi(p2)); }
private:
    Vector &_phi;
};

class FMMHeap{
public:
    FMMHeap(Vector &phi) : cmp(phi) {}
    inline void pop(){ pop_heap(_heap.begin(),_heap.end(),cmp); _heap.pop_back(); }
    [...lots of other stuff...]
    vectorU32 _heap;
    HeapSort cmp;
}

我不确定这是为什么。减速来自 *this 是因为该类有很多数据吗?这似乎很奇怪。还是与函数对象的使用方式有关?

4

2 回答 2

8

我不确定:但可能pop_heap最终会复制您传入的仿函数对象。您的副本FMMHeap会比简单的更昂贵HeapSort

于 2009-11-12T08:25:42.883 回答
0

STL 容器最大的加速是它们的内联,这样编译器就可以计算出如何删除和重新排序东西。

一个很好的猜测是编译器设法以 const 传播阻止它在慢速版本中这样做的方式内联外部函子。

如果 bool 运算符是 const,慢版本会发生什么?

于 2009-11-12T08:30:53.577 回答