Range library for C++14/17/20. This code is the basis of the range support in C++20.
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.
A notable exception is anything found within the ranges::cpp20
namespace. Those components will change rarely or (preferably) never at all.
This library is header-only. You can get the source code from the range-v3 repository on github. To compile with Range-v3, just #include
the individual headers you want.
This distribution actually contains three separate header-only libraries:
include/concepts/...
contains the Concepts Portability Preprocessor, or CPP, which is a set of macros for defining and using concept checks, regardless of whether your compiler happens to support the C++20 concepts language feature or not.include/meta/...
contains the Meta Library, which is a set of meta-programming utilities for processing types and lists of types at compile time.include/range/...
contains the Range-v3 library, as described below.The Range-v3 library is physically structured in directories by feature group:
include/range/v3/actions/...
contains actions, or composable components that operate eagerly on containers and return the mutated container for further actions.include/range/v3/algorithms/...
contains all the STL algorithms with overloads that accept ranges, in addition to the familiar overloads that take iterators.include/range/v3/functional/...
contains many generally useful components that would be familiar to functional programmers.include/range/v3/iterator/...
contains the definitions of many useful iterators and iterator-related concepts and utilities.include/range/v3/numeric/...
contains numeric algorithms corresponding to those found in the standard <numeric>
header.include/range/v3/range/...
contains range-related utilities, such as begin
, end
, and size
, range traits and concepts, and conversions to containers.include/range/v3/utility/...
contains a miscellaneous assortment of reusable code.include/range/v3/view/...
contains views, or composable components that operate lazily on ranges and that themselves return ranges that can be operated upon with additional view adaptors.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:
/permissive-
and either /std:c++latest
, /std:c++20
, or /std:c++17
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: convenience, composability, and correctness.
Convenience
It's more convenient to pass a single range object to an algorithm than separate begin/end iterators. Compare:
with
Range-v3 contains full implementations of all the standard algorithms with range-based overloads for convenience.
Composability
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.
For instance, the below uses views to filter a container using a predicate and transform the resulting range with a function. Note that the underlying data is const
and is not mutated by the views.
In the code above, rng
simply stores a reference to the underlying data and the filter and transformation functions. No work is done until rng
is iterated.
In contrast, actions do their work eagerly, but they also compose. Consider the code below, which reads some data into a vector, sorts it, and makes it unique.
Unlike views, with actions each step in the pipeline (actions::sort
and actions::unique
) accepts a container by value, mutates it in place, and returns it.
Correctness
Whether you are using views or actions, you are operating on data in a pure functional, declarative style. You rarely need to trouble yourself with iterators, although they are there under the covers should you need them.
By operating declaratively and functionally instead of imperatively, we reduce the need for overt state manipulation and branches and loops. This brings down the number of states your program can be in, which brings down your bug counts.
In short, if you can find a way to express your solution as a composition of functional transformations on your data, you can make your code correct by construction.
As described above, 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.
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 that use views:
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:
Logically, a view is a factory for iterators, but in practice a view is often implemented as a state machine, with the state stored within the view object itself (to keep iterators small) and mutated as the view is iterated. Because the view contains mutable state, many views lack a const
-qualified begin()
/end()
. When const
versions of begin()
/end()
are provided, they are truly const
; that is, thread-safe.
Since views present the same interface as containers, the temptation is to think they behave like containers with regard to const
-ness. This is not the case. Their behavior with regards to const
-ness is similar to iterators and pointers.
The const
-ness of a view is not related to the const
-ness of the underlying data. A non-const
view may refer to elements that are themselves const
, and vice versa. This is analogous to pointers; an int* const
is a const
pointer to a mutable int
, and a int const*
is a non-const
pointer to a const
int
.
Use non-const
views whenever possible. If you need thread-safety, work with view copies in threads; don't share.
Any operation on the underlying range that invalidates its iterators or sentinels will also invalidate any view that refers to any part of that range. Additionally, some views (e.g., views::filter
), are invalidated when the underlying elements of the range are mutated. It is best to recreate a view after any operation that may have mutated the underlying range.
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.
views::addressof
std::addressof
of each. views::adjacent_filter
adjacent_filter
with std::not_equal_to
filters out all the non-unique elements.) views::adjacent_remove_if
views::all
any_view<T>(rng)
T
; can store any range with this value type. views::c_str
\0
-terminated C string (e.g. from a const char*
) as a range. views::cache1
view::filter
and view::transform
, for instance. views::cache1
is always single-pass. views::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. views::chunk
views::common
end
is the same as the begin
. Useful for calling algorithms in the std::
namespace. views::concat
views::const_
const
view of a source range. views::counted
it
and a count n
, create a range that starts at it
and includes the next n
elements. views::cycle
views::delimit
views::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. views::drop
views::drop_last
views::drop_exactly
views::drop_while
views::empty
views::enumerate
views::filter
filter
adaptor.) views::for_each
views::generate
views::generate_n
views::chunk_by
views::chunk_by
groups contiguous elements together with a binary predicate. views::indirect
views::intersperse
views::ints
int
s. 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
. views::iota
views::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. views::join
views::keys
pair
s (like a std::map
), return a new range consisting of just the first element of the pair
. views::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
. views::move
views::partial_sum
views::remove
views::remove_if
filter
adaptor with the predicate negated.) views::repeat
views::repeat_n
views::replace
views::replace_if
views::reverse
views::sample
size(range)
. views::single
views::slice
views::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. views::split
views::split_when
true
if and only if the element is part of a delimiter. The function should accept an iterator and sentinel indicating the current position and end of the source range and return std::make_pair(true, iterator_past_the_delimiter)
if the current position is a boundary; otherwise std::make_pair(false, ignored_iterator_value)
. The elements matching the delimiter are excluded from the resulting range of ranges. views::stride
views::tail
views::take
views::take
is not a sized_range
.) views::take_exactly
views::take_exactly
is a sized_range
.) views::take_last
sized_range
. If the source range does not have at least count elements, the full range is returned. views::take_while
views::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>
. views::transform
views::trim
views::unbounded
views::unique
views::values
pair
s (like a std::map
), return a new range consisting of just the second element of the pair
. views::zip
make_tuple
on the Mth elements of all N ranges. views::zip_with
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:
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.
actions::drop
N
elements of the source range. actions::drop_while
actions::erase
actions::insert
actions::join
actions::push_back
actions::push_front
actions::remove_if
actions::remove
actions::reverse
actions::shuffle
actions::slice
actions::sort
actions::split
pair<bool, N>
). actions::stable_sort
actions::stride
actions::take
N
-th elements of the range, removes the rest. actions::take_while
actions::transform
actions::unique
actions::unstable_remove_if
remove_if
. Requires bidirectional container. Below we cover some utilities that range-v3 provides for creating your own view adaptors and iterators.
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 views::remove_if
and views::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 input range when it is wrapping an input range, a forward range when it's wrapping a forward range, 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 bidirectional_iterator. That's a finer point that you shouldn't worry about right now.)*
Each view_adaptor
contains base()
member in view and iterator. base()
- allow to access "adapted" range/iterator:
Like basic_iterator
's cursor
, view_adaptor
's adaptor
can contain mixin class too, to inject things into the public interface of the iterator:
From within mixin you can call:
get()
- to access adaptor internalsbase()
- to access adaptable iteratorIterator/sentinel adaptor may "override" the following members:
As you can see, some "overrides" have effect only for begin_adaptor
or end_adaptor
. In order to use full potential of adaptor, you need to have separate adaptors for begin and end:
Sometimes, you can use the same adaptor for both begin_adaptor
and end_adaptor
:
Note that all the data you store in the adaptor will become part of the iterator.
If you will not "override" begin_adaptor()
or/and end_adaptor()
in your view_adaptor, default ones will be used.
Here is an example of Range-v3 compatible random access proxy iterator. The iterator returns a key/value pair, like the zip
view.
read()
returns references. But the default for value_type
, which is decay_t<decltype(read())>
, is common_pair<Key&, Value&>
. That is not correct in our case. It should be pair<Key, Value>
, so we explicitly specify value_type
.
ranges::common_pair
has conversions:
ranges::common_pair<Key&, Value&>
↔ranges::common_pair<Key, Value>
.
All ranges::common_pair
s converts to their std::pair
equivalents, also.
For more information, see http://wg21.link/P0186#basic-iterators-iterators.basic
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 emulation layer that works on any standard-conforming C++14 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 CPP_template
macro, these two overloads are guaranteed to not be ambiguous. When compiling with C++20 concepts support, this uses real concept checks. On legacy compilers, it falls back to using std::enable_if
.
Range-v3 formed the basis for the Technical Specification on Ranges, which has since been merged into the working draft and shipped with C++20 in the std::ranges
namespace.
More range adaptors are slated for inclusion in C++23 and beyond.
The actions, as well as various utilities, have not yet been reviewed by the Committee, although the basic direction has already passed an initial review.