|
Range-v3
Range algorithms, views, and actions for the Standard Library
|
|
|
Range-v3
Range algorithms, views, and actions for the Standard Library
|
|
Range library for C++11/14/17. This code is the basis of a formal proposal to add range support to the C++ standard library.
Development Status:
This code is fairly stable, well-tested, and suitable for casual use, although currently lacking documentation. No promise is made about support or long-term stability. This code will evolve without regard to backwards compatibility.
This library is header-only. You can get the source code from the range-v3 repository on github. To compile with Range-v3, you can either #include the entire library:
Or you can #include only the core, and then the individual headers you want:
Most of the source code in this project are mine, and those are under the Boost Software License. Parts are taken from Alex Stepanov's Elements of Programming, Howard Hinnant's libc++, and from the SGI STL. Please see the attached LICENSE file and the CREDITS file for the licensing and acknowledgements.
The code is known to work on the following compilers:
Range v3 is a generic library that augments the existing standard library with facilities for working with ranges. A range can be loosely thought of a pair of iterators, although they need not be implemented that way. Bundling begin/end iterators into a single object brings several benefits.
It's more convenient to pass a single range object to an algorithm than separate begin/end iterators. Compare:
with
Range v3 contains a full implementation of all the standard algorithms with range-based overloads for convenience.
Having a single range object permits pipelines of operations. In a pipeline, a range is lazily adapted or eagerly mutated in some way, with the result immediately available for further adaptation or mutation. Lazy adaption is handled by views, and eager mutation is handled by actions.
A view is a lightweight wrapper that presents a view of an underlying sequence of elements in some custom way without mutating or copying it. Views are cheap to create and copy, and have non-owning reference semantics. Below are some examples:
Filter a container using a predicate and transform it.
Generate an infinite list of integers starting at 1, square them, take the first 10, and sum them:
Generate a sequence on the fly with a range comprehension and initialize a vector with it:
When you want to mutate a container in-place, or forward it through a chain of mutating operations, you can use actions. The following examples should make it clear.
Read data into a vector, sort it, and make it unique.
Do the same to a vector that already contains some data:
Mutate the container in-place:
Same as above, but with function-call syntax instead of pipe syntax:
Range v3 provides a utility for easily creating your own range types, called ranges::view_facade. The code below uses view_facade to create a range that traverses a null-terminated string:
The view_facade class generates an iterator and begin/end member functions from the minimal interface provided by c_string_range. This is an example of a very simple range for which it is not necessary to separate the range itself from the thing that iterates the range. Future examples will show examples of more sophisticated ranges.
With c_string_range, you can now use algorithms to operate on null-terminated strings, as below:
Often, a new range type is most easily expressed by adapting an existing range type. That's the case for many of the range views provided by the Range v3 library; for example, the view::remove_if and view::transform views. These are rich types with many moving parts, but thanks to a helper class called ranges::view_adaptor, they aren't hard to write.
Below in roughly 2 dozen lines of code is the transform view, which takes one range and transforms all the elements with a unary function.
Range transformation is achieved by defining a nested adaptor class that handles the transformation, and then defining begin_adaptor and end_adaptor members that return adaptors for the begin iterator and the end sentinel, respectively. The adaptor class has a read member that performs the transformation. It is passed an iterator to the current element. Other members are available for customization: equal, next, prev, advance, and distance_to; but the transform adaptor accepts the defaults defined in ranges::adaptor_base.
With transform_view, we can print out the first 20 squares:
The transform_view defined above is an InputRange when it's wrapping an InputRange, a ForwardRange when it's wrapping a ForwardRange, etc. That happens because of smart defaults defined in the adaptor_base class. That frees you from having to deal with a host of niggly detail when implementing iterators.
*(Note: the above transform_view always stores a copy of the function in the sentinel. That is only necessary if the underlying range's sentinel type models BidirectionalIterator. That's a finer point that you shouldn't worry about right now.)*
The Range v3 library makes heavy use of concepts to constrain functions, control overloading, and check type constraints at compile-time. It achieves this with the help of a Concepts Lite emulation layer that works on any standard-conforming C++11 compiler. The library provides many useful concepts, both for the core language and for iterators and ranges. You can use the concepts framework to constrain your own code.
For instance, if you would like to write a function that takes an iterator/sentinel pair, you can write it like this:
You can then add an overload that take a Range:
With the type constraints expressed with the CONCEPTS_REQUIRES_ macro, these two overloads are guaranteed to not be ambiguous.
Range v3 forms the basis for a proposal to add ranges to the standard library (N4128), and is also be the basis for a Technical Specification on Ranges. The Technical Specification contains many of Range v3's concept definitions (translated into the actual syntax of C++20 Concepts) in addition to constrained versions of the STL algorithms overloaded both for iterator/sentinel pairs and for ranges. The Ranges TS has already been sent to ISO for publication.
The views and actions, as well as various utilities, have not yet been reviewed by the committee, although the basic direction has already passed an initial review. A proposal to add a subset of the views to the Ranges TS is in the early stages.
The big advantage of ranges over iterators is their composability. They permit a functional style of programming where data is manipulated by passing it through a series of combinators. In addition, the combinators can be lazy, only doing work when the answer is requested, and purely functional, without mutating the original data. This makes it easier to reason about your code, especially when writing concurrent programs.
Below is a list of the lazy range combinators, or views, that Range v3 provides, and a blurb about how each is intended to be used.
view::adjacent_filter adjacent_filter with std::not_equal_to filters out all the non-unique elements.) view::adjacent_remove_if view::all any_view<T>(rng) T; can store any range with this value type. view::bounded end is the same as the begin. Useful for iterating over a range with C++'s range-based for loop. view::cartesian_product n ranges, i.e., generates all n-tuples (e1, e2, ... , en) where e1 is an element of the first range, e2 is an element of the second range, etc. view::chunk view::concat view::const_ const view of a source range. view::counted it and a count n, create a range that starts at it and includes the next n elements. view::cycle view::c_str \0-terminated C string (e.g. from a const char*) as a range. view::delimit view::delimit can be called with an iterator and a value, in which case it returns a range that starts at the specified position and ends at the first occurrence of the value. view::drop view::drop_exactly view::drop_while view::empty view::filter filter adaptor.) view::for_each view::generate view::generate_n view::group_by view::group_by groups contiguous elements together with a binary predicate. view::indirect view::intersperse view::ints ints. When used without arguments, it generates the quasi-infinite range [0,1,2,3...]. It can also be called with a lower bound, or with a lower and upper bound (exclusive). An inclusive version is provided by closed_ints. view::iota view::ints that generates a sequence of monotonically increasing values of any incrementable type. When specified with a single argument, the result is an infinite range beginning at the specified value. With two arguments, the values are assumed to denote a half-open range. view::join view::keys pairs (like a std::map), return a new range consisting of just the first element of the pair. view::linear_distribute n values linearly in the closed interval [from, to] (the end points are always included). If from == to, returns n-times to, and if n == 1 it returns to. view::move view::partial_sum view::remove_if filter adaptor with the predicate negated.) view::repeat view::repeat_n view::replace view::replace_if view::reverse view::sample size(range). view::single view::slice view::sliding n, place a window over the first n elements of the underlying range. Return the contents of that window as the first element of the adapted range, then slide the window forward one element at a time until hitting the end of the underlying range. view::split make_pair(true, iterator_past_the_delimiter) if the current position is a boundary; otherwise, make_pair(false, cur). The delimiter character(s) are excluded from the resulting range of ranges. view::stride view::tail view::take view::take is not a SizedRange.) view::take_exactly view::take_exactly is a SizedRange.) view::take_while view::tokenize std::regex_constants::match_flag_type, return a std::regex_token_iterator to step through the regex submatches of the source range. The submatch specifier may be either a plain int, a std::vector<int>, or a std::initializer_list<int>. view::transform view::unbounded view::unique view::values pairs (like a std::map), return a new range consisting of just the second element of the pair. view::zip make_tuple on the Mth elements of all N ranges. view::zip_with Below is a list of the eager range combinators, or actions, that Range v3 provides, and a blurb about how each is intended to be used.
action::drop N elements of the source range. action::drop_while action::erase action::insert action::join action::push_back action::push_front action::remove_if action::shuffle action::slice action::sort action::split pair<bool, N>). action::stable_sort action::stride action::take N-th elements of the range, removes the rest. action::take_while action::transform action::unique 
1.8.13