// Copyright (C) 2019 T. Zachary Laine
|
//
|
// Distributed under the Boost Software License, Version 1.0. (See
|
// accompanying file LICENSE_1_0.txt or copy at
|
// http://www.boost.org/LICENSE_1_0.txt)
|
#ifndef BOOST_STL_INTERFACES_CONTAINER_INTERFACE_HPP
|
#define BOOST_STL_INTERFACES_CONTAINER_INTERFACE_HPP
|
|
#include <boost/stl_interfaces/reverse_iterator.hpp>
|
|
#include <boost/assert.hpp>
|
#include <boost/config.hpp>
|
|
#include <algorithm>
|
#include <stdexcept>
|
#include <cstddef>
|
|
|
namespace boost { namespace stl_interfaces { namespace detail {
|
|
template<typename T, typename SizeType>
|
struct n_iter : iterator_interface<
|
n_iter<T, SizeType>,
|
std::random_access_iterator_tag,
|
T>
|
{
|
n_iter() : x_(nullptr), n_(0) {}
|
n_iter(T const & x, SizeType n) : x_(&x), n_(n) {}
|
|
constexpr std::ptrdiff_t operator-(n_iter other) const noexcept
|
{
|
return std::ptrdiff_t(n_) - std::ptrdiff_t(other.n_);
|
}
|
n_iter & operator+=(std::ptrdiff_t offset)
|
{
|
n_ += offset;
|
return *this;
|
}
|
|
private:
|
friend access;
|
constexpr T const *& base_reference() noexcept { return x_; }
|
constexpr T const * base_reference() const noexcept { return x_; }
|
|
T const * x_;
|
SizeType n_;
|
};
|
|
template<typename T, typename SizeType>
|
constexpr auto make_n_iter(T const & x, SizeType n) noexcept(
|
noexcept(n_iter<T, SizeType>(x, n)))
|
{
|
using result_type = n_iter<T, SizeType>;
|
return result_type(x, SizeType(0));
|
}
|
template<typename T, typename SizeType>
|
constexpr auto make_n_iter_end(T const & x, SizeType n) noexcept(
|
noexcept(n_iter<T, SizeType>(x, n)))
|
{
|
return n_iter<T, SizeType>(x, n);
|
}
|
|
template<typename Container>
|
std::size_t fake_capacity(Container const & c)
|
{
|
return SIZE_MAX;
|
}
|
template<
|
typename Container,
|
typename Enable = decltype(
|
std::size_t() = std::declval<Container const &>().capacity())>
|
std::size_t fake_capacity(Container const & c)
|
{
|
return c.capacity();
|
}
|
|
}}}
|
|
namespace boost { namespace stl_interfaces { inline namespace v1 {
|
|
/** A CRTP template that one may derive from to make it easier to define
|
container types.
|
|
The template parameter `D` for `sequence_container_interface` may be
|
an incomplete type. Before any member of the resulting specialization
|
of `sequence_container_interface` other than special member functions
|
is referenced, `D` shall be complete; shall model
|
`std::derived_from<sequence_container_interface<D>>`,
|
`std::semiregular`, and `std::forward_range`; and shall contain all
|
the nested types required in Table 72: Container requirements and, for
|
those whose iterator nested type models `std::bidirectinal_iterator`,
|
those in Table 73: Reversible container requirements.
|
|
For an object `d` of type `D`, a call to `std::ranges::begin(d)` sxhall
|
not mutate any data members of `d`, and `d`'s destructor shall end the
|
lifetimes of the objects in `[std::ranges::begin(d),
|
std::ranges::end(d))`. */
|
template<
|
typename Derived,
|
element_layout Contiguity = element_layout::discontiguous
|
#ifndef BOOST_STL_INTERFACES_DOXYGEN
|
,
|
typename E = std::enable_if_t<
|
std::is_class<Derived>::value &&
|
std::is_same<Derived, std::remove_cv_t<Derived>>::value>
|
#endif
|
>
|
struct sequence_container_interface;
|
|
namespace v1_dtl {
|
template<typename Iter>
|
using in_iter = std::is_convertible<
|
typename std::iterator_traits<Iter>::iterator_category,
|
std::input_iterator_tag>;
|
|
template<typename D, typename = void>
|
struct clear_impl
|
{
|
static constexpr void call(D & d) noexcept {}
|
};
|
template<typename D>
|
struct clear_impl<D, void_t<decltype(std::declval<D>().clear())>>
|
{
|
static constexpr void call(D & d) noexcept { d.clear(); }
|
};
|
|
template<typename D, element_layout Contiguity>
|
void derived_container(sequence_container_interface<D, Contiguity> const &);
|
}
|
|
template<
|
typename Derived,
|
element_layout Contiguity
|
#ifndef BOOST_STL_INTERFACES_DOXYGEN
|
,
|
typename E
|
#endif
|
>
|
struct sequence_container_interface
|
{
|
#ifndef BOOST_STL_INTERFACES_DOXYGEN
|
private:
|
constexpr Derived & derived() noexcept
|
{
|
return static_cast<Derived &>(*this);
|
}
|
constexpr const Derived & derived() const noexcept
|
{
|
return static_cast<Derived const &>(*this);
|
}
|
constexpr Derived & mutable_derived() const noexcept
|
{
|
return const_cast<Derived &>(static_cast<Derived const &>(*this));
|
}
|
#endif
|
|
public:
|
template<typename D = Derived>
|
constexpr auto empty() noexcept(
|
noexcept(std::declval<D &>().begin() == std::declval<D &>().end()))
|
-> decltype(
|
std::declval<D &>().begin() == std::declval<D &>().end())
|
{
|
return derived().begin() == derived().end();
|
}
|
template<typename D = Derived>
|
constexpr auto empty() const noexcept(noexcept(
|
std::declval<D const &>().begin() ==
|
std::declval<D const &>().end()))
|
-> decltype(
|
std::declval<D const &>().begin() ==
|
std::declval<D const &>().end())
|
{
|
return derived().begin() == derived().end();
|
}
|
|
template<
|
typename D = Derived,
|
element_layout C = Contiguity,
|
typename Enable = std::enable_if_t<C == element_layout::contiguous>>
|
constexpr auto data() noexcept(noexcept(std::declval<D &>().begin()))
|
-> decltype(std::addressof(*std::declval<D &>().begin()))
|
{
|
return std::addressof(*derived().begin());
|
}
|
template<
|
typename D = Derived,
|
element_layout C = Contiguity,
|
typename Enable = std::enable_if_t<C == element_layout::contiguous>>
|
constexpr auto data() const
|
noexcept(noexcept(std::declval<D const &>().begin()))
|
-> decltype(std::addressof(*std::declval<D const &>().begin()))
|
{
|
return std::addressof(*derived().begin());
|
}
|
|
template<typename D = Derived>
|
constexpr auto size()
|
#if !BOOST_CLANG
|
noexcept(noexcept(
|
std::declval<D &>().end() - std::declval<D &>().begin()))
|
#endif
|
-> decltype(typename D::size_type(
|
std::declval<D &>().end() - std::declval<D &>().begin()))
|
{
|
return derived().end() - derived().begin();
|
}
|
template<typename D = Derived>
|
constexpr auto size() const noexcept(noexcept(
|
std::declval<D const &>().end() -
|
std::declval<D const &>().begin()))
|
-> decltype(typename D::size_type(
|
#if !BOOST_CLANG
|
std::declval<D const &>().end() -
|
std::declval<D const &>().begin()
|
#endif
|
))
|
{
|
return derived().end() - derived().begin();
|
}
|
|
template<typename D = Derived>
|
constexpr auto front() noexcept(noexcept(*std::declval<D &>().begin()))
|
-> decltype(*std::declval<D &>().begin())
|
{
|
return *derived().begin();
|
}
|
template<typename D = Derived>
|
constexpr auto front() const
|
noexcept(noexcept(*std::declval<D const &>().begin()))
|
-> decltype(*std::declval<D const &>().begin())
|
{
|
return *derived().begin();
|
}
|
|
template<typename D = Derived>
|
constexpr auto push_front(typename D::value_type const & x) noexcept(
|
noexcept(std::declval<D &>().emplace_front(x)))
|
-> decltype((void)std::declval<D &>().emplace_front(x))
|
{
|
derived().emplace_front(x);
|
}
|
|
template<typename D = Derived>
|
constexpr auto push_front(typename D::value_type && x) noexcept(
|
noexcept(std::declval<D &>().emplace_front(std::move(x))))
|
-> decltype((void)std::declval<D &>().emplace_front(std::move(x)))
|
{
|
derived().emplace_front(std::move(x));
|
}
|
|
template<typename D = Derived>
|
constexpr auto pop_front() noexcept -> decltype(
|
std::declval<D &>().emplace_front(
|
std::declval<typename D::value_type &>()),
|
(void)std::declval<D &>().erase(std::declval<D &>().begin()))
|
{
|
derived().erase(derived().begin());
|
}
|
|
template<
|
typename D = Derived,
|
typename Enable = std::enable_if_t<
|
v1_dtl::decrementable_sentinel<D>::value &&
|
v1_dtl::common_range<D>::value>>
|
constexpr auto
|
back() noexcept(noexcept(*std::prev(std::declval<D &>().end())))
|
-> decltype(*std::prev(std::declval<D &>().end()))
|
{
|
return *std::prev(derived().end());
|
}
|
template<
|
typename D = Derived,
|
typename Enable = std::enable_if_t<
|
v1_dtl::decrementable_sentinel<D>::value &&
|
v1_dtl::common_range<D>::value>>
|
constexpr auto back() const
|
noexcept(noexcept(*std::prev(std::declval<D const &>().end())))
|
-> decltype(*std::prev(std::declval<D const &>().end()))
|
{
|
return *std::prev(derived().end());
|
}
|
|
template<typename D = Derived>
|
constexpr auto push_back(typename D::value_type const & x) noexcept(
|
noexcept(std::declval<D &>().emplace_back(x)))
|
-> decltype((void)std::declval<D &>().emplace_back(x))
|
{
|
derived().emplace_back(x);
|
}
|
|
template<typename D = Derived>
|
constexpr auto push_back(typename D::value_type && x) noexcept(
|
noexcept(std::declval<D &>().emplace_back(std::move(x))))
|
-> decltype((void)std::declval<D &>().emplace_back(std::move(x)))
|
{
|
derived().emplace_back(std::move(x));
|
}
|
|
template<typename D = Derived>
|
constexpr auto pop_back() noexcept -> decltype(
|
std::declval<D &>().emplace_back(
|
std::declval<typename D::value_type &>()),
|
(void)std::declval<D &>().erase(
|
std::prev(std::declval<D &>().end())))
|
{
|
derived().erase(std::prev(derived().end()));
|
}
|
|
template<typename D = Derived>
|
constexpr auto operator[](typename D::size_type n) noexcept(
|
noexcept(std::declval<D &>().begin()[n]))
|
-> decltype(std::declval<D &>().begin()[n])
|
{
|
return derived().begin()[n];
|
}
|
template<typename D = Derived>
|
constexpr auto operator[](typename D::size_type n) const
|
noexcept(noexcept(std::declval<D const &>().begin()[n]))
|
-> decltype(std::declval<D const &>().begin()[n])
|
{
|
return derived().begin()[n];
|
}
|
|
template<typename D = Derived>
|
constexpr auto at(typename D::size_type i)
|
-> decltype(std::declval<D &>().size(), std::declval<D &>()[i])
|
{
|
if (derived().size() <= i) {
|
throw std::out_of_range(
|
"Bounds check failed in sequence_container_interface::at()");
|
}
|
return derived()[i];
|
}
|
|
template<typename D = Derived>
|
constexpr auto at(typename D::size_type i) const -> decltype(
|
std::declval<D const &>().size(), std::declval<D const &>()[i])
|
{
|
if (derived().size() <= i) {
|
throw std::out_of_range(
|
"Bounds check failed in sequence_container_interface::at()");
|
}
|
return derived()[i];
|
}
|
|
template<typename D = Derived, typename Iter = typename D::const_iterator>
|
constexpr Iter begin() const
|
noexcept(noexcept(std::declval<D &>().begin()))
|
{
|
return Iter(mutable_derived().begin());
|
}
|
template<typename D = Derived, typename Iter = typename D::const_iterator>
|
constexpr Iter end() const noexcept(noexcept(std::declval<D &>().end()))
|
{
|
return Iter(mutable_derived().end());
|
}
|
|
template<typename D = Derived>
|
constexpr auto cbegin() const
|
noexcept(noexcept(std::declval<D const &>().begin()))
|
-> decltype(std::declval<D const &>().begin())
|
{
|
return derived().begin();
|
}
|
template<typename D = Derived>
|
constexpr auto cend() const
|
noexcept(noexcept(std::declval<D const &>().end()))
|
-> decltype(std::declval<D const &>().end())
|
{
|
return derived().end();
|
}
|
|
template<
|
typename D = Derived,
|
typename Enable = std::enable_if_t<v1_dtl::common_range<D>::value>>
|
constexpr auto rbegin() noexcept(noexcept(
|
stl_interfaces::make_reverse_iterator(std::declval<D &>().end())))
|
{
|
return stl_interfaces::make_reverse_iterator(derived().end());
|
}
|
template<
|
typename D = Derived,
|
typename Enable = std::enable_if_t<v1_dtl::common_range<D>::value>>
|
constexpr auto rend() noexcept(noexcept(
|
stl_interfaces::make_reverse_iterator(std::declval<D &>().begin())))
|
{
|
return stl_interfaces::make_reverse_iterator(derived().begin());
|
}
|
|
template<typename D = Derived>
|
constexpr auto rbegin() const
|
noexcept(noexcept(std::declval<D &>().rbegin()))
|
{
|
return
|
typename D::const_reverse_iterator(mutable_derived().rbegin());
|
}
|
template<typename D = Derived>
|
constexpr auto rend() const
|
noexcept(noexcept(std::declval<D &>().rend()))
|
{
|
return typename D::const_reverse_iterator(mutable_derived().rend());
|
}
|
|
template<typename D = Derived>
|
constexpr auto crbegin() const
|
noexcept(noexcept(std::declval<D const &>().rbegin()))
|
-> decltype(std::declval<D const &>().rbegin())
|
{
|
return derived().rbegin();
|
}
|
template<typename D = Derived>
|
constexpr auto crend() const
|
noexcept(noexcept(std::declval<D const &>().rend()))
|
-> decltype(std::declval<D const &>().rend())
|
{
|
return derived().rend();
|
}
|
|
template<typename D = Derived>
|
constexpr auto insert(
|
typename D::const_iterator pos,
|
typename D::value_type const &
|
x) noexcept(noexcept(std::declval<D &>().emplace(pos, x)))
|
-> decltype(std::declval<D &>().emplace(pos, x))
|
{
|
return derived().emplace(pos, x);
|
}
|
|
template<typename D = Derived>
|
constexpr auto insert(
|
typename D::const_iterator pos,
|
typename D::value_type &&
|
x) noexcept(noexcept(std::declval<D &>()
|
.emplace(pos, std::move(x))))
|
-> decltype(std::declval<D &>().emplace(pos, std::move(x)))
|
{
|
return derived().emplace(pos, std::move(x));
|
}
|
|
template<typename D = Derived>
|
constexpr auto insert(
|
typename D::const_iterator pos,
|
typename D::size_type n,
|
typename D::value_type const & x)
|
// If you see an error in this noexcept() expression, that's
|
// because this function is not properly constrained. In other
|
// words, Derived does not have a "range" insert like
|
// insert(position, first, last). If that is the case, this
|
// function should be removed via SFINAE from overload resolution.
|
// However, both the trailing decltype code below and a
|
// std::enable_if in the template parameters do not work. Sorry
|
// about that. See below for details.
|
noexcept(noexcept(std::declval<D &>().insert(
|
pos, detail::make_n_iter(x, n), detail::make_n_iter_end(x, n))))
|
// This causes the compiler to infinitely recurse into this function's
|
// declaration, even though the call below does not match the
|
// signature of this function.
|
#if 0
|
-> decltype(std::declval<D &>().insert(
|
pos, detail::make_n_iter(x, n), detail::make_n_iter_end(x, n)))
|
#endif
|
{
|
return derived().insert(
|
pos, detail::make_n_iter(x, n), detail::make_n_iter_end(x, n));
|
}
|
|
template<typename D = Derived>
|
constexpr auto insert(
|
typename D::const_iterator pos,
|
std::initializer_list<typename D::value_type>
|
il) noexcept(noexcept(std::declval<D &>()
|
.insert(pos, il.begin(), il.end())))
|
-> decltype(std::declval<D &>().insert(pos, il.begin(), il.end()))
|
{
|
return derived().insert(pos, il.begin(), il.end());
|
}
|
|
template<typename D = Derived>
|
constexpr auto erase(typename D::const_iterator pos) noexcept
|
-> decltype(std::declval<D &>().erase(pos, std::next(pos)))
|
{
|
return derived().erase(pos, std::next(pos));
|
}
|
|
template<
|
typename InputIterator,
|
typename D = Derived,
|
typename Enable =
|
std::enable_if_t<v1_dtl::in_iter<InputIterator>::value>>
|
constexpr auto assign(InputIterator first, InputIterator last) noexcept(
|
noexcept(std::declval<D &>().insert(
|
std::declval<D &>().begin(), first, last)))
|
-> decltype(
|
std::declval<D &>().erase(
|
std::declval<D &>().begin(), std::declval<D &>().end()),
|
(void)std::declval<D &>().insert(
|
std::declval<D &>().begin(), first, last))
|
{
|
auto out = derived().begin();
|
auto const out_last = derived().end();
|
for (; out != out_last && first != last; ++first, ++out) {
|
*out = *first;
|
}
|
if (out != out_last)
|
derived().erase(out, out_last);
|
if (first != last)
|
derived().insert(derived().end(), first, last);
|
}
|
|
template<typename D = Derived>
|
constexpr auto assign(
|
typename D::size_type n,
|
typename D::value_type const &
|
x) noexcept(noexcept(std::declval<D &>()
|
.insert(
|
std::declval<D &>().begin(),
|
detail::make_n_iter(x, n),
|
detail::make_n_iter_end(x, n))))
|
-> decltype(
|
std::declval<D &>().size(),
|
std::declval<D &>().erase(
|
std::declval<D &>().begin(), std::declval<D &>().end()),
|
(void)std::declval<D &>().insert(
|
std::declval<D &>().begin(),
|
detail::make_n_iter(x, n),
|
detail::make_n_iter_end(x, n)))
|
{
|
if (detail::fake_capacity(derived()) < n) {
|
Derived temp(n, x);
|
derived().swap(temp);
|
} else {
|
auto const min_size =
|
std::min<std::ptrdiff_t>(n, derived().size());
|
auto const fill_end =
|
std::fill_n(derived().begin(), min_size, x);
|
if (min_size < (std::ptrdiff_t)derived().size()) {
|
derived().erase(fill_end, derived().end());
|
} else {
|
n -= min_size;
|
derived().insert(
|
derived().begin(),
|
detail::make_n_iter(x, n),
|
detail::make_n_iter_end(x, n));
|
}
|
}
|
}
|
|
template<typename D = Derived>
|
constexpr auto
|
assign(std::initializer_list<typename D::value_type> il) noexcept(
|
noexcept(std::declval<D &>().assign(il.begin(), il.end())))
|
-> decltype((void)std::declval<D &>().assign(il.begin(), il.end()))
|
{
|
derived().assign(il.begin(), il.end());
|
}
|
|
template<typename D = Derived>
|
constexpr auto
|
operator=(std::initializer_list<typename D::value_type> il) noexcept(
|
noexcept(std::declval<D &>().assign(il.begin(), il.end())))
|
-> decltype(
|
std::declval<D &>().assign(il.begin(), il.end()),
|
std::declval<D &>())
|
{
|
derived().assign(il.begin(), il.end());
|
return *this;
|
}
|
|
template<typename D = Derived>
|
constexpr auto clear() noexcept
|
-> decltype((void)std::declval<D &>().erase(
|
std::declval<D &>().begin(), std::declval<D &>().end()))
|
{
|
derived().erase(derived().begin(), derived().end());
|
}
|
};
|
|
/** Implementation of free function `swap()` for all containers derived
|
from `sequence_container_interface`. */
|
template<typename ContainerInterface>
|
constexpr auto swap(
|
ContainerInterface & lhs,
|
ContainerInterface & rhs) noexcept(noexcept(lhs.swap(rhs)))
|
-> decltype(v1_dtl::derived_container(lhs), lhs.swap(rhs))
|
{
|
return lhs.swap(rhs);
|
}
|
|
/** Implementation of `operator==()` for all containers derived from
|
`sequence_container_interface`. */
|
template<typename ContainerInterface>
|
constexpr auto
|
operator==(ContainerInterface const & lhs, ContainerInterface const & rhs) noexcept(
|
noexcept(lhs.size() == rhs.size()) &&
|
noexcept(*lhs.begin() == *rhs.begin()))
|
-> decltype(
|
v1_dtl::derived_container(lhs),
|
lhs.size() == rhs.size(),
|
*lhs.begin() == *rhs.begin(),
|
true)
|
{
|
return lhs.size() == rhs.size() &&
|
std::equal(lhs.begin(), lhs.end(), rhs.begin());
|
}
|
|
/** Implementation of `operator!=()` for all containers derived from
|
`sequence_container_interface`. */
|
template<typename ContainerInterface>
|
constexpr auto operator!=(
|
ContainerInterface const & lhs,
|
ContainerInterface const & rhs) noexcept(noexcept(lhs == rhs))
|
-> decltype(v1_dtl::derived_container(lhs), lhs == rhs)
|
{
|
return !(lhs == rhs);
|
}
|
|
/** Implementation of `operator<()` for all containers derived from
|
`sequence_container_interface`. */
|
template<typename ContainerInterface>
|
constexpr auto operator<(
|
ContainerInterface const & lhs,
|
ContainerInterface const &
|
rhs) noexcept(noexcept(*lhs.begin() < *rhs.begin()))
|
-> decltype(
|
v1_dtl::derived_container(lhs), *lhs.begin() < *rhs.begin(), true)
|
{
|
auto it1 = lhs.begin();
|
auto const last1 = lhs.end();
|
auto it2 = rhs.begin();
|
auto const last2 = rhs.end();
|
for (; it1 != last1 && it2 != last2; ++it1, ++it2) {
|
if (*it1 < *it2)
|
return true;
|
if (*it2 < *it1)
|
return false;
|
}
|
return it1 == last1 && it2 != last2;
|
}
|
|
/** Implementation of `operator<=()` for all containers derived from
|
`sequence_container_interface`. */
|
template<typename ContainerInterface>
|
constexpr auto operator<=(
|
ContainerInterface const & lhs,
|
ContainerInterface const & rhs) noexcept(noexcept(lhs < rhs))
|
-> decltype(v1_dtl::derived_container(lhs), lhs < rhs)
|
{
|
return !(rhs < lhs);
|
}
|
|
/** Implementation of `operator>()` for all containers derived from
|
`sequence_container_interface`. */
|
template<typename ContainerInterface>
|
constexpr auto operator>(
|
ContainerInterface const & lhs,
|
ContainerInterface const & rhs) noexcept(noexcept(lhs < rhs))
|
-> decltype(v1_dtl::derived_container(lhs), lhs < rhs)
|
{
|
return rhs < lhs;
|
}
|
|
/** Implementation of `operator>=()` for all containers derived from
|
`sequence_container_interface`. */
|
template<typename ContainerInterface>
|
constexpr auto operator>=(
|
ContainerInterface const & lhs,
|
ContainerInterface const & rhs) noexcept(noexcept(lhs < rhs))
|
-> decltype(v1_dtl::derived_container(lhs), lhs < rhs)
|
{
|
return !(lhs < rhs);
|
}
|
|
}}}
|
|
#endif
|
