range-v3

Range library for C++14/17/20. This code was the basis of a formal proposal to add range support to the C++ standard library. That proposal evolved through a Technical Specification, and finally into P0896R4 "The One Ranges Proposal" which was merged into the C++20 working drafts in November 2018.

About:

Ranges are an extension of the Standard Template Library that makes its iterators and algorithms more powerful by making them composable. Unlike other range-like solutions which seek to do away with iterators, in range-v3 ranges are an abstration layer on top of iterators.

Range-v3 is built on three pillars: Views, Actions, and Algorithms. The algorithms are the same as those with which you are already familiar in the STL, except that in range-v3 all the algorithms have overloads that take ranges in addition to the overloads that take iterators. Views are composable adaptations of ranges where the adaptation happens lazily as the view is iterated. And an action is an eager application of an algorithm to a container that mutates the container in-place and returns it for further processing.

Views and actions use the pipe syntax (e.g., rng | adapt1 | adapt2 | ...) so your code is terse and readable from left to right.

Documentation:

Check out the (woefully incomplete) documentation here.

Other resources (mind the dates, the library probably has changed since then):

• Usage:

  • Talk: CppCon 2015: Eric Niebler "Ranges for the Standard Library", 2015.
  • A slice of Python in C++, 07.12.2014.
  • Actions (back then called Container Algorithms), 23.11.2014.
  • Range comprehensions, 27.04.2014.
  • Input iterators vs input ranges, 07.11.2013.

• Design / Implementation:

  • Rationale behind range-v3: N4128: Ranges for the standard library Revision 1, 2014.
  • Ranges TS: N4560: C++ Extensions for Ranges, 2015.
  • Implementation of customization points in range-v3:
    • N4381: Suggested Design for Customization Points, 2015.
    • P0386: Inline variables, 2016.
    • Customization Point Design in C++11 and Beyond, 2014.
  • Proxy iterators in range-v3:
    • D0022: Proxy Iterators for the Ranges Extensions.
    • To Be or Not to Be (an Iterator), 2015.
    • Iterators++: Part1, 2015.
    • Iterators++: Part2, 2015.
    • Iterators++: Part3, 2015.
  • Metaprogramming utilities:
    • See the meta documentation, the library has changed significantly since the 2014 blog post.
  • Concept emulation layer: Concept checking in C++11, 2013.
  • C++Now 2014: Eric Niebler "C++11 Library Design", 2014.

License:

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 acknowledgments.

Supported Compilers

The code is known to work on the following compilers:

