Document number: N4621
Date: 2016-11-27
Project: C++ Extensions for Ranges
Reply-to: Casey Carter <Casey@Carter.net>

1 Acknowledgements

Thanks to everyone who has invested time into reviewing this monster. An especial thanks to the review committee: Marshall Clow and Eric Niebler, who have reviewed most parts of the proposal more than once before undertaking yet another review. Thanks also to Eric Mittelette of Microsoft for translating the TS title to French for the DTS ballot document.

2 New Papers

3 Changes since N4560

commit a580da79192f2c33e862186daf3d2a326b74fa45
Author: Casey Carter 
Date:   Sun Nov 27 12:24:28 2016 -0800

    Front matter for [counted.iterator]

    * Relocate introductory material from [iterators.counted] into [counted.iterator] to be consistent with more recent library wording style.

commit 2f21473fd8d6eb350cb0e11fc9a1c98665a72b95
Author: Casey Carter 
Date:   Sun Nov 27 12:19:21 2016 -0800

    Review: front matter for [move.sentinel]

    * Retitle [iterators.move] as "Move iterators and sentinels."

    * Split the front matter from [iterators.move] out into [move.iterator] and [move.sentinel].

commit 378e5a3e28535ea867abaca1635c8ebff2e86949
Author: Casey Carter 
Date:   Sun Nov 27 11:43:15 2016 -0800

    Review: [utility.swap]/1.2 needs a line break

commit 4de8239a512a93c694bc671f25ce021d5c8d8e4d
Author: Casey Carter 
Date:   Sun Nov 27 11:42:38 2016 -0800

    Review: retitle [alg.find.first.of] "Find first of"

commit ebf0fef9b76d900d11a4fc0512e7ad0ca5335463
Author: Casey Carter <Casey@Carter.net>
Date:   Wed Nov 16 11:32:59 2016 -0800

    [Editorial] Finish applying PR for #210

commit 167efa2920310977a3749ead54fda87757aad03c
Author: Casey Carter <Casey@Carter.net>
Date:   Tue Nov 15 18:43:39 2016 -0800

    Annotate deprecation of rvalue range access.
    Fixes #271.

commit dc8a36d9a6e3ff231c2866ba53d067be4de30c45
Author: Casey Carter <Casey@Carter.net>
Date:   Wed Nov 2 17:25:54 2016 -0700

    Editorial: \tcode section headers where missing.
    Remove reference to proxy iterators and common_type future work which is now integrated.

commit b2c98d1551df129647573984325e7fba3714300c
Author: Eric Niebler <eniebler@boost.org>
Date:   Mon Oct 24 10:06:04 2016 -0700

    update editorial note about xvalues, add back missing indirect_result_of_t

commit cb3a468eaf0db585bd028c7a0708f7a08b686a74
Author: Eric Niebler <eniebler@boost.org>
Date:   Wed Oct 19 16:52:45 2016 -0700

    Integral P0022 into the combined Ranges TS draft

commit 0a6ff444100e1fda01ea216f55bd5f8e8ba8ac76
Author: Casey Carter <Casey@Carter.net>
Date:   Tue Oct 18 14:32:05 2016 -0700

    [Editorial] Strike "purely semantic" note about (Weakly)?EqualityComparable
    Fixes #201.

commit d3f53e542d1f8ced77a6fa02806a9b3b2f23ca5e
Author: Casey Carter <Casey@Carter.net>
Date:   Sat Oct 15 13:33:02 2016 -0700

    Make it VERY clear that this is not (at the moment) a TS working draft

commit 89147921eb840fdafdc8a988fcdd6d2b2274c6c1
Author: Casey Carter <Casey@Carter.net>
Date:   Sat Oct 15 13:07:11 2016 -0700

    Revert "respecify comparison function object types"

    This reverts commit 0f7034436df98da1d9a5ac8fbf4b8ca6081d3797.

commit 5306b154dbad64c3dc67d830e9015766cefed11b
Author: Eric Niebler <eniebler@boost.org>
Date:   Fri Oct 14 13:45:41 2016 -0700

    describes->specifies, more changes from ranges telecon 3

commit 9d428d95cd1ddd233dd2b9f95f1dc229906a51cd
Author: Eric Niebler <eniebler@boost.org>
Date:   Fri Oct 14 13:58:38 2016 -0700

    update the Acknowledgements section

