#ifndef STD_EXPERIMENTAL_FIXED_CAPACITY_VECTOR
#define STD_EXPERIMENTAL_FIXED_CAPACITY_VECTOR
/// \file
///
/// Dynamically-resizable vector with fixed-capacity.
///
/// Copyright Gonzalo Brito Gadeschi 2015-2017
/// Copyright Eric Niebler 2013-2014
/// Copyright Casey Carter 2016
///
/// This file is released under the Boost Software License:
//
// Boost Software License - Version 1.0 - August 17th, 2003
//
// Permission is hereby granted, free of charge, to any person or organization
// obtaining a copy of the software and accompanying documentation covered by
// this license (the "Software") to use, reproduce, display, distribute,
// execute, and transmit the Software, and to prepare derivative works of the
// Software, and to permit third-parties to whom the Software is furnished to
// do so, all subject to the following:
//
// The copyright notices in the Software and this entire statement, including
// the above license grant, this restriction and the following disclaimer,
// must be included in all copies of the Software, in whole or in part, and
// all derivative works of the Software, unless such copies or derivative
// works are solely in the form of machine-executable object code generated by
// a source language processor.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.
//
// Some of the code has been adapted from the range-v3 library:
//
// https://github.com/ericniebler/range-v3/
//
// which is also under the Boost Software license.
//
// Some of the code has been adapted from libc++:
//
// and is annotated with "adapted from libc++" below, and is thus under the
// following license:
//
//===----------------------------------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is dual licensed under the MIT and the University of Illinois Open
// Source Licenses. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
#include <array>
#include <cstddef>      // for size_t
#include <cstdint>      // for fixed-width integer types
#include <functional>   // for less and equal_to
#include <iterator>     // for reverse_iterator and iterator traits
#include <limits>       // for numeric_limits
#include <stdexcept>    // for length_error
#include <type_traits>  // for aligned_storage and all meta-functions
#include <cassert>

/// Unreachable code
#ifdef _MSC_VER
#define FCV_UNREACHABLE __assume(false)
#else
#define FCV_UNREACHABLE __builtin_unreachable()
#endif

/// Optimizer allowed to assume that EXPR evaluates to true
#define FCV_ASSUME(EXPR) \
    static_cast<void>((EXPR) ? void(0) : FCV_UNREACHABLE)

/// Likely/unlikely branches
#define FCV_LIKELY(boolean_expr) __builtin_expect(!!(boolean_expr), 1)
#define FCV_UNLIKELY(boolean_expr) __builtin_expect(!!(boolean_expr), 0)

/// Expect asserts the condition in debug builds and assumes the condition to be
/// true in release builds.
#ifdef NDEBUG
#define FCV_EXPECT(EXPR) FCV_ASSUME(EXPR)
#else
#define FCV_EXPECT(EXPR) assert(EXPR)
#endif

#define FCV_CONCEPT_PP_CAT_(X, Y) X##Y
#define FCV_CONCEPT_PP_CAT(X, Y) FCV_CONCEPT_PP_CAT_(X, Y)

/// Requires-clause emulation with SFINAE (for templates)
#define FCV_REQUIRES_(...)                                                 \
    int FCV_CONCEPT_PP_CAT(_concept_requires_, __LINE__)                   \
        = 42,                                                              \
        typename ::std::enable_if                                          \
                < (FCV_CONCEPT_PP_CAT(_concept_requires_, __LINE__) == 43) \
            || (__VA_ARGS__),                                              \
        int > ::type = 0 /**/

/// Requires-clause emulation with SFINAE (for "non-templates")
#define FCV_REQUIRES(...)                                                  \
    template <int FCV_CONCEPT_PP_CAT(_concept_requires_, __LINE__) = 42,   \
              typename ::std::enable_if<                                   \
                  (FCV_CONCEPT_PP_CAT(_concept_requires_, __LINE__) == 43) \
                      || (__VA_ARGS__),                                    \
                  int>::type                                               \
              = 0> /**/

namespace std
{
    namespace experimental
    {
        // Private utilites (each std lib should already have this)
        namespace fcv_detail
        {
            /// \name Utilities
            ///@{

            template <bool v>
            using bool_ = integral_constant<bool, v>;

            /// \name Concepts (poor-man emulation using type traits)
            ///@{
            template <typename T, typename... Args>
            static constexpr bool Constructible
                = is_constructible_v<T, Args...>;

            template <typename T>
            static constexpr bool CopyConstructible
                = is_copy_constructible_v<T>;

            template <typename T>
            static constexpr bool MoveConstructible
                = is_move_constructible_v<T>;

            template <typename T, typename U>
            static constexpr bool Assignable = is_assignable_v<T, U>;

            template <typename T>
            static constexpr bool Movable = is_object_v<T>&& Assignable<T&, T>&&
                MoveConstructible<T>&& is_swappable_v<T&>;

            template <typename From, typename To>
            static constexpr bool Convertible = is_convertible_v<From, To>;

            template <typename T>
            static constexpr bool Trivial = is_trivial_v<T>;

            template <typename T>
            static constexpr bool Const = is_const_v<T>;

            template <typename T>
            static constexpr bool Pointer = is_pointer_v<T>;
            ///@}  // Concepts

            template <typename Rng>
            using range_iterator_t = decltype(begin(declval<Rng>()));

            template <typename T>
            using iterator_reference_t = typename iterator_traits<T>::reference;

            template <typename T>
            using iterator_category_t =
                typename iterator_traits<T>::iterator_category;

            template <typename T, typename Cat, typename = void>
            struct Iterator_ : false_type
            {
            };

            template <typename T, typename Cat>
            struct Iterator_<T, Cat, void_t<iterator_category_t<T>>>
                : bool_<Convertible<iterator_category_t<T>, Cat>>
            {
            };

