Georg Wrede:
> You probably have to have an array of structs, where each struct
> contains a reference to a subarray, and a copy of the first value of
> this subarray.
Keeping a cached copy of the first item of the subarray ("subrange") may be
better in some situations and worse (compared to keeping just a
reference/pointer) in other situations. And it's not very simple to design a
data structure able to adapt itself dynamically to such two situations.
> Sort the array of structs, and beginning with the first struct, pop from
> the pointed-to subarray as long as it contains elements equal to the
> first one. Then pop from the subarray that belongs to following struct,
> and so on, until a subbarray's first element already is larger.
> While popping, you obviously update the value copies, and append to an
> output array.
Better to yield lazily the output items.
And probably keeping them in a heap is more efficient than scanning them all.
> The algorithm could be enhanced by, instead of an array of structs,
> having a singly liked list of these structs.
Today linked lists are mostly dead. In most situations arrays (or arrays with
holes, plus few other smart things) are more efficient, both in memory and
speed.
--------------------
For Andrei: in my last post I have suggested to remove from the heap the
references to the sub-ranges as soon they are exhausted. But lot of tests of
mine have shown me that's often not the most efficient strategy:
http://www.fantascienza.net/leonardo/ar/list_deletions.html
So better things are possible. The most refined strategy may be overkill, but
some medium strategy may be OK.
Bye,
bearophile
