priority queue

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

  1. Guest

    Hi all,
    I want to now your opinion on interface of my priority_queue. I now
    std has very good a priority_queue. But I couldn't use std. So I had
    to write my.
    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // example :
    // this class has the same interface like std::priority_queue
    template<
    class _Ty, // type to store
    class _Predicate = Less<_Ty>, // comparator
    class _Container = Array<_Ty> //
    >

    class StlPriorityQueuePolicy
    {
    _Container m_Cont;
    public:
    // common interface :
    push(const _Ty& val)
    _Ty& top();
    void pop();
    };
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // class has only push and pop methods
    template<
    class _Ty, // type to store
    class _Predicate = Less<_Ty>, // comparator
    class _Container = Array<_Ty> //
    >

    class PushPopPriorityQueuePolicy : protected
    StlPriorityQueuePolicy<_Ty, _Predicate, _Container >
    {
    typedef StlPriorityQueuePolicy<_Ty, _Predicate, _Container >
    base;
    public:
    // common interface :
    push(const _Ty& val){
    base::push(val);
    }
    _Ty pop(){
    if(base::is_empty()) throw exception;
    _Ty elem = base::top();
    base::pop();
    return elem;
    }
    };

    template<
    class _Ty,
    class _Predicate = Less<_Ty>,
    class _Container = Array<_Ty>,
    template<class, class, class> _PriorityQueuePolicy =
    StlPriorityQueuePolicy<>
    >

    class PriorityQueue : public _PriorityQueuePolicy< _Ty, _Predicate,
    _Container> {};
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    I'm not sure that this is very clever interface. Maybe is complicated
    to use.A lot of people know how to use std::priority_queue.It is good
    but I prefer the second policy. I know about one disadvantige of
    PushPopPriorityQueuePolicy. Pop method has to create an element which
    return. In the other hand PushPopPriorityQueuePolicy is very simple to
    use.

    If you know better way to implement priority queue please can you show
    me how.

    Thank you.
     
    , Oct 25, 2008
    #1
    1. Advertising

  2. Joe Gottman Guest

    wrote:
    > Hi all,
    > I want to now your opinion on interface of my priority_queue. I now
    > std has very good a priority_queue. But I couldn't use std. So I had
    > to write my.
    > //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    > // example :
    > // this class has the same interface like std::priority_queue
    > template<
    > class _Ty, // type to store
    > class _Predicate = Less<_Ty>, // comparator
    > class _Container = Array<_Ty> //
    > class StlPriorityQueuePolicy
    > {
    > _Container m_Cont;
    > public:
    > // common interface :
    > push(const _Ty& val)
    > _Ty& top();
    > void pop();
    > };
    > ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    > // class has only push and pop methods
    > template<
    > class _Ty, // type to store
    > class _Predicate = Less<_Ty>, // comparator
    > class _Container = Array<_Ty> //
    > class PushPopPriorityQueuePolicy : protected
    > StlPriorityQueuePolicy<_Ty, _Predicate, _Container >
    > {
    > typedef StlPriorityQueuePolicy<_Ty, _Predicate, _Container >
    > base;
    > public:
    > // common interface :
    > push(const _Ty& val){
    > base::push(val);
    > }
    > _Ty pop(){
    > if(base::is_empty()) throw exception;
    > _Ty elem = base::top();
    > base::pop();
    > return elem;
    > }
    > };
    >
    > template<
    > class _Ty,
    > class _Predicate = Less<_Ty>,
    > class _Container = Array<_Ty>,
    > template<class, class, class> _PriorityQueuePolicy =
    > StlPriorityQueuePolicy<>
    > class PriorityQueue : public _PriorityQueuePolicy< _Ty, _Predicate,
    > _Container> {};
    > ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    > I'm not sure that this is very clever interface. Maybe is complicated
    > to use.A lot of people know how to use std::priority_queue.It is good
    > but I prefer the second policy. I know about one disadvantige of
    > PushPopPriorityQueuePolicy. Pop method has to create an element which
    > return. In the other hand PushPopPriorityQueuePolicy is very simple to
    > use.
    >
    > If you know better way to implement priority queue please can you show
    > me how.
    >
    > Thank you.
    >
    >
    >
    >
    >


    The main problem is that it is impossible to make the pop() function
    exception-safe. pop() returns the top object by value, so it has to
    call a copy constructor inside the return statement. If that copy
    constructor throws (for instance if you have a priority_queue<string>)
    then even if you catch the exception and successfully deal with its
    underlying cause, you can't recover the element returned by pop() since
    it has already been removed from your priority_queue. What the standard
    does is define two member functions: top() which returns a reference or
    const reference to the top element and cannot throw; and pop() which
    erases the top element and returns void.


    Joe Gottman
     
    Joe Gottman, Oct 26, 2008
    #2
    1. Advertising

  3. James Kanze Guest

    On Oct 26, 12:02 am, Joe Gottman <> wrote:

    [...]
    > The main problem is that it is impossible to make the pop()
    > function exception-safe.


    For certain types. And a certain definition of "exception
    safe".

    > pop() returns the top object by value, so it has to
    > call a copy constructor inside the return statement. If that copy
    > constructor throws (for instance if you have a priority_queue<string>)
    > then even if you catch the exception and successfully deal with its
    > underlying cause, you can't recover the element returned by pop() since
    > it has already been removed from your priority_queue.


    It's important to realize the limitations of this idiom,
    but it's also important to realize that they don't always apply.
    Tom Cargill's article ("Exception Handling: a False Sense of
    Security",
    http://www.informit.com/content/images/020163371x/supplements/Exception_Handling_Article.html)
    was important in making us realize the limitations, but as David
    Abrahams points out in a footnote to "Exception-Safety in
    Generic Components"
    (http://www.boost.org/community/exception_safety.html),
    "Probably the greatest impediment to a solution in Cargill's
    case was an unfortunate combination of choices on his part: the
    interface he chose for his container was incompatible with his
    particular demands for safety. By changing either one he might
    have solved the problem." The key is matching the interface to
    the requirements. Is strong exception safety a requirement?
    (It's rarely really necessary.) Do we need to support objects
    whose copy constructor may throw? (Almost all of my queues only
    contain pointers, and the copy constructor of a pointer can
    never throw.)(

    > What the standard does is define two member functions: top()
    > which returns a reference or const reference to the top
    > element and cannot throw; and pop() which erases the top
    > element and returns void.


    What the standard does is overreact to a perceived problem.
    There's nothing wrong with a pop which returns the value if the
    copy constructor can't throw, or if you don't need the strong
    exception safety guarantee (if e.g. the queue is going to be
    destroyed as a result of stack unwinding due to the exception).

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Oct 28, 2008
    #3
    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,000
    Navhpf
    Feb 23, 2004
  2. Aaron W. LaFramboise

    Stable priority queue

    Aaron W. LaFramboise, Apr 5, 2004, in forum: C++
    Replies:
    19
    Views:
    1,546
    Claudio Puviani
    Apr 7, 2004
  3. Russell Warren

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

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    685
    Russell Warren
    Jun 27, 2006
  4. Marcel Müller
    Replies:
    3
    Views:
    565
    Marcel Müller
    Apr 27, 2009
  5. Kris
    Replies:
    0
    Views:
    486
Loading...

Share This Page