            /// \name Concepts (poor-man emulation using type traits)
            ///@{
            template <typename T>
            static constexpr bool InputIterator
                = Iterator_<T, input_iterator_tag>{};

            template <typename T>
            static constexpr bool ForwardIterator
                = Iterator_<T, forward_iterator_tag>{};

            template <typename T>
            static constexpr bool OutputIterator
                = Iterator_<T, output_iterator_tag>{} || ForwardIterator<T>;

            template <typename T>
            static constexpr bool BidirectionalIterator
                = Iterator_<T, bidirectional_iterator_tag>{};

            template <typename T>
            static constexpr bool RandomAccessIterator
                = Iterator_<T, random_access_iterator_tag>{};

            template <typename T>
            static constexpr bool RandomAccessRange
                = RandomAccessIterator<range_iterator_t<T>>;
            ///@}  // Concepts

            // clang-format off

            /// Smallest fixed-width unsigned integer type that can represent
            /// values in the range [0, N].
            template <size_t N>
            using smallest_size_t
                = conditional_t<(N < numeric_limits<uint8_t>::max()),  uint8_t,
                  conditional_t<(N < numeric_limits<uint16_t>::max()), uint16_t,
                  conditional_t<(N < numeric_limits<uint32_t>::max()), uint32_t,
                  conditional_t<(N < numeric_limits<uint64_t>::max()), uint64_t,
                                 size_t>>>>;
            // clang-format on

            /// Index a range doing bound checks in debug builds
            template <typename Rng, typename Index,
                      FCV_REQUIRES_(RandomAccessRange<Rng>)>
            constexpr decltype(auto) index(Rng&& rng, Index&& i) noexcept
            {
                FCV_EXPECT(static_cast<ptrdiff_t>(i) < (end(rng) - begin(rng)));
                return begin(forward<Rng>(rng))[forward<Index>(i)];
            }

            /// \name Workarounds
            ///@{

            // WORKAROUND: std::rotate is not constexpr
            template <typename ForwardIt,
                      FCV_REQUIRES_(ForwardIterator<ForwardIt>)>
            constexpr void slow_rotate(ForwardIt first, ForwardIt n_first,
                                       ForwardIt last)
            {
                ForwardIt next = n_first;
                while (first != next)
                {
                    swap(*(first++), *(next++));
                    if (next == last)
                    {
                        next = n_first;
                    }
                    else if (first == n_first)
                    {
                        n_first = next;
                    }
                }
            }

            // WORKAROUND: std::move is not constexpr
            template <typename InputIt, typename OutputIt,
                      FCV_REQUIRES_(
                          InputIterator<InputIt>&& OutputIterator<OutputIt>)>
            constexpr OutputIt move(InputIt b, InputIt e, OutputIt to)
            {
                for (; b != e; ++b, (void)++to)
                {
                    *to = ::std::move(*b);
                }
                return to;
            }

            // WORKAROUND: std::equal is not constexpr
            template <class BinaryPredicate, class InputIterator1,
                      class InputIterator2,
                      FCV_REQUIRES_(InputIterator<InputIterator1>&&
                                        InputIterator<InputIterator2>)>
            constexpr bool cmp(InputIterator1 first1, InputIterator1 last1,
                               InputIterator2 first2, InputIterator2 last2,
                               BinaryPredicate pred)
            {
                for (; first1 != last1 && first2 != last2;
                     ++first1, (void)++first2)
                {
                    if (!pred(*first1, *first2))
                    {
                        return false;
                    }
                }
                return first1 == last1 && first2 == last2;
            }

            ///@}  // Workarounds

            ///@} // Utilities

            /// Types implementing the `fixed_capactiy_vector`'s storage
            namespace storage
            {
                /// Storage for zero elements.
                template <typename T>
                struct zero_sized
                {
                    using size_type       = uint8_t;
                    using value_type      = T;
                    using difference_type = ptrdiff_t;
                    using pointer         = T*;
                    using const_pointer   = T const*;

                    /// Pointer to the data in the storage.
                    static constexpr pointer data() noexcept
                    {
                        return nullptr;
                    }
                    /// Number of elements currently stored.
                    static constexpr size_type size() noexcept
                    {
                        return 0;
                    }
                    /// Capacity of the storage.
                    static constexpr size_type capacity() noexcept
                    {
                        return 0;
                    }
                    /// Is the storage empty?
                    static constexpr bool empty() noexcept
                    {
                        return true;
                    }
                    /// Is the storage full?
                    static constexpr bool full() noexcept
                    {
                        return true;
                    }

                    /// Constructs a new element at the end of the storage
                    /// in-place.
                    ///
                    /// Increases size of the storage by one.
                    /// Always fails for empty storage.
                    template <typename... Args,
                              FCV_REQUIRES_(Constructible<T, Args...>)>
                    static constexpr void emplace_back(Args&&...) noexcept
                    {
                        FCV_EXPECT(false
                                   && "tried to emplace_back on empty storage");
                    }
                    /// Removes the last element of the storage.
                    /// Always fails for empty storage.
                    static constexpr void pop_back() noexcept
                    {
                        FCV_EXPECT(false
                                   && "tried to pop_back on empty storage");
                    }
                    /// Changes the size of the storage without adding or
                    /// removing elements (unsafe).
                    ///
                    /// The size of an empty storage can only be changed to 0.
                    static constexpr void unsafe_set_size(
                        size_t new_size) noexcept
                    {
                        FCV_EXPECT(
                            new_size == 0
                            && "tried to change size of empty storage to "
                               "non-zero value");
                    }

                    /// Destroys all elements of the storage in range [begin,
                    /// end) without changings its size (unsafe).
                    ///
                    /// Nothing to destroy since the storage is empty.
                    template <typename InputIt,
                              FCV_REQUIRES_(InputIterator<InputIt>)>
                    static constexpr void unsafe_destroy(
                        InputIt /* begin */, InputIt /* end */) noexcept
                    {
                    }

