
Boost Users : 
Subject: Re: [Boostusers] [boost][heap] Which heap to use.
From: Juan RamÃrez (jramirez.uy_at_[hidden])
Date: 20160927 10:57:19
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_at_[hidden]> wrote:
> On 25 September 2016 at 17:07, degski <degski_at_[hidden]> 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
>
>
> _______________________________________________
> Boostusers mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
>
 Juan :wq
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net