Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > priority_queue<> underlying container

Reply
Thread Tools

priority_queue<> underlying container

 
 
Dave
Guest
Posts: n/a
 
      04-22-2004

Hello all,

I'm pondering why the default underlying container for std:riority_queue<>
is std::vector<>. It would seem that inserts are liable to happen anywhere,
which would make std::list<> a superior alternative. Why factors am I not
considering here? Why in the general case would std::vector<> be best?

Thanks,
Dave


 
Reply With Quote
 
 
 
 
Joe Gottman
Guest
Posts: n/a
 
      04-22-2004

"Dave" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
>
> Hello all,
>
> I'm pondering why the default underlying container for

std:riority_queue<>
> is std::vector<>. It would seem that inserts are liable to happen

anywhere,
> which would make std::list<> a superior alternative. Why factors am I not
> considering here? Why in the general case would std::vector<> be best?
>


A priority_queue is generally implemented as a heap, which requires
random-access iterators.

Joe Gottman


 
Reply With Quote
 
 
 
 
John Carson
Guest
Posts: n/a
 
      04-22-2004
"Dave" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)
> Hello all,
>
> I'm pondering why the default underlying container for
> std:riority_queue<> is std::vector<>. It would seem that inserts
> are liable to happen anywhere, which would make std::list<> a
> superior alternative. Why factors am I not considering here? Why in
> the general case would std::vector<> be best?
>
> Thanks,
> Dave



According to Josuttis (The C++ Standard Library), priority queues are sorted
using the heap sorting algorithm. A heap sort is only a partial sort (which
allows it to be O(n), in contrast to full sorting algorithms which tend to
be O(n*log n)). A heap sort requires that the container offer a random
access iterator, which list does not do. The fact that the vector only needs
to be partially sorted also reduces the cost of insertion.


--
John Carson
1. To reply to email address, remove donald
2. Don't reply to email address (post here instead)

 
Reply With Quote
 
Claudio Puviani
Guest
Posts: n/a
 
      04-22-2004
"John Carson" <(E-Mail Removed)> wrote
> "Dave" <(E-Mail Removed)> wrote
> > Hello all,
> >
> > I'm pondering why the default underlying container for
> > std:riority_queue<> is std::vector<>. It would seem that inserts
> > are liable to happen anywhere, which would make std::list<> a
> > superior alternative. Why factors am I not considering here? Why in
> > the general case would std::vector<> be best?
> >
> > Thanks,
> > Dave

>
>
> According to Josuttis (The C++ Standard Library), priority queues are sorted
> using the heap sorting algorithm. A heap sort is only a partial sort (which
> allows it to be O(n), in contrast to full sorting algorithms which tend to
> be O(n*log n)). A heap sort requires that the container offer a random
> access iterator, which list does not do. The fact that the vector only needs
> to be partially sorted also reduces the cost of insertion.


You're confusing two completely different things. std:riority_queue uses a
heap DATA STRUCTURE, not a heap sort ALGORITHM. The heap sort algorithm, by the
way, works in O(n log n), not O(n) and does NOT sort partially; the result of a
heap sort is a fully sorted sequence. The heap sort algorithm USES a heap data
structure to perform its work, but the heap data structure has uses other than
sorting... such as priority queues.

You can read up on the details in any good book on data structures and
algorithms (Knuth if you're techically inclined, or Sedgewick if you prefer a
didactic approach).

Claudio Puviani


 
Reply With Quote
 
John Carson
Guest
Posts: n/a
 
      04-22-2004
"Claudio Puviani" <(E-Mail Removed)> wrote in message
news:aRMhc.93090$(E-Mail Removed). net
> "John Carson" <(E-Mail Removed)> wrote
>>
>>
>> According to Josuttis (The C++ Standard Library), priority queues
>> are sorted using the heap sorting algorithm. A heap sort is only a
>> partial sort (which allows it to be O(n), in contrast to full
>> sorting algorithms which tend to be O(n*log n)). A heap sort
>> requires that the container offer a random access iterator, which
>> list does not do. The fact that the vector only needs to be
>> partially sorted also reduces the cost of insertion.