                    /// Destroys all elements of the storage without changing
                    /// its size (unsafe).
                    ///
                    /// Nothing to destroy since the storage is empty.
                    static constexpr void unsafe_destroy_all() noexcept
                    {
                    }

                    constexpr zero_sized()                  = default;
                    constexpr zero_sized(zero_sized const&) = default;
                    constexpr zero_sized& operator          =(zero_sized const&)
                        = default;
                    constexpr zero_sized(zero_sized&&) = default;
                    constexpr zero_sized& operator=(zero_sized&&) = default;
                    ~zero_sized()                                 = default;

                    /// Constructs an empty storage from an initializer list of
                    /// zero elements.
                    template <typename U, FCV_REQUIRES_(Convertible<U, T>)>
                    constexpr zero_sized(initializer_list<U> il) noexcept
                    {
                        FCV_EXPECT(
                            il.size() == 0
                            && "tried to construct storage::empty from a "
                               "non-empty initializer list");
                    }
                };

                /// Storage for trivial types.
                template <typename T, size_t Capacity>
                struct trivial
                {
                    static_assert(Trivial<T>,
                                  "storage::trivial<T, C> requires Trivial<T>");
                    static_assert(Capacity != size_t{0},
                                  "Capacity must be greater "
                                  "than zero (use "
                                  "storage::zero_sized instead)");

                    using size_type       = smallest_size_t<Capacity>;
                    using value_type      = T;
                    using difference_type = ptrdiff_t;
                    using pointer         = T*;
                    using const_pointer   = T const*;

                  private:
                    // If the value_type is const, make a const array of
                    // non-const elements:
                    using data_t = conditional_t<
                        !Const<T>, array<T, Capacity>,
                        const array<remove_const_t<T>, Capacity>>;
                    alignas(alignof(T)) data_t data_{};

                    /// Number of elements allocated in the storage:
                    size_type size_ = 0;

                  public:
                    /// Direct access to the underlying storage.
                    ///
                    /// Complexity: O(1) in time and space.
                    constexpr const_pointer data() const noexcept
                    {
                        return data_.data();
                    }

                    /// Direct access to the underlying storage.
                    ///
                    /// Complexity: O(1) in time and space.
                    constexpr pointer data() noexcept
                    {
                        return data_.data();
                    }

                    /// Number of elements in the storage.
                    ///
                    /// Complexity: O(1) in time and space.
                    constexpr size_type size() const noexcept
                    {
                        return size_;
                    }

                    /// Maximum number of elements that can be allocated in the
                    /// storage.
                    ///
                    /// Complexity: O(1) in time and space.
                    static constexpr size_type capacity() noexcept
                    {
                        return Capacity;
                    }

                    /// Is the storage empty?
                    constexpr bool empty() const noexcept
                    {
                        return size() == size_type{0};
                    }

                    /// Is the storage full?
                    constexpr bool full() const noexcept
                    {
                        return size() == Capacity;
                    }

                    /// Constructs an element in-place at the end of the
                    /// storage.
                    ///
                    /// Complexity: O(1) in time and space.
                    /// Contract: the storage is not full.
                    template <typename... Args,
                              FCV_REQUIRES_(Constructible<T, Args...>and
                                                Assignable<value_type&, T>)>
                    constexpr void emplace_back(Args&&... args) noexcept
                    {
                        FCV_EXPECT(!full()
                                   && "tried to emplace_back on full storage!");
                        index(data_, size()) = T(forward<Args>(args)...);
                        unsafe_set_size(size() + 1);
                    }

                    /// Remove the last element from the container.
                    ///
                    /// Complexity: O(1) in time and space.
                    /// Contract: the storage is not empty.
                    constexpr void pop_back() noexcept
                    {
                        FCV_EXPECT(!empty()
                                   && "tried to pop_back from empty storage!");
                        unsafe_set_size(size() - 1);
                    }

                    /// (unsafe) Changes the container size to \p new_size.
                    ///
                    /// Contract: `new_size <= capacity()`.
                    /// \warning No elements are constructed or destroyed.
                    constexpr void unsafe_set_size(size_t new_size) noexcept
                    {
                        FCV_EXPECT(new_size <= Capacity
                                   && "new_size out-of-bounds [0, Capacity]");
                        size_ = size_type(new_size);
                    }

                    /// (unsafe) Destroy elements in the range [begin, end).
                    ///
                    /// \warning: The size of the storage is not changed.
                    template <typename InputIt,
                              FCV_REQUIRES_(InputIterator<InputIt>)>
                    constexpr void unsafe_destroy(InputIt, InputIt) noexcept
                    {
                    }

                    /// (unsafe) Destroys all elements of the storage.
                    ///
                    /// \warning: The size of the storage is not changed.
                    static constexpr void unsafe_destroy_all() noexcept
                    {
                    }

                    constexpr trivial() noexcept               = default;
                    constexpr trivial(trivial const&) noexcept = default;
                    constexpr trivial& operator=(trivial const&) noexcept
                        = default;
                    constexpr trivial(trivial&&) noexcept = default;
                    constexpr trivial& operator=(trivial&&) noexcept = default;
                    ~trivial()                                       = default;

                  private:
                    template <typename U, FCV_REQUIRES_(Convertible<U, T>)>
                    static constexpr array<remove_const_t<T>, Capacity>
                    unsafe_recast_init_list(initializer_list<U>& il) noexcept
                    {
                        FCV_EXPECT(
                            il.size() <= capacity()
                            && "trying to construct storage from an "
                               "initializer_list "
                               "whose size exceeds the storage capacity");
                        array<remove_const_t<T>, Capacity> d_{};
                        for (size_t i = 0, e = il.size(); i < e; ++i)
                        {
                            index(d_, i) = index(il, i);
                        }
                        return d_;
                    }

