1. 首页
  2. 未分类

起底 C++ Range 令人惊讶的局限性

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

原文始发于:起底 C++ Range 令人惊讶的局限性

主题测试文章,只做测试使用。发布者:杀手梦三刀,转转请注明出处:http://www.cxybcw.com/14658.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code