Printing priority_queue without emptying it?

Discussion in 'C++' started by Eric Lilja, Feb 15, 2007.

  1. Eric Lilja

    Eric Lilja Guest

    Hello, I have a the following priority_queue: priority_queue<pair<int,
    string> > pq;

    AFAICT, priority_queues doesn't support iterators. My question: is
    there a way to print its contents without emptying it?
    Right now I'm using the following code:

    while (!pq.empty())
    {
    cout << setw(3) << pq.top().first << ": " << pq.top().second <<
    endl;
    pq.pop();
    }

    -Eric
    Eric Lilja, Feb 15, 2007
    #1
    1. Advertising

  2. Eric Lilja

    Rolf Magnus Guest

    Eric Lilja wrote:

    > Hello, I have a the following priority_queue: priority_queue<pair<int,
    > string> > pq;
    >
    > AFAICT, priority_queues doesn't support iterators. My question: is
    > there a way to print its contents without emptying it?


    You could create a copy and empty that.

    > Right now I'm using the following code:
    >
    > while (!pq.empty())
    > {
    > cout << setw(3) << pq.top().first << ": " << pq.top().second <<
    > endl;
    > pq.pop();
    > }
    Rolf Magnus, Feb 15, 2007
    #2
    1. Advertising

  3. Eric Lilja

    P.J. Plauger Guest

    "Rolf Magnus" <> wrote in message
    news:er1pv0$r7q$02$-online.com...

    > Eric Lilja wrote:
    >
    >> Hello, I have a the following priority_queue: priority_queue<pair<int,
    >> string> > pq;
    >>
    >> AFAICT, priority_queues doesn't support iterators. My question: is
    >> there a way to print its contents without emptying it?

    >
    > You could create a copy and empty that.
    >
    >> Right now I'm using the following code:
    >>
    >> while (!pq.empty())
    >> {
    >> cout << setw(3) << pq.top().first << ": " << pq.top().second <<
    >> endl;
    >> pq.pop();
    >> }


    You can derive a class from priority_queue that accesses its protected
    member c, which is the underlying container. Note that it is organized
    as a heap, if the order of presentation matters to you.

    P.J. Plauger
    Dinkumware, Ltd.
    http://www.dinkumware.com
    P.J. Plauger, Feb 15, 2007
    #3
  4. On Feb 15, 3:12 pm, "Eric Lilja" <> wrote:
    > Hello, I have a the following priority_queue: priority_queue<pair<int,
    > string> > pq;
    >
    > AFAICT, priority_queues doesn't support iterators. My question: is
    > there a way to print its contents without emptying it?
    > Right now I'm using the following code:
    >
    > while (!pq.empty())
    > {
    > cout << setw(3) << pq.top().first << ": " << pq.top().second <<
    > endl;
    > pq.pop();
    >
    > }


    I also ran into this some time ago and decided that it was better for
    me to use a normal vector and sort it before starting to retrieve
    elements. This was actually faster than inserting the elements into
    the priority_queue and then retrieving them since insertion was O(1)
    for the vector. This option might not be available for you if you do
    not first insert all the elements and later only extracts.

    What you can do is to use the the fact that you can specify the
    container in the constructor, something like:

    std::vector base;
    std::priority_queue(std::less(), base) queue;

    Then push()/pop() from the queue but iterate over base. Be aware that
    if you make any changes to base you should run std::make_heap() on it.

    You might have guessed by now that priority_queue is just a wrapper
    that uses make_heap(), pop_heap() and push_heap() on a underlying
    container, which is why it's called an adaptor and not a container.

    --
    Erik Wikström
    =?iso-8859-1?q?Erik_Wikstr=F6m?=, Feb 15, 2007
    #4
  5. Eric Lilja

    P.J. Plauger Guest

    "Erik Wikström" <> wrote in message
    news:...

    On Feb 15, 3:12 pm, "Eric Lilja" <> wrote:
    > Hello, I have a the following priority_queue: priority_queue<pair<int,
    > string> > pq;
    >
    > AFAICT, priority_queues doesn't support iterators. My question: is
    > there a way to print its contents without emptying it?
    > Right now I'm using the following code:
    >
    > while (!pq.empty())
    > {
    > cout << setw(3) << pq.top().first << ": " << pq.top().second <<
    > endl;
    > pq.pop();
    >
    > }


    I also ran into this some time ago and decided that it was better for
    me to use a normal vector and sort it before starting to retrieve
    elements. This was actually faster than inserting the elements into
    the priority_queue and then retrieving them since insertion was O(1)
    for the vector. This option might not be available for you if you do
    not first insert all the elements and later only extracts.

    What you can do is to use the the fact that you can specify the
    container in the constructor, something like:

    std::vector base;
    std::priority_queue(std::less(), base) queue;

    Then push()/pop() from the queue but iterate over base. Be aware that
    if you make any changes to base you should run std::make_heap() on it.

    You might have guessed by now that priority_queue is just a wrapper
    that uses make_heap(), pop_heap() and push_heap() on a underlying
    container, which is why it's called an adaptor and not a container.

    [pjp] Nope. This constructor uses base to *initialize* the protected
    member c, which is of type container_type, not container_type&. So
    any changes to the priority_queue are *not* reflected in base.

    P.J. Plauger
    Dinkumware, Ltd.
    http://www.dinkumware.com
    P.J. Plauger, Feb 15, 2007
    #5
  6. Eric Lilja

    David O Guest

    <snip>
    > You can derive a class from priority_queue that accesses its protected
    > member c, which is the underlying container. Note that it is organized
    > as a heap, if the order of presentation matters to you.
    >
    > P.J. Plauger
    > Dinkumware, Ltd.http://www.dinkumware.com


    Deriving from priority_queue is necessary to resolve other
    limitations. I once needed to implemented a timeout queue for a
    relatively large number of protocol sessions, which seemed a natural
    mapping to a priority_queue of (smart pointers to) session objects
    inversely sorted by their time value, so the soonest to elapse was
    always highest priority.

    Adding sessions is naturally done by push(), and using the time value
    of the top() element as parameter of the main loop select() prevents
    busy waiting (priming the queue with a sentinel object set to expire
    at the end of time simplifies a lot of details). Unfortunately, this
    doesn't allow for the times to change (so as to reset a timeout) or to
    remove an element (for an expired session), so I added functions to
    the derived class to do this - fortunately, the algorithms to
    rebalance the heap (e.g. __push_heap(), __adjust_heap()) are probably
    already in your standard library implementation, but require their
    names and interfaces are library dependant.

    Best Regards,

    David O.
    David O, Feb 15, 2007
    #6
  7. On 2007-02-15 17:53, P.J. Plauger wrote:
    > "Erik Wikström" <> wrote in message
    > news:...
    >
    > On Feb 15, 3:12 pm, "Eric Lilja" <> wrote:
    >> Hello, I have a the following priority_queue: priority_queue<pair<int,
    >> string> > pq;
    >>
    >> AFAICT, priority_queues doesn't support iterators. My question: is
    >> there a way to print its contents without emptying it?
    >> Right now I'm using the following code:
    >>
    >> while (!pq.empty())
    >> {
    >> cout << setw(3) << pq.top().first << ": " << pq.top().second <<
    >> endl;
    >> pq.pop();
    >>
    >> }

    >
    > I also ran into this some time ago and decided that it was better for
    > me to use a normal vector and sort it before starting to retrieve
    > elements. This was actually faster than inserting the elements into
    > the priority_queue and then retrieving them since insertion was O(1)
    > for the vector. This option might not be available for you if you do
    > not first insert all the elements and later only extracts.
    >
    > What you can do is to use the the fact that you can specify the
    > container in the constructor, something like:
    >
    > std::vector base;
    > std::priority_queue(std::less(), base) queue;
    >
    > Then push()/pop() from the queue but iterate over base. Be aware that
    > if you make any changes to base you should run std::make_heap() on it.
    >
    > You might have guessed by now that priority_queue is just a wrapper
    > that uses make_heap(), pop_heap() and push_heap() on a underlying
    > container, which is why it's called an adaptor and not a container.
    >
    > [pjp] Nope. This constructor uses base to *initialize* the protected
    > member c, which is of type container_type, not container_type&. So
    > any changes to the priority_queue are *not* reflected in base.


    Oh, right you are. Missread the standard there, will be more carful the
    next time.

    --
    Erik Wikström
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Feb 15, 2007
    #7
    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. Daren
    Replies:
    0
    Views:
    379
    Daren
    Dec 19, 2005
  2. Wendy Smoak

    cached backed or self-emptying map

    Wendy Smoak, Apr 29, 2005, in forum: Java
    Replies:
    2
    Views:
    441
    Wendy Smoak
    Apr 29, 2005
  3. Lee

    Stack emptying

    Lee, Sep 23, 2005, in forum: C Programming
    Replies:
    5
    Views:
    349
    Keith Thompson
    Sep 24, 2005
  4. J.M.
    Replies:
    18
    Views:
    587
    Howard Hinnant
    Feb 6, 2007
  5. Bill Cunningham

    emptying files

    Bill Cunningham, Nov 18, 2008, in forum: C Programming
    Replies:
    19
    Views:
    457
    Bill Cunningham
    Nov 20, 2008
Loading...

Share This Page