Re: [boost] Proposed templated integer_sort

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-07-07 14:53:37

Steven Ross wrote:
> I've uploaded a new integer_sort release to
> http://sourceforge.net/projects/spreadsort/, and attached the source to this
> email.

> Suggestions are welcome.

Hi Steve,

Some comments, mostly minor things I think:

- Boost generally uses .hpp for header files.
- Identifiers (including macros) starting with _ are reserved.
- I don't recall seeing much Hungarian Notation in Boost.
- Some way of sorting structs, or pointers to structs, by passing some 
sort of key access functor as an additional template parameter is needed.
- Use new and delete rather than *alloc and free.
- Can any exceptions occur?  If so, is the dynamically allocated memory 
leaked?  Could you use a smart pointer to avoid this?
- 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?
- Does it work with uint64_t?  I see some variables declared as 'long', 
which often can't store a uint64_t.
- I look forward to seeing float and string versions.
- 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 use-case for a pure radix sort, without the std::sort 
fallback?  i.e. are there types that can't easily provide a comparison 
function, or distributions where the std::sort fallback is never useful?

Having said all that, personally I have little interest in an algorithm 
that has no benefit for fewer than millions of items.  What do other 
people think about that aspect?

Cheers, Phil.