commit 55f81ea62fc5cc925b7d5910f6743a272e827d23
Author: Eric Niebler <eniebler@boost.org>
Date:   Fri Oct 14 13:33:58 2016 -0700

    respecify make_tagged_(pair|tuple) in terms of make_$1 (#220)

commit 1ce501a3b7b64b2ada9e81dcf95a363b4e346906
Author: Eric Niebler <eniebler@boost.org>
Date:   Fri Oct 14 10:26:05 2016 -0700

    integrate Jacksonville review feedback

commit c1519e4ac01549157dddf374c6ec9ac338062142
Author: Casey Carter <Casey@Carter.net>
Date:   Fri Oct 14 11:50:33 2016 -0700

    Last couple of Kona fixes

commit f6ae0bb3c0fee87b0a420eec1fbada90c3f03677
Author: Eric Niebler <eniebler@boost.org>
Date:   Fri Oct 14 10:56:45 2016 -0700

    add missing paragraph number

commit 06aa69e942965a0024da316566734831eeb04b00
Author: Casey Carter <Casey@Carter.net>
Date:   Fri Oct 14 10:44:20 2016 -0700

    Cleanup and integration of P0441 (#217)

commit 2a1db364a5b8a45a126eb1e0d44903843f954e2d
Author: cjdb <cjdb.ns@gmail.com>
Date:   Sat Oct 15 00:54:22 2016 +1100

    Patched markup-reset

commit 893fe1ce4a2afb3f86cad2bcd2136877f2309ba6
Author: Casey Carter <Casey@Carter.net>
Date:   Thu Oct 13 21:23:49 2016 -0700

    [WeaklyIncrementable] Editorial fix

commit 99c3a948b9aad2a68e4554a319ced8c64afad47b
Author: Casey Carter <Casey@Carter.net>
Date:   Thu Oct 13 16:56:18 2016 -0700

    Replace 'requires (' with 'requires(' (#216)

    Fixes caseycarter/stl2#9.

commit 739b3ff8fb6e8915a0bb110f1a2c6f60f402d0d9
Author: Eric Niebler <eniebler@boost.org>
Date:   Thu Oct 13 16:44:08 2016 -0700

    s/template</template </g

commit 3e821f0a4320ca00ff93a3441d14600a809931c3
Author: Eric Niebler <eniebler@boost.org>
Date:   Thu Oct 13 16:41:04 2016 -0700

    space after ... always

commit d50e8309395db95ff3b521b959cb5d902a19c88d
Author: Eric Niebler <eniebler@boost.org>
Date:   Thu Oct 13 14:20:53 2016 -0700

    Markup reset (#213)

    Massive reset of all the markup in the Ranges TS, with thanks to @CaseyCarter and @cjdb.

commit d2a2c6702e639ad8e75530371dfe365a710a6e46
Author: Casey Carter <Casey@Carter.net>
Date:   Thu Oct 13 00:32:39 2016 -0700

    Use "Effects: Equivalent to" to specify distance in [ranges.primitives]
    Fixes #173.

commit 2a14daed5dbefede940e7d8e914127a30abd2fa9
Author: Casey Carter <Casey@Carter.net>
Date:   Thu Oct 13 00:00:45 2016 -0700

    [Editorial] Correct text of [algorithms.general]/15
    Fixes #175.

commit 79e1a7d31c550f81ea7080c9a35c26acef75808d
Author: Casey Carter <Casey@Carter.net>
Date:   Wed Oct 12 17:19:56 2016 -0700

    Change basename of the TS from "D4569" to "ranges"

    * there's no reason to track the document number
    * update document number to D0459R0

commit 889e2f97a58fd2ee11bccac99d1b6562d03c13d3
Author: Christopher Di Bella <cjdb.ns@gmail.com>
Date:   Sat Oct 8 22:55:43 2016 +1100

    Changed v to t in concept Writable

commit 97f0217088a05a1e5eb154572fbab8a08a2137cd
Author: Christopher Di Bella <cjdb.ns@gmail.com>
Date:   Fri Oct 7 21:10:32 2016 +1100

    Final changes from 'ranges review jacksonville.txt'.

commit f375324f848473c00ac138ad9468f4eba0e579fb
Merge: bd5840e dca9128
Author: Christopher Di Bella <cjdb.ns@gmail.com>
Date:   Fri Oct 7 08:33:50 2016 +1100

    Fixing merge issues

commit dca9128e53d53aa40ad1fe78133805d72034ce76
Author: Christopher Di Bella <cjdb.ns@gmail.com>
Date:   Fri Oct 7 08:29:31 2016 +1100

    First seven changes of 'ranges review jacksonville.txt' completed (excludes Writable)

commit bd5840e8920d9ae6364942e24d3f6b80591087aa
Author: Christopher Di Bella <cjdb.ns@gmail.com>
Date:   Sat Oct 1 17:36:51 2016 +1000

    Some changes from ranges-review-jacksonville.txt

commit e54f42643e44016cdcf869e8e4b85dddc4653c2c
Author: Eric Niebler <eniebler@boost.org>
Date:   Tue Sep 27 10:03:56 2016 -0700

    add review feedback notes

commit 555c81f6e7c36b95aad4c26559384787ffa1b2ee
Author: Casey Carter <Casey@Carter.net>
Date:   Thu Sep 8 07:33:56 2016 -0700

    Finish renaming Convertible to ConvertibleTo

commit 9188adda3c5932d7006d32fa123499baa740bf97
Author: Casey Carter <Casey@Carter.net>
Date:   Fri Jan 15 17:59:06 2016 -0600

    Correct "==" to "!=" in [istreambuf.iterator::op!=].

commit 8dac82596015fe05cac7b6f2d08597f165019fce
Author: Casey Carter <Casey@Carter.net>
Date:   Wed Jan 13 01:07:23 2016 -0600

    Remove extraneous "public:" from ostreambuf_iterator.

commit f43cf84a1c43f07a71045212f832bcdb408ccaad
Author: Casey Carter <Casey@Carter.net>
Date:   Tue Dec 15 15:20:27 2015 -0600

    Merge MoveWritable and Writable.
    * Writable<O, T> is satisfied if *o = v is a valid expression for an object o of
      type O and an expression v such that decltype(v) is T.

    * IndirectlyMovable<In, Out> requires Writable<Out, rvalue_reference_t<In>>
      (Spelled as Writable<Out, decltype(std::move(declval<reference_t<In>>()))>
       until we incorporate P0022.)

    * IndirectlyCopyable<In, Out> refines IndirectlyMovable with
      Writable<Out, reference_t<In>>. In other words, "copy" may actually be a move
      for move_iterators which are now unbroken.

    * Writable's sensitivity to cv/ref qualifiers cascades to OutputIterator and
      OutputRange. The constraint previously spelled OutputIterator<T> is now
      OutputIterator<const T&>. It is now possible to express an OutputIterator or
      OutputRange that accepts a move-only type.

    * This characterization in terms of reference types instead of value types will
      almost certainly ease the integration of P0022's proxy iterators.

    Define concepts Indirectly(Copy|Mov)ableStorable

    * Refinements of Indirectly(Copy|Mov)able that enable performing the transfer
      through an intermediate object. The "Storable" variants are equivalent to the
      reformulations in P0022, but given distinct names to avoid overconstraining
      algorithms that don't require the additional capabilities.

    * Relocate Indirectly(Copy|Mov|Swapp)able to [commonalgoreq].

    * Permutable requires IndirectlySwappable and IndirectlyMovableStorable
      instead of Movable and IndirectlyMovable.  (One of the iter_swap
      implementations will use IMS as well when P0022 is integrated.)

    * unique_copy requires in part (ForwardIterator<I>() || ForwardIterator<O>() ||
      IndirectlyCopyableStorable<I, O>()); it is the only user of ICS.

    Remove concept MoveMergeable.
    * Strike algorithms merge_move and partition_move.

    Specify move_sentinel. Fixes ericniebler/stl2#159.

commit 78b3874a8e6d7ad4d377c4bf6ecc65d8eb33f44d
Author: Casey Carter <Casey@Carter.net>
Date:   Fri Dec 11 12:32:53 2015 -0600

    Incrementable requires EqualityComparable; ForwardIterator need not require it directly.

commit e998199761aea40551662e9677fe72a88a1a212c
Author: Casey Carter <Casey@Carter.net>
Date:   Sat Nov 14 12:07:23 2015 -0600

        Sharpen semantics of Iterators and Sentinels:
        * Specify the required definition space of comparison
          operations on Iterators and Sentinels.
        * Rename SizedIteratorRange to SizedSentinel, factor out
          SizedIterator. Locate both concepts immediately after
          Iterator and Sentinel, respectively. (The section
          [iteratorranges] no longer exists.)
        * CommonSizedIteratorRange has *not* been renamed.
        * Rename disable_sized_range to disable_sized, make it a
          variable template, and relocate to [iterators.sizediterator].
          disable_sized serves as an opt out trait for both
          SizedIterator and SizedRange (and indirectly SizedSentinel,
          since it requires its iterator type to satisfy SizedIterator).
        * Respecify distance and advance in light of the updated
          iterator/sentinel/sized semantics.

        Closes caseycarter/stl2#13.
        Closes caseycarter/stl2#20.
        Touches on ericneibler/stl2#88.
        Closes ericniebler/stl2#107.
        Closes ericniebler/stl2#131.

        Review comments:
        * Reintegrate SizedIterator into SizedSentinel
        * Split disable_sized into disable_sized_sentinel and
          disable_sized_range
        * ranges::size also obeys disable_sized_range

        EqualityComparable changes.
        * Introduce expos concept "BaseEqualityComparable<T, U>" to
          encapsulate the requirements that == and != must have the
          same definition space and be complements of each other;
          all variants of EqualityComparable refine it.
        * EC<T> is a purely semantic refinement of BaseEC<T, T>.
        * Introduce concept "BikeshedEqualityComparable" to specify
          the relationship between two types that individually need
          not satisfy EC, but have a cross-type == that is equality
          preserving. Is a purely semantic refinement of
          BaseEC<T,U> && BaseEC<U, T>
        * EC<T, U> requirements are simplified by refining
          BikeshedEC<T, U>.

        Relax sentinel:
        * Sentinel now relates a WeakIterator and a Semiregular via
          BikeshedEqualityComparable.
        * Specify the definition space of i == s and relate it to
          the property "denotes a range," replacing the "domain of
          ==" discussion for Iterator.
        * Iterator is now simply a type I that satisfies
          Sentinel<I, I>(), i.e., is simultaneously a WeakIterator
          and its own sentinel.
        * Simplify SizedSentinel correspondingly. If s == s and
          i == i aren't required, s - s and i - i shouldn't be
          either. Consequently SizedSentinel<S, I>() no longer
          implies SizedSentinel<I, I>(), which (a) would be "weird"
          for a WeakIterator I, and (b) surprisingly has no effect
          on the rest of the specification. Finding the size of a
          range in constant time is incredibly useful; determining
          the distance between two arbitrary iterators in constant
          time only has value when the iterators are RandomAccess.
          (In any case the old semantic is still available by
          additionally requiring SizedSentinel<I, I>().)
        * Relax iterator operations advance et al to work with
          WeakIterator / Sentinel pairs.
        * Respecify common_iterator to require an Iterator and
          Sentinel, removing the now unnecessary exposition-only
          concepts __WeaklyEqualityComparable and __WeakSentinel.
          Specify a partial specialization of value_type for
          common_iterators that wrap InputIterators instead of the
          member value_type so that common_iterator<OutputIterator,
          ...> works. Respecify ==, !=, and - inline with the new
          Sentinel and SizedSentinel semantics, remove CommonSized
          IteratorRange and __common_difference_type.
        * Remove relational operators for default_sentinel and
          unreachable.

        Relax:
        * Mergeable and MoveMergeable only require WeakInputIterator
        * Simplify reverse_iterator declarations
        * Simplify move_iterator declarations
        * common_iterator only requires WeakIterator
        * Simplify counted_iterator declarations

        Weak ranges:
        * begin/cbegin/rbegin/crbegin require WeakIterator instead
          of Iterator
        * Remove OutputIterator, rename WeakOutputIterator to
          OutputIterator.
        * Remove InputIterator, rename WeakInputIterator to
          InputIterator.

        Closes ericniebler/stl2#6
        Closes caseycarter/cmcstl2#15

        Merge Iterator and WeakIterator.
        Remove common_type specializations.

        Rationale for iterator/sentinel design change.
        Coalesce __BaseEqualityComparable and BikeshedEqualityComparable.
        Update iterator.general description of ranges.
        Remove counted_iterator ordering operators with default_sentinel,
        and unreachable's ordering operators.

        Address review comments.
        Rename "BikeshedEqualityComparable" to "WeaklyEqualityComparable."

commit eb7cf62cb286c76eb1780d316fb685c61781eb5c
Author: Eric Niebler <eniebler@boost.org>
Date:   Wed Dec 9 15:39:46 2015 -0800

    New document numbers

commit 4a263eb734ab55acb3a88c831167bfb91ad6c990
Author: Casey Carter <Casey@Carter.net>
Date:   Wed Dec 9 09:15:30 2015 -0600

    Merge{_move} fixes:
    * Require the output iterator to satisfy WeaklyIncrementable instead of Incrementable.
    * Specify operational semantics in place of the ill-formed (and possibly meaningless) postcondition.

commit 470a020159980a963342a9ad12df9cc81abd8b6e
Author: Eric Niebler <eniebler@boost.org>
Date:   Mon Dec 7 14:25:46 2015 -0800

    common_iterator doesn't have a value_type nested typedef

commit 05093ad77de2bf713ad5832fbf71f3b9119e67f6
Author: Eric Niebler <eniebler@boost.org>
Date:   Wed Dec 2 12:03:17 2015 -0800

    The associative containers are not views. Fix typos.

commit 0f7034436df98da1d9a5ac8fbf4b8ca6081d3797
Author: Eric Niebler <eniebler@boost.org>
Date:   Wed Nov 18 10:56:54 2015 -0800

    respecify comparison function object types

commit b806abb60e91f3015ec29833b499e5a5c4bbf83f
Author: Casey Carter <Casey@Carter.net>
Date:   Fri Nov 13 15:23:56 2015 -0600

    Strong semantics for Assignable.
    * Remove the default for Assignable's second parameter.
    * Remove prose requirements from Copyable and Movable, they are now provided by Assignable.
    * exchange and default-swap both now require MoveConstructible and Assignable instead of Movable.
    * Movable can now explicitly require Swappable, and all is right with the world.
    * Use Assignable instead of is_assignable in the specification of advance(I, S) to ensure the post-condition (i == s).

commit 6c3c5e724b99992b7ed7f75cdfb95d5802d34d17
Author: Casey Carter <Casey@Carter.net>
Date:   Thu Nov 12 13:46:09 2015 -0600

    Function becomes Callable:
    * Import invoke from the WP. I've numbered its section 20.9.3 as in the WP, which could cause confusion since 20.9.3 is [refwrap] in C++14.
    * Change section number of [comparisons] to 20.9.5 to agree with C++14.
    * Despite that they are equivalent, replace occurrences of \textit{INVOKE} with invoke because \textit{INVOKE} is hard on the eyes.
    * Rename all sections in concepts.lib.functions to concepts.lib.callables. Retitle the section "Callable concepts".
    * Rename concept Function to Callable, change its required expression to invoke(f, args...)
    * Rename concept RegularFunction to RegularCallable.
    * Remove section indirectcallables.as_function_t, specify the IndirectCallableFoo<F, ...Is> concepts to require Foo<F, value_type_t<Is>...>.
    * Update indirect_result_of and projected appropriately.
    * Require the type of a customization point object to satisfy Callable instead of Function. Avoid confusion about invoke by explicitly requiring a customization point object to also be a function object.
    * Cleanup the specification of the generate algorithm family. (I had to touch it because of the invoke change, and thought it was overcomplicated. fill could use a similar treatment.)

    Drive-by fixes:
    * Fix occurrence of type/reference confusion in the specification of indirect_result_of. (We don't want to constrain e.g. less<>& to satisfy IndirectCallable, we want to constrain less<>.)
    * Simplify concept UniformRandomNumberGenerator, reorder requirements for shuffle properly.

commit 7fa3c0545a58613127a0179d9c45637a790fdfa2
Author: Casey Carter <Casey@Carter.net>
Date:   Mon Nov 9 17:22:38 2015 -0600

    New paragraphs for [alg.general]:
    * /16 requiring implementations to resolve range/iterator ambiguity
    * /17 makes the number and order of template parameters unspecified.
    * /18 makes it unspecified when and if the algorithm arguments are initialized with the argument expressions.

commit 8fbaaeea128a6297f01f7b78f7bd98e4b7dcbbee
Author: Casey Carter <Casey@Carter.net>
Date:   Fri Nov 6 18:45:09 2015 -0600

    Minor cleanup:
    * Consistency in value_type spec
    * Cleanup min, max, and minmax requirements
    * tell N4560.tex that the bibliography is named N4560 instead of N4382
    * Add () on RegularFunction in the spec for projected

commit 6c4abef8581318e122b71722f7d6a9da2ba18ed5
Author: Casey Carter <Casey@Carter.net>
Date:   Fri Nov 6 18:11:06 2015 -0600

    Simplify ranges::data