I am finding difficult to understand your answer, but I try to address the following question: >> *What criteria should I use to choose a specific Boost.Heap implementation from the ones provided by the Boost.Heap library?* Boost.Heap's data structures are documented here: http://www.boost.org/doc/libs/1_61_0/doc/html/heap/data_structures.html There is a simple table which shows the complexity for every public function you may use. Just go through those functions and look for the ones your are going to use the most and then choose the ones with less complexity. In most cases *fibonacci_heap* will be the best option... When in doubt, just go for fibonacci_heap. Best regards Juan On Tue, Sep 27, 2016 at 11:20 AM, degski <degski@gmail.com> wrote:

On 25 September 2016 at 17:07, degski <degski@gmail.com> wrote:

...

What criteria should I use to choose a specific Boost.Heap implementation (skew, fibonacci etc), from the ones provided by the Boost.Heap library?

Well, as no answer, wrote my own:

#define BV_NOEXCEPT noexcept #define BV_CONST_NOEXCEPT const noexcept

template < typename T > class priority_queue {

private:

typedef std::vector < T > Data;

public:

typedef typename Data::iterator iterator; typedef typename Data::const_iterator const_iterator;

private:

Data m_data;

public:

priority_queue ( ) BV_NOEXCEPT {

m_data.reserve ( 16 ); }

iterator begin ( ) BV_NOEXCEPT {

return m_data.begin ( ); }

const_iterator begin ( ) BV_CONST_NOEXCEPT {

return m_data.begin ( ); }

iterator end ( ) BV_NOEXCEPT {

return m_data.end ( ); }

const_iterator end ( ) BV_CONST_NOEXCEPT {

return m_data.end ( ); }

void push ( const T & t_ ) BV_NOEXCEPT {

const const_iterator i = std::lower_bound ( m_data.begin ( ), m_data.end ( ), t_, std::greater < T > ( ) );

if ( i == m_data.end ( ) or std::greater < T > ( ) ( t_, * i ) ) {

m_data.insert ( i, t_ ); } }

inline void pop ( ) BV_NOEXCEPT {

if ( m_data.size ( ) ) {

m_data.pop_back ( ); } }

inline T top ( ) BV_CONST_NOEXCEPT {

return m_data.back ( ); }

inline size_t size ( ) BV_CONST_NOEXCEPT {

return m_data.size ( ); }

inline bool empty ( ) BV_CONST_NOEXCEPT {

return m_data.empty ( ); } };

Have a good day,

degski

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

-- Juan :wq

Hi,

You've understood my question to a t. What I wanted was that link, but one don't get to that page from http://www.boost.org/doc/libs/1_61_0/doc/html/heap.html, which seems (to me) to be a (slight) problem. In the meanwhile I think I got (wrote) a better solution, as posted. Thanks for the post/response.

Your solution has linear complexity, while the heaps provided have logarithmic complexity. (insertion in the middle of a vector is a linear time operation). That is hardly better. For your case, boost::heap::priority_queue is perfect.

On 27 September 2016 at 18:55, Oswin Krause <Oswin.Krause@ruhr-uni-bochum. de> wrote:

...

Your solution has linear complexity...

It's actually log n. HAGD, degski

On 27 September 2016 at 23:06, Juan Ramírez <jramirez.uy@gmail.com> wrote:

vector<T>::insert is your bottleneck here:

You're absolutely right, if only inserting in a vector were cheap, life would be better. But like I said earlier, the constants (as compared to a heap or a set) are different... I timed my use-case and got an answer... Thanks for the feed-back, degski

Hi,

Yes, of course it has linear complexity, but the factors are much smaller. My test-case (which is more demanding than my use-case) with a (max heap) size of about 50'000 beats any (more intelligent) solution heads down. I'll just conclude with a quote: “In theory, theory and practice are the same. In practice, they are not.” When you have only 10 elements, you are free to do whatever you want, but as soon as you have a relevant amount, it is going to be hard to beat the std::heap because it is such an efficient data structure.

Have a nice day, Oswin