                  public:
                    /// Constructor from initializer list.
                    ///
                    /// Contract: `il.size() <= capacity()`.
                    template <typename U, FCV_REQUIRES_(Convertible<U, T>)>
                    constexpr trivial(initializer_list<U> il) noexcept
                        : data_(unsafe_recast_init_list(il))
                    {
                        unsafe_set_size(static_cast<size_type>(il.size()));
                    }
                };

                /// Storage for non-trivial elements.
                template <typename T, size_t Capacity>
                struct non_trivial
                {
                    static_assert(
                        !Trivial<T>,
                        "use storage::trivial for Trivial<T> elements");
                    static_assert(Capacity != size_t{0},
                                  "Capacity must be greater than zero!");

                    /// Smallest size_type that can represent Capacity:
                    using size_type       = smallest_size_t<Capacity>;
                    using value_type      = T;
                    using difference_type = ptrdiff_t;
                    using pointer         = T*;
                    using const_pointer   = T const*;

                  private:
                    /// Number of elements allocated in the embedded storage:
                    size_type size_ = 0;

                    using storage_t
                        = aligned_storage_t<sizeof(remove_const_t<T>),
                                            alignof(remove_const_t<T>)>;
                    using data_t = conditional_t<!Const<T>, storage_t,
                                                 const storage_t>;
                    alignas(alignof(T)) data_t data_[Capacity]{};
                    // FIXME: ^ this won't work for types with "broken" alignof
                    // like SIMD types (one would also need to provide an
                    // overload of operator new to make heap allocations of this
                    // type work for these types).

                  public:
                    /// Direct access to the underlying storage.
                    ///
                    /// Complexity: O(1) in time and space.
                    const_pointer data() const noexcept
                    {
                        return reinterpret_cast<const_pointer>(data_);
                    }

                    /// Direct access to the underlying storage.
                    ///
                    /// Complexity: O(1) in time and space.
                    pointer data() noexcept
                    {
                        return reinterpret_cast<pointer>(data_);
                    }

                    /// Pointer to one-past-the-end.
                    const_pointer end() const noexcept
                    {
                        return data() + size();
                    }

                    /// Pointer to one-past-the-end.
                    pointer end() noexcept
                    {
                        return data() + size();
                    }

                    /// Number of elements in the storage.
                    ///
                    /// Complexity: O(1) in time and space.
                    constexpr size_type size() const noexcept
                    {
                        return size_;
                    }

                    /// Maximum number of elements that can be allocated in the
                    /// storage.
                    ///
                    /// Complexity: O(1) in time and space.
                    static constexpr size_type capacity() noexcept
                    {
                        return Capacity;
                    }

                    /// Is the storage empty?
                    constexpr bool empty() const noexcept
                    {
                        return size() == size_type{0};
                    }

                    /// Is the storage full?
                    constexpr bool full() const noexcept
                    {
                        return size() == Capacity;
                    }

                    /// Constructs an element in-place at the end of the
                    /// embedded storage.
                    ///
                    /// Complexity: O(1) in time and space.
                    /// Contract: the storage is not full.
                    template <typename... Args,
                              FCV_REQUIRES_(Constructible<T, Args...>)>
                    void emplace_back(Args&&... args) noexcept(
                        noexcept(new (end()) T(forward<Args>(args)...)))
                    {
                        FCV_EXPECT(!full()
                                   && "tried to emplace_back on full storage");
                        new (end()) T(forward<Args>(args)...);
                        unsafe_set_size(size() + 1);
                    }

                    /// Remove the last element from the container.
                    ///
                    /// Complexity: O(1) in time and space.
                    /// Contract: the storage is not empty.
                    void pop_back() noexcept(is_nothrow_destructible_v<T>)
                    {
                        FCV_EXPECT(!empty()
                                   && "tried to pop_back from empty storage!");
                        auto ptr = end() - 1;
                        ptr->~T();
                        unsafe_set_size(size() - 1);
                    }

                    /// (unsafe) Changes the container size to \p new_size.
                    ///
                    /// Contract: `new_size <= capacity()`.
                    /// \warning No elements are constructed or destroyed.
                    constexpr void unsafe_set_size(size_t new_size) noexcept
                    {
                        FCV_EXPECT(new_size <= Capacity
                                   && "new_size out-of-bounds [0, Capacity)");
                        size_ = size_type(new_size);
                    }

                    /// (unsafe) Destroy elements in the range [begin, end).
                    ///
                    /// \warning: The size of the storage is not changed.
                    template <typename InputIt,
                              FCV_REQUIRES_(InputIterator<InputIt>)>
                    void unsafe_destroy(InputIt first, InputIt last) noexcept(
                        is_nothrow_destructible_v<T>)
                    {
                        FCV_EXPECT(first >= data() && first <= end()
                                   && "first is out-of-bounds");
                        FCV_EXPECT(last >= data() && last <= end()
                                   && "last is out-of-bounds");
                        for (; first != last; ++first)
                        {
                            first->~T();
                        }
                    }

                    /// (unsafe) Destroys all elements of the storage.
                    ///
                    /// \warning: The size of the storage is not changed.
                    void unsafe_destroy_all() noexcept(
                        is_nothrow_destructible_v<T>)
                    {
                        unsafe_destroy(data(), end());
                    }

                    constexpr non_trivial()                   = default;
                    constexpr non_trivial(non_trivial const&) = default;
                    constexpr non_trivial& operator=(non_trivial const&)
                        = default;
                    constexpr non_trivial(non_trivial&&) = default;
                    constexpr non_trivial& operator=(non_trivial&&) = default;
                    ~non_trivial() noexcept(is_nothrow_destructible_v<T>)
                    {
                        unsafe_destroy_all();
                    }

                    /// Constructor from initializer list.
                    ///
                    /// Contract: `il.size() <= capacity()`.
                    template <typename U, FCV_REQUIRES_(Convertible<U, T>)>
                    constexpr non_trivial(initializer_list<U> il) noexcept(
                        noexcept(declval<non_trivial>().emplace_back(index(il, 0))))
                    {
                        FCV_EXPECT(
                            il.size() <= capacity()
                            && "trying to construct storage from an "
                               "initializer_list "
                               "whose size exceeds the storage capacity");
                        for (size_t i = 0; i < il.size(); ++i)
                        {
                            emplace_back(index(il, i));
                        }
                    }
                };

                /// Selects the vector storage.
                template <typename T, size_t Capacity>
                using _t = conditional_t<
                    Capacity == 0, zero_sized<T>,
                    conditional_t<Trivial<T>, trivial<T, Capacity>,
                                  non_trivial<T, Capacity>>>;

            }  // namespace storage

        }  // namespace fcv_detail

        /// Dynamically-resizable fixed-capacity vector.
        template <typename T, size_t Capacity>
        struct fixed_capacity_vector
            : private fcv_detail::storage::_t<T, Capacity>
        {
          private:
            static_assert(is_nothrow_destructible_v<T>,
                          "T must be nothrow destructible");
            using base_t = fcv_detail::storage::_t<T, Capacity>;
            using self   = fixed_capacity_vector<T, Capacity>;

            using base_t::unsafe_destroy;
            using base_t::unsafe_destroy_all;
            using base_t::unsafe_set_size;

          public:
            using value_type       = typename base_t::value_type;
            using difference_type  = ptrdiff_t;
            using reference        = value_type&;
            using const_reference  = value_type const&;
            using pointer          = typename base_t::pointer;
            using const_pointer    = typename base_t::const_pointer;
            using iterator         = typename base_t::pointer;
            using const_iterator   = typename base_t::const_pointer;
            using size_type        = size_t;
            using reverse_iterator = ::std::reverse_iterator<iterator>;
            using const_reverse_iterator
                = ::std::reverse_iterator<const_iterator>;

            /// \name Size / capacity
            ///@{
            using base_t::empty;
            using base_t::full;

            /// Number of elements in the vector
            constexpr size_type size() const noexcept
            {
                return base_t::size();
            }

            /// Maximum number of elements that can be allocated in the vector
            static constexpr size_type capacity() noexcept
            {
                return base_t::capacity();
            }

            /// Maximum number of elements that can be allocated in the vector
            static constexpr size_type max_size() noexcept
            {
                return capacity();
            }

            ///@} // Size / capacity

            /// \name Data access
            ///@{

            using base_t::data;

            ///@} // Data access

            /// \name Iterators
            ///@{

            constexpr iterator begin() noexcept
            {
                return data();
            }
            constexpr const_iterator begin() const noexcept
            {
                return data();
            }
            constexpr iterator end() noexcept
            {
                return data() + size();
            }
            constexpr const_iterator end() const noexcept
            {
                return data() + size();
            }

            reverse_iterator rbegin() noexcept
            {
                return reverse_iterator(end());
            }
            const_reverse_iterator rbegin() const noexcept
            {
                return const_reverse_iterator(end());
            }
            reverse_iterator rend() noexcept
            {
                return reverse_iterator(begin());
            }
            const_reverse_iterator rend() const noexcept
            {
                return const_reverse_iterator(begin());
            }

            constexpr const_iterator cbegin() noexcept
            {
                return begin();
            }
            constexpr const_iterator cbegin() const noexcept
            {
                return begin();
            }
            constexpr const_iterator cend() noexcept
            {
                return end();
            }
            constexpr const_iterator cend() const noexcept
            {
                return end();
            }

            ///@}  // Iterators

          private:
            /// \name Iterator bound-check utilites
            ///@{

            template <typename It>
            constexpr void assert_iterator_in_range(It it) noexcept
            {
                static_assert(fcv_detail::Pointer<It>);
                FCV_EXPECT(begin() <= it && "iterator not in range");
                FCV_EXPECT(it <= end() && "iterator not in range");
            }

            template <typename It0, typename It1>
            constexpr void assert_valid_iterator_pair(It0 first,
                                                      It1 last) noexcept
            {
                static_assert(fcv_detail::Pointer<It0>);
                static_assert(fcv_detail::Pointer<It1>);
                FCV_EXPECT(first <= last && "invalid iterator pair");
            }

            template <typename It0, typename It1>
            constexpr void assert_iterator_pair_in_range(It0 first,
                                                         It1 last) noexcept
            {
                assert_iterator_in_range(first);
                assert_iterator_in_range(last);
                assert_valid_iterator_pair(first, last);
            }

            ///@}
          public:
            /// \name Element access
            ///
            ///@{

            /// Unchecked access to element at index \p pos (UB if index not in
            /// range)
            constexpr reference operator[](size_type pos) noexcept
            {
                return fcv_detail::index(*this, pos);
            }

            /// Unchecked access to element at index \p pos (UB if index not in
            /// range)
            constexpr const_reference operator[](size_type pos) const noexcept
            {
                return fcv_detail::index(*this, pos);
            }

            /// Checked access to element at index \p pos (throws `out_of_range`
            /// if index not in range)
            constexpr reference at(size_type pos)
            {
                if (FCV_UNLIKELY(pos >= size()))
                {
                    throw out_of_range("fixed_capacity_vector::at");
                }
                return fcv_detail::index(*this, pos);
            }

            /// Checked access to element at index \p pos (throws `out_of_range`
            /// if index not in range)
            constexpr const_reference at(size_type pos) const
            {
                if (FCV_UNLIKELY(pos >= size()))
                {
                    throw out_of_range("fixed_capacity_vector::at");
                }
                return fcv_detail::index(*this, pos);
            }

            ///
            constexpr reference front() noexcept
            {
                return fcv_detail::index(*this, 0);
            }
            constexpr const_reference front() const noexcept
            {
                return fcv_detail::index(*this, 0);
            }

            constexpr reference back() noexcept
            {
                FCV_EXPECT(!empty() && "calling back on an empty vector");
                return fcv_detail::index(*this, size() - 1);
            }
            constexpr const_reference back() const noexcept
            {
                FCV_EXPECT(!empty() && "calling back on an empty vector");
                return fcv_detail::index(*this, size() - 1);
            }

            ///@} // Element access

            /// \name Modifiers
            ///@{

            using base_t::emplace_back;
            using base_t::pop_back;

            /// Clears the vector.
            constexpr void clear() noexcept
            {
                unsafe_destroy_all();
                unsafe_set_size(0);
            }

            /// Appends \p value at the end of the vector.
            template <typename U,
                      FCV_REQUIRES_(fcv_detail::Constructible<T, U>&&
                                        fcv_detail::Assignable<reference, U&&>)>
            constexpr void push_back(U&& value) noexcept(
                noexcept(declval<fixed_capacity_vector>().emplace_back(forward<U>(value))))
            {
                FCV_EXPECT(!full() && "vector is full!");
                emplace_back(forward<U>(value));
            }

            /// Appends a default constructed `T` at the end of the vector.
            FCV_REQUIRES(fcv_detail::Constructible<T, T>&&
                             fcv_detail::Assignable<reference, T&&>)
            void push_back() noexcept(noexcept(declval<fixed_capacity_vector>().emplace_back(T{})))
            {
                FCV_EXPECT(!full() && "vector is full!");
                emplace_back(T{});
            }

            template <typename... Args,
                      FCV_REQUIRES_(fcv_detail::Constructible<T, Args...>)>
            constexpr iterator
            emplace(const_iterator position, Args&&... args) noexcept(
                noexcept(declval<fixed_capacity_vector>().move_insert(position, declval<value_type*>(),
                                     declval<value_type*>())))
            {
                FCV_EXPECT(!full()
                           && "tried emplace on full fixed_capacity_vector!");
                assert_iterator_in_range(position);
                value_type a(forward<Args>(args)...);
                return move_insert(position, &a, &a + 1);
            }
            FCV_REQUIRES(fcv_detail::CopyConstructible<T>)
            constexpr iterator insert(
                const_iterator position,
                const_reference x) noexcept(noexcept(declval<fixed_capacity_vector>().insert(position,
                                                            size_type(1), x)))
            {
                FCV_EXPECT(!full()
                           && "tried insert on full fixed_capacity_vector!");
                assert_iterator_in_range(position);
                return insert(position, size_type(1), x);
            }

            FCV_REQUIRES(fcv_detail::MoveConstructible<T>)
            constexpr iterator insert(
                const_iterator position,
                value_type&& x) noexcept(noexcept(declval<fixed_capacity_vector>().move_insert(position, &x,
                                                              &x + 1)))
            {
                FCV_EXPECT(!full()
                           && "tried insert on full fixed_capacity_vector!");
                assert_iterator_in_range(position);
                return move_insert(position, &x, &x + 1);
            }

            FCV_REQUIRES(fcv_detail::CopyConstructible<T>)
            constexpr iterator insert(
                const_iterator position, size_type n,
                const T& x) noexcept(noexcept(declval<fixed_capacity_vector>().push_back(x)))
            {
                assert_iterator_in_range(position);
                const auto new_size = size() + n;
                FCV_EXPECT(new_size <= capacity()
                           && "trying to insert beyond capacity!");
                auto b = end();
                while (n != 0)
                {
                    push_back(x);
                    --n;
                }

                auto writable_position = begin() + (position - begin());
                fcv_detail::slow_rotate(writable_position, b, end());
                return writable_position;
            }

            template <class InputIt,
                      FCV_REQUIRES_(
                          fcv_detail::InputIterator<InputIt>and
                              fcv_detail::Constructible<
                                  value_type,
                                  fcv_detail::iterator_reference_t<InputIt>>)>
            constexpr iterator insert(
                const_iterator position, InputIt first,
                InputIt last) noexcept(noexcept(declval<fixed_capacity_vector>().emplace_back(*first)))
            {
                assert_iterator_in_range(position);
                assert_valid_iterator_pair(first, last);
                if constexpr (fcv_detail::RandomAccessIterator<InputIt>)
                {
                    FCV_EXPECT(size() + static_cast<size_type>(last - first)
                                   <= capacity()
                               && "trying to insert beyond capacity!");
                }
                auto b = end();

                // insert at the end and then just rotate:
                // cannot use try in constexpr function
                // try {  // if copy_constructor throws you get basic-guarantee?
                for (; first != last; ++first)
                {
                    emplace_back(*first);
                }
                // } catch (...) {
                //   erase(b, end());
                //   throw;
                // }

                auto writable_position = begin() + (position - begin());
                fcv_detail::slow_rotate(writable_position, b, end());
                return writable_position;
            }

            template <class InputIt,
                      FCV_REQUIRES_(fcv_detail::InputIterator<InputIt>)>
            constexpr iterator move_insert(
                const_iterator position, InputIt first,
                InputIt last) noexcept(noexcept(declval<fixed_capacity_vector>().emplace_back(move(*first))))
            {
                assert_iterator_in_range(position);
                assert_valid_iterator_pair(first, last);
                if constexpr (fcv_detail::RandomAccessIterator<InputIt>)
                {
                    FCV_EXPECT(size() + static_cast<size_type>(last - first)
                                   <= capacity()
                               && "trying to insert beyond capacity!");
                }
                iterator b = end();

                // we insert at the end and then just rotate:
                for (; first != last; ++first)
                {
                    emplace_back(move(*first));
                }
                auto writable_position = begin() + (position - begin());
                fcv_detail::slow_rotate<iterator>(writable_position, b, end());
                return writable_position;
            }

            FCV_REQUIRES(fcv_detail::CopyConstructible<T>)
            constexpr iterator insert(
                const_iterator position,
                initializer_list<T> il) noexcept(noexcept(declval<fixed_capacity_vector>().insert(position,
                                                                 il.begin(),
                                                                 il.end())))
            {
                assert_iterator_in_range(position);
                return insert(position, il.begin(), il.end());
            }

            FCV_REQUIRES(fcv_detail::Movable<value_type>)
            constexpr iterator erase(const_iterator position) noexcept
            {
                assert_iterator_in_range(position);
                return erase(position, position + 1);
            }

            FCV_REQUIRES(fcv_detail::Movable<value_type>)
            constexpr iterator erase(const_iterator first,
                                     const_iterator last) noexcept
            {
                assert_iterator_pair_in_range(first, last);
                iterator p = begin() + (first - begin());
                if (first != last)
                {
                    unsafe_destroy(
                        fcv_detail::move(p + (last - first), end(), p), end());
                    unsafe_set_size(size()
                                    - static_cast<size_type>(last - first));
                }

                return p;
            }

            FCV_REQUIRES(fcv_detail::Assignable<T&, T&&>)
            constexpr void swap(fixed_capacity_vector& other) noexcept(
                is_nothrow_swappable_v<T>)
            {
                fixed_capacity_vector tmp = move(other);
                other                     = move(*this);
                (*this)                   = move(tmp);
            }

            /// Resizes the container to contain \p sz elements. If elements
            /// need to be appended, these are copy-constructed from \p value.
            ///
            FCV_REQUIRES(fcv_detail::CopyConstructible<T>)
            constexpr void resize(size_type sz, T const& value) noexcept(
                is_nothrow_copy_constructible_v<T>)
            {
                if (sz == size())
                {
                    return;
                }
                if (sz > size())
                {
                    FCV_EXPECT(sz <= capacity()
                               && "fixed_capacity_vector cannot be resized to "
                                  "a size greater than capacity");
                    insert(end(), sz - size(), value);
                }
                else
                {
                    erase(end() - (size() - sz), end());
                }
            }

          private:
            FCV_REQUIRES(fcv_detail::MoveConstructible<
                             T> or fcv_detail::CopyConstructible<T>)
            constexpr void emplace_n(size_type n) noexcept(
                (fcv_detail::MoveConstructible<
                     T> && is_nothrow_move_constructible_v<T>)
                || (fcv_detail::CopyConstructible<
                        T> && is_nothrow_copy_constructible_v<T>))
            {
                FCV_EXPECT(n <= capacity()
                           && "fixed_capacity_vector cannot be "
                              "resized to a size greater than "
                              "capacity");
                while (n != size())
                {
                    emplace_back(T{});
                }
            }

          public:
            /// Resizes the container to contain \p sz elements. If elements
            /// need to be appended, these are move-constructed from `T{}` (or
            /// copy-constructed if `T` is not `fcv_detail::MoveConstructible`).
            FCV_REQUIRES(fcv_detail::Movable<value_type>)
            constexpr void resize(size_type sz) noexcept(
                (fcv_detail::MoveConstructible<
                     T> && is_nothrow_move_constructible_v<T>)
                || (fcv_detail::CopyConstructible<
                        T> && is_nothrow_copy_constructible_v<T>))
            {
                if (sz == size())
                {
                    return;
                }

                if (sz > size())
                {
                    emplace_n(sz);
                }
                else
                {
                    erase(end() - (size() - sz), end());
                }
            }

            ///@}  // Modifiers

            /// \name Construct/copy/move/destroy
            ///@{

            /// Default constructor.
            constexpr fixed_capacity_vector() = default;

            /// Copy constructor.
            FCV_REQUIRES(fcv_detail::CopyConstructible<value_type>)
            constexpr fixed_capacity_vector(
                fixed_capacity_vector const&
                    other) noexcept(noexcept(declval<fixed_capacity_vector>().insert(begin(), other.begin(),
                                                    other.end())))
            {
                // nothin to assert: size of other cannot exceed capacity
                // because both vectors have the same type
                insert(begin(), other.begin(), other.end());
            }

            /// Move constructor.
            FCV_REQUIRES(fcv_detail::MoveConstructible<value_type>)
            constexpr fixed_capacity_vector(
                fixed_capacity_vector&&
                    other) noexcept(noexcept(declval<fixed_capacity_vector>().move_insert(begin(), other.begin(),
                                                         other.end())))
            {
                // nothin to assert: size of other cannot exceed capacity
                // because both vectors have the same type
                move_insert(begin(), other.begin(), other.end());
            }

            /// Copy assignment.
            FCV_REQUIRES(fcv_detail::Assignable<reference, const_reference>)
            constexpr fixed_capacity_vector&
            operator=(fixed_capacity_vector const& other) noexcept(
                noexcept(declval<fixed_capacity_vector>().clear())
                && noexcept(declval<fixed_capacity_vector>().insert(begin(), other.begin(), other.end())))
            {
                // nothin to assert: size of other cannot exceed capacity
                // because both vectors have the same type
                clear();
                insert(this->begin(), other.begin(), other.end());
                return *this;
            }

            /// Move assignment.
            FCV_REQUIRES(fcv_detail::Assignable<reference, reference>)
            constexpr fixed_capacity_vector&
            operator=(fixed_capacity_vector&& other) noexcept(
                noexcept(declval<fixed_capacity_vector>().clear())
                and noexcept(declval<fixed_capacity_vector>().move_insert(begin(), other.begin(), other.end())))
            {
                // nothin to assert: size of other cannot exceed capacity
                // because both vectors have the same type
                clear();
                move_insert(this->begin(), other.begin(), other.end());
                return *this;
            }

            /// Initializes vector with \p n default-constructed elements.
            FCV_REQUIRES(fcv_detail::CopyConstructible<
                             T> or fcv_detail::MoveConstructible<T>)
            explicit constexpr fixed_capacity_vector(size_type n) noexcept(
                noexcept(declval<fixed_capacity_vector>().emplace_n(n)))
            {
                FCV_EXPECT(n <= capacity() && "size exceeds capacity");
                emplace_n(n);
            }

            /// Initializes vector with \p n with \p value.
            FCV_REQUIRES(fcv_detail::CopyConstructible<T>)
            constexpr fixed_capacity_vector(
                size_type n,
                T const& value) noexcept(noexcept(declval<fixed_capacity_vector>().insert(begin(), n, value)))
            {
                FCV_EXPECT(n <= capacity() && "size exceeds capacity");
                insert(begin(), n, value);
            }

            /// Initialize vector from range [first, last).
            template <class InputIt,
                      FCV_REQUIRES_(fcv_detail::InputIterator<InputIt>)>
            constexpr fixed_capacity_vector(InputIt first, InputIt last)
            {
                if constexpr (fcv_detail::RandomAccessIterator<InputIt>)
                {
                    FCV_EXPECT(last - first >= 0);
                    FCV_EXPECT(static_cast<size_type>(last - first)
                                   <= capacity()
                               && "range size exceeds capacity");
                }
                insert(begin(), first, last);
            }

            template <typename U,
                      FCV_REQUIRES_(fcv_detail::Convertible<U, value_type>)>
            constexpr fixed_capacity_vector(initializer_list<U> il) noexcept(
                noexcept(base_t(move(il))))
                : base_t(move(il))
            {  // assert happens in base_t constructor
            }

            template <class InputIt,
                      FCV_REQUIRES_(fcv_detail::InputIterator<InputIt>)>
            constexpr void assign(InputIt first, InputIt last) noexcept(
                noexcept(declval<fixed_capacity_vector>().clear()) and noexcept(declval<fixed_capacity_vector>().insert(begin(), first, last)))
            {
                if constexpr (fcv_detail::RandomAccessIterator<InputIt>)
                {
                    FCV_EXPECT(last - first >= 0);
                    FCV_EXPECT(static_cast<size_type>(last - first)
                                   <= capacity()
                               && "range size exceeds capacity");
                }
                clear();
                insert(begin(), first, last);
            }

            FCV_REQUIRES(fcv_detail::CopyConstructible<T>)
            constexpr void assign(size_type n, const T& u)
            {
                FCV_EXPECT(n <= capacity() && "size exceeds capacity");
                clear();
                insert(begin(), n, u);
            }
            FCV_REQUIRES(fcv_detail::CopyConstructible<T>)
            constexpr void assign(initializer_list<T> const& il)
            {
                FCV_EXPECT(il.size() <= capacity()
                           && "initializer_list size exceeds capacity");
                clear();
                insert(this->begin(), il.begin(), il.end());
            }
            FCV_REQUIRES(fcv_detail::CopyConstructible<T>)
            constexpr void assign(initializer_list<T>&& il)
            {
                FCV_EXPECT(il.size() <= capacity()
                           && "initializer_list size exceeds capacity");
                clear();
                insert(this->begin(), il.begin(), il.end());
            }

            ///@}  // Construct/copy/move/destroy/assign
        };

