From: Steven Ross (spreadsort_at_[hidden])
Date: 2008-07-11 10:34:37
I've cleaned up the names so as not to use a leading _ for anything except
the #ifndef and not use Hungarian notation.
On Thu, Jul 10, 2008 at 9:21 AM, Phil Endecott <
> I'd like to use a smart pointer, but is there one that will call delete?
> With the way that you've now structured the code, I think your choice is
> between a boost::scoped_array (the difference between scoped_ptr and
> scoped_array is delete vs. delete), or to avoid dynamic allocation by
> using a std::vector. If the number of bins is knowable at compile time then
> a std::tr1::array or C-style array is another choice, but some people might
> complain about having so much data on the stack.
I decided to use a vector, and while I was at it, use a single vector for
the entire integer_sort call, so as to limit the number of
allocations/deallocations. I did use the &(vec[index]) trick to get the
bins, but the vector is defined to be based upon an array, so that works.
If I only used indices into the vector, I would need an extra addition in
the inner swap loop, which is expensive in terms of performance (about 2%).
> Is there a simple way to check if an iterator is a vector iterator?
> I have previously asked, probably on this list, about whether there's a
> good way to detect iterators that point to contiguous storage. The answer
> seems to be that there isn't, except for explicitly detecting those that are
> guaranteed to do so (as above).
My conclusion on the * usage for vector sorting is that the best way to
handle it would be to provide a vector::integer_sort just like vector::sort,
and people "in the know" can use the &(vec) trick.
Are there any more suggestions for the core algorithm? Once this is
finalized, I'll add functors, and once that's finalized, I'll move on to
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk