Range-v3 库入门
5.00/5 (4投票s)
Ranges 即将登陆 C++，而 Range-v3 库是为 C++ 标准库添加 Range 支持的提案的基础。
引言
Ranges 是对标准库的重要补充，它有可能真正改变我们在 C++ 中处理数据的方式。
range-v3 库 (https://github.com/ericniebler/range-v3) 主要由 Eric Niebler 编写，它是为 C++ 标准库添加 Range 支持的提案的基础。该库建立在标准模板库提供的迭代器和算法之上，并使它们能够组合使用——这可以说是一件大事。
将 Range 视为一对迭代器是有用的，基本上就是提供 begin() 和 end() 函数的东西。Ranges 根据其迭代器的能力进行分类：我们可以从输入 Range 读取，向输出 Range 写入，或者两者兼而有之，具体取决于迭代器的能力。
将两个迭代器组合在一起的关键好处是，我们可以将一个完整的 Range 作为函数的结果返回，并直接将其传递给另一个函数，而无需创建局部变量来保存临时结果。
视图、操作和算法
算法、视图和操作是 range-v3 库的三大支柱。
算法与标准模板库提供的算法相同，并增加了接受 Ranges 的重载。
视图是对 Range 的可组合适应，它在迭代视图时被惰性求值，在本文中我将尝试解释这实际意味着什么。
操作是对容器的即时应用，它会就地更改容器的内容并返回容器以进行进一步处理。
在查看 Ranges 之前，我们需要一些简单易用的东西
enum class Category { First, Second, Third };
struct A
{
Category category;
int value;
constexpr A( int v ) noexcept
: category( static_cast<Category>(v%3) ),
value( v )
{ }
constexpr int Value( ) const noexcept
{
return value;
}
};
const char* to_string( Category category )
{
return category == Category::First ?
"First" : category == Category::Second ? "Second" : "Third";
}
std::ostream& operator << ( std::ostream& stream, const A& a )
{
stream << to_string( a.category ) << ' ' << a.value << ' ';
return stream;
}
最后，是一些使用 range-v3 的代码
using namespace ranges;
void Example001a()
{
auto items = views::iota( 0, 6 )
| views::transform( []( int i ) { return A( i ); } )
| to<std::vector>( )
| actions::sort( less{}, &A::category );
// output: [First 0 ,First 3 ,Second 1 ,Second 4 ,Third 2 ,Third 5 ]
std::cout << views::all( items ) << std::endl;
}
很简单，但它说明了 Ranges 的一些主要好处。
便捷性
没有 Ranges，上述内容可以这样实现：
void Example001a_( )
{
std::vector<int> ints( 6 );
std::iota( ints.begin( ), ints.end( ), 0 );
std::vector<A> items;
std::transform( ints.begin( ), ints.end( ),
std::back_inserter( items ),
[]( auto i ) { return A( i ); } );
std::sort( items.begin( ), items.end( ),
[]( auto& first, auto& second )
{ return first.category < second.category; } );
bool isFirst = true;
std::for_each( items.begin( ), items.end( ), [&isFirst]( auto& item )
{
std::cout << (isFirst ? '[' : ',');
std::cout << item;
isFirst = false;
} );
std::cout << ']' << std::endl;
}
这需要更多的工作，而且由于传递迭代器造成的混乱，可读性稍差。
可组合性
Ranges 库通过允许我们使用“|”运算符将一系列操作链接在一起，从而促进了可组合性。
auto items = views::iota( 0, 6 )
| views::transform( []( int i ) { return A( i ); } )
| to<std::vector>( )
| actions::sort( less{}, &A::category );
这被称为管道，在我们这个小程序示例中，‘items’ 是通过一个包含四个步骤的管道创建的。
views::iota( 0, 6 )是一个有界值工厂，生产范围 [0,6) 中的值。views::transform( []( int i ) { return A( i ); } )使用第一个步骤的输出创建A对象。to<std::vector>( )创建一个 vector，这是管道最后一步所必需的，因为操作会就地更改容器的内容。actions::sort( less{}, &A::category )根据A的category成员对 vector 进行排序。
最后一步还演示了 Ranges 库的另一项功能，称为投影，它允许我们指定 ranges::less 应该操作哪个成员，从而无需实现谓词或 A 上的自定义比较函数——相比之下，这相当不灵活。
灵活性
Ranges 库与熟悉的基于迭代器的 STL 库一样灵活，易于与 POC 数据类型集成。
void Example001b( )
{
int values[] = {0,1,2,3,4,5};
auto items = values
| views::transform( []( int i ) { return A( i ); } )
| to<std::vector>( )
| actions::sort( less{}, &A::category );
std::cout << views::all( items ) << std::endl;
}
或
void Example001c( )
{
int ints[] = { 0,1,2,3,4,5 };
int* first = std::begin(ints);
int* last = std::end( ints );
auto items = span( first, last )
| views::transform( []( int i ) { return A( i ); } )
| to<std::vector>( )
| actions::sort( less{}, &A::category );
std::cout << views::all( items ) << std::endl;
}
容器
所有具有符合 STL 标准的 begin() 和 end() 实现的容器都是有效的 Ranges，因此您很可能已经有很多代码可以与 Ranges 一起使用了。
视图
视图是通常操作由其他 Ranges 提供的数据的 Ranges，根据一些视图特定的算法转换数据。视图不应拥有除实现其算法所需的数据之外的任何数据。视图实现的算法应在请求视图的数据时应用，而不是在创建视图时应用，这就是我们说视图被惰性求值的原因。
通过实现一个简单的玩具视图来计算输入的平方，可以更容易地解释这一点。
视图通常由视图实现、适配器实现和适配器实现的一个实例组成。
首先，我们创建一个简单的元函数，用于确定底层 Range 的迭代器类型。
template<typename T>
using IteratorBase = decltype( std::begin( std::declval<T&>( ) ) );
然后我们创建我们的视图实现。
template <typename Rng>
class SquareView : public ranges::view_base
{
...
};
我们将视图实现从 ranges::view_base 派生出来。ranges::view_base 是一个空基类，其唯一目的是提供一个机制，允许其他代码块将派生类识别为视图实现。
template <typename Rng>
class SquareView : public ranges::view_base
{
private:
using RangeType = ranges::views::all_t<Rng>;
RangeType range_;
...
};
SquareView 有一个数据成员，RangeType range_，其中 RangeType 是 ranges::views::all_t<Rng> 的别名，它会自适应地适配 Rng 指定的 Range 类型。
如果 Rng 是一个视图，我们得到该视图的类型；如果 Rng 是一个容器，我们得到一个引用底层容器的 ranges::ref_view<>；或者我们得到一个 ranges::subrange<>。这样做是为了确保容器不被复制，并最小化复制或移动视图实例所需的工作。
为了保持简单，我们让 IteratorType 从底层 Range 的迭代器实现派生，并重用基类的预增量和后增量实现。
template <typename Rng>
class SquareView : public ranges::view_base
{
...
class IteratorType : public IteratorBase<Rng>
{
public:
using Base = IteratorBase<Rng>;
using value_type = typename std::iterator_traits<Base>::value_type;
IteratorType( ) { }
IteratorType( const Base& other ) : Base( other ) { }
IteratorType& operator++( )
{
++static_cast<Base&>( *this );
return *this;
}
IteratorType operator++( int )
{
return static_cast<Base&>( *this )++;
}
// Where the magic happens
value_type operator*( ) const
{
value_type value = *static_cast<Base>( *this );
return value * value;
}
};
public:
...
};
解引用运算符的实现是事情变得有趣的地方。
- 我们从底层 Range 中检索“
input”值。 - 我们计算检索值的平方并返回结果。
这就是视图如何被惰性求值。
SquareView 的其余部分易于实现。
template <typename Rng>
class SquareView : public ranges::view_base
{
...
public:
using iterator = IteratorType;
SquareView( )
{ }
SquareView( Rng&& range )
: range_( ranges::views::all( static_cast<Rng&&>( range ) ) )
{ }
iterator begin( ) const { return ranges::begin( range_ ); }
auto end( ) const { return ranges::end( range_ ); }
};
接下来，我们需要为我们的视图实现一个适配器。
// Deduction guideline needed to help the
// compiler make the right choice for us
template <typename Rng>
SquareView( Rng&& )->SquareView<Rng>;
struct SquareFn
{
template <typename Rng>
auto operator()( Rng&& range ) const
{
return SquareView( std::forward<Rng>( range ) );
}
template <typename Rng>
friend auto operator|( Rng&& range, const SquareFn& )
{
return SquareView( std::forward<Rng>( range ) );
}
};
适配器实现的第一个运算符允许我们将视图视为一个函数。
auto view = Views::Square( inputValues );
而第二个运算符实现允许我们使用“|”管道符号进行组合。
auto view = inputValues | Views::Square;
最后，适配器的一个实例。
namespace Views
{
constexpr SquareFn Square;
}
如下所示，Views::Square 是我们视图的用户界面。
using namespace ranges;
void Example001( )
{
std::vector<int> inputValues{ 1,2,3,4,5,6,7 };
auto view = inputValues
| Views::Square
| views::drop( 2 );
int sum = 0;
for ( auto it = view.begin( ); it != view.end( ); ++it )
{
sum += *it;
}
std::cout << "Sum: " << sum << std::endl;
}
int main()
{
Example001( );
}
只有当我们迭代视图时，才会访问 inputValues 中的数据。
auto view = inputValues
| Views::Square
| views::drop( 2 );
不访问任何数据，它只指定数据将如何被访问。我们实际上是在组合一个类型。
ranges::drop_view<SquareView<std::vector<int,std::allocator<int>> &>>
为 view 变量实例化并操作整数 vector，让编译器为我们的视图生成高度优化的代码。
此时，我希望“视图是对 Range 的可组合适应，它在迭代视图时被惰性求值”的含义更加清晰。
我们真的需要经历这一切才能创建一个视图吗？
不，当我们需要为 range-v3 库实现类似 SquareView 的东西时，使用 ranges::view_adaptor 模板会更容易，也更好。
template<class Rng>
class SquareView : public ranges::view_adaptor<SquareView<Rng>, Rng>
{
friend ranges::range_access;
class adaptor : public ranges::adaptor_base
{
public:
adaptor( ) = default;
auto read( ranges::iterator_t<Rng> it ) const -> decltype( (*it) * ( *it ) )
{
auto value = *it;
return value * value;
}
};
adaptor begin_adaptor( ) const { return { }; }
adaptor end_adaptor( ) const { return { }; }
public:
SquareView( ) = default;
SquareView( Rng&& rng )
: SquareView::view_adaptor{ std::forward<Rng>( rng ) }
{}
};
ranges::adaptor_base 提供了处理真实视图实现应能够处理的各种迭代器所需的所有机制，包括指针——而我们的玩具实现由于我们简化的迭代器实现而无法处理。
SquareView 的此实现是输入 Range 的输入 Range，是转发 Range 的转发 Range，依此类推；允许编译器根据迭代器的能力选择算法实现。
通常，在实现类似的东西时，我们只会使用 views::transform。
auto result = inputValues
| views::transform( []( auto value ) { return value * value; } )
| views::drop( 2 );
性能
Range-v3 库的性能非常好。考虑以下几点：
constexpr size_t ValueCount = 1000000ULL;
constexpr size_t IterationCount = 10000ULL;
size_t RangeTest( )
{
using namespace ranges;
size_t result = 0;
for ( size_t i = 0; i < IterationCount; i++ )
{
auto values = views::iota( 0ULL, ValueCount )
| views::transform( []( auto value ) { return value * value; } );
for ( auto value : values )
{
result += value;
}
}
return result;
}
这是使用经典 STL 实现类似功能的示例：
size_t VectorTest( )
{
std::vector<size_t> values( ValueCount );
size_t result = 0;
for ( size_t i = 0; i < IterationCount; i++ )
{
std::iota( values.begin( ), values.end( ), 0 );
std::transform( values.begin( ), values.end( ), values.begin( ),
[]( auto value ) { return value * value; } );
for ( auto value : values )
{
result += value;
}
}
return result;
}
vector 在函数开头分配，然后在每次迭代中重新使用——因此不会产生太多开销。
最后，是直接执行计算的实现。
size_t DirectTest( )
{
size_t result = 0;
for ( size_t i = 0; i < IterationCount; i++ )
{
for ( size_t j = 0; j < ValueCount; j++ )
{
result += j * j;
}
}
return result;
}
在辅助函数（用于计时三个测试的执行）的帮助下
template <typename F>
void PerformanceOf(const char* testName, F testFunction )
{
using Seconds = std::chrono::duration<double, std::chrono::seconds::period>;
auto start = std::chrono::high_resolution_clock::now( );
auto value = testFunction( );
auto end = std::chrono::high_resolution_clock::now( );
auto duration = Seconds( end - start );
printf( "%s value: %llu, time: %f seconds\n", testName, value, duration.count( ) );
}
调用
void Performance001( )
{
PerformanceOf( "Range", RangeTest );
PerformanceOf( "Vector", VectorTest );
PerformanceOf( "Direct", DirectTest );
}
产生以下输出：
Range value: 12914400067280709120, time: 3.573238 seconds
Vector value: 12914400067280709120, time: 8.660025 seconds
Direct value: 12914400067280709120, time: 3.102976 seconds
DirectTest() 的性能优于其他实现不足为奇，但我认为 DirectTest() 和 RangeTest() 之间的差距并不算大，这还是很令人印象深刻的。虽然远非对 range-v3 库进行详尽的性能测试，但它证明了通过迭代器工作几乎没有开销。
此时，查看我们的视图实现如何运行也很有趣。
重写 RangeTest() 以使用基于 ranges::view_adaptor 的 SquareView 实现。
size_t RangeTest( )
{
using namespace ranges;
size_t result = 0;
for ( size_t i = 0; i < IterationCount; i++ )
{
auto values = views::iota( 0ULL, ValueCount )
| Views::Square;
for ( auto value : values )
{
result += value;
}
}
return result;
}
产生以下输出：
Range value: 12914400067280709120, time: 3.652167 seconds
并使用我们最初的玩具实现运行它，结果如下：
Range value: 12914400067280709120, time: 3.623685 seconds
C++ 20 Ranges：即将登陆您附近的编译器
C++ 20 Ranges 将在 Visual Studio 16.8.1 中提供——在此之前，甚至之后，range-v3 库都将是一个异常好的替代方案，已被全球数千名 C++ 程序员使用。
Range-v3 是一个设计精美的库，考虑到它在多大程度上依赖于模板元编程，它的可读性令人惊讶。
历史
- 2020 年 8 月 18 日 - 初始帖子