18

这是一个 C++/D 交叉问题。D 编程语言的范围——与 Boost.Range 等 C++ 库相比——不是基于迭代器对。官方的C++ Ranges Study Group似乎陷入了制定技术规范的困境。

问题：当前的 C++11 或即将发布的 C++14 标准是否有阻碍采用 D 范围以及适当范围版本的<algorithm>批发的任何障碍？

我不太了解 D 或其范围，但它们看起来很懒惰且可组合，并且能够提供 STL 算法的超集。鉴于他们声称 D 取得了成功，将其作为 C++ 库似乎非常好。我想知道 D 的独特功能（例如字符串混合、统一的函数调用语法）对于实现其范围是多么重要，以及 C++ 是否可以不费力气地模仿它（例如 C++14constexpr似乎与 D 编译时函数评估非常相似）

注意：我正在寻求技术答案，而不是意见 D 范围是否是作为 C++ 库的正确设计。

4

2 回答 2

9

我不认为 C++ 中存在任何固有的技术限制，这将导致无法在 C++ 中定义 D 风格范围和相应算法的系统。最大的语言级别问题是 C++ 基于范围的for循环需要begin()并且end()可以在范围上使用，但假设我们将使用 D 样式范围定义库的长度，扩展基于范围的for循环来处理它们似乎是边际变化。

我在 C++ 中对 D 样式范围的算法进行试验时遇到的主要技术问题是，我无法使算法与基于迭代器（实际上是光标）的实现一样快。当然，这可能只是我的算法实现，但我还没有看到任何人在 C++ 中提供了一套合理的基于 D 风格范围的算法，我可以对其进行分析。性能很重要，C++ 标准库至少应提供算法的弱效实现（算法的通用实现称为弱效如果它在应用于数据结构时至少与使用相同数据结构使用相同编程语言的相同算法的自定义实现一样快）。我无法创建基于 D 风格范围的弱效算法，而我的目标实际上是强效算法（类似于弱效算法，但允许任何编程语言，并且只假设相同的底层硬件）。

在试验基于 D 风格范围的算法时，我发现这些算法比基于迭代器的算法更难实现，并且发现有必要处理 kludges 以解决它们的一些限制。当然，目前在 C++ 中指定算法的方式也不是所有东西都是完美的。关于我想如何更改算法和它们使用的抽象的粗略概述在May STL 2.0页面上。然而，这个页面并没有真正涉及范围，因为这是一个相关但有些不同的主题。我宁愿设想基于迭代器（好吧，真的是光标）的范围而不是 D 样式范围，但问题不在于那个。

C++ 中所有范围抽象都面临的一个技术问题是必须以合理的方式处理临时对象。例如，考虑这个表达式：

auto result = ranges::unique(ranges::sort(std::vector<int>{ read_integers() }));

根据是否ranges::sort()懒惰ranges::unique()，需要处理临时范围的表示。仅仅提供源范围的视图对于这两种算法都不是一种选择，因为临时对象将在表达式结束时消失。一种可能性是移动范围，如果它以 r 值的形式出现，则两者都需要不同的结果，ranges::sort()并ranges::unique()区分实际参数是临时对象还是独立保持活动的对象的情况。D 没有这个特殊问题，因为它是垃圾收集的，因此在任何一种情况下，源范围都将保持活动状态。

上面的示例还显示了可能是惰性求值算法的问题之一：由于任何类型，包括无法以其他方式拼出的类型，都可以通过auto变量或模板函数推导出来，因此在末尾没有强制惰性求值的情况一种表达。因此，可以从表达式模板中获得结果，而算法并没有真正执行。也就是说，如果将左值传递给算法，则需要确保表达式实际被评估以获得实际效果。例如，任何sort()对整个序列进行突变的算法显然会就地进行突变（如果您想要一个版本不就地进行，只需复制容器并应用就地版本；如果您只有一个非就地版本，则无法避免额外的序列，这可能是一个直接的问题，例如，对于巨大的序列）。假设它在某种程度上是惰性的，对原始序列的左值访问提供了当前状态的峰值，这几乎可以肯定是一件坏事。这可能意味着对变异算法的惰性评估无论如何都不是一个好主意。

在任何情况下，C++ 的某些方面使得无法立即采用 D 样式范围，尽管同样的考虑也适用于其他范围抽象。因此，我认为这些考虑因素也有点超出了这个问题的范围。此外，第一个问题（添加垃圾收集）的明显“解决方案”不太可能发生。我不知道 D 中的第二个问题是否有解决方案。可能会出现第二个问题的解决方案（暂时称为operator auto），但我不知道具体的建议或这样的功能实际上看起来如何喜欢。