>
> You're confusing two completely different things. std:riority_queue
> uses a heap DATA STRUCTURE, not a heap sort ALGORITHM. The heap sort
> algorithm, by the way, works in O(n log n), not O(n) and does NOT
> sort partially; the result of a heap sort is a fully sorted sequence.
> The heap sort algorithm USES a heap data structure to perform its
> work, but the heap data structure has uses other than sorting... such
> as priority queues.
>
> You can read up on the details in any good book on data structures and
> algorithms (Knuth if you're techically inclined, or Sedgewick if you
> prefer a didactic approach).
>
> Claudio Puviani




Thanks for that. You are right. I was basing my remarks on the
half-remembered discussion in Eric Roberts, Programming Abstractions in C,
which, now that I check, does indeed deal with a heap data structure (in
which data is partially sorted) rather than a heap sort. I transferred that
hazy memory into my reading of Josuttis. Apologies to all concerned for the
misinformation.


--
John Carson
1. To reply to email address, remove donald
2. Don't reply to email address (post here instead)

 
Reply With Quote
 
Howard Hinnant
Guest
Posts: n/a
 
      04-22-2004
In article <aRMhc.93090$(E-Mail Removed)> ,
"Claudio Puviani" <(E-Mail Removed)> wrote:

> "John Carson" <(E-Mail Removed)> wrote
> > "Dave" <(E-Mail Removed)> wrote
> > > Hello all,
> > >
> > > I'm pondering why the default underlying container for
> > > std:riority_queue<> is std::vector<>. It would seem that inserts
> > > are liable to happen anywhere, which would make std::list<> a
> > > superior alternative. Why factors am I not considering here? Why in
> > > the general case would std::vector<> be best?
> > >
> > > Thanks,
> > > Dave

> >
> >
> > According to Josuttis (The C++ Standard Library), priority queues are
> > sorted
> > using the heap sorting algorithm. A heap sort is only a partial sort (which
> > allows it to be O(n), in contrast to full sorting algorithms which tend to
> > be O(n*log n)). A heap sort requires that the container offer a random
> > access iterator, which list does not do. The fact that the vector only
> > needs
> > to be partially sorted also reduces the cost of insertion.

>
> You're confusing two completely different things. std:riority_queue uses a
> heap DATA STRUCTURE, not a heap sort ALGORITHM. The heap sort algorithm, by
> the
> way, works in O(n log n), not O(n) and does NOT sort partially; the result of
> a
> heap sort is a fully sorted sequence. The heap sort algorithm USES a heap
> data
> structure to perform its work, but the heap data structure has uses other
> than
> sorting... such as priority queues.
>
> You can read up on the details in any good book on data structures and
> algorithms (Knuth if you're techically inclined, or Sedgewick if you prefer a
> didactic approach).


Actually std:riority_queue uses any data structure which supports
random access iterators:

> 23.2.3.2 - Template class priority_queue [lib.priority.queue]
>
> -1- Any sequence with random access iterator and supporting operations
> front(), push_back() and pop_back() can be used to instantiate
> priority_queue.


And the description of the std:riority_queue member functions
specifically mentions the heap algorithms, for example:

> void push(const value_type& x);
>
> -1- Effects:
> c.push_back(x);
> push_heap(c.begin(), c.end(), comp)


-Howard
 
Reply With Quote
 
Claudio Puviani
Guest
Posts: n/a
 
      04-22-2004
"Howard Hinnant" <(E-Mail Removed)> wrote
> "Claudio Puviani" <(E-Mail Removed)> wrote:
> > "John Carson" <(E-Mail Removed)> wrote
> > > "Dave" <(E-Mail Removed)> wrote
> > > > Hello all,
> > > >
> > > > I'm pondering why the default underlying container for
> > > > std:riority_queue<> is std::vector<>. It would seem that inserts
> > > > are liable to happen anywhere, which would make std::list<> a
> > > > superior alternative. Why factors am I not considering here? Why in
> > > > the general case would std::vector<> be best?
> > > >
> > > > Thanks,
> > > > Dave
> > >
> > >
> > > According to Josuttis (The C++ Standard Library), priority queues are
> > > sorted
> > > using the heap sorting algorithm. A heap sort is only a partial sort

