1. Acknowledgements
I would like to acknowledge the following people for their assistance with this proposal:
-
Casey Carter, for reviewing all submissions to [cmcstl2] and providing feedback that enabled the proposed range adaptors to have high-quality implementations.
-
Eric Niebler, for providing [range-v3] as a reference implementation.
2. Motivation
[P0789] introduces the notion of a range adaptor and twelve pioneering range adaptors that improve declarative, range-based programming. For example, it is possible to perform an inline, in-place, lazy reverse like so:
namespace ranges = std :: ranges ; namespace view = std :: ranges :: view ; // Old auto i = ranges :: find ( ranges :: rbegin ( employees ), ranges :: rend ( employees ), "Lovelace" , & employee :: surname ); // New auto j = ranges :: find ( employees | view :: reverse , "Lovelace" , & employee :: surname ); [[ assert : i == j ]];
P1035 recognises that P0789 introduces only a few of the widely experimented-with range adaptors in [range-v3], and would like to add a few more to complete the C++20 phase of range adaptors. To this end, P1035 discusses range adaptors that are related to those in P0789.
3. Proposals
Unless otherwise requested, each sub-subsection below should be polled individually from other sub-subsections. Two major questions are to be asked per range adaptor. It is up to LEWG to decide the exact phrasing, but the author’s intentions are listed below.
-
Do we want this range adaptor in C++20?
-
As-is?
-
With modifications, as suggested by LEWG?
-
If we do not want this range adaptor in C++20, do we want it in C++23?
-
As-is?
-
With modificaitons, as suggested by LEWG?
3.1. take_while_view
3.1.1. Motivation
P0789 introduces
, which rangifies the iterator pair
. As an example:
auto v = std :: vector { 0 , 1 , 2 , 3 , 4 , 5 }; std :: cout << distance ( v | view :: take ( 3 )) << '\n' ; // prints 3 copy ( v | view :: take ( 3 ), ostream_iterator < int > ( std :: cout , " " )); // prints 0 1 2 copy ( v | view :: take ( distance ( v )), ostream_iterator < int > ( std :: cout , " " )); // prints 0 1 2 3 4 5
will provide slightly different functionality, akin to having a sentinel that
checks if a certain predicate is satisfied.
Current | Proposed |
---|---|
|
|
Wandbox demo | Wandbox demo |
The former requires that a user define their own sentinel type: something that while not expert-friendly, is yet to be established as a widespread idiom in C++, and providing a range adaptor for this purpose will help programmers determine when a sentinel is _not_ necessary.
3.1.2. Notes
-
There is a slight programmer overhead in the naming: the author felt that both
andis_odd_sentinel
were applicable names: ultimately, the nameis_even_sentinel
was chosen because it describes the delimiting condition. An equally valid reason could probably be made foris_odd_sentinel
.is_even_sentinel -
A sentinel that takes a lambda may be of interest to LEWG. If there is interest in this, a proposal could be made in the C++23 timeframe.
3.1.3. Interface and specification
template < View R , class Pred > requires InputRange < R > && std :: is_object_v < Pred > && IndirectUnaryPredicate < const Pred , iterator_t < R > class take_while_view : public view_interface < take_while_view < R , Pred >> { template < bool > class __sentinel ; // exposition-only public : take_while_view () = default ; constexpr take_while_view ( R base , Pred pred ); template < ViewableRange O > requires constructible - from - range < R , O > constexpr take_while_view ( O && o , Pred pred ); constexpr R base () const ; constexpr const Pred & pred () const ; constexpr auto begin () requires ! SimpleView < R > ; constexpr auto begin () const requires Range < const R > ; constexpr auto end () requires ! SimpleView < R > ; constexpr auto end () const requires Range < const R > ; private : R base_ ; // exposition-only semiregular < Pred > pred_ ; // exposition-only }; template < class R , class Pred > take_while_view ( R && , Pred ) -> take_while_view < all_view < R > , Pred > ;
3.1.3.1. take_while_view
constructors
constexpr take_while_view ( R base , Pred pred );
-
Effects: Initialises
withbase_
and initialisesbase
withpred_
.pred
template < ViewableRange O > requires constructible - from - range < R , O > constexpr take_while_view ( O && o , Pred pred );
-
Effects: Initialises
withbase_
and initialisesview :: all ( std :: forward < O > ( o ))
withpred_
.pred
3.1.3.2. take_while_view
conversion
constexpr R base () const ;
-
Returns:
.base_
constexpr const Pred & pred () const ;
-
Returns:
.pred_
3.1.3.3. take_while_view
range begin
constexpr auto begin () requires ! SimpleView < R > ; constexpr auto begin () const requries Range < const R >
-
Effects: Equivalent to
.return ranges :: begin ( base_ );
3.1.3.4. take_while_view
range end
constexpr auto end () requires ! SimpleView < R > ; constexpr auto end () const requires Range < const R > ;
-
Effects: Equivalent to
.return __sentinel < is_const_v < decltype ( * this ) >> ( & pred ());
3.1.4. take_while_view :: __sentinel
template < class R , class Pred > template < bool Const > class take_while_view < R , Pred >:: __sentinel { using Parent = conditional_t < Const , const take_while_view , take_wile_view > ; using Base = conditional_t < Const , const R , R > ; sentinel_t < Base > end_ {}; // exposition-only const Pred * pred_ {}; // pred public : __sentinel () = default ; constexpr explicit __sentinel ( sentinel_t < Base > end , const Pred * pred ); constexpr __sentinel ( __sentinel <! Const > s ) requires Const && ConvertibleTo < sentinel_t < R > , sentinel_t < Base >> constexpr sentinel_t < Base > base () const { return end_ ; } friend constexpr bool operator == ( const __sentinel & x , const iterator_t < Base >& y ); friend constexpr bool operator == ( const iterator_t < Base >& x , const __sentinel & y ); friend constexpr bool operator != ( const __sentinel & x , const iterator_t < Base >& y ); friend constexpr bool operator != ( const iterator_t < Base >& x , const __sentinel & y ); };
3.1.5. take_while_view :: __sentinel
constructor
constexpr explicit __sentinel ( sentinel_t < Base > end , const Pred * pred );
-
Effects: Initialises
withend_
, andend
withpred_
.pred
constexpr __sentinel ( __sentinel <! Const > s ) requires Const && ConvertibleTo < sentinel_t < R > , sentinel_t < Base >> ;
-
Effects Initialises
withend_
ands . end_
withpred_
.s . pred_
3.1.6. take_while_view :: __sentinel
conversion
constexpr sentinel_t < Base > base () const ;
-
Effects: Equivalent to
return end_ ;
3.1.7. take_while_view :: __sentinel
comparisons
friend constexpr bool operator == ( const __sentinel & x , const iterator_t < Base >& y )
-
Effects: Equivalent to
.return x . end_ != y && ! ( * x . pred_ )( * y );
friend constexpr bool operator == ( const iterator_t < Base >& x , const __sentinel & y );
-
Effects: Equivalent to
.return y == x ;
friend constexpr bool operator != ( const __sentinel & x , const iterator_t < Base >& y );
-
Effects: Equivalent to
.! ( x == y );
friend constexpr bool operator != ( const iterator_t < Base >& x , const __sentinel & y );
-
Effects: Equivalent to
.! ( y == x );
3.2. view :: take_while
The name
denotes a range adaptor object. Let
and
be expressions such that type
is
. Then, the expression
is expression-equivalent to:
-
iftake_while_view { E , F }
modelsT
and ifInputRange
is an object, and modelsF
.IndirectUnaryPredicate -
Otherwise
is ill-formed.std :: ranges :: view :: take_while ( E , F )
3.3. drop_view
3.3.1. Motivation
is the complement to
: instead of providing the user with the
first _n_ elements, it provides the user with all _but_ the first _n_ elements.
Current (C++17) | Proposed (C++20) |
---|---|
|
|
3.3.2. Interface
template < View R > class drop_view : public view_interface < drop_view < R >> { using D = iter_distance_t < iterator_t < R >> ; // exposition-only public : drop_view (); constexpr drop_view ( R base , D count ); template < ViewableRange O > requires constructible - from - range < R , O > constexpr drop_view ( O && o , D count ); constexpr R base () const ; constexpr auto begin () requires ! ( SimpleView < R > && RandomAccessRange < R > ); constexpr auto begin () const requires Range < const R > && RandomAccessRange < const R > ; constexpr auto end () requires ! ( SimpleView < R > ); constexpr auto end () const requires Range < const R > ; constexpr auto size () requires ! SimpleView < R > && SizedRange < R > ; constexpr auto size () const requires SizedRange < const R > ; private : R base_ ; // exposition-only D count_ ; // exposition-only }; template < Range R > drop_view ( R && , iter_difference_t < iterator_t < R >> ) -> drop_view < all_view < R >> ;
3.3.2.1. drop_view
constructor
constexpr drop_view ( R base , D count );
-
Effects: Initialises
withbase_
andbase
withcount_
.count
template < ViewableRange O > requires constructible - from - range < R , O > constexpr drop_view ( O && o , D count );
-
Effects: Initialises
withbase_
andview :: all ( std :: forward < O > ( o ))
withcount_
.count
3.3.2.2. drop_view
conversion
constexpr R base () const ;
-
Effects: Equivalent to
.return base_
3.3.2.3. drop_view
range begin
constexpr auto begin () requires ! ( SimpleView < R > && RandomAccessRange < R > ); constexpr auto begin () const requires Range < const R > && RandomAccessRange < const R > ;
-
Effects: Equivalent to
.return ranges :: next ( ranges :: begin ( base_ ), count_ , ranges :: end ( base_ )); -
_Remarks_: In order to provide the amortized constant time complexity required by the Range concept, this function caches the result within the
for use on subsequent calls.drop_view
3.3.2.4. drop_view
range end
constexpr auto end () requires ! ( SimpleView < R > ); constexpr auto end () const requires Range < const R > ;
-
Effects: Equivalent to
.return ranges :: end ( base_ );
3.3.2.5. drop_view
size
constexpr auto size () requires ! SimpleView < R > && SizedRange < R > ; constexpr auto size () const requires SizedRange < const R > ;
-
Equivalent to:
auto const size = ranges :: size ( base_ ); auto const count = static_cast < decltype ( size ) > ( count_ ); return size < count ? 0 : size - count ;
3.4. view :: drop
The name
denotes a range adaptor object. Let
and
be expressions such that type
is
. Then, the expression
is expression-equivalent to:
-
ifdrop_view { E , F }
modelsT
andInputRange
is implicitly convertible toF
.iter_difference_t < iterator_t < T >> -
Otherwise
is ill-formed.view :: drop ( E , F )
3.5. drop_while_view
3.5.1. Motivation
The motivation for
is the union of
and
.
Unlike the others, there are two demonstrations of
below.
Current (C++17) | Proposed (C++20) v1 |
---|---|
|
|
3.5.2. Interface
template < View R , class Pred > requires InputRange < R > && std :: is_object_v < Pred > && IndirectPredicate < const Pred , iterator_t < R >> class drop_while_view : public view_interface < drop_while_view < R , Pred >> { public : drop_while_view () = default ; constexpr drop_while_view ( R base , Pred pred ); template < ViewableRange O > requires constructible - from - range < R , O > constexpr drop_while_view ( O && o , Pred pred ); constexpr R base () const ; constexpr Pred pred () const ; constexpr auto begin (); constexpr auto end (); private : R base_ ; // exposition-only semiregular < Pred > pred_ ; // exposition-only }; template < class R , class Pred > drop_while_view ( R && , Pred ) -> drop_while_view < all_view < R > , Pred > ;
3.5.2.1. drop_while_view
constructors
constexpr drop_while_view ( R base , Pred pred );
-
Effects: Initialises
withbase_
and initialisesbase
withpred_
.pred
template < ViewableRange O > requires constructible - from - range < R , O > constexpr drop_while_view ( O && o , Pred pred )
-
Effects: Initialises
withbase_
, and intialisesview :: all ( std :: forward < O > ( o ))
withpred_
.pred
3.5.2.2. drop_while_view
conversion
constexpr R base () const ;
-
Returns:
.base_
constexpr Pred pred () const ;
-
Returns:
.pred_
3.5.2.3. drop_while_view
begin
constexpr auto begin ();
-
Effects: Equivalent to
.return ranges :: find_if_not ( base_ , std :: ref ( pred_ )); -
_Remarks_: In order to provide the amortized constant time complexity required by the
concept, this function caches the result within theRange
for use on subsequent calls.drop_while_view
3.5.2.4. drop_while_view
end
-
Effects: Equivalent to
.return ranges :: end ( base_ );
3.6. view :: drop_while
The name
denotes a range adaptor object. Let
and
be expressions such that
type
is
. Then, the expression
is expression-equivalent
to:
-
ifdrop_while_view { E , F }
modelsT
, andInputRange
is both an object and modelsF
.IndirectUnaryPredicate -
Otherwise
is ill-formed.view :: drop ( E , F )
3.7. basic_istream_view
3.7.1. Motivation
is an abstraction over a
object, so that it may be used as though
it were an input iterator. It is a great way to populate a container from the get-go, or fill a
container later in its lifetime. This is great, as copy is a standard algorithm that cleanly
communicates that we’re copying something from one range into another. There aren’t any Hidden
SurprisesTM. This is also good when writing generic code, because the generic library
author does not need to care how things are inserted at the end of
, only that they are.
Without
| With
|
---|---|
|
|
The problem with
is that we need to provide a bogus
(or
) every time we want to use it; this acts as the sentinel for
. It is bogus, because the code is equivalent to saying "from the first element of
the istream range until the last element of the istream range", but an
range does not have
a last element. Instead, we denote the end of an istream range to be when the
's failbit is
set. This is otherwise known as the _end-of-stream_ iterator value, but it doesn’t denote a
'past-the-last element' in the same way that call to
does. Because it is the same
for every range, the _end-of-stream_ object may as well be dropped, so that we can write code that
resembles the code below.
auto v = std :: vector ( ranges :: istream_view < int > { std :: cin }); // ... copy ( ranges :: istream_view < int > { std :: cin }, back_inserter ( v ));
This code is cleaner: we are implicitly saying "until our
object fails, insert our
input into the back of
". There is less to read (and type!), and the code is simpler for it.
3.7.2. Interface
template < class T , class CharT = char , class Traits = char_traits < CharT >> concept bool StreamExtractable = see - below ; template < class T , class charT = char , class traits = std :: char_traits < charT >> concept bool StreamInsertable = see - below ; template < Semiregular Val , class CharT , class Traits = char_traits < CharT >> requires StreamExtractable < Val , CharT , Traits > class basic_istream_view : public view_interface < basic_istream_view < Val , CharT , Traits >> { public : basic_istream_view () = default ; explicit constexpr basic_istream_view ( std :: basic_istream < CharT , Traits >& stream ); constexpr auto begin (); constexpr default_sentinel end () const noexcept ; private : struct __iterator ; // exposition-only std :: basic_istream < CharT , Traits >* stream_ ; // exposition-only Val object_ ; // exposition-only };
3.7.2.1. Concept StreamExtractable
template < class T , class CharT = char , class Traits = char_traits < CharT >> concept bool StreamExtractable = requires ( std :: basic_istream < charT , traits >& is , T & t ) { { is >> t } -> Same < std :: basic_istream < charT , traits >>& ; };
-
Remarks:
.std :: addressof ( is ) == std :: addressof ( is << t )
3.7.2.2. Concept StreamInsertable
template < class T , class charT = char , class traits = std :: char_traits < charT >> concept bool StreamInsertable = requires ( std :: basic_ostream < charT , traits >& os , const T & t ) { { os << t } -> Same < std :: basic_ostream < charT , traits >>& ; };
-
Remarks:
.std :: addressof ( os ) == std :: addressof ( os >> t )
3.7.2.3. basic_istream_view
constructor
explicit constexpr basic_istream_view ( std :: basic_istream < CharT , Traits >& stream );
-
Effects: Initialises
tostream_
.std :: addressof ( stream )
3.7.2.4. basic_istream_view
begin
constexpr auto begin ();
-
Effects: Equivalent to
* stream_ >> object_ ; return __iterator { * this };
3.7.2.5. basic_istream_view
end
constexpr default_sentinel end () const noexcept ;
-
Returns:
.default_sentinel {}
3.7.2.6. basic_istream_view :: __iterator
template < class Val , class CharT , class Traits > class basic_istream_view < Val , CharT , Traits >:: __iterator { public : using iterator_category = input_iterator_tag ; using difference_type = std :: ptrdiff_t ; using value_type = Val ; __iterator () = default ; explicit constexpr __iterator ( istream_view < Val >& parent ) noexcept ; __iterator & operator ++ (); void operator ++ ( int ); Val & operator * () const ; friend bool operator == ( __iterator x , default_sentinel ); friend bool operator == ( default_sentinel y , __iterator x ); friend bool operator != ( __iterator x , default_sentinel y ); friend bool operator != ( default_sentinel y , __iterator x ); private : basic_istream_view < Val , CharT , Traits >* parent_ = nullptr ; // exposition-only };
3.7.2.7. basic_istream_view :: __iterator
constructor
explicit constexpr __iterator ( istream_view < Val >& parent ) noexcept ;
-
Effects: Initialises
withparent_
.std :: addressof ( parent_ )
3.7.2.8. basic_istream_view :: __iterator
next
__iterator & operator ++ (); void operator ++ ( int );
-
Effects: Equivalent to
* parent_ -> stream_ >> parent_ -> object_ ;
3.7.2.9. basic_istream_view :: __iterator
value
Val & operator * () const ;
-
Effects: Equivalent to
return parent_ -> value_ ;
3.7.2.10. basic_istream_view :: __iterator
comparison functions
friend bool operator == ( __iterator x , default_sentinel );
-
Effects: Equivalent to
.return !* x . parent_ -> stream_ ;
friend bool operator == ( default_sentinel y , __iterator x );
-
Returns:
.x == y
friend bool operator != ( __iterator x , default_sentinel y );
-
Returns:
.! ( x == y )
friend bool operator != ( default_sentinel y , __iterator x );
-
Returns:
.! ( x == y )
3.8. basic_istream_view
range adaptors
The names
,
,
, and
denote range
adaptors. Let
be an expression and
be a type distinct from
.
-
Then, the expression
is expression-equivalent to:istream_view < T > ( E ) -
ifbasic_istream_view < T , char > ( E )
modelsdecltype (( E ))
andDerivedFrom < std :: istream >
modelsT
.StreamExtractable -
Otherwise
is ill-formed.istream_view < T > ( E ) -
Then, the expression
is expression-equivalent to:wistream_view < T > ( E ) -
ifbasic_istream_view < T , wchar_t > ( E )
modelsdecltype (( E ))
andDerivedFrom < std :: wistream >
modesT
.StreamExtractable -
Otherwise
is ill-formed.wistream_view < T > ( E ) -
Then, the expression
is expression-equivalent to:u16istream_view -
ifbasic_istream_view < T , char16_t > ( E )
modelsdecltype (( E ))
andDerivedFrom < basic_istream < char16_t >>
modelsT
.StreamExtractable -
Otherwise
is ill-formed.u16istream_view < T > ( E ) -
Then, the expression
is expression-equivalent to:u32istream_view -
ifbasic_istream_view < T , char32_t > ( E )
modelsdecltype (( E ))
andDerivedFrom < basic_istream < char32_t >>
modelsT
.StreamExtractable -
Otherwise
is ill-formed.u32istream_view < T > ( E )
3.9. zip_with_view
3.9.1. Motivation
A zip, also known as a [convolution] operation, performs a transformation on multiple input ranges. The typical zip operation transforms several input ranges into a single input range containing a tuple with the ith element from each range, and terminates when the smallest finite range is delimited. The following example has been adapted from [P0836] §2.1.
Current (C++17) | Proposed (C++20) |
---|---|
|
|
The benefits of this proposed approach include:
-
More declared operations, leading to more declarative -- rather than imperative -- style programming.
-
Eliminates state.
-
can be declaredresult
without needing to rely on IILE. (Note the lack of IILE and the non-const
ness in the former).const -
Temporary storage is eliminated, which P0836 §2.1 articulates as beneficial for heterogeneous programming.
is a generalisation of
, such that we can apply an n-ary function in place of
the
s above. The following is an example of how
can refine
when tuples
are not necessary.
vector < float > const x = // ... vector < float > const y = // ... float const a = // ... // ... auto ax = x | view :: transform ([ a ]( auto const x ) noexcept { return a * x ; }); auto saxpy = view :: zip_with ( plus <> {}, ax , y ); auto const result = vector ( begin ( saxpy ), end ( saxpy ));
Another motivating example for using
involves replacing raw loops with algorithms and range
adaptors, but still being able to index the operation in question.
Current (C++17) | Proposed (C++20) |
---|---|
|
|
In the following text,
is implemented in terms of
.
3.9.2. __common_tuple
TODO (released before San Diego).
3.9.3. __iter_zip_with
TODO (released before San Diego).
3.9.4. zip_with_view
TODO (released before San Diego).
3.10. view :: zip_with
The name
denotes a range adaptor object. Let
be a parameter pack, with
as its pack expansion, and let
be an expression. Then, the expression
is expression-equivalent to:
-
, if all parameters in the parameter packzip_with_view { F , std :: forward < Args > ( args )...}
modelremove_cvref_t < Args > ...
, and ifInputRange
modelsF
.RegularInvocable < iter_reference_t < iterator_t < remove_cvref_t < Args >>> ... > -
Otherwise,
is ill-formed.view :: zip_with ( F , std :: forward < Args > ( args )...)
3.11. view :: zip
The name
denotes a range adptor object. Let
be a parameter pack, with
as its pack expansion. Then, the expression
is
expression-equivalent to:
-
, ifview :: zip_with { make_pair , std :: forward < Args > ( args )...}
, and both parameters in the parameter packsizeof ...( Args ) == 2
modelremove_cvref_t < Args > ...
.InputRange -
, ifview :: zip_with { make_tuple , std :: forward < Args > ( args )...}
, and all parameters in the parameter packsizeof ...( Args ) != 2
modelremove_cvref_t < Args > ...
.InputRange -
Otherwise,
is ill-formed.view :: zip ( std :: forward < Args > ( args )...)
3.12. Reviewing iter_value_t
, etc., and introducing range_value_t
, etc.
P1035 also proposes to review
on ranges, and to introduce a new
, if
it is deemed appropriate.
TODO (released before San Diego).