priority queue question

Discussion in 'C++' started by vaclavpich@atlas.cz, Oct 28, 2008.

  1. Guest

    Hi all,
    I want to know your opinion about my implemetaion of priority queue. I
    couldn't use std::priority_queue so I've written my. I designed two
    kinds of interface but I'm not sure that this is good idea.
    Please write me what do you think about this :
    /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 1) first class is similar to std::priority_queue
    template<
    class _Ty,
    class _Predicate = Less<_Ty>, // comparator
    class _Container = Array<_Ty> // like std::vector
    >

    class PriorityQueuePolicy
    {
    _Container m_c;
    public:
    // common interface like std::priority_queue
    void push(const _Ty& val);
    _Ty& top();
    void pop();
    };
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 2) this class has only pop and push
    template<
    class _Ty,
    class _Predicate = Less<_Ty>, // comparator
    class _Container = Array<_Ty> // like std::vector
    >

    class PushPopPolicy : protected PriorityQueuePolicy<_Ty, _Predicate,
    _Container >
    {
    typedef PriorityQueuePolicy<_Ty, _Predicate, _Container > base;
    public:
    // common interface like std::priority_queue
    void push(const _Ty& val){
    base::push(val);
    }

    _Ty pop(){
    if( base::empty()) throw exception;
    _Ty val = base::top();
    base::pop();
    return val;
    }
    };
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    //
    template<
    class _Ty,
    class _Predicate = Less<_Ty>,
    class _Container = Array<_Ty>
    class _Policy = PriorityQueuePolicy<_Ty, _Predicate, _Container >
    >

    class PriorityQueue : public _Policy {};
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    Thanks
     
    , Oct 28, 2008
    #1
    1. Advertising

  2. Guest

    On Oct 28, 12:19 pm, wrote:

    > Please write me what do you think about this :
    > /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    > // 1) first class is similar to std::priority_queue


    >     // common interface like std::priority_queue
    >     void push(const _Ty& val);
    >     _Ty& top();
    >     void pop();};


    That interface allows to make those functions strongly exception-safe.

    > // 2) this class has only pop and push


    >     void push(const _Ty& val){
    >     _Ty pop(){
    >         if( base::empty()) throw exception;
    >          _Ty val = base::top();
    >        base::pop();
    >        return val;
    >     }};


    That interface cannot be made strongly exception-safe because
    base::pop() changes the state of the container before the top object
    is handed over to the caller.

    Then, if the copy constructor of _Ty throws during 'return val;' the
    top object is lost. Herb Sutter's book Exceptional C++ and many other
    sources cover this. Here is one:

    http://www.boost.org/community/exception_safety.html

    Ali

    P.S. Any name that begins with an underscore followed by a capital
    letter is reserved. Ty_ would be a better name.
     
    , Oct 29, 2008
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Navhpf

    priority queue

    Navhpf, Feb 23, 2004, in forum: Java
    Replies:
    3
    Views:
    1,006
    Navhpf
    Feb 23, 2004
  2. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    691
    Russell Warren
    Jun 27, 2006
  3. Kelvin Moss

    Priority queue question

    Kelvin Moss, Apr 9, 2008, in forum: C++
    Replies:
    4
    Views:
    425
    Kai-Uwe Bux
    Apr 11, 2008
  4. Marcel Müller
    Replies:
    3
    Views:
    571
    Marcel Müller
    Apr 27, 2009
  5. Kris
    Replies:
    0
    Views:
    494
Loading...

Share This Page