起底 C++ Range 令人惊讶的局限性！
IT服务圈儿
有温度、有态度的IT自媒体平台
作者注：今天我们收到了一个来自亚历克斯·阿斯塔辛(Alex Astashyn)的客座帖子。Alex是美国国家生物技术信息中心的RefSeq(Reference Sequence–标准序列)资源的技术负责人。
注：本文所表达的观点是该帖子作者的观点。而且，我自己也不能算是个“range专家”，所以有些与range有关的信息实际上可能是不正确的（如果你发现有任何严重错误，请在下面留下你的评论）。
在本文中，我将讨论我在C++ range上遇到的问题和局限性。
我还将介绍我自己开发的库rangeless，它将所有我希望由range实现的功能提炼在一起，使得我能够处理更大范围的有趣的实际应用用例。
01
序言
和所有爱好面向函数的声明式无状态编程的开发者一样，我原以为ranges非常有前途。然而，在实践中使用它们的尝试，被证明是一个非常令人沮丧的经历。
我一直在尝试用range写出那些对我来说似乎很合理的代码，然而，编译器却不断地打印出一页页让我无法理解的错误消息。最后我意识到了我自己的错误。我原以为range和这样的UNIX管道一样：cat file | grep ... | sed ... | sort | uniq -c | sort -nr | head -n10，但事实并非如此……
示例：
示例1：Intersperse(插入分隔符)
让我们尝试编写一个view，在输入元素之间插入一个分隔符。
（此功能由range-v3提供，因此我们可以比较一下这些方法的不同）
// inputs: [x1, x2, ... xn]
// transform: [[x1, d], [x2, d], ... [xn, d]]
// flatten: [ x1, d, x2, d, ... xn, d ]
// drop last: [ x1, d, x2, d, ... xn ]
auto intersperse_view =
view::transform([delim](auto inp)
{
return std::array<decltype(inp), 2>{{ std::move(inp), delim }};
})
| view::join // also called concat or flatten in functional languages
| view::drop_last(1); // drop trailing delim
transform | join上面 的合成是对流的一种常见操作，该操作将每个输入转换为一个输出序列，并对结果序列进行展平。
[x] -> (x -> [y]) -> [y]
有些语言对此有单独的抽象，例如Elixir语言中的flat_map或LINQ中的SelectMany。
基于最小惊呀的原则，看来上述办法应该奏效。（如果你还没看过这篇演讲，那说明我推荐的力度还不够）。
但是，上面的代码与range-v3一起无法编译通过。出什么事了？结果发现问题在于view::join不喜欢subrange（子范围 - 返回的集合）是一个作为右值（rvalue）返回的容器这一事实。我想出了以下的技巧：（有时）用这些视图（view）的右值组成视图，所以让我们将容器返回值包装为一个视图！
view::transform([delim](auto inp)
{
return view::generate_n([delim, inp, i = 0]() mutable
{
return (i++ == 0) ? inp : delim;
}, 2);
})
或者，概括地说，我们可以返回一个容器，例如向量，作为其他用例的视图：
view::transform([](int x)
{
auto vec = ... ;
return view::generate_n([i = 0, vec = std::move(vec)]() mutable
{
return std::move(vec[i++]);
}, vec.size());
})
| view::join // now join composes with transform
这是不是很聪明的做法？也许是吧，但是必须想出一些巧妙的技巧来做一些基本的事情，这并不是一个好兆头。
事实证明，我不是第一个遇到此问题的人。range库的实现者们提出了他们自己的变通方法。正如Eric Niebler在此处指出的那样，我的解决方案是“非法的”，因为通过在视图中捕获向量不再满足O（1）复制复杂性的要求。
也就是说，如果我们看看在view::generate或view::generate_n后台发生的事，我们就会看到它们缓存了最后一个生成的值，因此让view :: generate成生std :: string或std :: vector， 或一种包含这些类型的类型，你就已经不满足库的要求了。
这个例子我们讲完了吗？差不多了。
接下来，我们讲讲最后的两行代码：
| view::join
| view::drop_last(1);
你可能会认为drop_last在内部会将n个元素的队列保留在循环缓冲区中，并在最后一个输入到达时简单地将其丢弃。
然而，range-v3视图可能不会缓冲元素，因此view::drop_last必须在输入上施加SizedRange或ForwardRange 约束，而view::join返回一个InputRange（即使它接收到一个ForwardRange作为输入）。
这不仅扼杀了组合，也扼杀了任何延迟计算的希望（你必须立刻将整个InputRange（希望是有限的）转储到std::vector，然后将其转换为一个ForwardRange）。
那么，我们将如何实现这一点呢？我们稍后再谈……
示例 2:
下面是一个使用rangeless库实现的示例（这是Knuth-vs-McIlroy挑战的一个稍作修改的版本，使其更加有趣）。
namespace fn = rangeless::fn;
using fn::operators::operator%;
//
// Top-5 most frequent words from stream chosen among the words of the same length.
//
auto my_isalnum = [](const int ch)
{
return std::isalnum(ch) || ch == '_';
};
fn::from( // (1)
std::istreambuf_iterator<char>(std::cin.rdbuf()),
std::istreambuf_iterator<char>{ /* end */ })
% fn::transform([](const char ch) // (2)
{
return std::tolower(uint8_t(ch));
})
% fn::group_adjacent_by(my_isalnum) // (3)
// (4) build word->count map
% fn::foldl_d([&](std::map<std::string, size_t> out, const std::string& w)
{
if(my_isalnum(w.front())) {
++out[ w ];
}
return out; // NB: no copies of the map are made
// because it is passed back by move.
})
% fn::group_all_by([](const auto& kv) // (5) kv is (word, count)
{
return kv.first.size(); // by word-size
})
% fn::transform( // (6)
fn::take_top_n_by(5UL, fn::by::second{})) // by count
% fn::concat() // (7) Note: concat is called _join_ in range-v3
% fn::for_each([](const auto& kv)
{
std::cerr << kv.first << " " << kv.second << "
";
})
;
正如你所看到的，这段代码在风格上与ranges非常相似，但是其幕后工作方式完全不同（稍后我们将进行讨论）。
尝试使用range-v3重写此代码时，我们会遇到以下问题：
(3)处：这将不起作用，因为view::group_by需要一个ForwardRange或更强的约束。
(4)处：如何使用ranges进行可组合的左折叠（filter/map/reduce习惯用法的三大支柱之一）？ranges::accumulate是一个可能的候选对象，但它不是“pipeable”，而且也不符合移动语义（面向数字）。
(5)处：foldl_d返回一个满足ForwardRange要求的STD::MAP，但由于它是一个右值，因此不会与下游的group-by组合。Ranges中没有group_all_by，因此我们必须先将中间结果转储到左值（lvalue）中才能应用sort(排序)操作
(6和7)处：transform，concat：这与我们在“intersperse”示例中已经看到的问题相同，在那个示例中，range-v3无法展平右值（rvalue）容器序列。
示例3：Transform-in-parallel（并行转换）
下面的函数取自aln_filter.cpp示例。（顺便说一下，它展示了在适用的用例中数据流延时操作的有用性）。
lazy_transform_in_parallel的目的是执行与普通transform相同的工作，不同之处在于，每次对transform函数的调用都与不超过指定数量的同时异步任务并行执行。（与c ++ 17的并行化std：：transform不同的是，我们希望它可以和延时的InputRange一起工作。）
static auto lazy_transform_in_parallel = [](auto fn,
size_t max_queue_size = std::thread::hardware_concurrency())
{
namespace fn = rangeless::fn;
using fn::operators::operator%;
assert(max_queue_size >= 1);
return [max_queue_size, fn](auto inputs) // inputs can be an lazy InputRange
{
return std::move(inputs)
//-------------------------------------------------------------------
// Lazily yield std::async invocations of fn.
% fn::transform([fn](auto inp)
{
return std::async(std::launch::async,
[inp = std::move(inp), fn]() mutable // mutable because inp will be moved-from
{
return fn(std::move(inp));
});
})
//-------------------------------------------------------------------
// Cap the incoming sequence of tasks with a seq of _max_queue_size_-1
// dummy future<...>'s, such that all real tasks make it
// from the other end of the sliding-window in the next stage.
% fn::append(fn::seq([i = 1UL, max_queue_size]() mutable
{
using fn_out_t = decltype(fn(std::move(*inputs.begin())));
return i++ < max_queue_size ? std::future<fn_out_t>() : fn::end_seq();
}))
//-------------------------------------------------------------------
// Buffer executing async-tasks in a fixed-sized sliding window;
// yield the result from the oldest (front) std::future.
% fn::sliding_window(max_queue_size)
% fn::transform([](auto view) // sliding_window yields a view into its queue
{
return view.begin()->get();
});
};
};
有人会认为这包含了所有可以用ranges实现的部分，但事实并非如此。明显的问题是view::sliding需要一个ForwardRange。即使我们决定实现sliding的一个“非法”的缓存版本，仍有更多问题在代码中不可见，但会在运行时显现：
在range-v3中，view::transform的正确用法取决于以下假设：
重新计算很便宜（这一点对在上例中的第一个transform中并不适用，因为它逐个接受和传递input输入，并启动一个异步任务）。
可以在同一个input上多次调用它（这对于第二个transform不起作用，因为对std::future::get的调用使它处于无效状态，因此只能被调用一次）。
如果transform函数类似于“加一”或“对一个整数取平方”，那么上面的这些假设可能很正确，但是如果transform函数需要查询数据库或生成一个进程以运行一个繁重的任务，那么这些假设会有点自以为是了。
这个问题和乔纳森（Jonathan）在“增加一个智能迭代器的可怕问题”中描述的问题如出一辙。
这种行为不是一个bug，显然是设计使然–这是我们无法很好地使用range-v3的另一个原因。
在rangeless中，fn::transform既不会对同一input上多次调用transform函数，也不会缓存结果。
注：rangeless库中提供了transform_in_parallel。我们可以比较使用rangless(Ctrl+F pigz)和使用RaftLib对并行gzip压缩器的实现的不同。
上面这一切的结论是什么呢？
02
Ranges的复杂性
我们需要一种合理一致的语言，可以被“普通程序员”使用，他们的主要关注点是准时交付优秀的应用程序。
Ranges简化了基本用例的代码，比如说，你可以编写action::sort(vec)来代替std::sort(vec.begin(), vec.end())。然而，除了最基本的用法以外，它会导致代码的复杂度呈指数级增长。
举个例子，如何实现上述的intersperse适配器？
让我们先看看Haskell语言写的的示例，看看我们心目中的“简单”应该是什么样子的。
intersperse :: a -> [ a ] -> [ a ]
intersperse _ [ ] = [ ]
intersperse _ [ x ] = [ x ]
intersperse delim (x:xs) = x : delim : intersperse delim xs
即使你一生中从未见过Haskell代码，你也可能知道上面的代码是如何工作的。
下面是使用rangeless来完成它的三种不同的方法。就像Haskell的签名一样，my_intersperse接受delim作为参数并返回一个一元可调用函数，该函数可以接受Iterable参数并返回一个产生元素的序列 - interspersing delim。
作为一个generator函数使用：auto my_intersperse = [](auto delim)
{
return [delim = std::move(delim)](auto inputs)
{
return fn::seq([ delim,
inputs = std::move(inputs),
it = inputs.end(),
started = false,
flag = false]() mutable
{
if(!started) {
started = true;
it = inputs.begin();
}
return it == inputs.end() ? fn::end_seq()
: (flag = !flag) ? std::move(*it++)
: delim;
});
};
};
通过使用rangeless中的fn::adapt这个用来实现自定义适配器的工具:
auto my_intersperse = [](auto delim)
{
return fn::adapt([delim, flag = false](auto gen) mutable
{
return !gen ? fn::end_seq()
: (flag = !flag) ? gen()
: delim;
});
};
作为现有功能的组成部分（我们尝试用range-views实现但未能实现的功能）：
auto my_intersperse = [](auto delim)
{
return [delim = std::move(delim)](auto inputs)
{
return std::move(inputs)
% fn::transform([delim](auto inp)
{
return std::array<decltype(inp), 2>{{ std::move(inp), delim }};
})
% fn::concat()
% fn::drop_last(); // drop trailing delim
};
};
我们也可以将intersperse作为一个协程（coroutine）来实现，而无需借助于rangeless::fn。
template<typename Xs, typename Delim>
static unique_generator<Delim> intersperse_gen(Xs xs, Delim delim)
{
bool started = false;
for (auto&& x : xs) {
if(!started) {
started = true;
} else {
co_yield delim;
}
co_yield std::move(x);
}
};
auto my_intersperse = [](auto delim)
{
return [delim](auto inps)
{
return intersperse_gen(std::move(inps), delim);
};
};
上述所有的实现在代码复杂度方面都差不多。现在让我们看看range-v3实现的样子：intersperse.hpp。就我个人而言，这看起来非常复杂。如果你对它的复杂度印象还不够深刻的话，考虑一下作为一个协程来实现笛卡尔乘积的情形：
template<typename Xs, typename Ys>
auto cartesian_product_gen(Xs xs, Ys ys)
-> unique_generator<std::pair<typename Xs::value_type,
typename Ys::value_type>>
{
for(const auto& x : xs)
for(const auto& y : ys)
co_yield std::make_pair(x, y);
}
我们把以上实现与range-v3的实现作一番比较。
用range-v3编写视图应该很容易，但是，正如示例所示，在后现代C++中被认为“容易”的标准已经提高到了普通人无法企及的高度。
应用程序代码中涉及range的情况并不简单。
如果我们比较一下日历格式化应用程序的Haskell，Rust，rangeless和range-v3的实现。我不知道你的情况如何，但最后一个实现（使用range-v3）并没有激发我去理解或编写这样的代码的热情。
注意，在range-v3的示例中，，开发者通过一个std::vector字段打破了在interleave_view本身的视图复制复杂度要求。
03
Range views的抽象泄漏
如果你回到上面基于range-v3库的intersperse和日历应用程序，并对其进行更详细的研究，你就会看到在视图的实现中，我们最终都是直接处理迭代器，实际上需要做非常多的事情。
除了在一个range上调用sort之外或某些类似的操作外，ranges并不能避免让你直接处理迭代器。相反，它是“以额外的步骤处理迭代器”。
04
编译时间开销
Range-v3库因其编译时间而臭名昭著。在我的机器上，上述日历示例的编译时间超过20秒，而相应的rangeless实现的编译可以2.4秒内完成，其中1.8秒是为了include<gregorian.hpp>，这几乎相差了整整一个数量级！
编译时间已经变成了C++开发中每天面临的一个大问题，而range让它变得更糟！以我个人的情况为例，仅仅编译时间这一项就排除了在生产代码中使用range的任何可能性。
05
Rangeless库
对于rangeless库，我没有想要浪费时间做无用功，而是遵循函数式编程语言中的streaming库（如Haskell的Data.List，Elixir的Stream，F#的 Seq，以及和LINQ）的设计。
与range-v3库不同，rangeless库没有ranges、views或actions，只是通过一个一元可调用函数链将值从一个函数传递到下一个函数，其中的一个值是容器或序列（输入范围，有界或无界）。
有一点语法上的甜头：
operator % (Arg arg, Fn fn) -> decltype(fn(std::forward<Arg>(arg)))
auto x1 = std::move(arg) % f % g % h; // same as auto x1 = h(g(f(std::move(arg))));
这相当于Haskell语言中的中缀运算符“&” 或F#语言中的“|>”运算符>in f。它允许我们以与数据流方向基本上一致的方式构造代码。这种方式对于一个单行的函数并没有什么影响，但是对于那些就地定义的多行lambda函数，就会很有帮助。
你可能想知道，为什么这里明确地使用“operator%”，而不用“>>”或者“？”操作符呢？
C++的可重载二进制运算符的列表并不长，前者往往由于流和管道运算符而大量地重载，通常用在有“smart”-flag 或“chaining”(也称为point-free composition)的地方，和在range中一样。
我考虑过使用可重载的运算符“operator->*”，但最终还是决定使用运算符“operator%”，因为考虑到上下文，它不太可能与整数取模运算混淆，而且还具有可以用于更改LHS（运算符左边的操作数）状态的“%=”对应项，例如：
vec %= fn::where(.../*satisfies-condition-lambda*/);
这里的输入要么是一个序列，要么是一个容器，输出也是一样。例如，fn::sort需要所有元素来完成它的工作，所以它会将整个输入序列转储到std::vector中，对其进行排序，然后返回std::vector。
另一方面，一个fn::transform将按值获取的输入封装为一个序列，它将惰性地生成转换后的输入元素。从概念上讲，这类似于一个带有eager sort和lazy sed的UNIX管道。
与range-v3中不同的是，input-ranges（序列）在rangeless中是一等公民。我们在range-v3中看到的由于实参(argument)和形参(parameter)之间概念不匹配而导致的问题是不存在的（例如，在期望有ForwardRange的地方，但却收到了InputRange这样的问题）。只要值类型兼容，一切都是可组合的。
06
束语
我尝试过用ranges来编写表达性的代码。我是唯一那个经常“错误地使用它”的人吗？
当我得知委员会在C++20标准中接纳了range时，我相当惊讶，大多数C++专家对此都很兴奋。看起来好象上面提到的这些问题（有局限的可用性、代码复杂性、漏洞百出的抽象和完全不合理的编译时间）对委员会成员没有任何影响一样。
我觉得这一点严重背离了率先开发这门语言的C++专家和那些想用更简单的方法来做复杂事情的普通程序员的初衷。在我看来，似乎所有人都对C++之父（Bjarne Stroustrup）在Remember the Vasa的发出的呼吁充耳不闻（当然，这是我个人的主观看法）。
原文：https://www.fluentcpp.com/2019/09/13/the-surprising-limitations-of-c-ranges-beyond-trivial-use-cases/本文为 CSDN 翻译，转载请注明来源出处。*版权声明：转载文章和图片均来自公开网络，版权归作者本人所有，推送文章除非无法确认，我们都会注明作者和来源。如果出处有误或侵犯到原作者权益，请与我们联系删除或授权事宜。