土耳其文《d编程》range 翻译 一
程序员文章站
2022-05-16 09:37:43
...
Ranges 范围
Ranges are an abstraction of element access. This abstraction enables the use of great number of algorithms over great number of container types. Ranges emphasize how container elements are accessed, as opposed to how the containers are implemented.
Ranges是一个抽象的元素访问。这种抽象允许使用大量的算法到容器类型。Ranges 强调容器中的元素是如何访问，而不是强调容器是如何实现。
Ranges are a very simple concept that is based on whether a type defines certain sets of member functions. We have already seen 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.
Ranges是一个非常简单的概念，这是基于一个类型是否定义了某些成员函数集。在 Structs 和 Classes 的 foreach 章节我们已经看到了这个概念 ：可用于任何类型的提供的成员函数 empty, front, and popFront() ，可以使用 foreach 循环。这三个成员函数是 range 类型之一的 InputRange 的必要条件。
I will start introducing ranges with InputRange, the simplest of all the range types. The other ranges require more member functions over InputRange.
我将开始介绍 InputRange，这是 range 类型里最简单的。其他 ranges 比InputRange 需要更多的成员函数。
Before going further, I 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.
容器（数据结构）：容器是一个几乎在每一个程序中都非常有用的概念。变量放在一起的目的是作为一个容器的元素一起使用。D容器的核心功能是arrays（数组）和associative arrays（关联数组）和在 std.container 模块中定义的特殊类型的容器。每个容器实现为一个特定的数据结构。例如，关联数组是一个哈希表的实现。
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 these 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.
每个数据结构存储其元素，并提供特殊的方式访问该数据结构。
例如，数组中的元素一个挨一个的存储和访问元素的索引；在链表中元素存储在节点，并通过这些节点逐个进行访问；在一个排序二叉树中，节点通过各自的分支提供访问前面和连续元素[color=red]？？？； 等等。[/color]
In this chapter, I will use the terms container and data structure interchangeably.
在这一章中，我将使用术语 “容器container” 和 “数据结构data structure” 互换。
Algorithm (function): Processing of 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, I will use the terms algorithm and function interchangeably.
在这一章中，我将使用术语 “算法algorithm” 和 “函数function” 互换。
For most of the samples below, I 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. I will leave examples of templated ranges to the next chapter.
对于下面大多数的示例，我将使用 int 作为元素类型和 int[ ] 作为容器类型。在现实中，容器模板和算法使用range将会更强大。事实上，（在 D2 的 phobos库中）大部分的容器和算法模板都是和 range 绑在一起的。模板 range 的例子我将在后面的章节再讲。
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.
一个非常成功的算法和数据结构库是标准模板库（STL），这似乎也作为C++标准库的一部分。STL提供了迭代器的概念，这是C + +中的模板实现。
Although they are a very useful abstraction, iterators do have some weaknesses. Ranges are designed by Andrei Alexandrescu partly to overcome these weaknesses. D's standard library Phobos is the only library that uses ranges that are the subject of this chapter.
虽然他们是一个非常有用的抽象，迭代器也有一些弱点。这些 Ranges 由 Andrei Alexandrescu 设计，部分克服了这些弱点。D2 的唯一标准库 Phobos，它使用的 ranges 是本章的主题。
Andrei Alexandrescu introduces ranges in the seminal paper On Iteration and demonstrates how they are superior to iterators.
Andrei Alexandrescu 开创性的论文介绍了 range 的迭代，并演示他们是如何优于 iterators 迭代器的。
Ranges are a part of D。 Ranges 是 D2 的一部分
Ranges are an integral part of D. D's arrays and slices happen to be implementations of the most powerful range RandomAccessRange, and there are many range features in Phobos. Although implementing new range types or algorithms are not common in most programs, it is important to understand how ranges are used in Phobos.
Ranges 是 D 不可分割的一部分，D 的 arrays 和 slices（切片）恰巧是范围 RandomAccessRange 最强大的实现，并在 Phobos 中有一系列 range 特性。虽然实现新的 range 类型或算法在大多数程序中不常见，重要的是了解在 Phobos 中如何使用 range。
Many Phobos algorithms return temporary range objects. For example filter(), which chooses elements that are greater than 10 in the following code, actually returns a range object, not an array:
Phobos 许多算法返回临时 range 对象。例如过滤器 filter() ，在下面的代码，选择大于10的元素，实际上返回一个 range 对象，而不是一个数组：
import std.stdio;
import std.algorithm;
void main()
{
int[] values = [ 1, 20, 7, 11 ];
writeln(filter!"a > 10"(values));
}
Note: We have seen template parameters that indicate variables with the special letters a, b, etc. when we used sort() earlier in the Delegates chapter.
注：我们已经看到的模板参数表明表明变量与特殊字母a，b 等， 在 Delegates 一章我们将使用sort()。
writeln uses that range object lazily and accesses the elements as it needs them:
[20, 11]
writeln使用惰性 range 对象，并访问元素，因为它需要：[20, 11]？？？
That output may suggest that filter() returns an int[] but this is not the case. We can see this from the fact that the following assignment produces a compilation error:
输出可能表明，filter()返回一个 int[ ] 的，但事实并非如此。我们可以看到一个事实，即下面的赋值产生一个编译错误：
int[] chosen = filter!"a > 10"(values); // ← compilation ERROR 编译错误
The error message contains the type of the range object:
错误信息中包含的 range 对象的类型：
Error: cannot implicitly convert expression (filter(values))
of type Result to int[]
错误：不能隐式转换表达式 filter(values) 的结果类型为 int[]
Note: The type may be different in the version of Phobos that you are using.
注：该类型可能会在您所使用的 Phobos 的版本不同。
It is possible to convert that temporary object to an actual array, as we will see later in the chapter.
正如在本章稍后我们将看到，它可以将临时对象转换成实际的数组。
Traditional implementations of algorithms
传统的算法实现
In traditional implementations of algorithms, the algorithms know how the data structures that they operate on are implemented. For example, the following function that prints the elements of a linked list must know that the nodes of the linked list have members named element and next:
在传统的算法实现中，算法，知道他们是怎么操作的数据结构的实现。例如，下面的函数打印一个链表元素，链表必须知道节点有已命名元素和下一个成员：
struct Node
{
int element;
Node * next;
}
void print(const(Node) * list)
{
for ( ; list; list = list.next) {
write(' ', list.element);
}
}
Similarly, a function that prints the elements of an array must know that arrays have a length property and their elements are accessed with the [] operator:
同样，一个函数，打印出数组中的元素，必须知道数组有一个长度属性和它们的元素都与访问[ ]操作符：
void print(const int[] array)
{
for (int i = 0; i != array.length; ++i) {
write(' ', array[i]);
}
}
Note: We know that foreach is more useful when iterating over arrays. As a demonstration of how traditional algorithms are tied to data structures, let's assume a case where the use of for is really needed.
注：我们知道的 foreach 遍历数组时更有用。作为示范，将演示如何将传统算法与数据结构绑在一起，让我们假设其中一个用例。
Having algorithms tied to data structures makes it necessary to write them specially for each type. For example, the functions find(), sort(), commonOnes(), swap(), etc. must be written separately for array, linked list, associative array, binary tree, heap, etc. As a result, N algorithms that support M data structures must be written NxM times. (Note: In reality, the count is less that NxM, because not every algorithm can be used with every data structure, e.g. associative arrays cannot be sorted.)
对于所有的数据结构和算法，使得有必要为每一个类型专门写一套。例如，函数 find(), sort(), commonOnes(), swap(),等等，必须分别写入单独的数组，链表，关联数组，二叉树，堆等。因此，N 算法支持 M 数据结构必须是 NxM 倍。（注：在现实中，计数小于NxM ？？？，因为不是每个算法可以用到每一个数据结构，例如关联数组不能排序）。
Conversely, because ranges abstract algorithms away from data structures, implementing just N algorithms and M data structures would be sufficient. A newly implemented data structure can work with all of the existing algorithms that support the type of range that the new data strtucture provides, and a newly implemented algorithm can work with all of the existing data structures that support the range type that the new algorithm requires.
相反，因为 range 的抽象算法远离数据结构，实现仅仅局限于 N 算法和 M 数据结构就足够了。新近实施的数据结构，可以工作在所有现有的算法，支持 range 类型这个新的数据结构，以及新实现的算法可以使用现有的数据结构，支持 range 类型的新算法的所有要求。
Phobos ranges。 Phobos 中的 ranges
The ranges in this chapter are different from values ranges that are written in the form begin..end. We had seen how value ranges are used with the foreach loop and with slices:
本章的 ranges 是以不同的值 range 的形式写在 begin..end 中间。我们已经看到了值 range 如何使用 foreach 循环和切片slices：
int[] slice = array[5..10]; // value range,值 range
// NOT a Phobos range 非 Phobos range
foreach (value; 3..7) { // value range,值 range
// NOT a Phobos range 非 Phobos range
When I write range, I mean a Phobos range in this chapter.
本章中的 range 仅代表 Phobos 中的 range
Ranges form a range hierarchy. At the bottom of this hierarchy is the simplest range InputRange. The other ranges bring more requirements on top of the range that they are based on. The following are all of the ranges with their requirements, sorted from the simplest to the more capable:
Ranges 一个有层次结构的 range。在这个层次结构的底部是最简单的InputRange。在层次结构顶部其他的 range 有更多的要求。以下是所有 range 的要求，从最简单到更强大排序：
InputRange: requires the empty, front and popFront() member functions
需要 empty, front and popFront() 成员函数
ForwardRange: additionally requires the save() member function
增加了 save() 成员函数
BidirectionalRange: additionally requires the back and popBack() member functions
增加了 back and popBack() 成员函数
RandomAccessRange: additionally requires the [] operator (and another member function depending on whether the range is finite or infinite)
增加了 [ ] 操作符（和另一个成员函数，取决于是否range 是有限或无限 range）
This hierarchy can be shown like the following. RandomAccessRange has finite and infinite versions:
这种层次结构可以像下面所示。 RandomAccessRange 有有限和无限的版本：
InputRange 输入range
↑
ForwardRange 向前迭代range
↗ ↖
BidirectionalRange RandomAccessRange (infinite无限版本)
双向迭代 range 随机访问 range
↑
RandomAccessRange (finite有限版本)
随机访问 range
The graph above uses the format of class hierarchies where the lowest level type is printed at the top.
上图中使用的类层次结构表示，越上面的越简单。
Those ranges are about providing element access. There is one more range, which is about element output:
这些 ranges 提供元素访问。还有一个 range 是有关元素的输出：
：
OutputRange: requires support for the put(range, element) operation
需要支持 put(range, element) 操作
These five range types are sufficient to abstract algorithms from data structures.
这五种 range 类型足以从数据结构抽象算法。
Iterating by shortening the range
通过 range 缩短迭代（比如缩短一个数组，译注）
Normally, iterating over the elements of a range does not change the range itself. For example, iterating over a slice with foreach or for does not affect the slice:
通常，对 range 的元素的迭代不会改变 range 本身。例如，foreach 迭代一个切片 slice 并不影响它自身：
int[] slice = [ 10, 11, 12 ];
for (int i = 0; i != slice.length; ++i) {
write(' ', slice[i]);
}
assert(slice.length == 3); // ← the length doesn't change 长度不发生变化
Another way of iteration requires a different way of thinking: iteration can be achieved by shortening the range from the beginning. In this method, always the first element is used for element access and the first element is popped from the beginning in order to get to the next element:
另一种迭代方式需要不同的思维方式： range 从前端缩短迭代（比如从起始处开始缩短一个数组，看到后面才明白大概是这个意思，译注） 。在这种方法中，第一个元素总是被先使用或弹出，然后获得下一个元素：
for ( ; slice.length; slice = slice[1..$]) {
write(' ', slice[0]); // ← always the first element 总是第一个元素
}
Iteration is achieved by removing the first element by the slice = slice[1..$] expression. The slice above is completely consumed by going through the following stages:
slice = slice[1..$] 迭代表达式将先移除第一个元素。然后通过以下阶段全部移除：
[ 10, 11, 12 ]
[ 11, 12 ]
[ 12 ]
[ ]
The iteration concept of Phobos ranges is based on this new thinking of shortening the range from the beginning. (BidirectionalRange and finite RandomAccessRange types can be shortened from the end as well.)
在 Phobos 中 ranges 的迭代概念是基于从起始缩短范围这一新的思想。（BidirectionalRange和有限RandomAccessRange类型可以从尾端开始缩短。）
Please note that the code above is just to demonstrate this type of iteration; it should not be considered normal to implement for loops as in that example.
请注意，上面的代码只是为了展示这种类型的迭代，这个例子它并不是个正常的循环实现。
Since losing elements just to iterate over a range would not be desired in most cases, a surrogate range may be consumed instead. The following code uses a separate slice to preserve the elements of the original one:
由于失去的元素只是在特定 range 内进行迭代，代理 range 被消耗。下面的代码使用一个单独的切片，以保留原有的元素：
int[] slice = [ 10, 11, 12 ];
int[] surrogate = slice;
for ( ; surrogate.length; surrogate = surrogate[1..$]) {
write(' ', surrogate[0]);
}
assert(surrogate.length == 0); // ← surrogate is consumed。代理被消耗
assert(slice.length == 3); // ← slice remains the same。slice 仍然是相同的
This is the method employed by most of the Phobos range functions: they return special range objects to be consumed in order to preserve the original elements.
这是 Phobos range 大部分函数采用的方法：他们返回要被消耗的特殊 range 对象，以保留原始元素。
InputRange
This type of range models the type of iteration where elements are accessed in sequence as we have seen in the print() functions above. This iteration is always in the forward direction; there is no way of going back to the elements that have already been iterated over. Despite this limitation, many algorithms are based merely on sequential access. InputRange covers the standard input streams of programs as well, where elements are removed from the stream as they are read.
这个 range 模块里的迭代是按元素的按顺序访问的，在上面的 print() 函数我们已经看到， 本次迭代总是在前进方向，并没有打算回已经遍历过的元素。尽管有这样的限制，许多算法是仅仅基于顺序访问。InputRange 涵盖了程序的标准输入流，其中的元素是从流中移除，因为它们是只读的。（移除又只读？？？？）
For completeness, here are the three functions that InputRange requires:
为了完整，这里 InputRange 要求有三个函数：
empty: specifies whether the range is empty; it must return true when the range is considered to be empty, and false otherwise
指定 range 是否是空的，为空则返回 true ，否则返回 false 。
front: provides access to the element at the beginning of the range
从 range 的起始元素开始访问
popFront(): shortens the range from the beginning by removing the first element
从起始处删除第一个元素缩短 range
Note: I write empty and front without parenthesis, as they can be seen as properties of the range; and popFront() with parenthesis as it is a function with side effects.
注： empty 和 front 我没有带括号（），因为它们可以被视为 range 的属性； popFront 带有括号（） ，因为它是一个函数。
Here is how print() can be implemented by using these range functions:
下面是 print() 函数使用 range 的实现：
void print(T)(T range)
{
for ( ; !range.empty; range.popFront()) {
write(' ', range.front);
}
writeln();
}
Please also note that print() is now a function template to avoid limiting the range type arbitrarily. print() can now work with any type that provides the three InputRange functions.
请注意， print() 函数现在是一个模板，以避免随意限制 range 类型。 print() 现在可以使用任何提供了三个函数的 InputRange （看代码应该是这意思。译注 ）
InputRange example 例子
Let's redesign the School type that we have seen before, this time as an InputRange. We can imagine School as a Student container so when designed as a range, it can be seen as a range of Students.
我们已经看到，我们用 InputRange 对 School 类型进行了重新设计。我们可以想像 School 为 Student 的容器，它被设计成容纳 Student 的 range
In order to keep the example short, let's disregard some important design aspects. Let's
为了保持示例简短，我们忽视了一些重要的方面。让我们
implement only the members that are related to this section
只实现那些与此相关的部分成员
design all types as structs
所有类型设计为 struct
ignore specifiers and qualifiers like private, public, and const
忽视说明符和限定符，如 private, public, and const
not take advantage of contract programming and unit testting
不利用契约编程和单元测试优势
import std.string;
struct Student
{
string name;
int number;
string toString()
{
return format("%s(%s)", name, number);
}
}
struct School
{
Student[] students;
}
void main()
{
auto school = School( [ Student("Ebru", 1),
Student("Derya", 2) ,
Student("Damla", 3) ] );
}
To make School be accepted as an InputRange, we must define the three InputRange member functions.
为了使 School 作为 InputRange，我们必须定义 InputRange 必需的三个成员函数。
For empty to return true when the range is empty, we can use the length of the students array. When the length of that array is 0, the range is considered empty:
当 range 为空，empty 则返回 true ，我们可以使用 students 数组的长度。当长度为0，range 为空：
struct School
{
// ...
@property bool empty()
{
return students.length == 0;
}
}
empty is defined as @property to be able to write it without parenthesis as in school.empty.
empty 定义为 @property ( 属性），以便 school.empty 不用带括号“()”。
For front to return the first element of the range, we can return the first element of the array:
front 返回 range 的第一元素，我们可以返回数组的第一个元素：
struct School
{
// ...
@property ref Student front()
{
return students[0];
}
}
Note: I have used the ref keyword to be able to provide access to the actual element instead of a copy of it. Otherwise the elements would be copied because Student is a struct.
注：我已经使用了 ref 关键字以便能访问实际元素，而不是它的一个副本。否则的元素会被复制，因为 Student 是一个struct 。
For popFront() to shorten the range from the beginning, we can shorten the students array from the beginning:
对于popFront（） ，从起始缩短 range ，我们可以从起始缩短 students 数组：
struct School
{
// ...
void popFront()
{
students = students[1 .. $];
}
}
Note: As I have mentioned above, it is not normal to lose the orgininal elements from the range just to iterate over them. We will address this issue below by introducing a special range type.
注：正如我上面提到的，这是不正常丢失 orgininal（是啥？？？错别字吧
） 元素只是为了从 range 遍历它们。下面我们将通过引进一个特殊的 range 类型解决这个问题。
These three functions are sufficient to make School to be used as an InputRange. As an example, let's add the following line at the end of main() above to have our new print() function template to use school as a range:
这三个函数都足以使 School 被作为 InputRange 使用。作为一个例子，让我们在main() 的结尾处添加新的 print() 函数模板以便 School 作为一个 range 使用：
print(school);
print() uses that object as an InputRange and prints its elements to the output:
print() 使用 InputRange 对象并打印其元素的输出：
Ebru(1) Derya(2) Damla(3)
We have achieved our goal of defining a user type as an InputRange; we have sent it to an algorithm that operates on InputRange types. School is actually ready to be used with algorithms of Phobos or any other library that work with InputRange types. We will see examples of this below.
我们已经实现了定义一个 InputRange 作为用户类型的目标；我们把它交给一个算法，去操作 InputRange 类型， 实际上 School 是 Phobos 或任何其他库中InputRange 类型随时可以使用的算法。下面的例子我们将看到。
The std.array module to use arrays as ranges
std.array 模块使用 range 数组
Merely importing the std.array module makes the most common container type conform to the most capable range type: arrays can seamlessly be used as RandomAccessRange objects.
仅仅导入 std.array 模块就可使得最常见的容器类型符合最有能力的 range ：数组可作为无缝的 RandomAccessRange 对象。
std.array defines empty, front, popFront() and other range functions specially for arrays. As a result, arrays are ready to be used with any range function, for example with print():
std.array 定义了 empty, front, popFront() ，和其他 range 函数专用的数组。因此，数组准备用于任何 range 函数， 一个 print() 例子：
import std.array;
// ...
print([ 1, 2, 3, 4 ]);
Note: It is not necessary to import std.array if the std.range module has already been imported.
注：它没必要导入 std.array 如果 std.range 模块已导入。
The reverse is not always true: although arrays can be used as ranges, not every range type can be used as an array. When necessary, all of the elements can be copied one by one into an array. std.array.array is a helper function to simplify this task; array() iterates over InputRange ranges, copies the elements, and returns a new array:
反向并非总是如此：虽然数组可以作为 ranges 使用，但不是每个 range 类型都可以作为数组使用。必要时，所有的元素可以被复制到一个数组，std.array.array是一个辅助函数，可以用来简化这一任务; array() 遍历 InputRange，复制元素，并返回一个新的数组：
import std.array;
// ...
auto copiesOfStudents = array(school);
writeln(copiesOfStudents);
The output: 输出：
[Ebru(1), Derya(2), Damla(3)]
Special feature of strings by the std.array module
std.array 模块字符串特殊功能
Being character arrays by definition, strings can also be used as ranges just by importing std.array. The two exceptions are, char and wchar strings cannot be used as RandomAccessRange.
字符数组的定义是，字符串也可以作为 range ，只需要导入 std.array。有两个例外是，char 和 wchar 字符串不能作为 RandomAccessRange 使用。
std.array provides a special functionality with all types of strings: iterating over strings becomes iterating over Unicode code points, not over UTF code units. As a result, strings appear as ranges of Unicode characters.
std.array提供了与所有现有字符串类型不同的特殊功能：字符串迭代变为迭代 Unicode 代码点[color=red]（？？？），不超过 UTF 编码单元（？？？）。因此，字符串以 Unicode 字符 range 出现。[/color]
The following strings contain ç and é, which cannot be represented by a single char and the gothic letter ahsa (
Ranges are an abstraction of element access. This abstraction enables the use of great number of algorithms over great number of container types. Ranges emphasize how container elements are accessed, as opposed to how the containers are implemented.
Ranges是一个抽象的元素访问。这种抽象允许使用大量的算法到容器类型。Ranges 强调容器中的元素是如何访问，而不是强调容器是如何实现。
Ranges are a very simple concept that is based on whether a type defines certain sets of member functions. We have already seen 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.
Ranges是一个非常简单的概念，这是基于一个类型是否定义了某些成员函数集。在 Structs 和 Classes 的 foreach 章节我们已经看到了这个概念 ：可用于任何类型的提供的成员函数 empty, front, and popFront() ，可以使用 foreach 循环。这三个成员函数是 range 类型之一的 InputRange 的必要条件。
I will start introducing ranges with InputRange, the simplest of all the range types. The other ranges require more member functions over InputRange.
我将开始介绍 InputRange，这是 range 类型里最简单的。其他 ranges 比InputRange 需要更多的成员函数。
Before going further, I 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.
容器（数据结构）：容器是一个几乎在每一个程序中都非常有用的概念。变量放在一起的目的是作为一个容器的元素一起使用。D容器的核心功能是arrays（数组）和associative arrays（关联数组）和在 std.container 模块中定义的特殊类型的容器。每个容器实现为一个特定的数据结构。例如，关联数组是一个哈希表的实现。
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 these 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.
每个数据结构存储其元素，并提供特殊的方式访问该数据结构。
例如，数组中的元素一个挨一个的存储和访问元素的索引；在链表中元素存储在节点，并通过这些节点逐个进行访问；在一个排序二叉树中，节点通过各自的分支提供访问前面和连续元素[color=red]？？？； 等等。[/color]
In this chapter, I will use the terms container and data structure interchangeably.
在这一章中，我将使用术语 “容器container” 和 “数据结构data structure” 互换。
Algorithm (function): Processing of 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, I will use the terms algorithm and function interchangeably.
在这一章中，我将使用术语 “算法algorithm” 和 “函数function” 互换。
For most of the samples below, I 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. I will leave examples of templated ranges to the next chapter.
对于下面大多数的示例，我将使用 int 作为元素类型和 int[ ] 作为容器类型。在现实中，容器模板和算法使用range将会更强大。事实上，（在 D2 的 phobos库中）大部分的容器和算法模板都是和 range 绑在一起的。模板 range 的例子我将在后面的章节再讲。
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.
一个非常成功的算法和数据结构库是标准模板库（STL），这似乎也作为C++标准库的一部分。STL提供了迭代器的概念，这是C + +中的模板实现。
Although they are a very useful abstraction, iterators do have some weaknesses. Ranges are designed by Andrei Alexandrescu partly to overcome these weaknesses. D's standard library Phobos is the only library that uses ranges that are the subject of this chapter.
虽然他们是一个非常有用的抽象，迭代器也有一些弱点。这些 Ranges 由 Andrei Alexandrescu 设计，部分克服了这些弱点。D2 的唯一标准库 Phobos，它使用的 ranges 是本章的主题。
Andrei Alexandrescu introduces ranges in the seminal paper On Iteration and demonstrates how they are superior to iterators.
Andrei Alexandrescu 开创性的论文介绍了 range 的迭代，并演示他们是如何优于 iterators 迭代器的。
Ranges are a part of D。 Ranges 是 D2 的一部分
Ranges are an integral part of D. D's arrays and slices happen to be implementations of the most powerful range RandomAccessRange, and there are many range features in Phobos. Although implementing new range types or algorithms are not common in most programs, it is important to understand how ranges are used in Phobos.
Ranges 是 D 不可分割的一部分，D 的 arrays 和 slices（切片）恰巧是范围 RandomAccessRange 最强大的实现，并在 Phobos 中有一系列 range 特性。虽然实现新的 range 类型或算法在大多数程序中不常见，重要的是了解在 Phobos 中如何使用 range。
Many Phobos algorithms return temporary range objects. For example filter(), which chooses elements that are greater than 10 in the following code, actually returns a range object, not an array:
Phobos 许多算法返回临时 range 对象。例如过滤器 filter() ，在下面的代码，选择大于10的元素，实际上返回一个 range 对象，而不是一个数组：
import std.stdio;
import std.algorithm;
void main()
{
int[] values = [ 1, 20, 7, 11 ];
writeln(filter!"a > 10"(values));
}
Note: We have seen template parameters that indicate variables with the special letters a, b, etc. when we used sort() earlier in the Delegates chapter.
注：我们已经看到的模板参数表明表明变量与特殊字母a，b 等， 在 Delegates 一章我们将使用sort()。
writeln uses that range object lazily and accesses the elements as it needs them:
[20, 11]
writeln使用惰性 range 对象，并访问元素，因为它需要：[20, 11]？？？
That output may suggest that filter() returns an int[] but this is not the case. We can see this from the fact that the following assignment produces a compilation error:
输出可能表明，filter()返回一个 int[ ] 的，但事实并非如此。我们可以看到一个事实，即下面的赋值产生一个编译错误：
int[] chosen = filter!"a > 10"(values); // ← compilation ERROR 编译错误
The error message contains the type of the range object:
错误信息中包含的 range 对象的类型：
Error: cannot implicitly convert expression (filter(values))
of type Result to int[]
错误：不能隐式转换表达式 filter(values) 的结果类型为 int[]
Note: The type may be different in the version of Phobos that you are using.
注：该类型可能会在您所使用的 Phobos 的版本不同。
It is possible to convert that temporary object to an actual array, as we will see later in the chapter.
正如在本章稍后我们将看到，它可以将临时对象转换成实际的数组。
Traditional implementations of algorithms
传统的算法实现
In traditional implementations of algorithms, the algorithms know how the data structures that they operate on are implemented. For example, the following function that prints the elements of a linked list must know that the nodes of the linked list have members named element and next:
在传统的算法实现中，算法，知道他们是怎么操作的数据结构的实现。例如，下面的函数打印一个链表元素，链表必须知道节点有已命名元素和下一个成员：
struct Node
{
int element;
Node * next;
}
void print(const(Node) * list)
{
for ( ; list; list = list.next) {
write(' ', list.element);
}
}
Similarly, a function that prints the elements of an array must know that arrays have a length property and their elements are accessed with the [] operator:
同样，一个函数，打印出数组中的元素，必须知道数组有一个长度属性和它们的元素都与访问[ ]操作符：
void print(const int[] array)
{
for (int i = 0; i != array.length; ++i) {
write(' ', array[i]);
}
}
Note: We know that foreach is more useful when iterating over arrays. As a demonstration of how traditional algorithms are tied to data structures, let's assume a case where the use of for is really needed.
注：我们知道的 foreach 遍历数组时更有用。作为示范，将演示如何将传统算法与数据结构绑在一起，让我们假设其中一个用例。
Having algorithms tied to data structures makes it necessary to write them specially for each type. For example, the functions find(), sort(), commonOnes(), swap(), etc. must be written separately for array, linked list, associative array, binary tree, heap, etc. As a result, N algorithms that support M data structures must be written NxM times. (Note: In reality, the count is less that NxM, because not every algorithm can be used with every data structure, e.g. associative arrays cannot be sorted.)
对于所有的数据结构和算法，使得有必要为每一个类型专门写一套。例如，函数 find(), sort(), commonOnes(), swap(),等等，必须分别写入单独的数组，链表，关联数组，二叉树，堆等。因此，N 算法支持 M 数据结构必须是 NxM 倍。（注：在现实中，计数小于NxM ？？？，因为不是每个算法可以用到每一个数据结构，例如关联数组不能排序）。
Conversely, because ranges abstract algorithms away from data structures, implementing just N algorithms and M data structures would be sufficient. A newly implemented data structure can work with all of the existing algorithms that support the type of range that the new data strtucture provides, and a newly implemented algorithm can work with all of the existing data structures that support the range type that the new algorithm requires.
相反，因为 range 的抽象算法远离数据结构，实现仅仅局限于 N 算法和 M 数据结构就足够了。新近实施的数据结构，可以工作在所有现有的算法，支持 range 类型这个新的数据结构，以及新实现的算法可以使用现有的数据结构，支持 range 类型的新算法的所有要求。
Phobos ranges。 Phobos 中的 ranges
The ranges in this chapter are different from values ranges that are written in the form begin..end. We had seen how value ranges are used with the foreach loop and with slices:
本章的 ranges 是以不同的值 range 的形式写在 begin..end 中间。我们已经看到了值 range 如何使用 foreach 循环和切片slices：
int[] slice = array[5..10]; // value range,值 range
// NOT a Phobos range 非 Phobos range
foreach (value; 3..7) { // value range,值 range
// NOT a Phobos range 非 Phobos range
When I write range, I mean a Phobos range in this chapter.
本章中的 range 仅代表 Phobos 中的 range
Ranges form a range hierarchy. At the bottom of this hierarchy is the simplest range InputRange. The other ranges bring more requirements on top of the range that they are based on. The following are all of the ranges with their requirements, sorted from the simplest to the more capable:
Ranges 一个有层次结构的 range。在这个层次结构的底部是最简单的InputRange。在层次结构顶部其他的 range 有更多的要求。以下是所有 range 的要求，从最简单到更强大排序：
InputRange: requires the empty, front and popFront() member functions
需要 empty, front and popFront() 成员函数
ForwardRange: additionally requires the save() member function
增加了 save() 成员函数
BidirectionalRange: additionally requires the back and popBack() member functions
增加了 back and popBack() 成员函数
RandomAccessRange: additionally requires the [] operator (and another member function depending on whether the range is finite or infinite)
增加了 [ ] 操作符（和另一个成员函数，取决于是否range 是有限或无限 range）
This hierarchy can be shown like the following. RandomAccessRange has finite and infinite versions:
这种层次结构可以像下面所示。 RandomAccessRange 有有限和无限的版本：
InputRange 输入range
↑
ForwardRange 向前迭代range
↗ ↖
BidirectionalRange RandomAccessRange (infinite无限版本)
双向迭代 range 随机访问 range
↑
RandomAccessRange (finite有限版本)
随机访问 range
The graph above uses the format of class hierarchies where the lowest level type is printed at the top.
上图中使用的类层次结构表示，越上面的越简单。
Those ranges are about providing element access. There is one more range, which is about element output:
这些 ranges 提供元素访问。还有一个 range 是有关元素的输出：
：
OutputRange: requires support for the put(range, element) operation
需要支持 put(range, element) 操作
These five range types are sufficient to abstract algorithms from data structures.
这五种 range 类型足以从数据结构抽象算法。
Iterating by shortening the range
通过 range 缩短迭代（比如缩短一个数组，译注）
Normally, iterating over the elements of a range does not change the range itself. For example, iterating over a slice with foreach or for does not affect the slice:
通常，对 range 的元素的迭代不会改变 range 本身。例如，foreach 迭代一个切片 slice 并不影响它自身：
int[] slice = [ 10, 11, 12 ];
for (int i = 0; i != slice.length; ++i) {
write(' ', slice[i]);
}
assert(slice.length == 3); // ← the length doesn't change 长度不发生变化
Another way of iteration requires a different way of thinking: iteration can be achieved by shortening the range from the beginning. In this method, always the first element is used for element access and the first element is popped from the beginning in order to get to the next element:
另一种迭代方式需要不同的思维方式： range 从前端缩短迭代（比如从起始处开始缩短一个数组，看到后面才明白大概是这个意思，译注） 。在这种方法中，第一个元素总是被先使用或弹出，然后获得下一个元素：
for ( ; slice.length; slice = slice[1..$]) {
write(' ', slice[0]); // ← always the first element 总是第一个元素
}
Iteration is achieved by removing the first element by the slice = slice[1..$] expression. The slice above is completely consumed by going through the following stages:
slice = slice[1..$] 迭代表达式将先移除第一个元素。然后通过以下阶段全部移除：
[ 10, 11, 12 ]
[ 11, 12 ]
[ 12 ]
[ ]
The iteration concept of Phobos ranges is based on this new thinking of shortening the range from the beginning. (BidirectionalRange and finite RandomAccessRange types can be shortened from the end as well.)
在 Phobos 中 ranges 的迭代概念是基于从起始缩短范围这一新的思想。（BidirectionalRange和有限RandomAccessRange类型可以从尾端开始缩短。）
Please note that the code above is just to demonstrate this type of iteration; it should not be considered normal to implement for loops as in that example.
请注意，上面的代码只是为了展示这种类型的迭代，这个例子它并不是个正常的循环实现。
Since losing elements just to iterate over a range would not be desired in most cases, a surrogate range may be consumed instead. The following code uses a separate slice to preserve the elements of the original one:
由于失去的元素只是在特定 range 内进行迭代，代理 range 被消耗。下面的代码使用一个单独的切片，以保留原有的元素：
int[] slice = [ 10, 11, 12 ];
int[] surrogate = slice;
for ( ; surrogate.length; surrogate = surrogate[1..$]) {
write(' ', surrogate[0]);
}
assert(surrogate.length == 0); // ← surrogate is consumed。代理被消耗
assert(slice.length == 3); // ← slice remains the same。slice 仍然是相同的
This is the method employed by most of the Phobos range functions: they return special range objects to be consumed in order to preserve the original elements.
这是 Phobos range 大部分函数采用的方法：他们返回要被消耗的特殊 range 对象，以保留原始元素。
InputRange
This type of range models the type of iteration where elements are accessed in sequence as we have seen in the print() functions above. This iteration is always in the forward direction; there is no way of going back to the elements that have already been iterated over. Despite this limitation, many algorithms are based merely on sequential access. InputRange covers the standard input streams of programs as well, where elements are removed from the stream as they are read.
这个 range 模块里的迭代是按元素的按顺序访问的，在上面的 print() 函数我们已经看到， 本次迭代总是在前进方向，并没有打算回已经遍历过的元素。尽管有这样的限制，许多算法是仅仅基于顺序访问。InputRange 涵盖了程序的标准输入流，其中的元素是从流中移除，因为它们是只读的。（移除又只读？？？？）
For completeness, here are the three functions that InputRange requires:
为了完整，这里 InputRange 要求有三个函数：
empty: specifies whether the range is empty; it must return true when the range is considered to be empty, and false otherwise
指定 range 是否是空的，为空则返回 true ，否则返回 false 。
front: provides access to the element at the beginning of the range
从 range 的起始元素开始访问
popFront(): shortens the range from the beginning by removing the first element
从起始处删除第一个元素缩短 range
Note: I write empty and front without parenthesis, as they can be seen as properties of the range; and popFront() with parenthesis as it is a function with side effects.
注： empty 和 front 我没有带括号（），因为它们可以被视为 range 的属性； popFront 带有括号（） ，因为它是一个函数。
Here is how print() can be implemented by using these range functions:
下面是 print() 函数使用 range 的实现：
void print(T)(T range)
{
for ( ; !range.empty; range.popFront()) {
write(' ', range.front);
}
writeln();
}
Please also note that print() is now a function template to avoid limiting the range type arbitrarily. print() can now work with any type that provides the three InputRange functions.
请注意， print() 函数现在是一个模板，以避免随意限制 range 类型。 print() 现在可以使用任何提供了三个函数的 InputRange （看代码应该是这意思。译注 ）
InputRange example 例子
Let's redesign the School type that we have seen before, this time as an InputRange. We can imagine School as a Student container so when designed as a range, it can be seen as a range of Students.
我们已经看到，我们用 InputRange 对 School 类型进行了重新设计。我们可以想像 School 为 Student 的容器，它被设计成容纳 Student 的 range
In order to keep the example short, let's disregard some important design aspects. Let's
为了保持示例简短，我们忽视了一些重要的方面。让我们
implement only the members that are related to this section
只实现那些与此相关的部分成员
design all types as structs
所有类型设计为 struct
ignore specifiers and qualifiers like private, public, and const
忽视说明符和限定符，如 private, public, and const
not take advantage of contract programming and unit testting
不利用契约编程和单元测试优势
import std.string;
struct Student
{
string name;
int number;
string toString()
{
return format("%s(%s)", name, number);
}
}
struct School
{
Student[] students;
}
void main()
{
auto school = School( [ Student("Ebru", 1),
Student("Derya", 2) ,
Student("Damla", 3) ] );
}
To make School be accepted as an InputRange, we must define the three InputRange member functions.
为了使 School 作为 InputRange，我们必须定义 InputRange 必需的三个成员函数。
For empty to return true when the range is empty, we can use the length of the students array. When the length of that array is 0, the range is considered empty:
当 range 为空，empty 则返回 true ，我们可以使用 students 数组的长度。当长度为0，range 为空：
struct School
{
// ...
@property bool empty()
{
return students.length == 0;
}
}
empty is defined as @property to be able to write it without parenthesis as in school.empty.
empty 定义为 @property ( 属性），以便 school.empty 不用带括号“()”。
For front to return the first element of the range, we can return the first element of the array:
front 返回 range 的第一元素，我们可以返回数组的第一个元素：
struct School
{
// ...
@property ref Student front()
{
return students[0];
}
}
Note: I have used the ref keyword to be able to provide access to the actual element instead of a copy of it. Otherwise the elements would be copied because Student is a struct.
注：我已经使用了 ref 关键字以便能访问实际元素，而不是它的一个副本。否则的元素会被复制，因为 Student 是一个struct 。
For popFront() to shorten the range from the beginning, we can shorten the students array from the beginning:
对于popFront（） ，从起始缩短 range ，我们可以从起始缩短 students 数组：
struct School
{
// ...
void popFront()
{
students = students[1 .. $];
}
}
Note: As I have mentioned above, it is not normal to lose the orgininal elements from the range just to iterate over them. We will address this issue below by introducing a special range type.
注：正如我上面提到的，这是不正常丢失 orgininal（是啥？？？错别字吧
These three functions are sufficient to make School to be used as an InputRange. As an example, let's add the following line at the end of main() above to have our new print() function template to use school as a range:
这三个函数都足以使 School 被作为 InputRange 使用。作为一个例子，让我们在main() 的结尾处添加新的 print() 函数模板以便 School 作为一个 range 使用：
print(school);
print() uses that object as an InputRange and prints its elements to the output:
print() 使用 InputRange 对象并打印其元素的输出：
Ebru(1) Derya(2) Damla(3)
We have achieved our goal of defining a user type as an InputRange; we have sent it to an algorithm that operates on InputRange types. School is actually ready to be used with algorithms of Phobos or any other library that work with InputRange types. We will see examples of this below.
我们已经实现了定义一个 InputRange 作为用户类型的目标；我们把它交给一个算法，去操作 InputRange 类型， 实际上 School 是 Phobos 或任何其他库中InputRange 类型随时可以使用的算法。下面的例子我们将看到。
The std.array module to use arrays as ranges
std.array 模块使用 range 数组
Merely importing the std.array module makes the most common container type conform to the most capable range type: arrays can seamlessly be used as RandomAccessRange objects.
仅仅导入 std.array 模块就可使得最常见的容器类型符合最有能力的 range ：数组可作为无缝的 RandomAccessRange 对象。
std.array defines empty, front, popFront() and other range functions specially for arrays. As a result, arrays are ready to be used with any range function, for example with print():
std.array 定义了 empty, front, popFront() ，和其他 range 函数专用的数组。因此，数组准备用于任何 range 函数， 一个 print() 例子：
import std.array;
// ...
print([ 1, 2, 3, 4 ]);
Note: It is not necessary to import std.array if the std.range module has already been imported.
注：它没必要导入 std.array 如果 std.range 模块已导入。
The reverse is not always true: although arrays can be used as ranges, not every range type can be used as an array. When necessary, all of the elements can be copied one by one into an array. std.array.array is a helper function to simplify this task; array() iterates over InputRange ranges, copies the elements, and returns a new array:
反向并非总是如此：虽然数组可以作为 ranges 使用，但不是每个 range 类型都可以作为数组使用。必要时，所有的元素可以被复制到一个数组，std.array.array是一个辅助函数，可以用来简化这一任务; array() 遍历 InputRange，复制元素，并返回一个新的数组：
import std.array;
// ...
auto copiesOfStudents = array(school);
writeln(copiesOfStudents);
The output: 输出：
[Ebru(1), Derya(2), Damla(3)]
Special feature of strings by the std.array module
std.array 模块字符串特殊功能
Being character arrays by definition, strings can also be used as ranges just by importing std.array. The two exceptions are, char and wchar strings cannot be used as RandomAccessRange.
字符数组的定义是，字符串也可以作为 range ，只需要导入 std.array。有两个例外是，char 和 wchar 字符串不能作为 RandomAccessRange 使用。
std.array provides a special functionality with all types of strings: iterating over strings becomes iterating over Unicode code points, not over UTF code units. As a result, strings appear as ranges of Unicode characters.
std.array提供了与所有现有字符串类型不同的特殊功能：字符串迭代变为迭代 Unicode 代码点[color=red]（？？？），不超过 UTF 编码单元（？？？）。因此，字符串以 Unicode 字符 range 出现。[/color]
The following strings contain ç and é, which cannot be represented by a single char and the gothic letter ahsa (
推荐阅读