Re: [boost] Proposed templated integer_sort

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 <
spam_from_boost_dev_at_[hidden]> wrote:

>
>
>  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[0]) 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
float_sort.

Steve