顺便说一句，Ranges Study Group 并没有真正陷入任何技术细节的困境。到目前为止，我们只是试图找出我们真正想要解决的问题，并在某种程度上确定解决方案的空间。此外，小组通常根本不会完成任何工作！实际工作总是由个人完成，通常由极少数个人完成。由于工作的主要部分实际上是设计一组抽象，我希望 Ranges Study Group 的任何结果的基础都是由 1 到 3 个人完成的，他们对需要什么以及它应该是什么样子有一定的了解。

于 2013-08-31T22:38:13.477 回答
8

我的 C++11 知识比我希望的要有限得多，所以可能有更新的功能可以改进我还不知道的事情，但目前我可以想到三个方面这至少是有问题的：模板约束static if，和类型自省。

在 D 中，基于范围的函数通常会有一个模板约束，指示它接受哪种类型的范围（例如，前向范围与随机访问范围）。例如，这是一个简化的签名std.algorithm.sort：

auto sort(alias less = "a < b", Range)(Range r)
    if(isRandomAccessRange!Range &&
       hasSlicing!Range &&
       hasLength!Range)
{...}

它检查传入的类型是否是随机访问范围，是否可以切片，是否具有length属性。任何不满足这些要求的类型都不会使用 进行编译sort，并且当模板约束失败时，程序员会清楚为什么他们的类型无法使用sort（而不是仅仅从中间给出一个讨厌的编译器错误）当使用给定类型编译失败时的模板化函数）。

现在，虽然这似乎只是在sort因为类型没有正确的操作而导致编译失败时给出编译错误的可用性改进，但它实际上对函数重载和类型自省有很大影响。例如，这里有两个std.algorithm.find's 重载：

R find(alias pred = "a == b", R, E)(R haystack, E needle)
    if(isInputRange!R &&
       is(typeof(binaryFun!pred(haystack.front, needle)) : bool))
{...}


R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
    if(isForwardRange!R1 && isForwardRange!R2 &&
       is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool) &&
       !isRandomAccessRange!R1)
{...}

第一个接受只有一个元素的指针，而第二个接受一个向前范围的指针。两者可以完全基于模板约束具有不同的参数类型，并且可以在内部具有截然不同的代码。如果没有模板约束之类的东西，您就不能拥有在其参数的属性上重载的模板化函数（而不是在特定类型本身上重载），这使得基于不同的实现变得更加困难（如果不是不可能的话）正在使用的范围类型（​​例如输入范围与前向范围）或正在使用的类型的其他属性。一些工作已经在 C++ 中用概念和类似的想法在这个领域完成了，但是 AFAIK，

一个相关的功能是static if. 它与 相同if，只是它的条件是在编译时评估的，以及它是否会true或false将实际确定编译哪个分支而不是运行哪个分支。它允许您根据编译时已知的条件分支代码。例如

static if(isDynamicArray!T)
{}
else
{}

或者

static if(isRandomAccessRange!Range)
{}
else static if(isBidirectionalRange!Range)
{}
else static if(isForwardRange!Range)
{}
else static if(isInputRange!Range)
{}
else
    static assert(0, Range.stringof ~ " is not a valid range!");

static if可以在某种程度上消除对模板约束的需要，因为您基本上可以将模板化函数的重载放在单个函数中。例如

R find(alias pred = "a == b", R, E)(R haystack, E needle)
{
    static if(isInputRange!R &&
       is(typeof(binaryFun!pred(haystack.front, needle)) : bool))
    {...}
    else static if(isForwardRange!R1 && isForwardRange!R2 &&
       is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool) &&
       !isRandomAccessRange!R1)
    {...}
}

但是当编译失败并且实际上使您无法重载模板（至少在 D 的实现中）时，这仍然会导致更严重的错误，因为重载是在模板实例化之前确定的。因此，您可以使用static if专门化模板实现的各个部分，但它并不能完全让您了解哪些模板约束让您不需要模板约束（或类似的东西）。

相反，static if它非常适合做一些事情，比如只专门化你的函数实现的一部分，或者使它成为一个范围类型可以正确地继承它所包装的范围类型的属性。例如，如果你调用std.algorithm.map一个整数数组，结果范围可以有切片（因为源范围有），而如果你调用map一个没有切片的范围（例如返回的范围std.algorithm.filter不能有切片)，那么生成的范围不会有切片。为了做到这一点，仅在源范围支持时才map使用static if编译。opSlice目前，map执行此操作的代码看起来像