        template <typename T, size_t Capacity>
        constexpr bool operator==(
            fixed_capacity_vector<T, Capacity> const& a,
            fixed_capacity_vector<T, Capacity> const& b) noexcept
        {
            return a.size() == b.size()
                   and fcv_detail::cmp(a.begin(), a.end(), b.begin(), b.end(),
                                       equal_to<>{});
        }

        template <typename T, size_t Capacity>
        constexpr bool operator<(
            fixed_capacity_vector<T, Capacity> const& a,
            fixed_capacity_vector<T, Capacity> const& b) noexcept
        {
            return fcv_detail::cmp(a.begin(), a.end(), b.begin(), b.end(),
                                   less<>{});
        }

        template <typename T, size_t Capacity>
        constexpr bool operator!=(
            fixed_capacity_vector<T, Capacity> const& a,
            fixed_capacity_vector<T, Capacity> const& b) noexcept
        {
            return not(a == b);
        }

        template <typename T, size_t Capacity>
        constexpr bool operator<=(
            fixed_capacity_vector<T, Capacity> const& a,
            fixed_capacity_vector<T, Capacity> const& b) noexcept
        {
            return fcv_detail::cmp(a.begin(), a.end(), b.begin(), b.end(),
                                   less_equal<>{});
        }

        template <typename T, size_t Capacity>
        constexpr bool operator>(
            fixed_capacity_vector<T, Capacity> const& a,
            fixed_capacity_vector<T, Capacity> const& b) noexcept
        {
            return fcv_detail::cmp(a.begin(), a.end(), b.begin(), b.end(),
                                   greater<>{});
        }

        template <typename T, size_t Capacity>
        constexpr bool operator>=(
            fixed_capacity_vector<T, Capacity> const& a,
            fixed_capacity_vector<T, Capacity> const& b) noexcept
        {
            return fcv_detail::cmp(a.begin(), a.end(), b.begin(), b.end(),
                                   greater_equal<>{});
        }



    }  // namespace experimental
}  // namespace std

// undefine all the internal macros
#undef FCV_UNREACHABLE
#undef FCV_ASSUME
#undef FCV_LIKELY
#undef FCV_UNLIKELY
#undef FCV_EXPECT
#undef FCV_CONCEPT_PP_CAT_
#undef FCV_CONCEPT_PP_CAT
#undef FCV_REQUIRES_
#undef FCV_REQUIRES

#endif  // STD_EXPERIMENTAL_FIXED_CAPACITY_VECTOR
