Subject: Re: [boost] [move][sort] Asymptotically optimal stable and in-place merging and sorting with no auxiliary memory
From: Steven Ross (spreadsort_at_[hidden])
Date: 2016-03-24 20:57:59
On Thu, Mar 24, 2016 at 7:14 AM Ion GaztaÃ±aga <igaztanaga_at_[hidden]> wrote:
> On 24/03/2016 2:02, Steven Ross wrote:
> > On Wed, Mar 23, 2016 at 6:52 PM Ion GaztaÃ±aga <igaztanaga_at_[hidden]>
> >> [Disclaimer, long e-mail, thank you for your attention]
> >> Hi to all,
> >> Some months ago I tried to gain interest from sorting experts about
> >> implementing stable and inplace merge [O(N)] or sort [O(NlongN)]
> >> algorithms that don't need additional memory.
> >> My main use case for these algorithms was lowering the complexity
> >> guarantees of range insertion functions offered by flat associative
> >> containers without any temporary allocation (the programmer does not
> >> expect allocations when capacity() is big enough to hold the new
> >> elements). On the other hand, I wanted those algorithms to be adaptive
> >> so as to take advantage of the extra capacity already allocated by flat
> >> containers.
> > I'm still confused why std::inplace_merge doesn't work for your use case;
> > what's wrong with attempting to create a temporary buffer, and falling
> > to O(Nlog(N)) if it fails? I still fail to see a practical advantage.
> For desktop systems this is not a problem, unless you want to sort big
> ranges (like 1 GB in 32bit systems, you can run out of memory).
> For flat containers, the issue is more related to class invariants where
> a vector/flat_map should never allocate if capacity() is enough, that's
> what the user expects.
> Although I've only mentioned flat_xxx containers, my goal was to have a
> tool that could be useful in other contexts.
> Another potential users are embedded developers that also don't like to
> allocate memory after initialization.
> Ok, your use case seems arcane, but I see how that might be useful. Do
you want to add it as a sub-library inside Boost.Sort?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk