c++ stl priority queue

This is a discussion on c++ stl priority queue within the C++ Programming forums, part of the General Programming Boards category; hi... i wanted to implement piority queues using c++ stl.... i want to extract both min and max elemnts (compute ...

  1. #1
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197

    c++ stl priority queue

    hi...
    i wanted to implement piority queues using c++ stl....

    i want to extract both min and max elemnts (compute with the extracted value as well a s pop them out of queue)
    for eg:
    stdriority_queue<int> q;
    q.push(i);
    q.push(j);.............
    i am able to pop the largest since front elemnet is largest...

    well i want to pop the smallest elemnts as well..i also want the samallest and largest elemnt to be stored in a temp variable so as to compute sumthng else...

    can u guide me on how do i get there

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If you want the min and the max, then you don't have a priority queue. Maybe you want a set or a map instead.

  3. #3
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    but for that is what priority queue is meant for ...am i right....

    the queue is automatically arranged according to the required spec..

    i dont want to sort in manually as it ll consume a lot of time.....

    extracting min and max from this ll save running time....

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    A set automatically stores it's values from low to high. A map stores it's values according to the key values, low to high (so you can have weights different from the values; if you need more than one item with the same weight, then I guess you need a multimap). Both of them allow access to both the low and the high, unlike a priority queue, which only allows access to the highest value.

  5. #5
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    thanks....can u give me an example on how do i implement it

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If I'm not mistaken, a priority_queue is not just a sorted container (every operation would have a bad complexity). It is based on a heap structure. A heap cannot be a max-heap and a min-heap at the same time. It is easy to get the max item and pop it, but finding the min item would require a linear search in the bottom levels, and popping a min item would require re-heapifying the structure.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Why implement them? They're already there, as std::set and std::map and std::multimap.

  8. #8
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    well i will have duplicating elements too...so i guess set wont work(just now googled...am i right)

    well think i can use mutiset...but what member function ll return min and max....
    wil map ll be more comfortable....

    well i want to know the member functions to take care rather than explicit sorting....

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    .begin() gives the first element of a container. .end() gives one past the end; you can use .rbegin() to get the actual last element I would guess.

    I have no idea what you're asking about sorting.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 09:17 AM
  2. Priority queue STL
    By dpp in forum C++ Programming
    Replies: 2
    Last Post: 01-08-2009, 02:21 AM
  3. Minimum priority queue STL
    By dpp in forum C++ Programming
    Replies: 7
    Last Post: 01-02-2009, 11:33 AM
  4. Priority Queue Help
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 11-15-2007, 12:48 AM
  5. STL min priority queue?
    By *ClownPimp* in forum C++ Programming
    Replies: 7
    Last Post: 04-30-2006, 12:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21