View source code Display the source code in std/range.d from which this page was generated on github. Improve this page Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone. Page wiki View or edit the community-maintained wiki page associated with this page.

Module `std.range`

This module defines the notion of a range. Ranges generalize the concept of arrays, lists, or anything that involves sequential access. This abstraction enables the same set of algorithms (see std.algorithm) to be used with a vast variety of different concrete types. For example, a linear search algorithm such as std.algorithm.find works not just for arrays, but for linked-lists, input files, incoming network data, etc.

For more detailed information about the conceptual aspect of ranges and the motivation behind them, see Andrei Alexandrescu's article On Iteration.

Submodules

This module has two submodules:

The std.range.primitives submodule provides basic range functionality. It defines several templates for testing whether a given object is a range, what kind of range it is, and provides some common range operations.

The std.range.interfaces submodule provides object-based interfaces for working with ranges via runtime polymorphism.

The remainder of this module provides a rich set of range creation and composition templates that let you construct new ranges out of existing ranges:


`chain`	Concatenates several ranges into a single range.
`choose`	`choose` one of several ranges.
`chunks`	Creates a range that returns fixed-size `chunks` of the original range.
`cycle`	Creates an infinite range that repeats the given forward range indefinitely. Good for implementing circular buffers.
`drop`	Creates the range that results from discarding the first n elements from the given range.
`dropExactly`	Creates the range that results from discarding exactly n of the first elements from the given range.
`dropOne`	Creates the range that results from discarding the first elements from the given range.
`enumerate`	Iterates a range with an attached index variable.
`frontTransversal`	Creates a range that iterates over the first elements of the given ranges.
`indexed`	Creates a range that offers a view of a given range as though its elements were reordered according to a given range of indices.
`iota`	Creates a range consisting of numbers between a starting point and ending pointspaced apart by a given interval.
`lockstep`	Iterates n ranges in `lockstep`, for use in a `foreach` loop. Similar to `zip`, except that `lockstep` is designed especially for `foreach` loops.
`NullSink`	An output range that discards the data it receives.
`only`	Creates a range that iterates over the given arguments.
`radial`	Given a random-access range and a starting point, creates a range that alternately returns the next left and next right element to the starting point.
`recurrence`	Creates a forward range whose values are defined by a mathematical `recurrence` relation.
`repeat`	Creates a range that consists of a single element repeated n times, or an infinite range repeating that element indefinitely.
`retro`	Iterates a bidirectional range backwards.
`roundRobin`	Given n ranges, creates a new range that return the n first elements of each range, in turn, then the second element of each range, and so on, in a round-robin fashion.
`sequence`	Similar to `recurrence`, except that a random-access range is created.
`stride`	Iterates a range with `stride` n.
`take`	Creates a sub-range consisting of `only` up to the first n elements of the given range.
`takeExactly`	Like `take`, but assumes the given range actually has n elements, and therefore also defines the `length` property.
`takeNone`	Creates a random-access range consisting of zero elements of the given range.
`takeOne`	Creates a random-access range consisting of exactly the first element of the given range.
`tee`	Creates a range that wraps a given range, forwarding along its elements while also calling a provided function with each element.
`transposed`	Transposes a range of ranges.
`transversal`	Creates a range that iterates over the n'th elements of the given random-access ranges.
`zip`	Given n ranges, creates a range that successively returns a tuple of all the first elements, a tuple of all the second elements, etc.

Ranges whose elements are sorted afford better efficiency with certain operations. For this, the assumeSorted function can be used to construct a SortedRange from a pre-sorted range. The std.algorithm.sort function also conveniently returns a SortedRange. SortedRange objects provide some additional range operations that take advantage of the fact that the range is sorted.

Functions

