12-Jul-2013 02:23, Joseph Rushton Wakeling пишет:
On 07/11/2013 10:43 PM, Dmitry Olshansky wrote:
In such a case if inserting exactly one element into a sorted range you may want
to special case it to lowerbound + insert.
E.g. something like this:
auto idx = sortedRange.lowerbound(val).length;
//insert should be called on array backing that sortedRange
insert(sortedRange, idx, val);
... which would basically correspond to an insertion sort, right?
Yup, but done in one step. I'd put it the other way around: simply put
this is inserting an item into a sorted range => binary search + insert.
An insertion sort is built around this operation performed repeatedly.
I'm quite tired on reading this so will have to think it over fresh tomorrow.
What I'm not certain of is how to tweak it given that actually here we have two
arrays:
size_t[] values; // doesn't change, but we've added a new value at the end
size_t[] sortedIndices; // indices 0 .. values.length, sorted according
// to values[i]
Append new value to values.
Then use 'values.length-1' (new length - 1 i.e. the old length) as an
item to insert into sortedIndices.
The last step is to figure out what range to call lowerBound on - I'd
say something like:
assumeSorted(sortedIndices.map!(x => values[x]))
then use that to find a suitable place to insert in sortedIndices.
... so, it's sortedIndices that we need to sort, but according to the
corresponding entries in the array of values.
Anyway, thanks for the thought -- lowerbound() is a function I've never used
before so it wouldn't have occurred to me.
--
Dmitry Olshansky