(which
> > > allows it to be O(n), in contrast to full sorting algorithms which tend

to
> > > be O(n*log n)). A heap sort requires that the container offer a random
> > > access iterator, which list does not do. The fact that the vector only
> > > needs
> > > to be partially sorted also reduces the cost of insertion.

> >
> > You're confusing two completely different things. std:riority_queue
> > uses a heap DATA STRUCTURE, not a heap sort ALGORITHM.
> > The heap sort algorithm, by the way, works in O(n log n), not O(n)
> > and does NOT sort partially; the result of a heap sort is a fully sorted
> > sequence. The heap sort algorithm USES a heap data structure to
> > perform its work, but the heap data structure has uses other than
> > sorting... such as priority queues.
> >
> > You can read up on the details in any good book on data structures and
> > algorithms (Knuth if you're techically inclined, or Sedgewick if you prefer

a
> > didactic approach).

>
> Actually std:riority_queue uses any data structure which supports
> random access iterators:
>
> > 23.2.3.2 - Template class priority_queue [lib.priority.queue]
> >
> > -1- Any sequence with random access iterator and supporting operations
> > front(), push_back() and pop_back() can be used to instantiate
> > priority_queue.


That describes the underlying storage mechanism, not the way the data is
organized. For example, the underlying storage could be a non-contiguous
sequence, but the data organization would still be a heap.

> And the description of the std:riority_queue member functions
> specifically mentions the heap algorithms, for example:
>
> > void push(const value_type& x);
> >
> > -1- Effects:
> > c.push_back(x);
> > push_heap(c.begin(), c.end(), comp)


'push_heap()' is a heap management function, just as I described above. It is
NOT performing a heap sort (which only uses heap management internally and
temporarily). Heap algorithms are NOT the heap sort algorithm but building
blocks thereof.

Claudio Puviani


 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      04-22-2004
"Dave" <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>...
> Hello all,
>
> I'm pondering why the default underlying container for std:riority_queue<>
> is std::vector<>. It would seem that inserts are liable to happen anywhere,
> which would make std::list<> a superior alternative. Why factors am I not
> considering here? Why in the general case would std::vector<> be best?


This exemplifies why std::list (and linked lists in general) are
rarely as useful as they initially appear.

Linked lists allow O(k) insertion or deletion anywhere in the list,
which sounds good. Unfortunately, in typical situations, you first
have to figure out where in the list to to do that insertion or
deletion -- and traversing the list to that point is O(N). As such,
the O(k) insertion/deletion is really O(N) unless you can find the
right spot in the list without actually traversing it (cf. skip
lists).

In the case of a heap, things are a really even worse: you never
really have to insert in the middle of the heap anyway -- you make the
addition at one end of the heap, and then swap the new element with
roughly lg(N) elements to get it to the right spot. Since you can add
an item to one end of a vector (or either end of a deque) in
(amortized) constant time, the total complexity is O(lg N).

Each insertion in the list would involve O(N) traversal steps along
with the O(lg N) comparisons, and finally an O(k) insertion at the
right spot. As such, the only hope for a list would be if we could
count on those N traversal steps being _extraordinarily_ fast (it
clearly loses asymtotically, but might remain better in practical
ones).

Unfortunately, that's exactly the opposite of reality: in a vector,
the memory is contiguous, leading to high locality of reference.
Along with that, we have only the data we care about being stored --
i.e. data density is 100%. Both of these help with cache utilization.

In a list, each node is normally allocated individually, and includes
not only the data itself, but a couple of pointers as well. Therefore
we have relatively poor locality of reference, and lower density of
data (i.e. the cache ends up holding lots of pointers along with the
data proper). The result is poorer use of the cache, so not only is
the complexity higher, but the constants are too...
Later,
Jerry.

--
The universe is a figment of its own imagination.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
container inside container in stl wolverine C++ 2 07-24-2006 03:08 PM
Copy elements from one STL container to another STL container Marko.Cain.23@gmail.com C++ 4 02-16-2006 05:03 PM
std::transform container => std::abs(container) Steven T. Hatton C++ 4 12-05-2004 07:10 AM
STL: container's values setup by another container Maitre Bart C++ 2 02-11-2004 12:11 AM
std::container::iterator vs std::container::pointer Vivi Orunitia C++ 11 02-04-2004 08:09 AM



Advertisments