时间间隔：即将到来的C ++演变

C ++ 20标准将很快出现，它可能会添加范围的概念，但是很少有人知道它们是什么以及一起吃什么。 我找不到关于这种野兽的通俗易懂的俄文资料，这就是为什么在本文中，我根据大会会议C ++ 2015-的一年。 对于那些首次遇到此概念的人，我将尽力使本文尽可能清晰，同时，对于那些已经熟悉此概念并想了解更多信息的人，我将谈论各种芯片，例如区间适配器。

范围库

在撰写本文时，有三个主要的实现间隔的库：

• 升压范围
• 范围v3
• 智库公共图书馆

实际上，第一个库就是这个概念的源头（这并不奇怪，因为Boost库的集合中什么都没有：）。 第二个是Eric Niebler的库，稍后将对其进行描述。 最后，您可能会猜到，最后一个库是由think-cell编写的，可以说是开发和改进了Boost.Range。

为什么间隔是我们的未来？

对于不熟悉间隔概念的人，我们将此非平凡的概念定义为具有开始和结束（一对迭代器 ）的概念。

现在让我们考虑以下任务：有一个向量，有必要从其中删除所有重复的元素。 在当前标准下，我们将这样解决：

std::vector<T> vec=...; std::sort( vec.begin(), vec.end() ); vec.erase( std::unique( vec.begin(), vec.end() ), vec.end() ); 

在这种情况下，我们将向量的名称最多指定6次！ 但是，使用间隔的概念（将向量的开始和结束处的迭代器组合到一个对象中），只需指定一次所需的向量，就可以编写很多次代码：

 tc::unique_inplace( tc::sort(vec) ); 

当前哪个间隔在当前标准之内？

在C ++ 11标准中，添加了基于范围的for循环和对容器的开始/结尾的通用访问，在最新的C ++ 17标准中，未添加与间隔有关的新内容。

 for ( int& i : <range_expression> ) { ... } 

 std::begin/end(<range_expression>) 

未来间隔

现在让我们来谈谈前面提到的Range V3库。 其创建者Eric Nibler在其家庭项目中创建了Range的技术规范 ，并修改了算法库以支持间隔。 看起来像这样：

 namespace ranges { template< typename Rng, typename What > decltype(auto) find( Rng && rng, What const& what ) { return std::find( ranges::begin(rng), ranges::end(rng), what ); } } 

在他的网站上有一些他想标准化的预览，这是Range V3 。

可以考虑什么范围？

首先， 容器 （向量，字符串，列表等），因为它们有一个开始和一个结束。 显然，容器具有它们自己的元素，也就是说，当我们引用容器时，我们将引用其所有元素。 同样，在复制和声明常量时（深度复制和一致性）。 其次， 视图也可以视为间隔。 视图只是分别指向起点和终点的一对迭代器。 这是他们最简单的实现：

 template<typename It> struct iterator_range { It m_itBegin; It m_itEnd; It begin() const { return m_itBegin; } It end() const { return m_itEnd; } }; 

而视图仅引用元素，因此复制和一致性是惰性的（这不会影响元素）。

间隔适配器

间隔的发明者并不仅限于此，因为否则该概念将毫无用处。 因此，他们引入了范围适配器之类的概念。

转换适配器

考虑以下任务：给出一个int向量，其中我们需要找到等于4的第一个元素：

 std::vector<int> v; auto it = ranges::find(v, 4); 

现在想象一下，向量的类型不是int，而是某种复杂的自写结构，但是其中有一个int，并且任务是相同的：

 struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find_if( v, [](A const& a) { return a.id == 4; } ); 

显然，这两个代码在语义上相似，但是在语法上却有很大不同，因为在后一种情况下，我们必须手动编写一个贯穿int字段的函数。 但是，如果您使用转换适配器（ transform adapter ），那么一切看起来都会更加简洁：

 struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4); 