• clang 3.6.2 (or later)
• GCC 5.0.2 (or later) (C++14 "extended constexpr" support is poor before 6.1.)
• Clang/LLVM 6 (or later) on Windows (older versions may work - we haven't tested.)
• Visual Studio 2019 Preview 4 (or later) on Windows, with some caveats due to range-v3's strict conformance requirements:
  • range-v3 needs /std:c++17 /permissive-
  • range-v3 needs a fully conforming preprocessor, so /experimental:preprocessor is necessary. Note that the conforming preprocessor diagnoses C5105 "macro expansion producing 'defined' has undefined behavior" in some of the Windows SDK headers, so you'll probably want to suppress that warning with /wd5105.

[ Note: We've "retired" support for Clang/C2 with the VS2015 toolset (i.e., the v140_clang_c2 toolset) which Microsoft no longer supports for C++ use. We no longer have CI runs, but haven't gone out of our way to break anything, so it will likely continue to work. ]

Development Status: This code is fairly stable, well-tested, and suitable for casual use, although currently lacking documentation. In general, 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.

Build status

• on Travis-CI:
• on AppVeyor:

Release Notes:

• 0.5.0 Apr 30, 2019

  • NEW: MSVC support, from @CaseyCarter 🎉 (See the docs for the list of supported compilers.)
  • NEW: view::enumerate, from @MikeGitb
  • NEW: view::addressof, from @tower120
  • NEW: unstable_remove_if algorithm and action, from @tower120
  • NEW: adjacent_remove_if algorithm and action, from @cjdb
  • NEW: ostream_joiner, from @sv1990
  • view::drop_while and view::take_while get projection support, from @mrpi
  • view::filter and view::remove_if get projection support, from @mrpi
  • view::unique accepts optional comparison operator, from @tete17
  • action::slice supports sliding from the end, from @tete17
  • Support coroutines on MSVC, from @CaseyCarter
  • Faster view::generate_n, from GitHub user @tower120
  • Improved aligned new detection for libc++ on iOS, from @mtak-
  • Various CMake improvements, from @johelegp
  • view_adaptor supports basic_iterator-style mixins, from @tower120
  • Fix ranges::advance for random-access iterators for n==0, from @tower120
  • Bugs fixed: #755, #759, #942, #946, #952, #975, #978, #986, #996, #1041, #1047, #1088, #1094, #1107, #1129

• 0.4.0 Oct 18, 2018

  • Minor interface-breaking changes:
    • single_view returns by const & (see #817).
    • reverse_view of a non-Sized, non-Bounded RandomAccess range (eg., a null-terminated string) no longer satisfies SizedRange.
    • The generate and generate_n views now return the generated values by xvalue reference (T &&) to the value cached within the view (see #905).
    • Views no longer prefer returning constant iterators when they can; some views have different constant and mutable iterators.
  • Enhancements:
    • Views can successfully adapt other views that have different constant and mutable iterators.
    • The single and empty views are much closer to the versions as specified in P0896.
  • Bug fixes:
    • "single_view should not copy the value" #817.
    • "Calling back() on strided range does not return the correct last value in range" #901.
    • "generate(foo) | take(n) calls foo n+1 times" #819.
    • "generate seems broken with move-only return types" #905.
    • "Unexpected behavior in generate with return by reference" #807.
    • "Inconsistent behaviour of ranges::distance with ranges::view::zip using infinite views." #783.
    • "Infinite loop when using ranges::view::cycle with an infinite range" #780.
    • "Composing ranges::view::cycle with ranges::view::slice" #778.
    • "cartesian_product view, now with moar bugs." #919.

• 0.3.7 Sept 19, 2018

  • Improved support for clang-cl (thanks to @CaseyCarter).
  • Fix for any_view<T, category::sized | category::input> (see #869).
  • Fix iter_move of a ranges::reverse_iterator (see #888).
  • Fix move_sentinel comparisons (see #889).
  • Avoid ambiguity created by boost::advance and std::advance (see #893).

• 0.3.6 May 15, 2018

  • NEW: view::exclusive_scan (thanks to GitHub user @mitsutaka-takeda).
  • All views get non-const overloads of .empty() and .size() (see ericniebler/stl2#793).
  • Upgrade Conan support for conan 1.0.
  • subspan interface tweaks.
  • Fix bug in view::split (see this stackoverflow question).
  • Fix bug in view::stride (see ericniebler/stl2#805).
  • Fix const-correctness problem in view::chunk (see this stackoverflow question).
  • Replace uses of ranges::result_of with ranges::invoke_result.
  • Fix potential buffer overrun of view::drop over RandomAccessRanges.
  • Lots of view::cartesian_product fixes (see ericniebler/stl2#820, ericniebler/stl2#823).
  • Work around gcc-8 regression regarding volatile std::initializer_lists (see ericniebler/stl2#826).
  • Fix const-correctness problem of view::take.

• 0.3.5 February 17, 2018

  • Rvalues may satisfy Writable (see ericniebler/stl2#387).
  • view_interface gets a bounds-checking at method.
  • chunk_view works on Input ranges.
  • Fix bug in group_by_view.
  • Improved concept checks for partial_sum numeric algorithm.
  • Define ContiguousIterator concept and contiguous_iterator_tag iterator category tag.
  • Sundry span fixes.
  • action::insert avoids interfering with vector's exponentional growth strategy.
  • Add an experimental shared view for views that need container-like scratch space to do their work.
  • Faster, simpler reverse_view.
  • Rework ranges::reference_wrapper to avoid LWG#2993.
  • Reworked any_view, the type-erased view wrapper.
  • equal algorithm is constexpr in C++14.
  • stride_view no longer needs an atomic data member.
  • const-correct drop_view.
  • adjacent_filter_view supports bidirectional iteration.
  • Massive view_adaptor cleanup to remove the need for a mutable data member holding the adapted view.
  • Fix counting_iterator post-increment bug.
  • tail_view of an empty range is an empty range, not undefined behavior.
  • Various portability fixes for gcc and clang trunk.

• 0.3.0 June 30, 2017

  • Input views may now be move-only (from @CaseyCarter)
  • Input any_views are now much more efficient (from @CaseyCarter)
  • Better support for systems lacking a working <thread> header (from @CaseyCarter)

• 0.2.6 June 21, 2017

  • Experimental coroutines with ranges::experimental::generator (from @CaseyCarter)
  • ranges::optional now behaves like std::optional (from @CaseyCarter)
  • Extensive bug fixes with Input ranges (from @CaseyCarter)

• 0.2.5 May 16, 2017

  • view::chunk works on Input ranges (from @CaseyCarter)
  • for_each_n algorithm (from @khlebnikov)
  • Portability fixes for MinGW, clang-3.6 and -3.7, and gcc-7; and cmake 3.0

• 0.2.4 April 12, 2017 Fix the following bug:

  • action::stable_sort of vector broken on Clang 3.8.1 since ~last Xmas (ericniebler#632).

• 0.2.3 April 4, 2017 Fix the following bug:

  • iterators that return move-only types by value do not satisfy Readable (ericniebler/stl2#399).

• 0.2.2 March 30, 2017 New in this release:

  • view::linear_distribute(from,to,n) - A view of n elements between from and to, distributed evenly.
  • view::indices(n) - A view of the indices [0,1,2...n-1].
  • view::closed_indices(n) - A view of the indices [0,1,2...n].

  This release deprecates view::ints(n) as confusing to new users.

• 0.2.1 March 22, 2017 New in this release:

  • view::cartesian_product
  • action::reverse

• 0.2.0 March 13, 2017 Bring many interfaces into sync with the Ranges TS.

  • Many interfaces are simply renamed. The following table shows the old names and the new. (All names are in the ranges::v3 namespace.)

    Old Name	New Name
    indirect_swap	iter_swap
    indirect_move	iter_move
    iterator_value_t	value_type_t
    iterator_reference_t	reference_t
    iterator_difference_t	difference_type_t
    iterator_size_t	size_type_t
    iterator_rvalue_reference_t	rvalue_reference_t
    iterator_common_reference_t	iter_common_reference_t
    range_value_t	range_value_type_t
    range_difference_t	range_difference_type_t
    range_size_t	range_size_type_t
    range_iterator_t	iterator_t
    range_sentinel_t	sentinel_t

  • common_iterator now requires that its two types (Iterator and Sentinel) are different. Use common_iterator_t<I, S> to get the old behavior (i.e., if the two types are the same, it is an alias for I; otherwise, it is common_iterator<I, S>).

  • The following iterator adaptors now work with iterators that return proxies from their postfix increment operator (i.e., operator++(int)):

    • common_iterator
    • counted_iterator

  • The following customization points are now implemented per the Ranges TS spec and will no longer find the associated unconstrained overload in namespace std:::

    • ranges::begin
    • ranges::end
    • ranges::size
    • ranges::swap
    • ranges::iter_swap

    (In practice, this has very little effect but it may effect overloading in rare situations.)

  • ranges::is_swappable now only takes one template parameter. The new ranges::is_swappable_with<T, U> tests whether T and U are swappable. ranges::is_swappable<T> is equivalent to ranges::is_swappable_with<T &, T &>.

  • The following object concepts have changed to conform with the Ranges TS specification, and approved changes (see P0547):

    • Destructible
    • Constructible
    • DefaultConstructible
    • MoveConstructible
    • MoveConstructible
    • Movable
    • Assignable

  • The View concept is no longer satisfied by reference types.

  • The syntax for defining a concept has changed slightly. See iterator/concepts.hpp for examples.

• 0.1.1 Small tweak to Writable concept to fix #537.

• 0.1.0 March 8, 2017, Begin semantic versioning

Say Thanks!

I do this work because I love it and because I love C++ and want it to be as excellent as I know it can be. If you like my work and are looking for a way to say thank you, you can leave a supportive comment on my blog. Or you could leave me some kudos on my Open Hub range-v3 contribution page. Just click the Give Kudos button here.