Function std.algorithm.sorting.makeIndex
Computes an index for rless. 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
The first overload of makeIndexRange to be a forward range, and the
latter requires it to be a random-access range.
makeIndex
Prototypes
SortedRange!(RangeIndex,(a,b)=>binaryFun!less(*a,*b)) makeIndex(alias less, std.algorithm.mutation.SwapStrategy ss, Range, RangeIndex)( Range r, RangeIndex index ) if (isForwardRange!Range && isRandomAccessRange!RangeIndex && is(ElementType!RangeIndex : ElementType!Range*)); void makeIndex(alias less, std.algorithm.mutation.SwapStrategy ss, Range, RangeIndex)( Range r, RangeIndex index ) if (isRandomAccessRange!Range && !isInfinite!Range && isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex && isIntegral!(ElementType!RangeIndex));
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 indexr
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));