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