Function std.algorithm.sorting.makeIndex
Computes an index for r
based on the comparison less
.
SortedRange!(RangeIndex,(a,b)=>binaryFun!less(*a,*b)) makeIndex(alias less, SwapStrategy ss = SwapStrategy .unstable, Range, RangeIndex)
(
Range r,
RangeIndex index
)
if (isForwardRange!Range && isRandomAccessRange!RangeIndex && is(ElementType!RangeIndex : ElementType!Range*) && hasAssignableElements!RangeIndex);
void makeIndex(alias less, SwapStrategy ss = SwapStrategy .unstable, Range, RangeIndex)
(
Range r,
RangeIndex index
)
if (isRandomAccessRange!Range && !isInfinite!Range && isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex && isIntegral!(ElementType!RangeIndex) && hasAssignableElements!RangeIndex);
The index is a sorted array of pointers or indices into the original
range. This technique is similar to sorting, but it is more flexible
because (1) it allows "sorting" of immutable collections, (2) allows
binary search even if the original collection does not offer random
access, (3) allows multiple indexes, each on a different predicate,
and (4) may be faster when dealing with large objects. However, using
an index may also be slower under certain circumstances due to the
extra indirection, and is always larger than a sorting-based solution
because it needs space for the index in addition to the original
collection. The complexity is the same as sort
's.
The first overload of makeIndex
writes to a range containing
pointers, and the second writes to a range containing offsets. The
first overload requires Range
to be a
forward range, and the
latter requires it to be a random-access range.
makeIndex
overwrites its second argument with the result, but
never reallocates it.
Parameters
Name | Description |
---|---|
less | The comparison to use. |
ss | The swapping strategy. |
r | The range to index. |
index | The resulting index. |
Returns
The pointer-based version returns a SortedRange
wrapper
over index, of type
SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b))
thus reflecting the ordering of the
index. The index-based version returns void
because the ordering
relation involves not only index
but also r
.
Throws
If the second argument's length is less than that of the range indexed, an exception is thrown.
Example
immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
// index using pointers
auto index1 = new immutable(int)*[arr .length];
makeIndex!("a < b")(arr, index1);
assert(isSorted!("*a < *b")(index1));
// index using offsets
auto index2 = new size_t[arr .length];
makeIndex!("a < b")(arr, index2);
assert(isSorted!
((size_t a, size_t b){ return arr[a] < arr[b];})
(index2));