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

Subject: Re: [boost] [GSoC] Heaps & Queues (draft proposal)
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-04-02 18:54:09

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

Well said. The only thing I would add to this is that a linked list will not
suffice for a binary heap implementation, if that's what's being proposed,
but binary tree will. The difference is in these highlighted nicely in the
difference between std::set/map and the upcoming Boost.Container
flat_set/flat_map [1], which I just discovered :)

Andrew Sutton
andrew.n.sutton_at_[hidden]

[1]
http://svn.boost.org/svn/boost/sandbox/move/libs/container/doc/html/index.html