Re: binary search trees & binning

FROM : Michael Ash
DATE : Wed Apr 16 22:35:04 2008

On Wed, Apr 16, 2008 at 1:20 PM, John Stiles <<email_removed>> wrote:
>  The difference is, in STL, if you want an array where you can remove from
> the beginning, you would never use vector<> anyway. You'd use deque<>, which
> has different tradeoffs and allows fast removal of elements from the
> beginning of the array. CoreFoundation doesn't let you choose and instead it
> just changes which algorithms it uses as the size of the array grows past a
> certain point, which to me is just weird. It doesn't seem like a great
> design to me. If you wanted to say one good thing about it, though...
> CFArray may never give you the best performance, but it will probably also
> prevent you from getting worst-case performance if you write really
> poorly-designed algorithms.


The real difference is that they provide different concepts. STL
provides data structures, CF and Foundation provide containers. You
generally know how STL data structures are implemented and they have
performance guarantees which are pretty ironclad. CF collections are
considerably more vague about both implementation and performance.

With STL you can choose exactly how you want your stuff to be stored.
With CF, you generally choose how you want to *access* your data, and
leave the rest up to the implementation. If you want an ordered
collection, you just choose a CFArray and you can generally assume
that the performance will be decent. Since most such uses are not
performance critical, the ability to save programmer time by not
having to make a choice is generally a good tradeoff.

The nice thing about CF is that, thanks to toll-free bridging, if
you've used a CFArray everywhere and it turns out that your particular
access pattern isn't fast enough with the built-in implementation, you
can easily write a replacement (perhaps using STL on the back end) and
drop it in without changing any code other than the bit that
instantiates it.

Interestingly, CFBinaryHeap doesn't fit into this at all. It all but
advertises exactly how it's implemented inside, provides tight
performance guarantees to match, and has no bridging so you can't
provide your own implementation.

Mike