Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Optional Range Capabilities
The range API defined so far is surprisingly capable, allowing the implementation of many algorithms in a container-independent manner. However, some useful primitives are conspicuously absent. For example, most random access ranges and some of the others support a notion of length. The length of a range can be computed easily for even an input range by simply walking it to exhaustion, but certain containers naturally support constant-time length as a primitive.
Interestingly, length is not restricted to a specific range category. One might suppose that random access ranges must have a length, whereas others don't. However, there are random access ranges that don't have a length. Infinite ranges (such as the range of numbers modulo 10 discussed above in the section "Random Access Ranges") are an obvious example, but there are more subtle cases. Consider, for example, a circular buffer implemented atop an array. You can access the ith element in constant time—it's the (i % n)th element of the array. Claiming that the length of the buffer itself is n may, however, surprise clients: They'd expect that taking n steps would take them to the end of the sequence, but that doesn't happen. Conversely, there are even input ranges that have a length—for example, a range that yields 100 random numbers.
So length is an optional attribute. If the range can define it, it should, but it's never obligated to do so. A range-based algorithm may or may not require that length be defined by its range parameters.
Infiniteness is another property that turned out to be quite useful in practice. An infinite forward range would always return false from empty(). Detecting that is difficult in most languages, so a separate Boolean property or trait isInfinite could be provided. I don't think infiniteness is an essential component of a range API, but it was very easy to define in D with no additional effort, and sometimes comes in quite handy. There is also a relationship (briefly alluded to in the section "Random Access Ranges") between random access ranges, double-ended ranges, and infiniteness: If a random access range is infinite, it extends a forward range. Otherwise, it extends a double-ended range.
Other, more exotic range capabilities are primitives such as lookahead or putback. An input range may have a lookahead capability up to a specified number of elements and/or the feature of allowing an element to be returned to the range. C's sequential file API offers the ungetc function, which is guaranteed to work for at least one character. The primitives lookahead and putback are useful in a variety of applications, particularly those concerned with parsing streams.