Name	Description
`assumeSorted`	Assumes `r` is sorted by predicate `pred` and returns the corresponding `SortedRange!(pred, R)` having `r` as support. To keep the checking costs low, the cost is Ο(`1`) in release mode (no checks for sortedness are performed). In debug mode, a few random elements of `r` are checked for sortedness. The size of the sample is proportional Ο(`log(r.length)`). That way, checking has no effect on the complexity of subsequent operations specific to sorted ranges (such as binary search). The probability of an arbitrary unsorted range failing the test is very high (however, an almost-sorted range is likely to pass it). To check for sortedness at cost Ο(`n`), use `std.algorithm.sorting.isSorted`.
`chain`	Spans multiple ranges in `sequence`. The function `chain` takes any number of ranges and returns a `Chain!(R1, R2,...)` `object`. The ranges may be different, but they must have the same element type. The result is a range that offers the `front`, `popFront`, and `empty` primitives. If all input ranges offer random access and `length`, `Chain` offers them as well.
`choose`	Choose one of two ranges at runtime depending on a Boolean `condition`.
`chooseAmong`	Choose one of multiple ranges at runtime.
`chunks`	This range iterates over fixed-sized `chunks` of size `chunkSize` of a `source` range. `Source` must be a forward range.
`cycle`	Repeats the given forward range ad infinitum. If the original range is infinite (fact that would make `Cycle` the identity application), `Cycle` detects that and aliases itself to the range type itself. If the original range has random access, `Cycle` offers random access and also offers a constructor taking an initial position `index`. `Cycle` works with static arrays in addition to ranges, mostly for performance reasons.
`drop`	Convenience function which calls `range.popFrontN(n)` and returns `range`. `drop` makes it easier to pop elements from a `range` and then pass it to another function within a single expression, whereas `popFrontN` would require multiple statements.
`dropBack`	Convenience function which calls `range.popFrontN(n)` and returns `range`. `drop` makes it easier to pop elements from a `range` and then pass it to another function within a single expression, whereas `popFrontN` would require multiple statements.
`dropBackExactly`	Similar to `drop` and `dropBack` but they call `range.popFrontExactly(n)` and `range.popBackExactly(n)` instead.
`dropBackOne`	Convenience function which calls `range.popFront()` and returns `range`. `dropOne` makes it easier to pop an element from a `range` and then pass it to another function within a single expression, whereas `popFront` would require multiple statements.
`dropExactly`	Similar to `drop` and `dropBack` but they call `range.popFrontExactly(n)` and `range.popBackExactly(n)` instead.
`dropOne`	Convenience function which calls `range.popFront()` and returns `range`. `dropOne` makes it easier to pop an element from a `range` and then pass it to another function within a single expression, whereas `popFront` would require multiple statements.
`enumerate`	Iterate over `range` with an attached index variable.
`frontTransversal`	Given a range of ranges, iterate transversally through the first elements of each of the enclosed ranges.
`generate`	Given callable (`std.traits.isCallable`) `fun`, create as a range whose front is defined by successive calls to `fun()`. This is especially useful to call function with global side effects (random functions), or to create ranges expressed as a single delegate, rather than an entire `front`/`popFront`/`empty` structure. `fun` maybe be passed either a template alias parameter (existing function, delegate, struct type defining static `opCall`... ) or a run-time value argument (delegate, function `object`... ). The result range models an InputRange (`std.range.primitives.isInputRange`). The resulting range will call `fun()` on every call to `front`, and `only` when `front` is called, regardless of how the range is iterated. It is advised to compose `generate` with either `std.algorithm.iteration.cache` or `std.array.array`, or to use it in a foreach loop. A by-value foreach loop means that the loop value is not `ref`.
`indexed`	This struct takes two ranges, `source` and `indices`, and creates a view of `source` as if its elements were reordered according to `indices`. `indices` may include `only` a subset of the elements of `source` and may also `repeat` elements.
`iota`	Construct a range of values that span the given starting and stopping values.
`lockstep`	Iterate multiple `ranges` in `lockstep` using a `foreach` loop. If `only` a single range is passed in, the `Lockstep` aliases itself away. If the `ranges` are of different lengths and `s` == `StoppingPolicy.shortest` stop after the shortest range is empty. If the `ranges` are of different lengths and `s` == `StoppingPolicy.requireSameLength`, throw an exception. `s` may not be `StoppingPolicy.longest`, and passing this will throw an exception.
`only`	Assemble `values` into a range that carries all its elements in-situ.
`radial`	Iterates a random-access range starting from a given point and progressively extending left and right from that point. If no initial point is given, iteration starts from the middle of the range. Iteration spans the entire range.
`recurrence`	Creates a mathematical `sequence` given the `initial` values and a `recurrence` function that computes the next value from the existing values. The `sequence` comes in the form of an infinite forward range. The type `Recurrence` itself is seldom used directly; most often, recurrences are obtained by calling the function `recurrence`.
`refRange`	Helper function for constructing a `RefRange`.
`repeat`	Repeats one `value` forever.
`repeat`	Repeats `value` exactly `n` times. Equivalent to `take(repeat(value), n)`.
`retro`	Iterates a bidirectional range backwards. The original range can be accessed by using the `source` property. Applying `retro` twice to the same range yields the original range.
`roundRobin`	`roundRobin(r1, r2, r3)` yields `r1.front`, then `r2.front`, then `r3.front`, after which it pops off one element from each and continues again from `r1`. For example, if two ranges are involved, it alternately yields elements off the two ranges. `roundRobin` stops after it has consumed all ranges (skipping over the ones that finish early).
`sequence`	`Sequence` is similar to `Recurrence` except that iteration is presented in the so-called closed form. This means that the `n`th element in the series is computable directly from the initial values and `n` itself. This implies that the interface offered by `Sequence` is a random-access range, as opposed to the regular `Recurrence`, which `only` offers forward iteration.
`stride`	Iterates range `r` with `stride` `n`. If the range is a random-access range, moves by indexing into the range; otherwise, moves by successive calls to `popFront`. Applying `stride` twice to the same range results in a `stride` with a step that is the product of the two applications. It is an error for `n` to be 0.
`take`	Lazily takes `only` up to `n` elements of a range. This is particularly useful when using with infinite ranges. If the range offers random access and `length`, `Take` offers them as well.
`takeExactly`	Similar to `take`, but assumes that `range` has at least `n` elements. Consequently, the result of `takeExactly(range, n)` always defines the `length` property (and initializes it to `n`) even when `range` itself does not define `length`.
`takeNone`	Creates an empty `range` from the given `range` in Ο(`1`). If it can, it will return the same `range` type. If not, it will return `takeExactly(range, 0)`.
`takeNone`	Returns an empty range which is statically known to be empty and is guaranteed to have `length` and be random access regardless of `R`'s capabilities.
`takeOne`	Returns a range with at most one element; for example, `takeOne([42, 43, 44])` returns a range consisting of the integer `42`. Calling `popFront()` off that range renders it empty.
`tee`	Implements a "`tee`" style pipe, wrapping an input range so that elements of the range can be passed to a provided function or OutputRange as they are iterated over. This is useful for printing out intermediate values in a long `chain` of range code, performing some operation with side-effects on each call to `front` or `popFront`, or diverting the elements of a range into an auxiliary OutputRange.
`transposed`	Given a range of ranges, returns a range of ranges where the i'th subrange contains the i'th elements of the original subranges.
`transversal`	Given a range of ranges, iterate transversally through the the `n`th element of each of the enclosed ranges. All elements of the enclosing range must offer random access.
`zip`	Iterate several `ranges` in `lockstep`. The element type is a proxy tuple that allows accessing the current element in the `n`th range by using `e[n]`. `Zip` offers the lowest range facilities of all components, e.g. it offers random access iff all `ranges` offer random access, and also offers mutation and swapping if all `ranges` offer it. Due to this, `Zip` is extremely powerful because it allows manipulating several `ranges` in `lockstep`. For example, the following code sorts two arrays in parallel:

Structs

Name	Description
`Chunks`	This range iterates over fixed-sized `chunks` of size `chunkSize` of a `source` range. `Source` must be a forward range.
`Cycle`	Repeats the given forward range ad infinitum. If the original range is infinite (fact that would make `Cycle` the identity application), `Cycle` detects that and aliases itself to the range type itself. If the original range has random access, `Cycle` offers random access and also offers a constructor taking an initial position `index`. `Cycle` works with static arrays in addition to ranges, mostly for performance reasons.
`FrontTransversal`	Given a range of ranges, iterate transversally through the first elements of each of the enclosed ranges.
`Indexed`	This struct takes two ranges, `source` and `indices`, and creates a view of `source` as if its elements were reordered according to `indices`. `indices` may include `only` a subset of the elements of `source` and may also `repeat` elements.
`Lockstep`	Iterate multiple ranges in `lockstep` using a `foreach` loop. If `only` a single range is passed in, the `Lockstep` aliases itself away. If the ranges are of different lengths and `s` == `StoppingPolicy.shortest` stop after the shortest range is empty. If the ranges are of different lengths and `s` == `StoppingPolicy.requireSameLength`, throw an exception. `s` may not be `StoppingPolicy.longest`, and passing this will throw an exception.
`NullSink`	An OutputRange that discards the data it receives.
`Recurrence`	Creates a mathematical `sequence` given the initial values and a `recurrence` function that computes the next value from the existing values. The `sequence` comes in the form of an infinite forward range. The type `Recurrence` itself is seldom used directly; most often, recurrences are obtained by calling the function `recurrence`.
`RefRange`	Wrapper which effectively makes it possible to pass a range by reference. Both the original range and the `RefRange` will always have the exact same elements. Any operation done on one will affect the other. So, for instance, if it's passed to a function which would implicitly copy the original range if it were passed to it, the original range is not copied but is consumed as if it were a reference type.
`Repeat`	Repeats one value forever.
`Sequence`	`Sequence` is similar to `Recurrence` except that iteration is presented in the so-called closed form. This means that the `n`th element in the series is computable directly from the initial values and `n` itself. This implies that the interface offered by `Sequence` is a random-access range, as opposed to the regular `Recurrence`, which `only` offers forward iteration.
`SortedRange`	Represents a sorted range. In addition to the regular range primitives, supports additional operations that `take` advantage of the ordering, such as merge and binary search. To obtain a `SortedRange` from an unsorted range `r`, use `std.algorithm.sorting.sort` which sorts `r` in place and returns the corresponding `SortedRange`. To construct a `SortedRange` from a range `r` that is known to be already sorted, use `assumeSorted` described below.
`Take`	Lazily takes `only` up to `n` elements of a range. This is particularly useful when using with infinite ranges. If the range offers random access and `length`, `Take` offers them as well.
`Transversal`	Given a range of ranges, iterate transversally through the the `n`th element of each of the enclosed ranges. All elements of the enclosing range must offer random access.
`Zip`	Iterate several ranges in `lockstep`. The element type is a proxy tuple that allows accessing the current element in the `n`th range by using `e[n]`. `Zip` offers the lowest range facilities of all components, e.g. it offers random access iff all ranges offer random access, and also offers mutation and swapping if all ranges offer it. Due to this, `Zip` is extremely powerful because it allows manipulating several ranges in `lockstep`. For example, the following code sorts two arrays in parallel:

Enums

Name	Description
`SearchPolicy`	Policy used with the searching primitives `lowerBound`, `upperBound`, and `equalRange` of `SortedRange` below.
`StoppingPolicy`	Dictates how iteration in a `Zip` should stop. By default stop at the end of the `shortest` of all ranges.
`TransverseOptions`	Options for the `FrontTransversal` and `Transversal` ranges (below).

Enum values

Name	Type	Description
`isTwoWayCompatible`		Returns true if `fn` accepts variables of type T1 and T2 in any order. The following code should compile:

Authors

Andrei Alexandrescu, David Simcha, and Jonathan M Davis. Credit for some of the ideas in building this module goes to Leonardo Maffi.

License

Boost License 1.0.