Range concepts (details)
========================

.. contents:: Table of Contents
    :local:


.. _concept-details-Range:

Range
-----

.. cpp:concept:: template<typename Rng> Range

    #. Refines the :cpp:concept:`template <typename T> Semiregular` concept.
    #. ``Rng`` provides methods ``begin``, ``end``, ``cbegin`` and ``cend``.

    **Notation**

    .. cpp:type::   value_type = Rng::value_type
    .. cpp:var::    Rng rng
    .. cpp:var::    Rng rng_cpy
    .. cpp:var::    const Rng crng

    **Valid Expressions**

    - :cpp:expr:`rng()` returns an instance of :cpp:expr:`Rng`.
    - :cpp:expr:`crng()` returns an instance of :cpp:expr:`const Rng`.

    - :cpp:expr:`rng_cpy(rng)` returns an instance of :cpp:expr:`Rng`.
    - :cpp:expr:`rng_cpy(crng)` returns an instance of :cpp:expr:`Rng`.
    - :cpp:expr:`rng_cpy(move(rng))` returns an instance of :cpp:expr:`Rng`.

    - :cpp:expr:`rng_cpy = rng` returns an instance of :cpp:expr:`Rng&`.
    - :cpp:expr:`rng_cpy = crng` returns an instance of :cpp:expr:`Rng&`.
    - :cpp:expr:`rng_cpy = move(rng)` returns an instance of :cpp:expr:`Rng&`.

    - :cpp:expr:`rng.begin()` is valid and return type is implementation defined.
    - :cpp:expr:`rng.end()` is valid and return type is implementation defined.
    - :cpp:expr:`crng.cbegin()` is valid and return type is implementation defined.
    - :cpp:expr:`crng.cend()` is valid and return type is implementation defined.

    **Possible implementation**

    .. code:: cpp

        template<typename R, Rng = remove_cvref<R>>
        concept Range = Semiregular<Rng> &&

                        requires(Rng rng, const Rng crng) {
                            { rng.begin() }     -> /* implementation defined */;
                            { rng.end() }       -> /* implementation defined */;
                            { crng.cbegin() }   -> /* implementation defined */;
                            { crng.cend() }     -> /* implementation defined */;
                        };


.. _concept-details-SizedRange:

SizedRange
----------

.. cpp:concept:: template<typename SRng> SizedRange

    #. Refines the :cpp:concept:`template <typename SRng> Range` concept.
    #. ``SRng::iterator_type`` provides method ``size``.

    **Notation**

    .. cpp:type::   iterator_type = SRng::iterator_type
    .. cpp:type::   difference_type = iterator_type::difference_type
    .. cpp:var::    const SRng csrng

    **Valid Expressions**

    - :cpp:expr:`csrng.size()` returns an instance of :cpp:expr:`difference_type`.

    **Possible implementation**

    .. code:: cpp

        template <typename Rng>
        inline constexpr bool disable_sized_range = /* implementation defined */;

        template<typename R, SRng = remove_cvref<R>>
        concept SizedRange =    Range<SRng> &&
                                !disable_sized_range<SRng> &&

                                requires(const SRng csrng) {
                                    { csrng.size() } -> Rng::iterator_type::difference_type;
                                };



.. _concept-details-InputRange:

InputRange
----------

.. cpp:concept:: template<typename IRng> InputRange

    #. Refines the :cpp:concept:`template <typename Rng> Range` concept.
    #. ``IRng::iterator_type`` models the :cpp:concept:`template <typename I> InputIterator` concept. 
    #. ``IRng::iterator_type`` provides ``operator++`` (pre- and post-fix) and ``operator*`` (dereference read-only).

    **Notation**

    .. cpp:type::   value_type = IRng::value_type
    .. cpp:type::   iterator_type = IRng::iterator_type
    .. cpp:var::    iterator_type it
    .. cpp:var::    const iterator_type cit

    **Valid Expressions**

    - :cpp:expr:`++it` returns an instance of :cpp:expr:`iterator_type&`.
    - :cpp:expr:`it++` is not requires to be equality preserving.
    - :cpp:expr:`*cit` return-type can be deduced by :cpp:expr:`auto&&`.

    **Possible implementation**

    .. code:: cpp

        template<typename R, Rng = remove_cvref<R>>
        concept InputRange =    Range<Rng> &&

                                requires {
                                    typename Rng::iterator_type;
                                } &&

                                InputIterator<Rng::iterator_type>;


