ceph/src/boost/boost/stl_interfaces/sequence_container_interface.hpp

   1 // Copyright (C) 2019 T. Zachary Laine
   2 //
   3 // Distributed under the Boost Software License, Version 1.0. (See
   4 // accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6 #ifndef BOOST_STL_INTERFACES_CONTAINER_INTERFACE_HPP
   7 #define BOOST_STL_INTERFACES_CONTAINER_INTERFACE_HPP
   8
   9 #include <boost/stl_interfaces/reverse_iterator.hpp>
  10
  11 #include <boost/assert.hpp>
  12 #include <boost/config.hpp>
  13
  14 #include <algorithm>
  15 #include <stdexcept>
  16 #include <cstddef>
  17
  18
  19 namespace boost { namespace stl_interfaces { namespace detail {
  20
  21     template<typename T, typename SizeType>
  22     struct n_iter : iterator_interface<
  23                         n_iter<T, SizeType>,
  24                         std::random_access_iterator_tag,
  25                         T>
  26     {
  27         n_iter() : x_(nullptr), n_(0) {}
  28         n_iter(T const & x, SizeType n) : x_(&x), n_(n) {}
  29
  30         T const & operator*() const { return *x_; }
  31         constexpr std::ptrdiff_t operator-(n_iter other) const noexcept
  32         {
  33             return std::ptrdiff_t(n_) - std::ptrdiff_t(other.n_);
  34         }
  35         n_iter & operator+=(std::ptrdiff_t offset)
  36         {
  37             n_ += offset;
  38             return *this;
  39         }
  40
  41     private:
  42         T const * x_;
  43         SizeType n_;
  44     };
  45
  46     template<typename T, typename SizeType>
  47     constexpr auto make_n_iter(T const & x, SizeType n) noexcept(
  48         noexcept(n_iter<T, SizeType>(x, n)))
  49     {
  50         using result_type = n_iter<T, SizeType>;
  51         return result_type(x, SizeType(0));
  52     }
  53     template<typename T, typename SizeType>
  54     constexpr auto make_n_iter_end(T const & x, SizeType n) noexcept(
  55         noexcept(n_iter<T, SizeType>(x, n)))
  56     {
  57         return n_iter<T, SizeType>(x, n);
  58     }
  59
  60     template<typename Container>
  61     std::size_t fake_capacity(Container const & c)
  62     {
  63         return SIZE_MAX;
  64     }
  65     template<
  66         typename Container,
  67         typename Enable = decltype(
  68             std::size_t() = std::declval<Container const &>().capacity())>
  69     std::size_t fake_capacity(Container const & c)
  70     {
  71         return c.capacity();
  72     }
  73
  74 }}}
  75
  76 namespace boost { namespace stl_interfaces { BOOST_STL_INTERFACES_NAMESPACE_V1 {
  77
  78     /** A CRTP template that one may derive from to make it easier to define
  79         container types.
  80
  81         The template parameter `D` for `sequence_container_interface` may be
  82         an incomplete type. Before any member of the resulting specialization
  83         of `sequence_container_interface` other than special member functions
  84         is referenced, `D` shall be complete; shall model
  85         `std::derived_from<sequence_container_interface<D>>`,
  86         `std::semiregular`, and `std::forward_range`; and shall contain all
  87         the nested types required in Table 72: Container requirements and, for
  88         those whose iterator nested type models `std::bidirectinal_iterator`,
  89         those in Table 73: Reversible container requirements.
  90
  91         For an object `d` of type `D`, a call to `std::ranges::begin(d)` sxhall
  92         not mutate any data members of `d`, and `d`'s destructor shall end the
  93         lifetimes of the objects in `[std::ranges::begin(d),
  94         std::ranges::end(d))`. */
  95     template<
  96         typename Derived,
  97         element_layout Contiguity = element_layout::discontiguous
  98 #ifndef BOOST_STL_INTERFACES_DOXYGEN
  99         ,
 100         typename E = std::enable_if_t<
 101             std::is_class<Derived>::value &&
 102             std::is_same<Derived, std::remove_cv_t<Derived>>::value>
 103 #endif
 104         >
 105     struct sequence_container_interface;
 106
 107     namespace v1_dtl {
 108         template<typename Iter>
 109         using in_iter = std::is_convertible<
 110             typename std::iterator_traits<Iter>::iterator_category,
 111             std::input_iterator_tag>;
 112
 113         template<typename D, typename = void>
 114         struct clear_impl
 115         {
 116             static constexpr void call(D & d) noexcept {}
 117         };
 118         template<typename D>
 119         struct clear_impl<D, void_t<decltype(std::declval<D>().clear())>>
 120         {
 121             static constexpr void call(D & d) noexcept { d.clear(); }
 122         };
 123
 124         template<typename D, element_layout Contiguity>
 125         void derived_container(sequence_container_interface<D, Contiguity> const &);
 126     }
 127
 128     template<
 129         typename Derived,
 130         element_layout Contiguity
 131 #ifndef BOOST_STL_INTERFACES_DOXYGEN
 132         ,
 133         typename E
 134 #endif
 135         >
 136     struct sequence_container_interface
 137     {
 138 #ifndef BOOST_STL_INTERFACES_DOXYGEN
 139     private:
 140         constexpr Derived & derived() noexcept
 141         {
 142             return static_cast<Derived &>(*this);
 143         }
 144         constexpr const Derived & derived() const noexcept
 145         {
 146             return static_cast<Derived const &>(*this);
 147         }
 148         constexpr Derived & mutable_derived() const noexcept
 149         {
 150             return const_cast<Derived &>(static_cast<Derived const &>(*this));
 151         }
 152 #endif
 153
 154     public:
 155         template<typename D = Derived>
 156         constexpr auto empty() noexcept(
 157             noexcept(std::declval<D &>().begin() == std::declval<D &>().end()))
 158             -> decltype(
 159                 std::declval<D &>().begin() == std::declval<D &>().end())
 160         {
 161             return derived().begin() == derived().end();
 162         }
 163         template<typename D = Derived>
 164         constexpr auto empty() const noexcept(noexcept(
 165             std::declval<D const &>().begin() ==
 166             std::declval<D const &>().end()))
 167             -> decltype(
 168                 std::declval<D const &>().begin() ==
 169                 std::declval<D const &>().end())
 170         {
 171             return derived().begin() == derived().end();
 172         }
 173
 174         template<
 175             typename D = Derived,
 176             element_layout C = Contiguity,
 177             typename Enable = std::enable_if_t<C == element_layout::contiguous>>
 178         constexpr auto data() noexcept(noexcept(std::declval<D &>().begin()))
 179             -> decltype(std::addressof(*std::declval<D &>().begin()))
 180         {
 181             return std::addressof(*derived().begin());
 182         }
 183         template<
 184             typename D = Derived,
 185             element_layout C = Contiguity,
 186             typename Enable = std::enable_if_t<C == element_layout::contiguous>>
 187         constexpr auto data() const
 188             noexcept(noexcept(std::declval<D const &>().begin()))
 189                 -> decltype(std::addressof(*std::declval<D const &>().begin()))
 190         {
 191             return std::addressof(*derived().begin());
 192         }
 193
 194         template<typename D = Derived>
 195         constexpr auto size()
 196 #if !BOOST_CLANG
 197             noexcept(noexcept(
 198                 std::declval<D &>().end() - std::declval<D &>().begin()))
 199 #endif
 200             -> decltype(typename D::size_type(
 201                 std::declval<D &>().end() - std::declval<D &>().begin()))
 202         {
 203             return derived().end() - derived().begin();
 204         }
 205         template<typename D = Derived>
 206         constexpr auto size() const noexcept(noexcept(
 207             std::declval<D const &>().end() -
 208             std::declval<D const &>().begin()))
 209             -> decltype(typename D::size_type(
 210 #if !BOOST_CLANG
 211                 std::declval<D const &>().end() -
 212                 std::declval<D const &>().begin()
 213 #endif
 214                 ))
 215         {
 216             return derived().end() - derived().begin();
 217         }
 218
 219         template<typename D = Derived>
 220         constexpr auto front() noexcept(noexcept(*std::declval<D &>().begin()))
 221             -> decltype(*std::declval<D &>().begin())
 222         {
 223             return *derived().begin();
 224         }
 225         template<typename D = Derived>
 226         constexpr auto front() const
 227             noexcept(noexcept(*std::declval<D const &>().begin()))
 228                 -> decltype(*std::declval<D const &>().begin())
 229         {
 230             return *derived().begin();
 231         }
 232
 233         template<typename D = Derived>
 234         constexpr auto push_front(typename D::value_type const & x) noexcept(
 235             noexcept(std::declval<D &>().emplace_front(x)))
 236             -> decltype((void)std::declval<D &>().emplace_front(x))
 237         {
 238             derived().emplace_front(x);
 239         }
 240
 241         template<typename D = Derived>
 242         constexpr auto push_front(typename D::value_type && x) noexcept(
 243             noexcept(std::declval<D &>().emplace_front(std::move(x))))
 244             -> decltype((void)std::declval<D &>().emplace_front(std::move(x)))
 245         {
 246             derived().emplace_front(std::move(x));
 247         }
 248
 249         template<typename D = Derived>
 250         constexpr auto pop_front() noexcept -> decltype(
 251             std::declval<D &>().emplace_front(
 252                 std::declval<typename D::value_type &>()),
 253             (void)std::declval<D &>().erase(std::declval<D &>().begin()))
 254         {
 255             derived().erase(derived().begin());
 256         }
 257
 258         template<
 259             typename D = Derived,
 260             typename Enable = std::enable_if_t<
 261                 v1_dtl::decrementable_sentinel<D>::value &&
 262                 v1_dtl::common_range<D>::value>>
 263         constexpr auto
 264         back() noexcept(noexcept(*std::prev(std::declval<D &>().end())))
 265             -> decltype(*std::prev(std::declval<D &>().end()))
 266         {
 267             return *std::prev(derived().end());
 268         }
 269         template<
 270             typename D = Derived,
 271             typename Enable = std::enable_if_t<
 272                 v1_dtl::decrementable_sentinel<D>::value &&
 273                 v1_dtl::common_range<D>::value>>
 274         constexpr auto back() const
 275             noexcept(noexcept(*std::prev(std::declval<D const &>().end())))
 276                 -> decltype(*std::prev(std::declval<D const &>().end()))
 277         {
 278             return *std::prev(derived().end());
 279         }
 280
 281         template<typename D = Derived>
 282         constexpr auto push_back(typename D::value_type const & x) noexcept(
 283             noexcept(std::declval<D &>().emplace_back(x)))
 284             -> decltype((void)std::declval<D &>().emplace_back(x))
 285         {
 286             derived().emplace_back(x);
 287         }
 288
 289         template<typename D = Derived>
 290         constexpr auto push_back(typename D::value_type && x) noexcept(
 291             noexcept(std::declval<D &>().emplace_back(std::move(x))))
 292             -> decltype((void)std::declval<D &>().emplace_back(std::move(x)))
 293         {
 294             derived().emplace_back(std::move(x));
 295         }
 296
 297         template<typename D = Derived>
 298         constexpr auto pop_back() noexcept -> decltype(
 299             std::declval<D &>().emplace_back(
 300                 std::declval<typename D::value_type>()),
 301             (void)std::declval<D &>().erase(
 302                 std::prev(std::declval<D &>().end())))
 303         {
 304             derived().erase(std::prev(derived().end()));
 305         }
 306
 307         template<typename D = Derived>
 308         constexpr auto operator[](typename D::size_type n) noexcept(
 309             noexcept(std::declval<D &>().begin()[n]))
 310             -> decltype(std::declval<D &>().begin()[n])
 311         {
 312             return derived().begin()[n];
 313         }
 314         template<typename D = Derived>
 315         constexpr auto operator[](typename D::size_type n) const
 316             noexcept(noexcept(std::declval<D const &>().begin()[n]))
 317                 -> decltype(std::declval<D const &>().begin()[n])
 318         {
 319             return derived().begin()[n];
 320         }
 321
 322         template<typename D = Derived>
 323         constexpr auto at(typename D::size_type i)
 324             -> decltype(std::declval<D &>().size(), std::declval<D &>()[i])
 325         {
 326             if (derived().size() <= i) {
 327                 throw std::out_of_range(
 328                     "Bounds check failed in sequence_container_interface::at()");
 329             }
 330             return derived()[i];
 331         }
 332
 333         template<typename D = Derived>
 334         constexpr auto at(typename D::size_type i) const -> decltype(
 335             std::declval<D const &>().size(), std::declval<D const &>()[i])
 336         {
 337             if (derived().size() <= i) {
 338                 throw std::out_of_range(
 339                     "Bounds check failed in sequence_container_interface::at()");
 340             }
 341             return derived()[i];
 342         }
 343
 344         template<typename D = Derived, typename Iter = typename D::const_iterator>
 345         constexpr Iter begin() const
 346             noexcept(noexcept(std::declval<D &>().begin()))
 347         {
 348             return Iter(mutable_derived().begin());
 349         }
 350         template<typename D = Derived, typename Iter = typename D::const_iterator>
 351         constexpr Iter end() const noexcept(noexcept(std::declval<D &>().end()))
 352         {
 353             return Iter(mutable_derived().end());
 354         }
 355
 356         template<typename D = Derived>
 357         constexpr auto cbegin() const
 358             noexcept(noexcept(std::declval<D const &>().begin()))
 359                 -> decltype(std::declval<D const &>().begin())
 360         {
 361             return derived().begin();
 362         }
 363         template<typename D = Derived>
 364         constexpr auto cend() const
 365             noexcept(noexcept(std::declval<D const &>().end()))
 366                 -> decltype(std::declval<D const &>().end())
 367         {
 368             return derived().end();
 369         }
 370
 371         template<
 372             typename D = Derived,
 373             typename Enable = std::enable_if_t<v1_dtl::common_range<D>::value>>
 374         constexpr auto rbegin() noexcept(noexcept(
 375             stl_interfaces::make_reverse_iterator(std::declval<D &>().end())))
 376         {
 377             return stl_interfaces::make_reverse_iterator(derived().end());
 378         }
 379         template<
 380             typename D = Derived,
 381             typename Enable = std::enable_if_t<v1_dtl::common_range<D>::value>>
 382         constexpr auto rend() noexcept(noexcept(
 383             stl_interfaces::make_reverse_iterator(std::declval<D &>().begin())))
 384         {
 385             return stl_interfaces::make_reverse_iterator(derived().begin());
 386         }
 387
 388         template<typename D = Derived>
 389         constexpr auto rbegin() const
 390             noexcept(noexcept(std::declval<D &>().rbegin()))
 391         {
 392             return
 393                 typename D::const_reverse_iterator(mutable_derived().rbegin());
 394         }
 395         template<typename D = Derived>
 396         constexpr auto rend() const
 397             noexcept(noexcept(std::declval<D &>().rend()))
 398         {
 399             return typename D::const_reverse_iterator(mutable_derived().rend());
 400         }
 401
 402         template<typename D = Derived>
 403         constexpr auto crbegin() const
 404             noexcept(noexcept(std::declval<D const &>().rbegin()))
 405                 -> decltype(std::declval<D const &>().rbegin())
 406         {
 407             return derived().rbegin();
 408         }
 409         template<typename D = Derived>
 410         constexpr auto crend() const
 411             noexcept(noexcept(std::declval<D const &>().rend()))
 412                 -> decltype(std::declval<D const &>().rend())
 413         {
 414             return derived().rend();
 415         }
 416
 417         template<typename D = Derived>
 418         constexpr auto insert(
 419             typename D::const_iterator pos,
 420             typename D::value_type const &
 421                 x) noexcept(noexcept(std::declval<D &>().emplace(pos, x)))
 422             -> decltype(std::declval<D &>().emplace(pos, x))
 423         {
 424             return derived().emplace(pos, x);
 425         }
 426
 427         template<typename D = Derived>
 428         constexpr auto insert(
 429             typename D::const_iterator pos,
 430             typename D::value_type &&
 431                 x) noexcept(noexcept(std::declval<D &>()
 432                                          .emplace(pos, std::move(x))))
 433             -> decltype(std::declval<D &>().emplace(pos, std::move(x)))
 434         {
 435             return derived().emplace(pos, std::move(x));
 436         }
 437
 438         template<typename D = Derived>
 439         constexpr auto insert(
 440             typename D::const_iterator pos,
 441             typename D::size_type n,
 442             typename D::value_type const & x)
 443             // If you see an error in this noexcept() expression, that's
 444             // because this function is not properly constrained.  In other
 445             // words, Derived does not have a "range" insert like
 446             // insert(position, first, last).  If that is the case, this
 447             // function should be removed via SFINAE from overload resolution.
 448             // However, both the trailing decltype code below and a
 449             // std::enable_if in the template parameters do not work.  Sorry
 450             // about that.  See below for details.
 451             noexcept(noexcept(std::declval<D &>().insert(
 452                 pos, detail::make_n_iter(x, n), detail::make_n_iter_end(x, n))))
 453         // This causes the compiler to infinitely recurse into this function's
 454         // declaration, even though the call below does not match the
 455         // signature of this function.
 456 #if 0
 457             -> decltype(std::declval<D &>().insert(
 458                 pos, detail::make_n_iter(x, n), detail::make_n_iter_end(x, n)))
 459 #endif
 460         {
 461             return derived().insert(
 462                 pos, detail::make_n_iter(x, n), detail::make_n_iter_end(x, n));
 463         }
 464
 465         template<typename D = Derived>
 466         constexpr auto insert(
 467             typename D::const_iterator pos,
 468             std::initializer_list<typename D::value_type>
 469                 il) noexcept(noexcept(std::declval<D &>()
 470                                           .insert(pos, il.begin(), il.end())))
 471             -> decltype(std::declval<D &>().insert(pos, il.begin(), il.end()))
 472         {
 473             return derived().insert(pos, il.begin(), il.end());
 474         }
 475
 476         template<typename D = Derived>
 477         constexpr auto erase(typename D::const_iterator pos) noexcept
 478             -> decltype(std::declval<D &>().erase(pos, std::next(pos)))
 479         {
 480             return derived().erase(pos, std::next(pos));
 481         }
 482
 483         template<
 484             typename InputIterator,
 485             typename D = Derived,
 486             typename Enable =
 487                 std::enable_if_t<v1_dtl::in_iter<InputIterator>::value>>
 488         constexpr auto assign(InputIterator first, InputIterator last) noexcept(
 489             noexcept(std::declval<D &>().insert(
 490                 std::declval<D &>().begin(), first, last)))
 491             -> decltype(
 492                 std::declval<D &>().erase(
 493                     std::declval<D &>().begin(), std::declval<D &>().end()),
 494                 (void)std::declval<D &>().insert(
 495                     std::declval<D &>().begin(), first, last))
 496         {
 497             auto out = derived().begin();
 498             auto const out_last = derived().end();
 499             for (; out != out_last && first != last; ++first, ++out) {
 500                 *out = *first;
 501             }
 502             if (out != out_last)
 503                 derived().erase(out, out_last);
 504             if (first != last)
 505                 derived().insert(derived().end(), first, last);
 506         }
 507
 508         template<typename D = Derived>
 509         constexpr auto assign(
 510             typename D::size_type n,
 511             typename D::value_type const &
 512                 x) noexcept(noexcept(std::declval<D &>()
 513                                          .insert(
 514                                              std::declval<D &>().begin(),
 515                                              detail::make_n_iter(x, n),
 516                                              detail::make_n_iter_end(x, n))))
 517             -> decltype(
 518                 std::declval<D &>().size(),
 519                 std::declval<D &>().erase(
 520                     std::declval<D &>().begin(), std::declval<D &>().end()),
 521                 (void)std::declval<D &>().insert(
 522                     std::declval<D &>().begin(),
 523                     detail::make_n_iter(x, n),
 524                     detail::make_n_iter_end(x, n)))
 525         {
 526             if (detail::fake_capacity(derived()) < n) {
 527                 Derived temp(n, x);
 528                 derived().swap(temp);
 529             } else {
 530                 auto const min_size =
 531                     std::min<std::ptrdiff_t>(n, derived().size());
 532                 auto const fill_end =
 533                     std::fill_n(derived().begin(), min_size, x);
 534                 if (min_size < (std::ptrdiff_t)derived().size()) {
 535                     derived().erase(fill_end, derived().end());
 536                 } else {
 537                     n -= min_size;
 538                     derived().insert(
 539                         derived().begin(),
 540                         detail::make_n_iter(x, n),
 541                         detail::make_n_iter_end(x, n));
 542                 }
 543             }
 544         }
 545
 546         template<typename D = Derived>
 547         constexpr auto
 548         assign(std::initializer_list<typename D::value_type> il) noexcept(
 549             noexcept(std::declval<D &>().assign(il.begin(), il.end())))
 550             -> decltype((void)std::declval<D &>().assign(il.begin(), il.end()))
 551         {
 552             derived().assign(il.begin(), il.end());
 553         }
 554
 555         template<typename D = Derived>
 556         constexpr auto
 557         operator=(std::initializer_list<typename D::value_type> il) noexcept(
 558             noexcept(std::declval<D &>().assign(il.begin(), il.end())))
 559             -> decltype(
 560                 std::declval<D &>().assign(il.begin(), il.end()),
 561                 std::declval<D &>())
 562         {
 563             derived().assign(il.begin(), il.end());
 564             return *this;
 565         }
 566
 567         template<typename D = Derived>
 568         constexpr auto clear() noexcept
 569             -> decltype((void)std::declval<D &>().erase(
 570                 std::declval<D &>().begin(), std::declval<D &>().end()))
 571         {
 572             derived().erase(derived().begin(), derived().end());
 573         }
 574     };
 575
 576     /** Implementation of free function `swap()` for all containers derived
 577         from `sequence_container_interface`.  */
 578     template<typename ContainerInterface>
 579     constexpr auto swap(
 580         ContainerInterface & lhs,
 581         ContainerInterface & rhs) noexcept(noexcept(lhs.swap(rhs)))
 582         -> decltype(v1_dtl::derived_container(lhs), lhs.swap(rhs))
 583     {
 584         return lhs.swap(rhs);
 585     }
 586
 587     /** Implementation of `operator==()` for all containers derived from
 588         `sequence_container_interface`.  */
 589     template<typename ContainerInterface>
 590     constexpr auto
 591     operator==(ContainerInterface const & lhs, ContainerInterface const & rhs) noexcept(
 592         noexcept(lhs.size() == rhs.size()) &&
 593         noexcept(*lhs.begin() == *rhs.begin()))
 594         -> decltype(
 595             v1_dtl::derived_container(lhs),
 596             lhs.size() == rhs.size(),
 597             *lhs.begin() == *rhs.begin(),
 598             true)
 599     {
 600         return lhs.size() == rhs.size() &&
 601                std::equal(lhs.begin(), lhs.end(), rhs.begin());
 602     }
 603
 604     /** Implementation of `operator!=()` for all containers derived from
 605         `sequence_container_interface`.  */
 606     template<typename ContainerInterface>
 607     constexpr auto operator!=(
 608         ContainerInterface const & lhs,
 609         ContainerInterface const & rhs) noexcept(noexcept(lhs == rhs))
 610         -> decltype(v1_dtl::derived_container(lhs), lhs == rhs)
 611     {
 612         return !(lhs == rhs);
 613     }
 614
 615     /** Implementation of `operator<()` for all containers derived from
 616         `sequence_container_interface`.  */
 617     template<typename ContainerInterface>
 618     constexpr auto operator<(
 619         ContainerInterface const & lhs,
 620         ContainerInterface const &
 621             rhs) noexcept(noexcept(*lhs.begin() < *rhs.begin()))
 622         -> decltype(
 623             v1_dtl::derived_container(lhs), *lhs.begin() < *rhs.begin(), true)
 624     {
 625         auto it1 = lhs.begin();
 626         auto const last1 = lhs.end();
 627         auto it2 = rhs.begin();
 628         auto const last2 = rhs.end();
 629         for (; it1 != last1 && it2 != last2; ++it1, ++it2) {
 630             if (*it1 < *it2)
 631                 return true;
 632             if (*it2 < *it1)
 633                 return false;
 634         }
 635         return it1 == last1 && it2 != last2;
 636     }
 637
 638     /** Implementation of `operator<=()` for all containers derived from
 639         `sequence_container_interface`.  */
 640     template<typename ContainerInterface>
 641     constexpr auto operator<=(
 642         ContainerInterface const & lhs,
 643         ContainerInterface const & rhs) noexcept(noexcept(lhs < rhs))
 644         -> decltype(v1_dtl::derived_container(lhs), lhs < rhs)
 645     {
 646         return !(rhs < lhs);
 647     }
 648
 649     /** Implementation of `operator>()` for all containers derived from
 650         `sequence_container_interface`.  */
 651     template<typename ContainerInterface>
 652     constexpr auto operator>(
 653         ContainerInterface const & lhs,
 654         ContainerInterface const & rhs) noexcept(noexcept(lhs < rhs))
 655         -> decltype(v1_dtl::derived_container(lhs), lhs < rhs)
 656     {
 657         return rhs < lhs;
 658     }
 659
 660     /** Implementation of `operator>=()` for all containers derived from
 661         `sequence_container_interface`.  */
 662     template<typename ContainerInterface>
 663     constexpr auto operator>=(
 664         ContainerInterface const & lhs,
 665         ContainerInterface const & rhs) noexcept(noexcept(lhs < rhs))
 666         -> decltype(v1_dtl::derived_container(lhs), lhs < rhs)
 667     {
 668         return !(lhs < rhs);
 669     }
 670
 671 }}}
 672
 673 #if defined(BOOST_STL_INTERFACES_DOXYGEN) || BOOST_STL_INTERFACES_USE_CONCEPTS
 674
 675 namespace boost { namespace stl_interfaces { BOOST_STL_INTERFACES_NAMESPACE_V2 {
 676
 677     namespace v2_dtl {
 678
 679         // This needs to become an exposition-only snake-case template alias
 680         // when standardized.
 681         template<typename T>
 682         using container_size_t = typename T::size_type;
 683
 684         template<typename T, typename I>
 685         // clang-format off
 686         concept range_insert =
 687             requires (T t, std::ranges::iterator_t<T> t_it, I it) {
 688             t.template insert<I>(t_it, it, it);
 689             // clang-format on
 690         };
 691
 692         template<typename T>
 693         using n_iter_t =
 694             detail::n_iter<std::ranges::range_value_t<T>, container_size_t<T>>;
 695     }
 696
 697     // clang-format off
 698
 699     /** A CRTP template that one may derive from to make it easier to define
 700         container types.
 701
 702         The template parameter `D` for `sequence_container_interface` may be
 703         an incomplete type. Before any member of the resulting specialization
 704         of `sequence_container_interface` other than special member functions
 705         is referenced, `D` shall be complete; shall model
 706         `std::derived_from<sequence_container_interface<D>>`,
 707         `std::semiregular`, and `std::forward_range`; and shall contain all
 708         the nested types required in Table 72: Container requirements and, for
 709         those whose iterator nested type models `std::bidirectinal_iterator`,
 710         those in Table 73: Reversible container requirements.
 711
 712         For an object `d` of type `D`, a call to `std::ranges::begin(d)` shall
 713         not mutate any data members of `d`, and `d`'s destructor shall end the
 714         lifetimes of the objects in `[std::ranges::begin(d),
 715         std::ranges::end(d))`.
 716
 717         The `Contiguity` template parameter is not needed, and is unused.  It
 718         only exists to make the transition from `namespace v1` to `namespace
 719         v2` seamless. */
 720     template<typename D,
 721              element_layout Contiguity = element_layout::discontiguous>
 722       requires std::is_class_v<D> && std::same_as<D, std::remove_cv_t<D>>
 723     struct sequence_container_interface
 724     {
 725     private:
 726       constexpr D& derived() noexcept {
 727         return static_cast<D&>(*this);
 728       }
 729       constexpr const D& derived() const noexcept {
 730         return static_cast<const D&>(*this);
 731       }
 732       constexpr D & mutable_derived() const noexcept {
 733         return const_cast<D&>(static_cast<const D&>(*this));
 734       }
 735       static constexpr void clear_impl(D& d) noexcept {}
 736       static constexpr void clear_impl(D& d) noexcept
 737         requires requires { d.clear(); }
 738       { d.clear(); }
 739
 740     public:
 741       constexpr bool empty() const {
 742         return std::ranges::begin(derived()) == std::ranges::end(derived());
 743       }
 744
 745       constexpr auto data() requires std::contiguous_iterator<std::ranges::iterator_t<D>> {
 746         return std::to_address(std::ranges::begin(derived()));
 747       }
 748       constexpr auto data() const requires std::contiguous_iterator<std::ranges::iterator_t<const D>> {
 749           return std::to_address(std::ranges::begin(derived()));
 750         }
 751
 752       template<typename C = D>
 753       constexpr v2_dtl::container_size_t<C> size() const
 754         requires std::sized_sentinel_for<std::ranges::sentinel_t<const C>, std::ranges::iterator_t<const C>> {
 755           return v2_dtl::container_size_t<C>(
 756             std::ranges::end(derived()) - std::ranges::begin(derived()));
 757         }
 758
 759       constexpr decltype(auto) front() {
 760         BOOST_ASSERT(!empty());
 761         return *std::ranges::begin(derived());
 762       }
 763       constexpr decltype(auto) front() const {
 764         BOOST_ASSERT(!empty());
 765         return *std::ranges::begin(derived());
 766       }
 767
 768       template<typename C = D>
 769         constexpr void push_front(const std::ranges::range_value_t<C>& x)
 770           requires requires { derived().emplace_front(x); } {
 771             derived().emplace_front(x);
 772           }
 773       template<typename C = D>
 774         constexpr void push_front(std::ranges::range_value_t<C>&& x)
 775           requires requires { derived().emplace_front(std::move(x)); } {
 776             derived().emplace_front(std::move(x));
 777           }
 778       constexpr void pop_front() noexcept
 779         requires requires (const std::ranges::range_value_t<D>& x, std::ranges::iterator_t<D> position) {
 780           derived().emplace_front(x);
 781           derived().erase(position);
 782         } {
 783           return derived().erase(std::ranges::begin(derived()));
 784         }
 785
 786       constexpr decltype(auto) back()
 787         requires std::ranges::bidirectional_range<D> && std::ranges::common_range<D> {
 788           BOOST_ASSERT(!empty());
 789           return *std::ranges::prev(std::ranges::end(derived()));
 790         }
 791       constexpr decltype(auto) back() const
 792         requires std::ranges::bidirectional_range<const D> && std::ranges::common_range<const D> {
 793           BOOST_ASSERT(!empty());
 794           return *std::ranges::prev(std::ranges::end(derived()));
 795         }
 796
 797       template<std::ranges::bidirectional_range C = D>
 798         constexpr void push_back(const std::ranges::range_value_t<C>& x)
 799           requires std::ranges::common_range<C> && requires { derived().emplace_back(x); } {
 800             derived().emplace_back(x);
 801           }
 802       template<std::ranges::bidirectional_range C = D>
 803         constexpr void push_back(std::ranges::range_value_t<C>&& x)
 804           requires std::ranges::common_range<C> && requires { derived().emplace_back(std::move(x)); } {
 805             derived().emplace_back(std::move(x));
 806           }
 807       constexpr void pop_back() noexcept
 808         requires std::ranges::bidirectional_range<D> && std::ranges::common_range<D> &&
 809           requires (std::ranges::range_value_t<D> x, std::ranges::iterator_t<D> position) {
 810           derived().emplace_back(std::move(x));
 811             derived().erase(position);
 812           } {
 813             return derived().erase(std::ranges::prev(std::ranges::end(derived())));
 814           }
 815
 816       template<std::ranges::random_access_range C = D>
 817         constexpr decltype(auto) operator[](v2_dtl::container_size_t<C> n) {
 818           return std::ranges::begin(derived())[n];
 819         }
 820       template<std::ranges::random_access_range C = const D>
 821         constexpr decltype(auto) operator[](v2_dtl::container_size_t<C> n) const {
 822           return std::ranges::begin(derived())[n];
 823         }
 824
 825       template<std::ranges::random_access_range C = D>
 826         constexpr decltype(auto) at(v2_dtl::container_size_t<C> n) {
 827           if (derived().size() <= n)
 828             throw std::out_of_range("Bounds check failed in sequence_container_interface::at()");
 829           return std::ranges::begin(derived())[n];
 830         }
 831       template<std::ranges::random_access_range C = const D>
 832         constexpr decltype(auto) at(v2_dtl::container_size_t<C> n) const {
 833           if (derived().size() <= n)
 834             throw std::out_of_range("Bounds check failed in sequence_container_interface::at()");
 835           return std::ranges::begin(derived())[n];
 836         }
 837
 838       constexpr auto begin() const {
 839         return typename D::const_iterator(mutable_derived().begin());
 840       }
 841       constexpr auto end() const {
 842         return typename D::const_iterator(mutable_derived().end());
 843       }
 844
 845       constexpr auto cbegin() const { return derived().begin(); }
 846       constexpr auto cend() const { return derived().end(); }
 847
 848       constexpr auto rbegin()
 849         requires std::ranges::bidirectional_range<D> && std::ranges::common_range<D> {
 850           return std::reverse_iterator(std::ranges::end(derived()));
 851         }
 852       constexpr auto rend()
 853         requires std::ranges::bidirectional_range<D> && std::ranges::common_range<D> {
 854           return std::reverse_iterator(std::ranges::begin(derived()));
 855         }
 856
 857       constexpr auto rbegin() const
 858         requires std::ranges::bidirectional_range<const D> &&
 859           std::ranges::common_range<const D> {
 860             return std::reverse_iterator(std::ranges::iterator_t<const D>(
 861               mutable_derived().end()));
 862           }
 863       constexpr auto rend() const
 864         requires std::ranges::bidirectional_range<const D> &&
 865           std::ranges::common_range<const D> {
 866             return std::reverse_iterator(std::ranges::iterator_t<const D>(
 867               mutable_derived().begin()));
 868           }
 869
 870       constexpr auto crbegin() const
 871         requires std::ranges::bidirectional_range<const D> &&
 872           std::ranges::common_range<const D> {
 873             return std::reverse_iterator(std::ranges::iterator_t<const D>(
 874               mutable_derived().end()));
 875             }
 876       constexpr auto crend() const
 877         requires std::ranges::bidirectional_range<const D> &&
 878           std::ranges::common_range<const D> {
 879             return std::reverse_iterator(std::ranges::iterator_t<const D>(
 880               mutable_derived().begin()));
 881             }
 882
 883       template<typename C = D>
 884         constexpr auto insert(std::ranges::iterator_t<const C> position,
 885                               const std::ranges::range_value_t<C>& x)
 886           requires requires { derived().emplace(position, x); } {
 887             return derived().emplace(position, x);
 888           }
 889       template<typename C = D>
 890         constexpr auto insert(std::ranges::iterator_t<const C> position,
 891                               std::ranges::range_value_t<C>&& x)
 892           requires requires { derived().emplace(position, std::move(x)); } {
 893             return derived().emplace(position, std::move(x));
 894           }
 895       template<typename C = D>
 896         constexpr auto insert(std::ranges::iterator_t<const C> position,
 897                               v2_dtl::container_size_t<C> n,
 898                               const std::ranges::range_value_t<C>& x)
 899           requires v2_dtl::range_insert<C, v2_dtl::n_iter_t<C>> {
 900             auto first = detail::make_n_iter(x, n);
 901             auto last = detail::make_n_iter_end(x, n);
 902             return derived().insert(
 903                 position, detail::make_n_iter(x, n), detail::make_n_iter_end(x, n));
 904             }
 905       template<typename C = D>
 906         constexpr auto insert(std::ranges::iterator_t<const C> position,
 907                               std::initializer_list<std::ranges::range_value_t<C>> il)
 908           requires requires {
 909             derived().template insert<decltype(position), decltype(il)>(
 910                 position, il.begin(), il.end()); } {
 911               return derived().insert(position, il.begin(), il.end());
 912             }
 913
 914       template<typename C = D>
 915         constexpr void erase(C::const_iterator position)
 916           requires requires { derived().erase(position, std::ranges::next(position)); } {
 917             derived().erase(position, std::ranges::next(position));
 918           }
 919
 920       template<std::input_iterator Iter, typename C = D>
 921         constexpr void assign(Iter first, Iter last)
 922           requires requires {
 923             derived().erase(std::ranges::begin(derived()), std::ranges::end(derived()));
 924             derived().insert(std::ranges::begin(derived()), first, last); } {
 925               auto out = derived().begin();
 926               auto const out_last = derived().end();
 927               for (; out != out_last && first != last; ++first, ++out) {
 928                 *out = *first;
 929               }
 930               if (out != out_last)
 931                 derived().erase(out, out_last);
 932               if (first != last)
 933                 derived().insert(derived().end(), first, last);
 934             }
 935       template<typename C = D>
 936         constexpr void assign(v2_dtl::container_size_t<C> n,
 937                               const std::ranges::range_value_t<C>& x)
 938           requires requires {
 939             { derived().size() } -> std::convertible_to<std::size_t>;
 940             derived().erase(std::ranges::begin(derived()), std::ranges::end(derived()));
 941             derived().insert(std::ranges::begin(derived()),
 942                              detail::make_n_iter(x, n),
 943                              detail::make_n_iter_end(x, n)); } {
 944               if (detail::fake_capacity(derived()) < n) {
 945                 C temp(n, x);
 946                 derived().swap(temp);
 947               } else {
 948                 auto const min_size = std::min<std::ptrdiff_t>(n, derived().size());
 949                 auto const fill_end = std::fill_n(derived().begin(), min_size, x);
 950                 if (min_size < (std::ptrdiff_t)derived().size()) {
 951                   derived().erase(fill_end, derived().end());
 952                 } else {
 953                   n -= min_size;
 954                   derived().insert(
 955                     derived().begin(),
 956                     detail::make_n_iter(x, n),
 957                     detail::make_n_iter_end(x, n));
 958                 }
 959               }
 960             }
 961       template<typename C = D>
 962         constexpr void assign(std::initializer_list<std::ranges::range_value_t<C>> il)
 963           requires requires { derived().assign(il.begin(), il.end()); } {
 964             derived().assign(il.begin(), il.end());
 965           }
 966
 967       constexpr void clear() noexcept
 968         requires requires {
 969           derived().erase(std::ranges::begin(derived()), std::ranges::end(derived())); } {
 970             derived().erase(std::ranges::begin(derived()), std::ranges::end(derived()));
 971           }
 972
 973       template<typename C = D>
 974         constexpr decltype(auto) operator=(
 975             std::initializer_list<std::ranges::range_value_t<C>> il)
 976           requires requires { derived().assign(il.begin(), il.end()); } {
 977             derived().assign(il.begin(), il.end());
 978             return *this;
 979           }
 980
 981       friend constexpr void swap(D& lhs, D& rhs) requires requires { lhs.swap(rhs); } {
 982         return lhs.swap(rhs);
 983       }
 984
 985       friend constexpr bool operator==(const D& lhs, const D& rhs)
 986         requires std::ranges::sized_range<const D> &&
 987           requires { std::ranges::equal(lhs, rhs); } {
 988             return lhs.size() == rhs.size() && std::ranges::equal(lhs, rhs);
 989           }
 990 #if 0 // TODO: This appears to work, but as of this writing (and using GCC
 991       // 10), op<=> is not yet being used to evaluate op==, op<, etc.
 992       friend constexpr std::compare_three_way_result_t<std::ranges::range_reference_t<const D>>
 993         operator<=>(const D& lhs, const D& rhs)
 994         requires std::three_way_comparable<std::ranges::range_reference_t<const D>> {
 995           return std::lexicographical_compare_three_way(lhs.begin(), lhs.end(),
 996                                                         rhs.begin(), rhs.end());
 997         }
 998 #else
 999       friend constexpr bool operator!=(const D& lhs, const D& rhs)
1000         requires requires { lhs == rhs; } {
1001           return !(lhs == rhs);
1002         }
1003       friend constexpr bool operator<(D lhs, D rhs)
1004         requires std::totally_ordered<std::ranges::range_reference_t<D>> {
1005           return std::ranges::lexicographical_compare(lhs, rhs);
1006         }
1007       friend constexpr bool operator<=(D lhs, D rhs)
1008         requires std::totally_ordered<std::ranges::range_reference_t<D>> {
1009             return lhs == rhs || lhs < rhs;
1010           }
1011       friend constexpr bool operator>(D lhs, D rhs)
1012         requires std::totally_ordered<std::ranges::range_reference_t<D>> {
1013           return !(lhs <= rhs);
1014         }
1015       friend constexpr bool operator>=(D lhs, D rhs)
1016         requires std::totally_ordered<std::ranges::range_reference_t<D>> {
1017             return rhs <= lhs;
1018           }
1019 #endif
1020     };
1021
1022     // clang-format on
1023
1024 }}}
1025
1026 #endif
1027
1028 #endif