std.algorithm.find 是否需要引用范围元素？

Question

我一直在研究基于 class 的有限随机访问范围。对其进行一些测试时：

auto myRange = /* construct my range */
static assert (isRandomAccessRange!(typeof(myRange))); // 
static assert (!isInfinite!(typeof(myRange)));         // both pass 
auto preamble = myRange[0..128];
assert( all!"a == 0"(preamble)); // check for all zeros

我在 GDC 4.9.2 中遇到了这个编译错误，关于上面代码片段的最后一行："algorithm.d|4838|error: foreach: cannot make e ref"

错误指向 std.algorithm.find 中的这段代码（find_if 变体，采用范围和谓词），它确实引用了 foreach 中的每个元素:

InputRange find(alias pred, InputRange)(InputRange haystack)
if (isInputRange!InputRange)
{
    alias R = InputRange;
    alias predFun = unaryFun!pred;
    static if (isNarrowString!R)
    {
        ...
    }
    else static if (!isInfinite!R && hasSlicing!R && is(typeof(haystack[cast(size_t)0 .. $])))
    {
        size_t i = 0;
        foreach (ref e; haystack) // <-- needs a ref
        {
            if (predFun(e))
                return haystack[i .. $];
            ++i;
        }
        return haystack[$ .. $];
    }
    else
    {
       ...
    }
}

这很可能发生，因为我提供了一个 opApply 的实现，它没有提供 ref 参数（class 也没有提供 ref return 键入任何其他成员函数）。

int opApply(int delegate(E) f) {...}
int opApply(int delegate(size_t,E) f) {...}

我可以改变它，但真正困扰我的是现在范围 class 符合函数的先决条件，并且 foreach 迭代仍然应该与它们一起工作。引用文档：

Iteration over struct and class objects can be done with ranges. For foreach, this means the following properties and methods must be defined:

Properties:

.empty returns true if no more elements

.front return the leftmost element of the range

Methods:

.popFront() move the left edge of the range right by one

这些都提供了（不然就不是随机访问范围了），应该用吧。相反，它可能正在寻找下面描述的替代迭代方法：

If the aggregate expression is a struct or class object, and the range properties do not exist, then the foreach is defined by the special opApply member function and the foreach_reverse behavior is defined by the special opApplyReverse member function. These functions have the type:

int opApply(int delegate(ref Type [, ...]) dg);

根据我的解释，不应该寻找哪个。

也引用 std.algorithm.all，它似乎也不需要迭代引用：

bool all(Range)(Range range) if (isInputRange!Range && is(typeof(unaryFun!pred(range.front))));

Returns true if and only if all values v found in the input range range satisfy the predicate pred. Performs (at most) Ο(range.length) evaluations of pred.

那么这是 Phobos 库中的错误，std.algorithm.find 应该首先按值进行迭代吗？或者我错过了什么？

Answer 1

在应该是一个范围的对象上声明 opApply 甚至没有意义，因为如果它是一个范围，那么基于范围的函数将用于 foreach ，而不是 opApply。当然，如果在范围类型而不是 front、popFront 和 empty 上调用 opApply，那么这是一个编译器错误。从它的声音来看，编译器错误地选择了 opApply，因为 opApply 使用了 ref，而 front 没有。但是，front 在没有 ref 的情况下工作得很好，只要 opApply 未声明，foreach 使用 ref。因此，ref 并不是一个问题，因为编译器在看到 opApply 有 ref 而 front 没有时错误地使用了 opApply 't.

因此，需要修复编译器，但这可能以前从未被发现，因为像您所做的那样在范围类型上声明 opApply 是没有意义的。因此，我认为您的代码需要更改为不在范围类型上声明 opApply 。那么你甚至不会遇到这个特定的错误。

也就是说，Phobos 中有问题的代码是 引用类型范围（如类）的错误，因为它无法调用 save 在 haystack 上迭代时。其结果是原始范围发生变异以指代正在搜索的位置，而返回的内容指向与元素从大海捞针的前面一样远的正确位置。因此，即使您停止声明 opApply and/or 编译器错误得到修复，如果您使用范围的引用类型，std.algorithm.find 也需要修复才能让您的代码开始工作.

编辑：

好的。这不太对。我在与一些编译器开发人员讨论它时得到了纠正。过去，范围函数比 opApply 更受青睐，这就是规范所说的，但在某些时候，它被更改为 opApply 比范围函数更受青睐，因此范围类型可以使用 opApply 和 foreach 进行迭代，如果这对它更有效的话（尽管这显然引入了范围函数的风险并且 opApply 没有相同的行为，这可能会导致一些真的讨厌的错误）。因此，该规范与编译器的当前行为不匹配，它应该可以让您在范围类型上声明 opApply （尽管我仍然建议不要这样做除非你从中获得了明确的性能提升。

话虽如此，您在此处遇到的错误仍然是编译器错误。由于您的 opApply 不使用 ref，因此它不适用于 ref 循环变量，而范围函数可以，因此在这种情况下编译器应该调用范围函数，显然不是。无论哪种方式，以前都没有发现，因为几乎没有人在范围上使用 opApply，因为这样做的唯一原因是这样做是否有性能提升，而且我确信事实是规范仍然说范围函数优于 opApply 使得尝试它的人比其他情况下更少。

std.algorithm.find 是否需要引用范围元素？

Should std.algorithm.find demand a reference to range elements?

d

phobos