.. _concept-details-OutputRange:

OutputRange
-----------

.. cpp:concept:: template<typename ORng, typename T> OutputRange

    #. Refines the :cpp:concept:`template <typename Rng> Range` concept.
    #. ``ORng::iterator_type`` models the :cpp:concept:`template <typename I, typename T> OutputIterator` concept.
    #. ``ORng::iterator_type`` provides ``operator++`` (pre- and post-fix) and ``operator*`` (dereference writable).

    **Notation**

    .. cpp:type::   iterator_type = ORng::iterator_type
    .. cpp:type::   reference = iterator_type::reference
    .. cpp:var::    iterator_type o
    .. cpp:var::    const iterator_type co
    .. cpp:var::    T t

    **Valid Expressions**

    - :cpp:expr:`++o` returns an instance of :cpp:expr:`FwdRng&`.
    - :cpp:expr:`o++` is not requires to be equality preserving.
    - :cpp:expr:`*co` return-type can be deduced by :cpp:expr:`auto&&`.
    - :cpp:expr:`*o++ = forward<T>(t)` is not requires to be equality preserving.
    - :cpp:expr:`*o = forward<T>(t)` is not requires to be equality preserving.
    - :cpp:expr:`*forward<iterator_type>(o) = forward<T>(t)` is not requires to be equality preserving.
    - :cpp:expr:`const_cast<const reference&&>(*o) = forward<T>(t)` is not requires to be equality preserving.
    - :cpp:expr:`const_cast<const reference&&>(*forward<iterator_type>(o)) = forward<T>(t)` is not requires to be equality preserving.

    **Possible implementation**

    .. code:: cpp

        template<typename R, typename T, Rng = remove_cvref<R>>
        concept OutputRange =   Range<Rng> &&

                                requires {
                                    typename Rng::iterator_type;
                                } &&

                                OuputIterator<Rng::iterator_type, T>;


.. _concept-details-ForwardRange:

ForwardRange
------------

.. cpp:concept:: template<typename FwdRng> ForwardRange

    #. Refines the :cpp:concept:`template <typename IRng> InputRange` concept.
    #. ``FwdRng::iterator_type`` models the :cpp:concept:`template <typename I> ForwardIterator` concept.
    #. ``FwdRng`` is consistant with ``value_type`` from ``iterator_type``.
    #. ``FwdRng::iterator_type`` provides methods ``operator++``.

    **Notation**

    .. cpp:type::   iterator_type = FwdRng::iterator_type
    .. cpp:var::    iterator_type it
    .. cpp:var::    const iterator_type lhs
    .. cpp:var::    const iterator_type rhs

    **Valid Expressions**

    - :cpp:expr:`lhs == rhs` return-type models :cpp:concept:`template<typename B> Boolean`.
    - :cpp:expr:`lhs != rhs` return-type models :cpp:concept:`template<typename B> Boolean`.
    - :cpp:expr:`rhs == lhs` return-type models :cpp:concept:`template<typename B> Boolean`.
    - :cpp:expr:`rhs != lhs` return-type models :cpp:concept:`template<typename B> Boolean`.

    - :cpp:expr:`it++` returns an instance of :cpp:expr:`iterator_type&&`

    **Possible implementation**

    .. code:: cpp

        template<typename R, FwdRng = remove_cvref<R>>
        concept ForwardRange =  InputRange<FwdRng> &&
                                ForwardIterator<FwdRng::iterator_type> &&

                                requires {
                                    typename FwdRng::value_type;
                                } &&

                                Same<FwdRng::value_type, FwdRng::iterator_type::value_type>;


.. _concept-details-BidirectionalRange:

BidirectionalRange
------------------