实际上，转换适配器通过在int字段周围创建包装器类来“转换”我们的结构。 显然，指针指向id字段，但是如果我们希望它指向整个结构，则需要在末尾添加.base（） 。 此命令封装了该字段，因此指针可以在整个结构中运行：

 auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4).base(); 

这是转换适配器的示例实现（它由迭代器组成，每个迭代器都有自己的函子）：

 template<typename Base, typename Func> struct transform_range { struct iterator { private: Func m_func; //    decltype( tc::begin(std::declval<Base&>()) ) m_it; public: decltype(auto) operator*() const { return m_func(*m_it); } decltype(auto) base() const { return (m_it); } ... }; }; 

过滤器适配器

并且如果在最后一个任务中我们不需要查找第一个此类元素，而是“过滤” int的整个字段以查找此类元素的存在？ 在这种情况下，我们将使用过滤器适配器：

 tc::filter( v, [](A const& a) { return 4 == a.id; } ); 

请注意，过滤器在迭代过程中延迟执行。

这是他幼稚的实现（类似的东西在Boost.Range中实现）：

 template<typename Base, typename Func> struct filter_range { struct iterator { private: Func m_func; //     decltype( ranges::begin(std::declval<Base&>()) ) m_it; decltype( ranges::begin(std::declval<Base&>()) ) m_itEnd; public: iterator& operator++() { ++m_it; while( m_it != m_itEnd && !static_cast<bool>(m_func(*m_it)) ) ++m_it; return *this; } ... }; }; 

如我们所见，这里需要两个迭代器，而不是转换适配器中的一个。 为了避免在迭代过程中意外超出容器的边界，第二个迭代器是必需的。

一些优化

好的，但是从tc ::过滤器（tc ::过滤器（tc ::过滤器（...）））来看，迭代器是什么样的？

升压范围

作为上述实现的一部分，它看起来像这样：


显然，这是非常低效的。

范围v3

让我们考虑如何优化此适配器。 Eric Nibler的想法是在适配器对象中放入常规信息（仿函数和指向末尾的指针），然后我们可以存储指向该适配器对象和所需迭代器的链接
*m_rng
m_it

然后，在这种实现的框架中，三重过滤器将如下所示：


尽管有时比以前的实现要快，但这仍然不是完美的。

智库，索引概念

现在考虑think-cell解决方案。 他们引入了所谓的索引概念来解决这个问题。 索引就是这样一种迭代器，它执行与常规迭代器相同的所有操作，但是通过引用间隔来执行此操作。

 template<typename Base, typename Func> struct index_range { ... using Index = ...; Index begin_index() const; Index end_index() const; void increment_index( Index& idx ) const; void decrement_index( Index& idx ) const; reference dereference( Index& idx ) const; ... }; 

我们展示了如何将索引与常规迭代器结合在一起。

显然，常规迭代器也可以视为索引。 在相反的方向上，兼容性可以例如这样实现：

 template<typename IndexRng> struct iterator_for_index { IndexRng* m_rng; typename IndexRng::Index m_idx; iterator& operator++() { m_rng.increment_index(m_idx); return *this; } ... }; 

然后，将高效地实现三重过滤器：

 template<typename Base, typename Func> struct filter_range { Func m_func; Base& m_base; using Index = typename Base::Index; void increment_index( Index& idx ) const { do { m_base.increment_index(idx); } while ( idx != m_base.end_index() && !m_func(m_base.dereference_index(idx)) ); } }; 

 template<typename IndexRng> struct iterator_for_index { IndexRng* m_rng; typename IndexRng::Index m_idx; ... }; 

在这种实现的框架中，无论过滤器的深度如何，该算法都能快速工作。

具有左值和右值容器的间隔

现在，让我们看看区间如何与左值和右值容器一起工作：

左值

范围V3和思考单元的行为与左值相同。 假设我们有如下代码：

 auto rng = view::filter(vec, pred1); bool b = ranges::any_of(rng, pred2); 

在这里，我们有一个预先声明的向量位于内存（左值）中，我们需要创建一个间隔，然后以某种方式使用它。 我们使用view :: filter或tc :: filter创建一个视图，然后变得快乐，没有错误，然后可以在例如any_of中使用此视图。

范围V3和右值

但是，如果矢量还没有存储在内存中（例如，如果我们只是在创建它），并且我们将面临相同的任务，那么我们将尝试编写并面临错误：

 auto rng = view::filter(create_vector(), pred1); //   bool b = ranges::any_of(rng, pred2); 

为什么会出现？ 由于我们创建了一个向量并将其直接放入过滤器中，因此View将成为rvalue的悬挂链接，也就是说，过滤器中将存在一个rvalue链接，当编译器转到下一行并发生错误时，它将指向一个未知的东西。 为了解决此问题，Range V3提出了以下措施 ：

 auto rng = action::filter(create_vector(), pred1); //   bool b = ranges::any_of(rng, pred2); 

动作同时执行所有操作，也就是说，它只需要一个向量，按谓词过滤并将其放入一个间隔中。 但是，缺点是它不再是懒惰的，因此Think-cell试图解决此问题。

思维单元和右值

Think-cell做到了，因此创建了一个容器而不是视图：

 auto rng = tc::filter(creates_vector(), pred1); bool b = ranges::any_of(rng, pred2); 

结果，我们不会遇到类似的错误，因为在其实现中，过滤器会收集右值容器而不是链接，因此这种情况很懒惰。 Range V3不想这样做，因为他们担心由于过滤器以视图或容器的形式出现错误，但是think-cell确信程序员会理解过滤器的行为，并且大多数错误正是由于这种“懒惰”而产生的。

发电机间隔

我们概括了区间的概念。 实际上，存在没有迭代器的间隔。 它们称为发电机范围 。 假设我们有一个GUI小部件（一个界面元素），我们称之为移动小部件。 我们有一个窗口要求移动其窗口小部件，在列表框中还有一个按钮，另一个窗口也应在其窗口小部件之间滚动，即调用traverse_widgets ，它将元素连接到函子（ 您可以说有一个枚举函数，您可以在其中连接仿函数，该函数将列出它在仿函数中具有的所有元素 。

 template<typename Func> void traverse_widgets( Func func ) { if (window1) { window1->traverse_widgets(std::ref(func)); } func(button1); func(listbox1); if (window2) { window2->traverse_widgets(std::ref(func)); } } 

这在某种程度上让人联想到小部件间距，但是这里没有迭代器。 直接编写它们效率低下，最困难的是。 在这种情况下，可以说这样的结构也被视为间隔。 在这种情况下，可以使用一些有用的间隔方法，例如any_of ：

 mouse_hit_any_widget=tc::any_of( [] (auto func) { traverse_widgets(func); }, [] (auto const& widget) { return widget.mouse_hit(); } ); 

think-cell尝试实现方法，以使它们对于所有间隔都具有相同的接口：

 namespace tc { template< typename Rng > bool any_of( Rng const& rng ) { bool bResult = false; tc::enumerate( rng, [&](bool_context b) { bResult = bResult || b; } ); return bResult; } } 

使用tc :: enumerate可以隐藏时间间隔之间的差异，因为这种实现遵循内部迭代的概念（在本讲座中将更详细地描述外部 迭代和内部迭代的概念），但是这种实现有其缺点，即std :: any_of会在遇到true时 立即停止。 他们尝试通过添加例外（所谓的生成器间隔中断 ）来解决此问题。

结论

我讨厌基于范围的for循环，因为它会激励人们在需要和不需要的地方编写它，因为代码的简洁性通常会变差，例如，人们会这样写：

 bool b = false; for (int n : rng) { if ( is_prime(n) ) { b = true; break; } } 

相反：

 bool b = tc::any_of( rng, is_prime );