Re: [boost] [GSoC] Heaps & Queues (draft proposal)

Subject: Re: [boost] [GSoC] Heaps & Queues (draft proposal)
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-04-02 18:07:37

iaml wrote:
>  And I would prefer to use lists rather than vectors (as shown in
> boost/pending/fibonacci_heap.hpp) to implement it for three reasons.
>         1. It will save memory since the later needs extra space to
> store 
> the key to value mapping.
>         2. Vector requires continuous memory while list doesn't. It
> does not matter when the amount of data is small. But when the amount
> of data becomes large, it will be a tough problem;
>         3. It takes time to resize and reallocate the memory for
> vectors. 
> 
>         Of course, list implementation has its own drawback such as
> easy to leak memory and cost more time when searching the heap. From
> my point of view, it is acceptable comparing with the problems
>  mentioned before. As the adaptor of heaps, the priority queue API
> may like: 

I think you are wrong about all three objections to vector.  

1. Vectors should save you memory over lists.

2. Large vectors causing memory allocation failure due to fragmentation isn't generally a problem in 64 bit platforms and the right way to deal with the problem in 32 bit systems is to not fragment your memory in the first place.  You should not sacrifice performance of a library to accommodate poorly written applications on some platforms at the expense of all other applications and all other platforms.  

3. Vectors are faster than lists for almost all use cases.

I also agree with Andrew that you can parameterize for container type.  In the stl, heap operations there is a very clear abstraction between data structures and algorithms.  I would think that providing that abstraction should be a goal of the project.

Regards,
Luke