Introduction and History

Ranges

Ranges of algorithms over a great number of container types. Ranges emphasize how container elements are accessed, as opposed to how the containers are implemented.

Ranges are a very simple concept that is based on whether a type defines certain sets of member functions. We have already covered this concept in the foreach with structs and classes chapter: any type that provides the member functions empty, front, and popFront() can be used with the foreach loop. The set of those three member functions is the requirement of the range type InputRange.

We will start introducing ranges with InputRange, the simplest of all the range types. The other ranges require more member functions over InputRange. Before going further, we would like to provide the definitions of containers and algorithms.

Container (data structure): Container is a very useful concept that appears in almost every program. Variables are put together for a purpose and are used together as elements of a container. D’s containers are its core features arrays and associative arrays, and special container types that are defined in the std.container module. Every container is implemented as a specific data structure. For example, associative arrays are a hash table implementation.

Every data structure stores its elements and provides access to them in ways that are special to that data structure. For example, in the array data structure, the elements are stored side by side and accessed by an element index; in the linked list data structure the elements are stored in nodes and are accessed by going through those nodes one by one; in a sorted binary tree data structure, the nodes provide access to the preceding and successive elements through separate branches; etc.

In this chapter, we will use the terms container and data structure interchangeably.

Algorithm (function): Processing data structures for specific purposes in specific ways is called an algorithm. For example, linear search is an algorithm that searches by iterating over a container from the beginning to the end; binary search is an algorithm that searches for an element by eliminating half of the candidates at every step; etc.

In this chapter, we will use the terms algorithm and function interchangeably. For most of the samples below, we will use int as the element type and int[] as the container type. In reality, ranges are more powerful when used with templated containers and algorithms. In fact, most of the containers and algorithms that ranges tie together are all templates. We will leave examples of templated ranges to the next chapter.

History

A very successful library that abstracts algorithms and data structures from each other is the Standard Template Library (STL), which also appears as a part of the C++ standard library. STL provides this abstraction with the iterator concept, which is implemented by C++'s templates. Although they are a very useful abstraction, iterators do have some weaknesses. D’s ranges were designed to overcome these weaknesses.

Andrei Alexandrescu introduces ranges in his paper on iteration and demonstrates how they can be superior to iterators.

---