boost/stl_interfaces/sequence_container_interface.hpp

0001 // Copyright (C) 2019 T. Zachary Laine
0002 //
0003 // Distributed under the Boost Software License, Version 1.0. (See
0004 // accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006 #ifndef BOOST_STL_INTERFACES_CONTAINER_INTERFACE_HPP
0007 #define BOOST_STL_INTERFACES_CONTAINER_INTERFACE_HPP
0008
0009 #include <boost/stl_interfaces/reverse_iterator.hpp>
0010
0011 #include <boost/assert.hpp>
0012 #include <boost/config.hpp>
0013
0014 #include <algorithm>
0015 #include <stdexcept>
0016 #include <cstddef>
0017
0018
0019 namespace boost { namespace stl_interfaces { namespace detail {
0020
0021     template<typename T, typename SizeType>
0022     struct n_iter : iterator_interface<
0023 #if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS
0024                         n_iter<T, SizeType>,
0025 #endif
0026                         std::random_access_iterator_tag,
0027                         T>
0028     {
0029         n_iter() : x_(nullptr), n_(0) {}
0030         n_iter(T const & x, SizeType n) : x_(&x), n_(n) {}
0031
0032         T const & operator*() const { return *x_; }
0033         constexpr std::ptrdiff_t operator-(n_iter other) const noexcept
0034         {
0035             return std::ptrdiff_t(n_) - std::ptrdiff_t(other.n_);
0036         }
0037         n_iter & operator+=(std::ptrdiff_t offset)
0038         {
0039             n_ += offset;
0040             return *this;
0041         }
0042
0043     private:
0044         T const * x_;
0045         SizeType n_;
0046     };
0047
0048     template<typename T, typename SizeType>
0049     constexpr auto make_n_iter(T const & x, SizeType n) noexcept(
0050         noexcept(n_iter<T, SizeType>(x, n)))
0051     {
0052         using result_type = n_iter<T, SizeType>;
0053         return result_type(x, SizeType(0));
0054     }
0055     template<typename T, typename SizeType>
0056     constexpr auto make_n_iter_end(T const & x, SizeType n) noexcept(
0057         noexcept(n_iter<T, SizeType>(x, n)))
0058     {
0059         return n_iter<T, SizeType>(x, n);
0060     }
0061
0062     template<typename Container>
0063     std::size_t fake_capacity(Container const & c)
0064     {
0065         return SIZE_MAX;
0066     }
0067     template<
0068         typename Container,
0069         typename Enable = decltype(
0070             std::size_t() = std::declval<Container const &>().capacity())>
0071     std::size_t fake_capacity(Container const & c)
0072     {
0073         return c.capacity();
0074     }
0075
0076 }}}
0077
0078 namespace boost { namespace stl_interfaces { BOOST_STL_INTERFACES_NAMESPACE_V1 {
0079
0080     /** A CRTP template that one may derive from to make it easier to define
0081         container types.
0082
0083         The template parameter `D` for `sequence_container_interface` may be
0084         an incomplete type. Before any member of the resulting specialization
0085         of `sequence_container_interface` other than special member functions
0086         is referenced, `D` shall be complete; shall model
0087         `std::derived_from<sequence_container_interface<D>>`,
0088         `std::semiregular`, and `std::forward_range`; and shall contain all
0089         the nested types required in Table 72: Container requirements and, for
0090         those whose iterator nested type models `std::bidirectinal_iterator`,
0091         those in Table 73: Reversible container requirements.
0092
0093         For an object `d` of type `D`, a call to `std::ranges::begin(d)` sxhall
0094         not mutate any data members of `d`, and `d`'s destructor shall end the
0095         lifetimes of the objects in `[std::ranges::begin(d),
0096         std::ranges::end(d))`. */
0097     template<
0098         typename Derived,
0099         element_layout Contiguity = element_layout::discontiguous
0100 #ifndef BOOST_STL_INTERFACES_DOXYGEN
0101         ,
0102         typename E = std::enable_if_t<
0103             std::is_class<Derived>::value &&
0104             std::is_same<Derived, std::remove_cv_t<Derived>>::value>
0105 #endif
0106         >
0107     struct sequence_container_interface;
0108
0109     namespace v1_dtl {
0110         template<typename Iter>
0111         using in_iter = std::is_convertible<
0112             typename std::iterator_traits<Iter>::iterator_category,
0113             std::input_iterator_tag>;
0114
0115         template<typename D, typename = void>
0116         struct clear_impl
0117         {
0118             static constexpr void call(D & d) noexcept {}
0119         };
0120         template<typename D>
0121         struct clear_impl<D, void_t<decltype(std::declval<D>().clear())>>
0122         {
0123             static constexpr void call(D & d) noexcept { d.clear(); }
0124         };
0125
0126         template<typename D, element_layout Contiguity>
0127         void derived_container(sequence_container_interface<D, Contiguity> const &);
0128     }
0129
0130     template<
0131         typename Derived,
0132         element_layout Contiguity
0133 #ifndef BOOST_STL_INTERFACES_DOXYGEN
0134         ,
0135         typename E
0136 #endif
0137         >
0138     struct sequence_container_interface
0139     {
0140 #ifndef BOOST_STL_INTERFACES_DOXYGEN
0141     private:
0142         constexpr Derived & derived() noexcept
0143         {
0144             return static_cast<Derived &>(*this);
0145         }
0146         constexpr const Derived & derived() const noexcept
0147         {
0148             return static_cast<Derived const &>(*this);
0149         }
0150         constexpr Derived & mutable_derived() const noexcept
0151         {
0152             return const_cast<Derived &>(static_cast<Derived const &>(*this));
0153         }
0154 #endif
0155
0156     public:
0157         template<typename D = Derived>
0158         constexpr auto empty() noexcept(
0159             noexcept(std::declval<D &>().begin() == std::declval<D &>().end()))
0160             -> decltype(
0161                 std::declval<D &>().begin() == std::declval<D &>().end())
0162         {
0163             return derived().begin() == derived().end();
0164         }
0165         template<typename D = Derived>
0166         constexpr auto empty() const noexcept(noexcept(
0167             std::declval<D const &>().begin() ==
0168             std::declval<D const &>().end()))
0169             -> decltype(
0170                 std::declval<D const &>().begin() ==
0171                 std::declval<D const &>().end())
0172         {
0173             return derived().begin() == derived().end();
0174         }
0175
0176         template<
0177             typename D = Derived,
0178             element_layout C = Contiguity,
0179             typename Enable = std::enable_if_t<C == element_layout::contiguous>>
0180         constexpr auto data() noexcept(noexcept(std::declval<D &>().begin()))
0181             -> decltype(std::addressof(*std::declval<D &>().begin()))
0182         {
0183             return std::addressof(*derived().begin());
0184         }
0185         template<
0186             typename D = Derived,
0187             element_layout C = Contiguity,
0188             typename Enable = std::enable_if_t<C == element_layout::contiguous>>
0189         constexpr auto data() const
0190             noexcept(noexcept(std::declval<D const &>().begin()))
0191                 -> decltype(std::addressof(*std::declval<D const &>().begin()))
0192         {
0193             return std::addressof(*derived().begin());
0194         }
0195
0196         template<typename D = Derived>
0197         constexpr auto size()
0198 #if !BOOST_CLANG
0199             noexcept(noexcept(
0200                 std::declval<D &>().end() - std::declval<D &>().begin()))
0201 #endif
0202             -> decltype(typename D::size_type(
0203                 std::declval<D &>().end() - std::declval<D &>().begin()))
0204         {
0205             return derived().end() - derived().begin();
0206         }
0207         template<typename D = Derived>
0208         constexpr auto size() const noexcept(noexcept(
0209             std::declval<D const &>().end() -
0210             std::declval<D const &>().begin()))
0211             -> decltype(typename D::size_type(
0212 #if !BOOST_CLANG
0213                 std::declval<D const &>().end() -
0214                 std::declval<D const &>().begin()
0215 #endif
0216                 ))
0217         {
0218             return derived().end() - derived().begin();
0219         }
0220
0221         template<typename D = Derived>
0222         constexpr auto front() noexcept(noexcept(*std::declval<D &>().begin()))
0223             -> decltype(*std::declval<D &>().begin())
0224         {
0225             return *derived().begin();
0226         }
0227         template<typename D = Derived>
0228         constexpr auto front() const
0229             noexcept(noexcept(*std::declval<D const &>().begin()))
0230                 -> decltype(*std::declval<D const &>().begin())
0231         {
0232             return *derived().begin();
0233         }
0234
0235         template<typename D = Derived>
0236         constexpr auto push_front(typename D::value_type const & x) noexcept(
0237             noexcept(std::declval<D &>().emplace_front(x)))
0238             -> decltype((void)std::declval<D &>().emplace_front(x))
0239         {
0240             derived().emplace_front(x);
0241         }
0242
0243         template<typename D = Derived>
0244         constexpr auto push_front(typename D::value_type && x) noexcept(
0245             noexcept(std::declval<D &>().emplace_front(std::move(x))))
0246             -> decltype((void)std::declval<D &>().emplace_front(std::move(x)))
0247         {
0248             derived().emplace_front(std::move(x));
0249         }
0250
0251         template<typename D = Derived>
0252         constexpr auto pop_front() noexcept -> decltype(
0253             std::declval<D &>().emplace_front(
0254                 std::declval<typename D::value_type &>()),
0255             (void)std::declval<D &>().erase(std::declval<D &>().begin()))
0256         {
0257             derived().erase(derived().begin());
0258         }
0259
0260         template<
0261             typename D = Derived,
0262             typename Enable = std::enable_if_t<
0263                 v1_dtl::decrementable_sentinel<D>::value &&
0264                 v1_dtl::common_range<D>::value>>
0265         constexpr auto
0266         back() noexcept(noexcept(*std::prev(std::declval<D &>().end())))
0267             -> decltype(*std::prev(std::declval<D &>().end()))
0268         {
0269             return *std::prev(derived().end());
0270         }
0271         template<
0272             typename D = Derived,
0273             typename Enable = std::enable_if_t<
0274                 v1_dtl::decrementable_sentinel<D>::value &&
0275                 v1_dtl::common_range<D>::value>>
0276         constexpr auto back() const
0277             noexcept(noexcept(*std::prev(std::declval<D const &>().end())))
0278                 -> decltype(*std::prev(std::declval<D const &>().end()))
0279         {
0280             return *std::prev(derived().end());
0281         }
0282
0283         template<typename D = Derived>
0284         constexpr auto push_back(typename D::value_type const & x) noexcept(
0285             noexcept(std::declval<D &>().emplace_back(x)))
0286             -> decltype((void)std::declval<D &>().emplace_back(x))
0287         {
0288             derived().emplace_back(x);
0289         }
0290
0291         template<typename D = Derived>
0292         constexpr auto push_back(typename D::value_type && x) noexcept(
0293             noexcept(std::declval<D &>().emplace_back(std::move(x))))
0294             -> decltype((void)std::declval<D &>().emplace_back(std::move(x)))
0295         {
0296             derived().emplace_back(std::move(x));
0297         }
0298
0299         template<typename D = Derived>
0300         constexpr auto pop_back() noexcept -> decltype(
0301             std::declval<D &>().emplace_back(
0302                 std::declval<typename D::value_type>()),
0303             (void)std::declval<D &>().erase(
0304                 std::prev(std::declval<D &>().end())))
0305         {
0306             derived().erase(std::prev(derived().end()));
0307         }
0308
0309         template<typename D = Derived>
0310         constexpr auto operator[](typename D::size_type n) noexcept(
0311             noexcept(std::declval<D &>().begin()[n]))
0312             -> decltype(std::declval<D &>().begin()[n])
0313         {
0314             return derived().begin()[n];
0315         }
0316         template<typename D = Derived>
0317         constexpr auto operator[](typename D::size_type n) const
0318             noexcept(noexcept(std::declval<D const &>().begin()[n]))
0319                 -> decltype(std::declval<D const &>().begin()[n])
0320         {
0321             return derived().begin()[n];
0322         }
0323
0324         template<typename D = Derived>
0325         constexpr auto at(typename D::size_type i)
0326             -> decltype(std::declval<D &>().size(), std::declval<D &>()[i])
0327         {
0328             if (derived().size() <= i) {
0329                 throw std::out_of_range(
0330                     "Bounds check failed in sequence_container_interface::at()");
0331             }
0332             return derived()[i];
0333         }
0334
0335         template<typename D = Derived>
0336         constexpr auto at(typename D::size_type i) const -> decltype(
0337             std::declval<D const &>().size(), std::declval<D const &>()[i])
0338         {
0339             if (derived().size() <= i) {
0340                 throw std::out_of_range(
0341                     "Bounds check failed in sequence_container_interface::at()");
0342             }
0343             return derived()[i];
0344         }
0345
0346         template<typename D = Derived, typename Iter = typename D::const_iterator>
0347         constexpr Iter begin() const
0348             noexcept(noexcept(std::declval<D &>().begin()))
0349         {
0350             return Iter(mutable_derived().begin());
0351         }
0352         template<typename D = Derived, typename Iter = typename D::const_iterator>
0353         constexpr Iter end() const noexcept(noexcept(std::declval<D &>().end()))
0354         {
0355             return Iter(mutable_derived().end());
0356         }
0357
0358         template<typename D = Derived>
0359         constexpr auto cbegin() const
0360             noexcept(noexcept(std::declval<D const &>().begin()))
0361                 -> decltype(std::declval<D const &>().begin())
0362         {
0363             return derived().begin();
0364         }
0365         template<typename D = Derived>
0366         constexpr auto cend() const
0367             noexcept(noexcept(std::declval<D const &>().end()))
0368                 -> decltype(std::declval<D const &>().end())
0369         {
0370             return derived().end();
0371         }
0372
0373         template<
0374             typename D = Derived,
0375             typename Enable = std::enable_if_t<v1_dtl::common_range<D>::value>>
0376         constexpr auto rbegin() noexcept(noexcept(
0377             stl_interfaces::make_reverse_iterator(std::declval<D &>().end())))
0378         {
0379             return stl_interfaces::make_reverse_iterator(derived().end());
0380         }
0381         template<
0382             typename D = Derived,
0383             typename Enable = std::enable_if_t<v1_dtl::common_range<D>::value>>
0384         constexpr auto rend() noexcept(noexcept(
0385             stl_interfaces::make_reverse_iterator(std::declval<D &>().begin())))
0386         {
0387             return stl_interfaces::make_reverse_iterator(derived().begin());
0388         }
0389
0390         template<typename D = Derived>
0391         constexpr auto rbegin() const
0392             noexcept(noexcept(std::declval<D &>().rbegin()))
0393         {
0394             return
0395                 typename D::const_reverse_iterator(mutable_derived().rbegin());
0396         }
0397         template<typename D = Derived>
0398         constexpr auto rend() const
0399             noexcept(noexcept(std::declval<D &>().rend()))
0400         {
0401             return typename D::const_reverse_iterator(mutable_derived().rend());
0402         }
0403
0404         template<typename D = Derived>
0405         constexpr auto crbegin() const
0406             noexcept(noexcept(std::declval<D const &>().rbegin()))
0407                 -> decltype(std::declval<D const &>().rbegin())
0408         {
0409             return derived().rbegin();
0410         }
0411         template<typename D = Derived>
0412         constexpr auto crend() const
0413             noexcept(noexcept(std::declval<D const &>().rend()))
0414                 -> decltype(std::declval<D const &>().rend())
0415         {
0416             return derived().rend();
0417         }
0418
0419         template<typename D = Derived>
0420         constexpr auto insert(
0421             typename D::const_iterator pos,
0422             typename D::value_type const &
0423                 x) noexcept(noexcept(std::declval<D &>().emplace(pos, x)))
0424             -> decltype(std::declval<D &>().emplace(pos, x))
0425         {
0426             return derived().emplace(pos, x);
0427         }
0428
0429         template<typename D = Derived>
0430         constexpr auto insert(
0431             typename D::const_iterator pos,
0432             typename D::value_type &&
0433                 x) noexcept(noexcept(std::declval<D &>()
0434                                          .emplace(pos, std::move(x))))
0435             -> decltype(std::declval<D &>().emplace(pos, std::move(x)))
0436         {
0437             return derived().emplace(pos, std::move(x));
0438         }
0439
0440         template<typename D = Derived>
0441         constexpr auto insert(
0442             typename D::const_iterator pos,
0443             typename D::size_type n,
0444             typename D::value_type const & x)
0445             // If you see an error in this noexcept() expression, that's
0446             // because this function is not properly constrained.  In other
0447             // words, Derived does not have a "range" insert like
0448             // insert(position, first, last).  If that is the case, this
0449             // function should be removed via SFINAE from overload resolution.
0450             // However, both the trailing decltype code below and a
0451             // std::enable_if in the template parameters do not work.  Sorry
0452             // about that.  See below for details.
0453             noexcept(noexcept(std::declval<D &>().insert(
0454                 pos, detail::make_n_iter(x, n), detail::make_n_iter_end(x, n))))
0455         // This causes the compiler to infinitely recurse into this function's
0456         // declaration, even though the call below does not match the
0457         // signature of this function.
0458 #if 0
0459             -> decltype(std::declval<D &>().insert(
0460                 pos, detail::make_n_iter(x, n), detail::make_n_iter_end(x, n)))
0461 #endif
0462         {
0463             return derived().insert(
0464                 pos, detail::make_n_iter(x, n), detail::make_n_iter_end(x, n));
0465         }
0466
0467         template<typename D = Derived>
0468         constexpr auto insert(
0469             typename D::const_iterator pos,
0470             std::initializer_list<typename D::value_type>
0471                 il) noexcept(noexcept(std::declval<D &>()
0472                                           .insert(pos, il.begin(), il.end())))
0473             -> decltype(std::declval<D &>().insert(pos, il.begin(), il.end()))
0474         {
0475             return derived().insert(pos, il.begin(), il.end());
0476         }
0477
0478         template<typename D = Derived>
0479         constexpr auto erase(typename D::const_iterator pos) noexcept
0480             -> decltype(std::declval<D &>().erase(pos, std::next(pos)))
0481         {
0482             return derived().erase(pos, std::next(pos));
0483         }
0484
0485         template<
0486             typename InputIterator,
0487             typename D = Derived,
0488             typename Enable =
0489                 std::enable_if_t<v1_dtl::in_iter<InputIterator>::value>>
0490         constexpr auto assign(InputIterator first, InputIterator last) noexcept(
0491             noexcept(std::declval<D &>().insert(
0492                 std::declval<D &>().begin(), first, last)))
0493             -> decltype(
0494                 std::declval<D &>().erase(
0495                     std::declval<D &>().begin(), std::declval<D &>().end()),
0496                 (void)std::declval<D &>().insert(
0497                     std::declval<D &>().begin(), first, last))
0498         {
0499             auto out = derived().begin();
0500             auto const out_last = derived().end();
0501             for (; out != out_last && first != last; ++first, ++out) {
0502                 *out = *first;
0503             }
0504             if (out != out_last)
0505                 derived().erase(out, out_last);
0506             if (first != last)
0507                 derived().insert(derived().end(), first, last);
0508         }
0509
0510         template<typename D = Derived>
0511         constexpr auto assign(
0512             typename D::size_type n,
0513             typename D::value_type const &
0514                 x) noexcept(noexcept(std::declval<D &>()
0515                                          .insert(
0516                                              std::declval<D &>().begin(),
0517                                              detail::make_n_iter(x, n),
0518                                              detail::make_n_iter_end(x, n))))
0519             -> decltype(
0520                 std::declval<D &>().size(),
0521                 std::declval<D &>().erase(
0522                     std::declval<D &>().begin(), std::declval<D &>().end()),
0523                 (void)std::declval<D &>().insert(
0524                     std::declval<D &>().begin(),
0525                     detail::make_n_iter(x, n),
0526                     detail::make_n_iter_end(x, n)))
0527         {
0528             if (detail::fake_capacity(derived()) < n) {
0529                 Derived temp(n, x);
0530                 derived().swap(temp);
0531             } else {
0532                 auto const min_size =
0533                     std::min<std::ptrdiff_t>(n, derived().size());
0534                 auto const fill_end =
0535                     std::fill_n(derived().begin(), min_size, x);
0536                 if (min_size < (std::ptrdiff_t)derived().size()) {
0537                     derived().erase(fill_end, derived().end());
0538                 } else {
0539                     n -= min_size;
0540                     derived().insert(
0541                         derived().begin(),
0542                         detail::make_n_iter(x, n),
0543                         detail::make_n_iter_end(x, n));
0544                 }
0545             }
0546         }
0547
0548         template<typename D = Derived>
0549         constexpr auto
0550         assign(std::initializer_list<typename D::value_type> il) noexcept(
0551             noexcept(std::declval<D &>().assign(il.begin(), il.end())))
0552             -> decltype((void)std::declval<D &>().assign(il.begin(), il.end()))
0553         {
0554             derived().assign(il.begin(), il.end());
0555         }
0556
0557         template<typename D = Derived>
0558         constexpr auto
0559         operator=(std::initializer_list<typename D::value_type> il) noexcept(
0560             noexcept(std::declval<D &>().assign(il.begin(), il.end())))
0561             -> decltype(
0562                 std::declval<D &>().assign(il.begin(), il.end()),
0563                 std::declval<D &>())
0564         {
0565             derived().assign(il.begin(), il.end());
0566             return *this;
0567         }
0568
0569         template<typename D = Derived>
0570         constexpr auto clear() noexcept
0571             -> decltype((void)std::declval<D &>().erase(
0572                 std::declval<D &>().begin(), std::declval<D &>().end()))
0573         {
0574             derived().erase(derived().begin(), derived().end());
0575         }
0576     };
0577
0578     /** Implementation of free function `swap()` for all containers derived
0579         from `sequence_container_interface`.  */
0580     template<typename ContainerInterface>
0581     constexpr auto swap(
0582         ContainerInterface & lhs,
0583         ContainerInterface & rhs) noexcept(noexcept(lhs.swap(rhs)))
0584         -> decltype(v1_dtl::derived_container(lhs), lhs.swap(rhs))
0585     {
0586         return lhs.swap(rhs);
0587     }
0588
0589     /** Implementation of `operator==()` for all containers derived from
0590         `sequence_container_interface`.  */
0591     template<typename ContainerInterface>
0592     constexpr auto
0593     operator==(ContainerInterface const & lhs, ContainerInterface const & rhs) noexcept(
0594         noexcept(lhs.size() == rhs.size()) &&
0595         noexcept(*lhs.begin() == *rhs.begin()))
0596         -> decltype(
0597             v1_dtl::derived_container(lhs),
0598             lhs.size() == rhs.size(),
0599             *lhs.begin() == *rhs.begin(),
0600             true)
0601     {
0602         return lhs.size() == rhs.size() &&
0603                std::equal(lhs.begin(), lhs.end(), rhs.begin());
0604     }
0605
0606     /** Implementation of `operator!=()` for all containers derived from
0607         `sequence_container_interface`.  */
0608     template<typename ContainerInterface>
0609     constexpr auto operator!=(
0610         ContainerInterface const & lhs,
0611         ContainerInterface const & rhs) noexcept(noexcept(lhs == rhs))
0612         -> decltype(v1_dtl::derived_container(lhs), lhs == rhs)
0613     {
0614         return !(lhs == rhs);
0615     }
0616
0617     /** Implementation of `operator<()` for all containers derived from
0618         `sequence_container_interface`.  */
0619     template<typename ContainerInterface>
0620     constexpr auto operator<(
0621         ContainerInterface const & lhs,
0622         ContainerInterface const &
0623             rhs) noexcept(noexcept(*lhs.begin() < *rhs.begin()))
0624         -> decltype(
0625             v1_dtl::derived_container(lhs), *lhs.begin() < *rhs.begin(), true)
0626     {
0627         auto it1 = lhs.begin();
0628         auto const last1 = lhs.end();
0629         auto it2 = rhs.begin();
0630         auto const last2 = rhs.end();
0631         for (; it1 != last1 && it2 != last2; ++it1, ++it2) {
0632             if (*it1 < *it2)
0633                 return true;
0634             if (*it2 < *it1)
0635                 return false;
0636         }
0637         return it1 == last1 && it2 != last2;
0638     }
0639
0640     /** Implementation of `operator<=()` for all containers derived from
0641         `sequence_container_interface`.  */
0642     template<typename ContainerInterface>
0643     constexpr auto operator<=(
0644         ContainerInterface const & lhs,
0645         ContainerInterface const & rhs) noexcept(noexcept(lhs < rhs))
0646         -> decltype(v1_dtl::derived_container(lhs), lhs < rhs)
0647     {
0648         return !(rhs < lhs);
0649     }
0650
0651     /** Implementation of `operator>()` for all containers derived from
0652         `sequence_container_interface`.  */
0653     template<typename ContainerInterface>
0654     constexpr auto operator>(
0655         ContainerInterface const & lhs,
0656         ContainerInterface const & rhs) noexcept(noexcept(lhs < rhs))
0657         -> decltype(v1_dtl::derived_container(lhs), lhs < rhs)
0658     {
0659         return rhs < lhs;
0660     }
0661
0662     /** Implementation of `operator>=()` for all containers derived from
0663         `sequence_container_interface`.  */
0664     template<typename ContainerInterface>
0665     constexpr auto operator>=(
0666         ContainerInterface const & lhs,
0667         ContainerInterface const & rhs) noexcept(noexcept(lhs < rhs))
0668         -> decltype(v1_dtl::derived_container(lhs), lhs < rhs)
0669     {
0670         return !(lhs < rhs);
0671     }
0672
0673 }}}
0674
0675 #if defined(BOOST_STL_INTERFACES_DOXYGEN) || BOOST_STL_INTERFACES_USE_CONCEPTS
0676
0677 namespace boost { namespace stl_interfaces { BOOST_STL_INTERFACES_NAMESPACE_V2 {
0678
0679     namespace v2_dtl {
0680
0681         // This needs to become an exposition-only snake-case template alias
0682         // when standardized.
0683         template<typename T>
0684         using container_size_t = typename T::size_type;
0685
0686         template<typename T, typename I>
0687         // clang-format off
0688         concept range_insert =
0689             requires (T t, std::ranges::iterator_t<T> t_it, I it) {
0690             t.template insert<I>(t_it, it, it);
0691             // clang-format on
0692         };
0693
0694         template<typename T>
0695         using n_iter_t =
0696             detail::n_iter<std::ranges::range_value_t<T>, container_size_t<T>>;
0697     }
0698
0699     // clang-format off
0700
0701     /** A CRTP template that one may derive from to make it easier to define
0702         container types.
0703
0704         The template parameter `D` for `sequence_container_interface` may be
0705         an incomplete type. Before any member of the resulting specialization
0706         of `sequence_container_interface` other than special member functions
0707         is referenced, `D` shall be complete; shall model
0708         `std::derived_from<sequence_container_interface<D>>`,
0709         `std::semiregular`, and `std::forward_range`; and shall contain all
0710         the nested types required in Table 72: Container requirements and, for
0711         those whose iterator nested type models `std::bidirectinal_iterator`,
0712         those in Table 73: Reversible container requirements.
0713
0714         For an object `d` of type `D`, a call to `std::ranges::begin(d)` shall
0715         not mutate any data members of `d`, and `d`'s destructor shall end the
0716         lifetimes of the objects in `[std::ranges::begin(d),
0717         std::ranges::end(d))`.
0718
0719         The `Contiguity` template parameter is not needed, and is unused.  It
0720         only exists to make the transition from `namespace v1` to `namespace
0721         v2` seamless. */
0722     template<typename D,
0723              element_layout Contiguity = element_layout::discontiguous>
0724       requires std::is_class_v<D> && std::same_as<D, std::remove_cv_t<D>>
0725     struct sequence_container_interface
0726     {
0727     private:
0728       constexpr D& derived() noexcept {
0729         return static_cast<D&>(*this);
0730       }
0731       constexpr const D& derived() const noexcept {
0732         return static_cast<const D&>(*this);
0733       }
0734       constexpr D & mutable_derived() const noexcept {
0735         return const_cast<D&>(static_cast<const D&>(*this));
0736       }
0737       static constexpr void clear_impl(D& d) noexcept {}
0738       static constexpr void clear_impl(D& d) noexcept
0739         requires requires { d.clear(); }
0740       { d.clear(); }
0741
0742     public:
0743       constexpr bool empty() const {
0744         return std::ranges::begin(derived()) == std::ranges::end(derived());
0745       }
0746
0747       constexpr auto data() requires std::contiguous_iterator<std::ranges::iterator_t<D>> {
0748         return std::to_address(std::ranges::begin(derived()));
0749       }
0750       constexpr auto data() const requires std::contiguous_iterator<std::ranges::iterator_t<const D>> {
0751           return std::to_address(std::ranges::begin(derived()));
0752         }
0753
0754       template<typename C = D>
0755       constexpr v2_dtl::container_size_t<C> size() const
0756         requires std::sized_sentinel_for<std::ranges::sentinel_t<const C>, std::ranges::iterator_t<const C>> {
0757           return v2_dtl::container_size_t<C>(
0758             std::ranges::end(derived()) - std::ranges::begin(derived()));
0759         }
0760
0761       constexpr decltype(auto) front() {
0762         BOOST_ASSERT(!empty());
0763         return *std::ranges::begin(derived());
0764       }
0765       constexpr decltype(auto) front() const {
0766         BOOST_ASSERT(!empty());
0767         return *std::ranges::begin(derived());
0768       }
0769
0770       template<typename C = D>
0771         constexpr void push_front(const std::ranges::range_value_t<C>& x)
0772           requires requires (D d) { d.emplace_front(x); } {
0773             derived().emplace_front(x);
0774           }
0775       template<typename C = D>
0776         constexpr void push_front(std::ranges::range_value_t<C>&& x)
0777           requires requires (D d) { d.emplace_front(std::move(x)); } {
0778             derived().emplace_front(std::move(x));
0779           }
0780       constexpr void pop_front() noexcept
0781         requires requires (D d, const std::ranges::range_value_t<D>& x, std::ranges::iterator_t<D> position) {
0782           d.emplace_front(x);
0783           d.erase(position);
0784         } {
0785           return derived().erase(std::ranges::begin(derived()));
0786         }
0787
0788       constexpr decltype(auto) back()
0789         requires std::ranges::bidirectional_range<D> && std::ranges::common_range<D> {
0790           BOOST_ASSERT(!empty());
0791           return *std::ranges::prev(std::ranges::end(derived()));
0792         }
0793       constexpr decltype(auto) back() const
0794         requires std::ranges::bidirectional_range<const D> && std::ranges::common_range<const D> {
0795           BOOST_ASSERT(!empty());
0796           return *std::ranges::prev(std::ranges::end(derived()));
0797         }
0798
0799       template<std::ranges::bidirectional_range C = D>
0800         constexpr void push_back(const std::ranges::range_value_t<C>& x)
0801     requires std::ranges::common_range<C> && requires (D d) { d.emplace_back(x); } {
0802             derived().emplace_back(x);
0803           }
0804       template<std::ranges::bidirectional_range C = D>
0805         constexpr void push_back(std::ranges::range_value_t<C>&& x)
0806     requires std::ranges::common_range<C> && requires (D d) { d.emplace_back(std::move(x)); } {
0807             derived().emplace_back(std::move(x));
0808           }
0809       constexpr void pop_back() noexcept
0810         requires std::ranges::bidirectional_range<D> && std::ranges::common_range<D> &&
0811         requires (D d, std::ranges::range_value_t<D> x, std::ranges::iterator_t<D> position) {
0812           d.emplace_back(std::move(x));
0813             d.erase(position);
0814           } {
0815             return derived().erase(std::ranges::prev(std::ranges::end(derived())));
0816           }
0817
0818       template<std::ranges::random_access_range C = D>
0819         constexpr decltype(auto) operator[](v2_dtl::container_size_t<C> n) {
0820           return std::ranges::begin(derived())[n];
0821         }
0822       template<std::ranges::random_access_range C = const D>
0823         constexpr decltype(auto) operator[](v2_dtl::container_size_t<C> n) const {
0824           return std::ranges::begin(derived())[n];
0825         }
0826
0827       template<std::ranges::random_access_range C = D>
0828         constexpr decltype(auto) at(v2_dtl::container_size_t<C> n) {
0829           if (derived().size() <= n)
0830             throw std::out_of_range("Bounds check failed in sequence_container_interface::at()");
0831           return std::ranges::begin(derived())[n];
0832         }
0833       template<std::ranges::random_access_range C = const D>
0834         constexpr decltype(auto) at(v2_dtl::container_size_t<C> n) const {
0835           if (derived().size() <= n)
0836             throw std::out_of_range("Bounds check failed in sequence_container_interface::at()");
0837           return std::ranges::begin(derived())[n];
0838         }
0839
0840       constexpr auto begin() const {
0841         return typename D::const_iterator(mutable_derived().begin());
0842       }
0843       constexpr auto end() const {
0844         return typename D::const_iterator(mutable_derived().end());
0845       }
0846
0847       constexpr auto cbegin() const { return derived().begin(); }
0848       constexpr auto cend() const { return derived().end(); }
0849
0850       constexpr auto rbegin()
0851         requires std::ranges::bidirectional_range<D> && std::ranges::common_range<D> {
0852           return std::reverse_iterator(std::ranges::end(derived()));
0853         }
0854       constexpr auto rend()
0855         requires std::ranges::bidirectional_range<D> && std::ranges::common_range<D> {
0856           return std::reverse_iterator(std::ranges::begin(derived()));
0857         }
0858
0859       constexpr auto rbegin() const
0860         requires std::ranges::bidirectional_range<const D> &&
0861           std::ranges::common_range<const D> {
0862             return std::reverse_iterator(std::ranges::iterator_t<const D>(
0863               mutable_derived().end()));
0864           }
0865       constexpr auto rend() const
0866         requires std::ranges::bidirectional_range<const D> &&
0867           std::ranges::common_range<const D> {
0868             return std::reverse_iterator(std::ranges::iterator_t<const D>(
0869               mutable_derived().begin()));
0870           }
0871
0872       constexpr auto crbegin() const
0873         requires std::ranges::bidirectional_range<const D> &&
0874           std::ranges::common_range<const D> {
0875             return std::reverse_iterator(std::ranges::iterator_t<const D>(
0876               mutable_derived().end()));
0877             }
0878       constexpr auto crend() const
0879         requires std::ranges::bidirectional_range<const D> &&
0880           std::ranges::common_range<const D> {
0881             return std::reverse_iterator(std::ranges::iterator_t<const D>(
0882               mutable_derived().begin()));
0883             }
0884
0885       template<typename C = D>
0886         constexpr auto insert(std::ranges::iterator_t<const C> position,
0887                               const std::ranges::range_value_t<C>& x)
0888           requires requires (D d) { d.emplace(position, x); } {
0889             return derived().emplace(position, x);
0890           }
0891       template<typename C = D>
0892         constexpr auto insert(std::ranges::iterator_t<const C> position,
0893                               std::ranges::range_value_t<C>&& x)
0894           requires requires (D d) { d.emplace(position, std::move(x)); } {
0895             return derived().emplace(position, std::move(x));
0896           }
0897       template<typename C = D>
0898         constexpr auto insert(std::ranges::iterator_t<const C> position,
0899                               v2_dtl::container_size_t<C> n,
0900                               const std::ranges::range_value_t<C>& x)
0901           requires v2_dtl::range_insert<C, v2_dtl::n_iter_t<C>> {
0902             auto first = detail::make_n_iter(x, n);
0903             auto last = detail::make_n_iter_end(x, n);
0904             return derived().insert(
0905                 position, detail::make_n_iter(x, n), detail::make_n_iter_end(x, n));
0906             }
0907       template<typename C = D>
0908         constexpr auto insert(std::ranges::iterator_t<const C> position,
0909                               std::initializer_list<std::ranges::range_value_t<C>> il)
0910     requires requires (D d) {
0911             d.template insert<decltype(position), decltype(il)>(
0912                 position, il.begin(), il.end()); } {
0913               return derived().insert(position, il.begin(), il.end());
0914             }
0915
0916       template<typename C = D>
0917         constexpr void erase(typename C::const_iterator position)
0918     requires requires (D d) { d.erase(position, std::ranges::next(position)); } {
0919             derived().erase(position, std::ranges::next(position));
0920           }
0921
0922       template<std::input_iterator Iter, typename C = D>
0923         constexpr void assign(Iter first, Iter last)
0924     requires requires (D d) {
0925             d.erase(std::ranges::begin(d), std::ranges::end(d));
0926             d.insert(std::ranges::begin(d), first, last); } {
0927               auto out = derived().begin();
0928               auto const out_last = derived().end();
0929               for (; out != out_last && first != last; ++first, ++out) {
0930                 *out = *first;
0931               }
0932               if (out != out_last)
0933                 derived().erase(out, out_last);
0934               if (first != last)
0935                 derived().insert(derived().end(), first, last);
0936             }
0937       template<typename C = D>
0938         constexpr void assign(v2_dtl::container_size_t<C> n,
0939                               const std::ranges::range_value_t<C>& x)
0940           requires requires (D d) {
0941             { d.size() } -> std::convertible_to<std::size_t>;
0942             d.erase(std::ranges::begin(d), std::ranges::end(d));
0943             d.insert(std::ranges::begin(d),
0944                              detail::make_n_iter(x, n),
0945                              detail::make_n_iter_end(x, n)); } {
0946               if (detail::fake_capacity(derived()) < n) {
0947                 C temp(n, x);
0948                 derived().swap(temp);
0949               } else {
0950                 auto const min_size = std::min<std::ptrdiff_t>(n, derived().size());
0951                 auto const fill_end = std::fill_n(derived().begin(), min_size, x);
0952                 if (min_size < (std::ptrdiff_t)derived().size()) {
0953                   derived().erase(fill_end, derived().end());
0954                 } else {
0955                   n -= min_size;
0956                   derived().insert(
0957                     derived().begin(),
0958                     detail::make_n_iter(x, n),
0959                     detail::make_n_iter_end(x, n));
0960                 }
0961               }
0962             }
0963       template<typename C = D>
0964         constexpr void assign(std::initializer_list<std::ranges::range_value_t<C>> il)
0965           requires requires (D d) { d.assign(il.begin(), il.end()); } {
0966             derived().assign(il.begin(), il.end());
0967           }
0968
0969       constexpr void clear() noexcept
0970         requires requires (D d) {
0971           d.erase(std::ranges::begin(d), std::ranges::end(d)); } {
0972             derived().erase(std::ranges::begin(derived()), std::ranges::end(derived()));
0973           }
0974
0975       template<typename C = D>
0976         constexpr decltype(auto) operator=(
0977             std::initializer_list<std::ranges::range_value_t<C>> il)
0978           requires requires (D d) { d.assign(il.begin(), il.end()); } {
0979             derived().assign(il.begin(), il.end());
0980             return *this;
0981           }
0982
0983       friend constexpr void swap(D& lhs, D& rhs) requires requires { lhs.swap(rhs); } {
0984         return lhs.swap(rhs);
0985       }
0986
0987       friend constexpr bool operator==(const D& lhs, const D& rhs)
0988         requires std::ranges::sized_range<const D> &&
0989           requires { std::ranges::equal(lhs, rhs); } {
0990             return lhs.size() == rhs.size() && std::ranges::equal(lhs, rhs);
0991           }
0992 #if 0 // TODO: This appears to work, but as of this writing (and using GCC
0993       // 10), op<=> is not yet being used to evaluate op==, op<, etc.
0994       friend constexpr std::compare_three_way_result_t<std::ranges::range_reference_t<const D>>
0995         operator<=>(const D& lhs, const D& rhs)
0996         requires std::three_way_comparable<std::ranges::range_reference_t<const D>> {
0997           return std::lexicographical_compare_three_way(lhs.begin(), lhs.end(),
0998                                                         rhs.begin(), rhs.end());
0999         }
1000 #else
1001       friend constexpr bool operator!=(const D& lhs, const D& rhs)
1002         requires requires { lhs == rhs; } {
1003           return !(lhs == rhs);
1004         }
1005       friend constexpr bool operator<(D lhs, D rhs)
1006         requires std::totally_ordered<std::ranges::range_reference_t<D>> {
1007           return std::ranges::lexicographical_compare(lhs, rhs);
1008         }
1009       friend constexpr bool operator<=(D lhs, D rhs)
1010         requires std::totally_ordered<std::ranges::range_reference_t<D>> {
1011             return lhs == rhs || lhs < rhs;
1012           }
1013       friend constexpr bool operator>(D lhs, D rhs)
1014         requires std::totally_ordered<std::ranges::range_reference_t<D>> {
1015           return !(lhs <= rhs);
1016         }
1017       friend constexpr bool operator>=(D lhs, D rhs)
1018         requires std::totally_ordered<std::ranges::range_reference_t<D>> {
1019             return rhs <= lhs;
1020           }
1021 #endif
1022     };
1023
1024     // clang-format on
1025
1026 }}}
1027
1028 #endif
1029
1030 #if defined(BOOST_STL_INTERFACES_DOXYGEN) || BOOST_STL_INTERFACES_USE_DEDUCED_THIS
1031
1032 namespace boost { namespace stl_interfaces { BOOST_STL_INTERFACES_NAMESPACE_V3 {
1033
1034     // TODO: Reimplement using deduced this.
1035     template<typename D,
1036              element_layout Contiguity = element_layout::discontiguous>
1037     using sequence_container_interface = v2::sequence_container_interface<D, Contiguity>;
1038
1039 }}}
1040
1041 #endif
1042
1043 #endif