static if (hasSlicing!R)
{
    static if (is(typeof(_input[ulong.max .. ulong.max])))
        private alias opSlice_t = ulong;
    else
        private alias opSlice_t = uint;

    static if (hasLength!R)
    {
        auto opSlice(opSlice_t low, opSlice_t high)
        {
            return typeof(this)(_input[low .. high]);
        }
    }
    else static if (is(typeof(_input[opSlice_t.max .. $])))
    {
        struct DollarToken{}
        enum opDollar = DollarToken.init;
        auto opSlice(opSlice_t low, DollarToken)
        {
            return typeof(this)(_input[low .. $]);
        }

        auto opSlice(opSlice_t low, opSlice_t high)
        {
            return this[low .. $].take(high - low);
        }
    }
}

这是返回类型的类型定义中的代码，map该代码是否编译完全取决于static ifs 的结果，没有一个可以替换为基于特定类型的模板特化，而无需编写新的为您使用的每种新类型提供专门的模板map（这显然是站不住脚的）。为了根据类型的属性而不是特定类型在代码中编译，您确实需要类似的东西static if（C++ 目前没有）。

C++ 缺少的第三个主要项目（我在整个过程中或多或少地谈到过）是类型内省。您可以做类似is(typeof(binaryFun!pred(haystack.front, needle)) : bool)或isForwardRange!Range的事情这一事实至关重要。如果无法检查特定类型是否具有特定属性集或特定代码段是否编译，您甚至无法编写模板约束和static if使用的条件。例如，std.range.isInputRange看起来像这样

template isInputRange(R)
{
    enum bool isInputRange = is(typeof(
    {
        R r = void;       // can define a range object
        if (r.empty) {}   // can test for empty
        r.popFront();     // can invoke popFront()
        auto h = r.front; // can get the front of the range
    }));
}

它检查一段特定的代码是否为给定的类型编译。如果是这样，那么该类型可以用作输入范围。如果没有，那么它不能。AFAIK，在 C++ 中甚至不可能像这样模糊地做任何事情。但是要明智地实现范围，您确实需要能够执行诸如 haveisInputRange或测试特定类型是否使用sort-编译之类的事情is(typeof(sort(myRange)))。否则，您将无法根据特定范围支持的操作类型来专门实现，在包装范围时无法正确转发范围的属性（范围函数始终将其参数包装在新范围中），并且你甚至不能正确地保护你的函数不被不适用的类型编译。当然，结果static if和模板约束也会影响类型自省（因为它们会影响将编译和不会编译的内容），因此这三个功能非常相互关联。

确实，范围在 C++ 中不能很好地工作的主要原因是C++ 中的元编程与 D 中的元编程相比是原始的。AFAIK，没有理由不能将这些特性（或类似特性）添加到 C++ 并解决问题，但在 C++ 具有类似于 D 的元编程能力之前，C++ 中的范围将受到严重损害。

mixin 和统一函数调用语法等其他特性也会有所帮助，但它们远不是基本的。Mixins 主要有助于减少代码重复，而 UFCS 主要有助于实现它，以便通用代码可以像调用成员函数一样调用所有函数，这样如果一个类型恰好定义了一个特定函数（例如find），那么它将被使用而不是更一般的自由函数版本（如果没有声明这样的成员函数，代码仍然可以工作，因为那时使用了自由函数）。UFCS 从根本上不是必需的，您甚至可以反其道而行之，为所有事物提供自由函数（就像 C++11 对begin和end)，尽管要做到这一点，它本质上要求自由函数能够测试成员函数的存在，然后在内部调用成员函数，而不是使用它们自己的实现。因此，您再次需要类型自省以及static if和/或模板约束。

尽管我很喜欢范围，但在这一点上，我几乎已经放弃了尝试在 C++ 中对它们做任何事情，因为使它们变得理智的功能不存在。但是，如果其他人能够弄清楚如何做到这一点，那么他们的权力就更大了。不管范围如何，我希望看到 C++ 获得诸如模板约束、static if类型自省等功能，因为没有它们，元编程就不那么令人愉快了，以至于虽然我一直在 D 中这样做，但我几乎永远不要在 C++ 中这样做。

于 2013-08-31T21:04:06.620 回答