Re: [boost] Proposed templated integer_sort

From: Steven Ross (spreadsort_at_[hidden])
Date: 2008-07-10 10:54:23

Hi Phil,

My responses are inline.

On Mon, Jul 7, 2008 at 11:53 AM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:

> Some comments, mostly minor things I think:
>
> - Boost generally uses .hpp for header files.
>
Done

> - Identifiers (including macros) starting with _ are reserved.
> - I don't recall seeing much Hungarian Notation in Boost.

I can remove the Hungarian notation.  Is there any suggested notation, or
should I just use names that make sense, and try to be similar to standard
libraries?
__last and __first were copied from std::sort.  Is there a good reason I
shouldn't use the same notation?

>
> - Some way of sorting structs, or pointers to structs, by passing some sort
> of key access functor as an additional template parameter is needed.

I'll do that as soon as the rest of this is acceptable.  There is no sense
in copying code that isn't ready yet (and the additional template parameter
is handled by a duplicate method).

- Use new and delete rather than *alloc and free.

Done.  The runtime seems more variable now, but on average is the same
within my margin of error.

- Can any exceptions occur?  If so, is the dynamically allocated memory
> leaked?  Could you use a smart pointer to avoid this?

I'd like to use a smart pointer, but is there one that will call delete[]?
As this is a very simple situation, I could also write my own trivial one,
copying part of the implementation out of More Effective C++.

- If you re-organise the recursion so that SpreadSortCore calls
> SpreadSortBins directly, rather than first returning to SpreadSortRec, can
> you limit the scope of the bins to SpreadSortCore?

Yes.  In fact, I eliminated both SpreadSortCore and SpreadSortBins, now that
SpreadSort is just a wrapper around SpreadSortRec (I found that had a
slightly positive impact on performance), so SpreadSortRec calls itself and
the BinArray is scoped just to it.

> - Does it work with uint64_t?  I see some variables declared as 'long',
> which often can't store a uint64_t.

I used the templating off a return value trick from the standard library to
handle this.

> - I look forward to seeing float and string versions.

Once integer_sort is finished, float_sort shouldn't take long.  I want it
finished first, to avoid modifying the same code in multiple places.
string_sort will come after that.

> - If std::vector<int>::iterator really is slower than int* (and I suggest
> some investigation of the assembler to see why this is), then you could add
> a specialisation that converts vector::iterators into pointers.

Is there a simple way to check if an iterator is a vector iterator?

Thanks again.

Steve