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. Advertisements

  2. Eric Lilja

    Rolf Magnus Guest

    You could create a copy and empty that.
     
    Rolf Magnus, Feb 15, 2007
    #2
    1. Advertisements

  3. Eric Lilja

    P.J. Plauger Guest

    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. 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.
     
    =?iso-8859-1?q?Erik_Wikstr=F6m?=, Feb 15, 2007
    #4
  5. Eric Lilja

    P.J. Plauger Guest

    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

    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. Oh, right you are. Missread the standard there, will be more carful the
    next time.
     
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Feb 15, 2007
    #7
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.