.. cpp:concept:: template<typename BidirRng> BidirectionalRange

    #. Refines the :cpp:concept:`template <typename Rng> ForwardRange` concept.
    #. ``BidirRng::iterator_type`` models the :cpp:concept:`template <typename I> BidirectionalIterator` concept.
    #. ``BidirRng::iterator_type`` provides methods ``operator--`` (postfix and prefix).
    #. ``BidirRng`` provides methods ``rbegin``, ``rend``, ``crbegin`` and ``crend``.

    **Notation**

    .. cpp:type::   iterator_type = BidirRng::iterator_type
    .. cpp:var::    iterator_type it
    .. cpp:var::    BidirRng bidirrng
    .. cpp:var::    const BidirRng cbidirrng

    **Valid Expressions**

    - :cpp:expr:`--it` returns an instance of :cpp:expr:`iterator_type&`.
    - :cpp:expr:`it--` returns an instance of :cpp:expr:`iterator_type&&`.

    - :cpp:expr:`bidirrng.rbegin()` is valid and return type is implementation defined.
    - :cpp:expr:`bidirrng.rend()` is valid and return type is implementation defined.
    - :cpp:expr:`cbidirrng.crbegin()` is valid and return type is implementation defined.
    - :cpp:expr:`cbidirrng.crend()` is valid and return type is implementation defined.

    **Possible implementation**

    .. code:: cpp

        template<typename R, BidirRng = remove_cvref<R>>
        concept BidirectionalRange =    ForwardRange<BidirRng> &&
                                        BidirectionalIterator<BidirRng::iterator_type> &&

                                        requires(BidirRng bidirrng, const BidirRng cbidirrng) {
                                            { bidirrng.rbegin() }   -> /* implementation defined */;
                                            { bidirrng.rend() }     -> /* implementation defined */;
                                            { cbidirrng.crbegin() } -> /* implementation defined */;
                                            { cbidirrng.crend() }   -> /* implementation defined */;
                                        };


.. _concept-details-RandomAccessRange:

RandomAccessRange
-----------------

.. cpp:concept:: template<typename RndAccRng> RandomAccessRange

    #. Refines the :cpp:concept:`template <typename Rng> BidirectionalRange` concept.
    #. ``RndAccRng::iterator_type`` models the :cpp:concept:`template <typename I> RandomAccessIterator` concept.
    #. ``RndAccRng::iterator_type`` provides methods ``operator+=``, ``operator+``, ``operator-=``, ``operator-`` and ``operator[]``.

    **Notation**

    .. cpp:type::   iterator_type = RndAccRng::iterator_type
    .. cpp:type::   difference_type = iterator_type::difference_type
    .. cpp:var::    iterator_type it
    .. cpp:var::    const iterator_type cit
    .. cpp:var::    const iterator_type lhs
    .. cpp:var::    const iterator_type rhs
    .. cpp:var::    difference_type n

    **Valid Expressions**

    - :cpp:expr:`lhs < rhs` return-type models :cpp:concept:`template<typename B> Boolean`.
    - :cpp:expr:`lhs > rhs` return-type models :cpp:concept:`template<typename B> Boolean`.
    - :cpp:expr:`lhs <= rhs` return-type models :cpp:concept:`template<typename B> Boolean`.
    - :cpp:expr:`lhs >= rhs` return-type models :cpp:concept:`template<typename B> Boolean`.

    - :cpp:expr:`it += n` returns an instance of :cpp:expr:`iterator_type&`.
    - :cpp:expr:`cit + n` returns an instance of :cpp:expr:`iterator_type&&`.
    - :cpp:expr:`n + cit` returns an instance of :cpp:expr:`iterator_type&&`.
    - :cpp:expr:`it -= n` returns an instance of :cpp:expr:`iterator_type&`.
    - :cpp:expr:`cit - n` returns an instance of :cpp:expr:`iterator_type&&`.
    - :cpp:expr:`cit[n]` returns an instance of :cpp:expr:`iterator_type::reference`.

    **Possible implementation**

    .. code:: cpp

        template<typename R, RndAccRng = remove_cvref<R>>
        concept RandomAccessRange = BidirectionalRange<RndAccRng> &&
                                    RandomAccessIterator<RndAccRng::iterator_type>;