Even more tidbits.

[Morwenn]

Make the random number generator thread-safe with thread_local (this is probably the cheapest solution). Remove attribute((unused)) and simply put the parameter's name into comments to improve portability.

[Morwenn]

On a side note, I was planning to make the algorithm take a comparison function à la std::sort, and to make sure that the algorithm works with move-only types too. Tell me if you're interested :)

[lorenzhs]

Thanks, good idea to make it thread_local.

Adding support for a compare function would entail dragging another template everywhere but other than that it should be simple.

Making it work with move-only types could be a bit trickier (due to the sampling, for example).

[Morwenn]

I believe that it should be possible to store iterators instead of copies for the samples. I did not try to implement it yet though. Anyway, I will try to do that if you're fine with it :)

[lorenzhs]

Hmm you'd need to carefully measure the impact on performance, as there are lots of comparisons being made against the splitters. I'm not sure how fast it'll be (probably depends a lot on what optimizations the compiler can do?)

[Morwenn]

In my experience, compilers are good and using std::less<> produces exactly the same code than using a raw operator< (except maybe for pointers since std::less<> has to provide a total order for pointers). That's the advantage of templates: the compiler has all the information it needs at compile time and can aggressively inline such trivial calls.

[lorenzhs]

Oh I'm not worried about std::less<>, I was talking about the iterators. They require de-referentiation like pointers, which could be expensive if the compiler is dumb about it.