RandomAccessRange: Infinite

an overview of RandomAccessRange and the infinite RandomAccessRange.

We'll cover the following

RandomAccessRange

RandomAccessRange represents ranges that allow accessing elements by the [] operator. As we covered in the operator overloading chapter, [] operator is defined by the opIndex() member function.

Importing the std.array module makes slices become RandomAccessRange ranges only if possible. For example, since UTF-8 and UTF-16 encodings do not allow accessing Unicode characters by an index, char and wchar arrays cannot be used as RandomAccessRange ranges of Unicode characters. On the other hand, since the codes of the UTF-32 encoding correspond one-to-one to Unicode character codes, dchar arrays can be used as RandomAccessRange ranges of Unicode characters.

It is natural that every type would define the opIndex() member function according to its functionality. However, computer science has an expectation of its algorithmic complexity; random access must take constant time. Constant-time access means that the time spent when accessing an element is independent of the number of elements in the container. Therefore, no matter how large the range is, element access should not depend on the length of the range.

In order to be considered a RandomAccessRange, one of the following conditions must also be satisfied:

  • to be an infinite ForwardRange or

  • to be a BidirectionalRange that also provides the length property

Depending on the condition that is satisfied, the range is either infinite or finite.

Infinite RandomAccessRange

The following are all of the requirements of a RandomAccessRange that is based on an infinite ForwardRange:

  • empty,front, and popFront() required by InputRange
  • save required by ForwardRange
  • opIndex() required by RandomAccessRange requires
  • the value of empty to be known at compile time as false

We were able to define FibonacciSeries as a ForwardRange. However, opIndex() cannot be implemented to operate at a constant time for FibonacciSeries because accessing an element requires accessing all of the previous elements first.

As an example where opIndex() can operate at constant time, let’s define an infinite range that consists of squares of integers. Although the following range is infinite, accessing any one of its elements can happen at a constant time:

Get hands-on with 1400+ tech skills courses.