dynamic_array.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <libcaramel/iterators/random_iterator.hpp>
#include <libcaramel/memory/memory_allocator.hpp>
#include <libcaramel/util/types.hpp>
 
#include <gsl/gsl_assert>
 
#include <concepts>
#include <cstdint>
#include <initializer_list>
#include <limits>
#include <memory>
#include <type_traits>
 
namespace caramel::detail
{
   template <typename First, typename Second>
   auto synth_three_way(const First& lhs, const Second& rhs)
   {
      if constexpr (std::three_way_comparable_with<First, Second>)
      {
         return lhs <=> rhs;
      }
      else
      {
         if (lhs == rhs)
         {
            return std::strong_ordering::equal;
         }
 
         if (lhs < rhs)
         {
            return std::strong_ordering::less;
         }
 
         return std::strong_ordering::greater;
      }
   }
} // namespace caramel::detail
 
namespace caramel
{
   struct in_place_t
   {
      explicit constexpr in_place_t() = default;
   };
 
   inline constexpr in_place_t in_place;
 
   template <typename Any, i64_t Size, typename Allocator = memory_allocator<Any>>
   class basic_dynamic_array
   {
   public:
      using value_type = Any;
      using size_type = std::int64_t;
      using difference_type = std::ptrdiff_t;
      using allocator_type = Allocator;
      using reference = value_type&;
      using const_reference = const value_type&;
      using pointer = typename Allocator::pointer;
      using const_pointer = typename Allocator::const_pointer;
      using iterator = random_access_iterator<value_type>;
      using const_iterator = random_access_iterator<const value_type>;
      using reverse_iterator = std::reverse_iterator<iterator>;
      using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
   public:
      constexpr basic_dynamic_array() noexcept = default;
      constexpr basic_dynamic_array(const allocator_type& allocator) : m_allocator{allocator} {}
      constexpr basic_dynamic_array(size_type count, const_reference value,
                                    const allocator_type& allocator = allocator_type{}) :
         m_allocator{allocator}
      {
         Expects(count >= 0);
 
         assign(count, value);
      }
      constexpr basic_dynamic_array(std::initializer_list<Any> init,
                                    const allocator_type& allocator = allocator_type{}) :
         m_allocator{allocator}
      {
         assign(init);
      }
      template <std::input_iterator InputIt>
      constexpr basic_dynamic_array(InputIt first, InputIt last,
                                    const allocator_type& allocator = allocator_type{}) :
         m_allocator{allocator}
      {
         assign(first, last);
      }
      constexpr basic_dynamic_array(const basic_dynamic_array& other)
      {
         if (this != &other)
         {
            *this = other;
         }
      }
      constexpr basic_dynamic_array(const basic_dynamic_array& other,
                                    const allocator_type& allocator)
      {
         if (this != &other)
         {
            clear();
 
            if (!is_static())
            {
               m_allocator.deallocate(gsl::make_not_null(mp_begin), count_t{capacity()});
            }
 
            reset_to_static();
 
            m_allocator = allocator;
 
            const size_type new_count = std::distance(std::begin(other), std::end(other));
            if (new_count > capacity())
            {
               grow(new_count);
            }
 
            m_size = new_count;
 
            std::uninitialized_copy(std::begin(other), std::end(other), begin());
         }
      }
      constexpr basic_dynamic_array(basic_dynamic_array&& other) noexcept
      {
         if (!other.empty())
         {
            *this = std::move(other);
         }
      }
      constexpr basic_dynamic_array(basic_dynamic_array&& other, const allocator_type& alloc)
      {
         clear();
 
         if (!is_static())
         {
            m_allocator.deallocate(gsl::make_not_null(mp_begin), count_t{capacity()});
         }
 
         reset_to_static();
 
         m_allocator = alloc;
 
         using mi = std::move_iterator<iterator>;
         assign(mi{other.begin()}, mi{other.end()});
 
         other.reset_to_static();
      }
      constexpr ~basic_dynamic_array() noexcept
      {
         clear();
 
         if (!is_static() && mp_begin)
         {
            m_allocator.deallocate(gsl::make_not_null(mp_begin), count_t{capacity()});
         }
 
         reset_to_static();
      }
 
      constexpr auto operator=(const basic_dynamic_array& rhs) -> basic_dynamic_array&
      {
         if (this != &rhs)
         {
            if (m_allocator != rhs.m_allocator)
            {
               clear();
 
               if (!is_static())
               {
                  m_allocator.deallocate(gsl::make_not_null(mp_begin), count_t{capacity()});
               }
 
               reset_to_static();
            }
 
            m_allocator = rhs.m_allocator;
 
            assign(rhs.begin(), rhs.end());
         }
 
         return *this;
      }
 
      constexpr auto operator=(basic_dynamic_array&& rhs) noexcept -> basic_dynamic_array&
      {
         if (m_allocator != rhs.allocator())
         {
            using move_it = std::move_iterator<iterator>;
            assign(move_it{rhs.begin()}, move_it{rhs.end()});
 
            rhs.reset_to_static();
         }
         else
         {
            if (!rhs.is_static())
            {
               if (!is_static())
               {
                  clear();
 
                  m_allocator.deallocate(gsl::make_not_null(mp_begin), count_t{capacity()});
 
                  reset_to_static();
               }
 
               m_size = rhs.size();
               m_capacity = rhs.capacity();
               mp_begin = rhs.mp_begin;
            }
            else
            {
               using move_it = std::move_iterator<iterator>;
               assign(move_it{rhs.begin()}, move_it{rhs.end()});
            }
 
            rhs.reset_to_static();
         }
 
         return *this;
      }
 
      constexpr auto operator=(std::initializer_list<Any> init_list) -> basic_dynamic_array&
      {
         assign(init_list);
 
         return *this;
      }
 
      constexpr auto allocator() const noexcept -> allocator_type { return m_allocator; }
 
      constexpr auto lookup(size_type index) -> reference
      {
         Expects(index < m_size);
         Expects(index >= 0);
 
         return mp_begin[index];
      }
      constexpr auto lookup(size_type index) const -> const_reference
      {
         Expects(index < m_size);
 
         return mp_begin[index];
      }
 
      constexpr auto data() noexcept -> pointer { return pointer{&(*begin())}; }
      constexpr auto data() const noexcept -> const_pointer { return const_pointer{&(*cbegin())}; }
 
      constexpr auto begin() noexcept -> iterator { return iterator{mp_begin}; }
      constexpr auto begin() const noexcept -> const_iterator { return const_iterator{mp_begin}; }
      constexpr auto cbegin() const noexcept -> const_iterator { return const_iterator{mp_begin}; }
 
      constexpr auto end() noexcept -> iterator { return iterator{mp_begin + m_size}; }
      constexpr auto end() const noexcept -> const_iterator
      {
         return const_iterator{mp_begin + m_size};
      }
      constexpr auto cend() const noexcept -> const_iterator
      {
         return const_iterator{mp_begin + m_size};
      }
 
      constexpr auto rbegin() noexcept -> reverse_iterator { return reverse_iterator{end()}; }
      constexpr auto rbegin() const noexcept -> const_reverse_iterator
      {
         return const_reverse_iterator{cend()};
      }
      constexpr auto rcbegin() const noexcept -> const_reverse_iterator
      {
         return const_reverse_iterator{cend()};
      }
 
      constexpr auto rend() noexcept -> reverse_iterator { return reverse_iterator{begin()}; }
      constexpr auto rend() const noexcept -> const_reverse_iterator
      {
         return const_reverse_iterator{cbegin()};
      }
      constexpr auto rcend() const noexcept -> const_reverse_iterator
      {
         return const_reverse_iterator{cbegin()};
      }
 
      [[nodiscard]] constexpr auto empty() const noexcept -> bool { return begin() == end(); };
      [[nodiscard]] constexpr auto size() const noexcept -> size_type { return m_size; };
      [[nodiscard]] constexpr auto capacity() const noexcept -> size_type { return m_capacity; };
      constexpr void reserve(size_type new_cap)
      {
         if (new_cap > capacity())
         {
            grow(new_cap);
         }
      }
 
      constexpr void clear() noexcept
      {
         std::destroy(begin(), end());
         m_size = 0;
      }
 
      constexpr auto insert(const_iterator pos, const_reference value) -> iterator
      {
         Expects(pos >= cbegin());
         Expects(pos <= cend());
 
         if (pos == cend())
         {
            append(value);
 
            return end() - 1;
         }
 
         iterator new_pos;
         if (size() >= capacity())
         {
            size_type offset = pos - cbegin();
            grow();
            new_pos = begin() + offset;
         }
         else
         {
            new_pos = begin() + (pos - cbegin());
         }
 
         std::construct_at(offset(size()), std::move(*(end() - 1)));
         std::move_backward(new_pos, end() - 1, end());
 
         ++m_size;
 
         const_pointer p_element = &value;
         if (pointer{&(*new_pos)} <= p_element && pointer{&(*end())} > p_element)
         {
            ++p_element;
         }
 
         *new_pos = *p_element;
 
         return new_pos;
      }
 
      constexpr auto insert(const_iterator pos, value_type&& value) -> iterator
      {
         Expects(pos >= cbegin());
         Expects(pos <= cend());
 
         if (pos == cend())
         {
            append(std::move(value));
 
            return end() - 1;
         }
 
         iterator new_pos;
         if (size() >= capacity())
         {
            size_type offset = pos - cbegin();
            grow();
            new_pos = begin() + offset;
         }
         else
         {
            new_pos = begin() + (pos - cbegin());
         }
 
         construct(offset(size()), std::move(*(end() - 1)));
 
         std::move_backward(new_pos, end() - 1, end());
 
         ++m_size;
 
         pointer p_element = &value;
         if (pointer{&(*new_pos)} <= p_element && pointer{&(*end())} > p_element)
         {
            ++p_element;
         }
 
         *new_pos = std::move(*p_element);
 
         return new_pos;
      }
      template <typename... Args>
      constexpr auto insert(const_iterator pos, Args... args) -> iterator
      {
         Expects(pos >= cbegin());
         Expects(pos <= cend());
 
         if (pos == cend())
         {
            append(in_place, std::forward<Args>(args)...);
 
            return end() - 1;
         }
 
         iterator new_pos;
         if (size() >= capacity())
         {
            size_type offset = pos - cbegin();
            grow();
            new_pos = begin() + offset;
         }
         else
         {
            new_pos = begin() + (pos - cbegin());
         }
 
         new (&(*end())) value_type(std::move(*(end() - 1)));
 
         std::move_backward(new_pos, end() - 1, end());
 
         ++m_size;
 
         *new_pos = value_type(std::forward<Args>(args)...);
 
         return new_pos;
      }
      constexpr auto insert(const_iterator pos, size_type count, const_reference value) -> iterator
      {
         Expects(pos >= cbegin());
         Expects(pos <= cend());
 
         size_type start_index = pos - cbegin();
 
         if (pos == cend())
         {
            if (size() + count >= capacity())
            {
               grow(size() + count);
            }
 
            std::uninitialized_fill_n(end(), count, value);
 
            m_size += count;
 
            return begin() + start_index;
         }
 
         reserve(size() + count);
 
         iterator updated_pos = begin() + start_index;
 
         if (iterator old_end = end(); end() - updated_pos >= count)
         {
            std::uninitialized_move(end() - count, end(), end());
 
            m_size += count;
 
            std::move_backward(updated_pos, old_end - count, old_end);
            std::fill_n(updated_pos, count, value);
         }
         else
         {
            size_type move_count = old_end - updated_pos;
            m_size += count;
 
            std::uninitialized_move(updated_pos, old_end, end() - move_count);
            std::fill_n(updated_pos, move_count, value);
            std::uninitialized_fill_n(old_end, count - move_count, value);
         }
 
         return updated_pos;
      }
 
      template <std::input_iterator InputIt>
      constexpr auto insert(const_iterator pos, InputIt first, InputIt last) -> iterator
      {
         Expects(pos >= cbegin());
         Expects(pos <= cend());
 
         size_type start_index = pos - cbegin();
         difference_type count = std::distance(first, last);
 
         if (pos == cend())
         {
            if (size() + count >= capacity())
            {
               grow(size() + count);
            }
 
            std::uninitialized_copy(first, last, end());
 
            m_size += count;
 
            return begin() + start_index;
         }
 
         reserve(size() + count);
 
         iterator updated_pos = begin() + start_index;
         if (iterator old_end = end(); end() - updated_pos >= count)
         {
            std::uninitialized_move(end() - count, end(), end());
 
            m_size += count;
 
            std::move_backward(updated_pos, old_end - count, old_end);
            std::copy(first, last, updated_pos);
         }
         else
         {
            size_type move_count = old_end - updated_pos;
            m_size += count;
 
            std::uninitialized_move(updated_pos, old_end, end() - move_count);
 
            for (auto it = updated_pos; count > 0; --count)
            {
               *it = *first;
 
               ++it;
               ++first;
            }
 
            std::uninitialized_copy(first, last, old_end);
         }
 
         return updated_pos;
      }
 
      constexpr auto insert(const_iterator pos, std::initializer_list<value_type> init_list)
         -> iterator
      {
         return insert(pos, init_list.begin(), init_list.end());
      }
 
      constexpr auto erase(const_iterator pos) -> iterator
      {
         Expects(pos >= cbegin());
         Expects(pos <= cend());
 
         if (pos == cend())
         {
            return end();
         }
 
         auto it = begin() + (pos - cbegin());
 
         std::move(it + 1, end(), it);
 
         pop_back();
 
         return it;
      }
      constexpr auto erase(const_iterator first, const_iterator last) -> iterator
      {
         Expects(first >= cbegin());
         Expects(last <= cend());
         Expects(first >= last);
 
         if (first == last)
         {
            return begin() + (first - cbegin());
         }
 
         size_type const distance = std::distance(first, last);
 
         iterator it_f = begin() + (first - cbegin());
         iterator it_l = begin() + (last - cbegin());
         iterator it = std::move(it_l, end(), it_f);
 
         std::destroy(it, end());
 
         m_size -= distance;
 
         return it_f;
      }
 
      constexpr void append(const value_type& value)
      {
         if (size() >= capacity())
         {
            grow();
         }
 
         construct(mp_begin + size(), value);
 
         ++m_size;
      }
      constexpr void append(value_type&& value)
      {
         if (size() >= capacity())
         {
            grow();
         }
 
         construct(mp_begin + size(), std::move(value));
 
         ++m_size;
      }
      template <typename... Args>
      requires std::constructible_from<value_type, Args...> constexpr auto append(in_place_t,
                                                                                  Args&&... args)
         -> reference
      {
         if (size() >= capacity())
         {
            grow();
         }
 
         std::construct_at(offset(size()), std::forward<Args>(args)...);
 
         ++m_size;
 
         return *(end() - 1);
      }
 
      constexpr void pop_back()
      {
         Expects(size() != 0);
 
         std::destroy_at(offset(size()));
         --m_size;
      };
 
      constexpr void resize(size_type count)
      {
         if (size() > count)
         {
            std::destroy(begin() + count, end());
            m_size = count;
         }
         else if (size() < count)
         {
            if (capacity() < count)
            {
               grow(count);
            }
 
            for (size_type i = size(); i < count; ++i)
            {
               construct(offset(i), value_type{});
            }
 
            m_size = count;
         }
      }
      constexpr void resize(size_type count, const_reference value)
      {
         if (size() > count)
         {
            std::destroy(begin() + count, end());
            m_size = count;
         }
         else if (size() < count)
         {
            if (capacity() < count)
            {
               grow(count);
            }
 
            std::uninitialized_fill(end(), begin() + count, value);
 
            m_size = count;
         }
      }
 
   private:
      [[nodiscard]] constexpr auto is_static() const noexcept -> bool
      {
         return mp_begin == get_first_element();
      }
 
      constexpr auto get_first_element() const -> pointer
      {
         return const_cast<pointer>(reinterpret_cast<const_pointer>(&m_static_storage)); // NOLINT
      }
 
      constexpr void grow(size_type min_size = 0)
      {
         const auto new_capacity = compute_new_capacity(std::max(m_capacity + 1, min_size));
         auto* new_elements = m_allocator.allocate(count_t{new_capacity});
 
         if constexpr (std::is_move_constructible_v<value_type>)
         {
            std::uninitialized_move(begin(), end(), iterator{new_elements});
         }
         else
         {
            std::uninitialized_copy(begin(), end(), iterator{new_elements});
         }
 
         std::destroy(begin(), end());
 
         if (!is_static())
         {
            if (mp_begin)
            {
               m_allocator.deallocate(gsl::make_not_null(mp_begin), count_t{capacity()});
            }
         }
 
         mp_begin = new_elements;
         m_capacity = new_capacity;
      }
 
      constexpr void reset_to_static()
      {
         mp_begin = get_first_element();
         m_size = 0;
         m_capacity = Size;
      }
 
      constexpr void assign(size_type count, const_reference value)
      {
         clear();
 
         if (count > m_capacity)
         {
            grow(count);
         }
 
         m_size = count;
 
         std::uninitialized_fill(begin(), end(), value);
      }
 
      template <std::input_iterator InputIt>
      constexpr void assign(InputIt first, InputIt last)
      {
         clear();
 
         const auto new_count = static_cast<size_type>(std::distance(first, last));
         if (new_count > capacity())
         {
            grow(new_count);
         }
 
         m_size = new_count;
 
         std::uninitialized_copy(first, last, begin());
      }
 
      constexpr void assign(std::initializer_list<value_type> initializer_list)
      {
         assign(initializer_list.begin(), initializer_list.end());
      }
 
      constexpr auto offset(size_type i) noexcept -> pointer { return mp_begin + i; }
      constexpr auto offset(size_type i) const noexcept -> const_pointer { return mp_begin + i; }
 
      static constexpr auto compute_new_capacity(size_type min_capacity) -> size_type
      {
         constexpr auto max_digits = std::numeric_limits<size_type>::digits;
         constexpr auto max_capacity = size_type{1} << (max_digits - 1);
 
         if (min_capacity > max_capacity)
         {
            return max_capacity;
         }
 
         --min_capacity;
 
         for (size_type i = 1; i < max_digits; i *= 2)
         {
            min_capacity |= min_capacity >> i;
         }
 
         return ++min_capacity;
      }
 
   private:
      pointer mp_begin{nullptr};
 
      alignas(alignof(Any)) std::array<std::byte, sizeof(Any) * Size> m_static_storage;
 
      size_type m_size{0u};
      size_type m_capacity{0u};
 
      allocator_type m_allocator;
   };
 
   template <std::equality_comparable Any, i64_t SizeOne, i64_t SizeTwo, typename allocator>
   constexpr auto operator==(const basic_dynamic_array<Any, SizeOne, allocator>& lhs,
                             const basic_dynamic_array<Any, SizeTwo, allocator>& rhs) -> bool
   {
      return std::equal(std::begin(lhs), std::end(lhs), std::begin(rhs), std::end(rhs));
   }
 
   template <typename Any, i64_t SizeOne, i64_t SizeTwo, typename allocator>
   constexpr auto operator<=>(const basic_dynamic_array<Any, SizeOne, allocator>& lhs,
                              const basic_dynamic_array<Any, SizeTwo, allocator>& rhs)
   {
      return std::lexicographical_compare_three_way(std::begin(lhs), std::end(lhs), std::begin(rhs),
                                                    std::end(rhs), detail::synth_three_way);
   }
 
   template <typename Iter, i64_t Size = 0,
             typename Allocator = memory_allocator<typename std::iterator_traits<Iter>::value_type>>
   basic_dynamic_array(Iter, Iter)
      -> basic_dynamic_array<typename std::iterator_traits<Iter>::value_type, Size, Allocator>;
 
   template <typename Any, typename... U, typename Allocator = memory_allocator<Any>>
   basic_dynamic_array(Any, U...) -> basic_dynamic_array<Any, 1 + sizeof...(U), Allocator>;
 
   template <typename Any, i64_t Size>
   class small_dynamic_array
   {
      using underlying_type = basic_dynamic_array<Any, Size, memory_allocator<Any>>;
 
   public:
      using value_type = Any;
      using size_type = typename underlying_type::size_type;
      using difference_type = std::ptrdiff_t;
      using allocator_type = typename underlying_type::allocator_type;
      using reference = value_type&;
      using const_reference = const value_type&;
      using pointer = typename std::allocator_traits<allocator_type>::pointer;
      using const_pointer = typename std::allocator_traits<allocator_type>::const_pointer;
      using iterator = typename underlying_type::iterator;
      using const_iterator = typename underlying_type::const_iterator;
      using reverse_iterator = std::reverse_iterator<iterator>;
      using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
   public:
      constexpr small_dynamic_array() noexcept(noexcept(underlying_type{})) = default;
      constexpr small_dynamic_array(size_type count, const_reference value) :
         m_underlying{count, value}
      {}
      constexpr small_dynamic_array(std::initializer_list<Any> init) : m_underlying{init} {}
      template <std::input_iterator InputIt>
      constexpr small_dynamic_array(InputIt first, InputIt last) : m_underlying{first, last}
      {}
 
      constexpr auto operator=(std::initializer_list<Any> init_list) -> small_dynamic_array&
      {
         m_underlying = init_list;
 
         return *this;
      }
 
      constexpr auto allocator() const noexcept -> allocator_type
      {
         return m_underlying.allocator();
      }
 
      constexpr auto lookup(size_type index) -> reference { return m_underlying.lookup(index); }
      constexpr auto lookup(size_type index) const -> const_reference
      {
         return m_underlying.lookup(index);
      }
 
      constexpr auto data() noexcept -> pointer { return m_underlying.data(); }
      constexpr auto data() const noexcept -> const_pointer { return m_underlying.data(); }
 
      constexpr auto begin() noexcept -> iterator { return m_underlying.begin(); }
      constexpr auto begin() const noexcept -> const_iterator { return m_underlying.begin(); }
      constexpr auto cbegin() const noexcept -> const_iterator { return m_underlying.cbegin(); }
 
      constexpr auto end() noexcept -> iterator { return m_underlying.end(); }
      constexpr auto end() const noexcept -> const_iterator { return m_underlying.end(); }
      constexpr auto cend() const noexcept -> const_iterator { return m_underlying.cend(); }
 
      constexpr auto rbegin() noexcept -> reverse_iterator { return m_underlying.rbegin(); }
      constexpr auto rbegin() const noexcept -> const_reverse_iterator
      {
         return m_underlying.rbegin();
      }
      constexpr auto rcbegin() const noexcept -> const_reverse_iterator
      {
         return m_underlying.rcbegin();
      }
 
      constexpr auto rend() noexcept -> reverse_iterator { return m_underlying.end(); }
      constexpr auto rend() const noexcept -> const_reverse_iterator { return m_underlying.rend(); }
      constexpr auto rcend() const noexcept -> const_reverse_iterator
      {
         return m_underlying.rcend();
      }
 
      [[nodiscard]] constexpr auto empty() const noexcept -> bool { return m_underlying.empty(); };
      [[nodiscard]] constexpr auto size() const noexcept -> size_type
      {
         return m_underlying.size();
      };
      [[nodiscard]] constexpr auto capacity() const noexcept -> size_type
      {
         return m_underlying.capacity();
      };
      constexpr void reserve(size_type new_cap) { m_underlying.reserve(new_cap); }
 
      constexpr void clear() noexcept { m_underlying.clear(); }
 
      constexpr auto insert(const_iterator pos, const_reference value) -> iterator
      {
         return m_underlying.insert(pos, value);
      }
 
      constexpr auto insert(const_iterator pos, value_type&& value) -> iterator
      {
         return m_underlying.insert(pos, std::move(value));
      }
      template <typename... Args>
      constexpr auto insert(const_iterator pos, Args... args) -> iterator
      {
         return m_underlying.insert(pos, std::forward<Args>(args)...);
      }
      constexpr auto insert(const_iterator pos, size_type count, const_reference value) -> iterator
      {
         return m_underlying.insert(pos, count, value);
      }
 
      template <std::input_iterator InputIt>
      constexpr auto insert(const_iterator pos, InputIt first, InputIt last) -> iterator
      {
         return m_underlying.insert(pos, first, last);
      }
 
      constexpr auto insert(const_iterator pos, std::initializer_list<value_type> init_list)
         -> iterator
      {
         return m_underlying(pos, init_list);
      }
 
      constexpr auto erase(const_iterator pos) -> iterator { return m_underlying.erase(pos); }
      constexpr auto erase(const_iterator first, const_iterator last) -> iterator
      {
         return m_underlying.erase(first, last);
      }
 
      constexpr void append(const value_type& value) { m_underlying.append(value); }
      constexpr void append(value_type&& value) { m_underlying.append(std::move(value)); }
      template <typename... Args>
      requires std::constructible_from<value_type, Args...> constexpr auto append(in_place_t,
                                                                                  Args&&... args)
         -> reference
      {
         return m_underlying.append(in_place, std::forward<Args>(args)...);
      }
 
      constexpr void pop_back() { return m_underlying.pop_back(); };
 
      constexpr void resize(size_type count) { m_underlying.resize(count); }
      constexpr void resize(size_type count, const_reference value)
      {
         m_underlying.resize(count, value);
      }
 
   private:
      underlying_type m_underlying;
   };
 
   template <std::equality_comparable Any, i64_t SizeOne, i64_t SizeTwo>
   constexpr auto operator==(const small_dynamic_array<Any, SizeOne>& lhs,
                             const small_dynamic_array<Any, SizeTwo>& rhs) -> bool
   {
      return std::equal(std::begin(lhs), std::end(lhs), std::begin(rhs), std::end(rhs));
   }
 
   template <typename Any, i64_t SizeOne, i64_t SizeTwo>
   constexpr auto operator<=>(const small_dynamic_array<Any, SizeOne>& lhs,
                              const small_dynamic_array<Any, SizeTwo>& rhs)
   {
      return std::lexicographical_compare_three_way(std::begin(lhs), std::end(lhs), std::begin(rhs),
                                                    std::end(rhs), detail::synth_three_way);
   }
 
   template <typename Iter, i64_t Size = 0>
   small_dynamic_array(Iter, Iter)
      -> small_dynamic_array<typename std::iterator_traits<Iter>::value_type, Size>;
 
   template <typename Any, typename... U>
   small_dynamic_array(Any, U...) -> small_dynamic_array<Any, 1 + sizeof...(U)>;
 
   template <typename Any>
   class dynamic_array
   {
      using underlying_type = basic_dynamic_array<Any, 0u, memory_allocator<Any>>;
 
   public:
      using value_type = Any;
      using size_type = typename underlying_type::size_type;
      using difference_type = std::ptrdiff_t;
      using allocator_type = typename underlying_type::allocator_type;
      using reference = value_type&;
      using const_reference = const value_type&;
      using pointer = typename allocator_type::pointer;
      using const_pointer = typename allocator_type::const_pointer;
      using iterator = typename underlying_type::iterator;
      using const_iterator = typename underlying_type::const_iterator;
      using reverse_iterator = std::reverse_iterator<iterator>;
      using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
   public:
      constexpr dynamic_array() noexcept(noexcept(underlying_type{})) = default;
      constexpr dynamic_array(size_type count, const_reference value) : m_underlying{count, value}
      {}
      constexpr dynamic_array(std::initializer_list<Any> init) : m_underlying{init} {}
      template <std::input_iterator InputIt>
      constexpr dynamic_array(InputIt first, InputIt last) : m_underlying{first, last}
      {}
 
      constexpr auto operator=(std::initializer_list<Any> init_list) -> dynamic_array&
      {
         m_underlying = init_list;
 
         return *this;
      }
 
      constexpr auto allocator() const noexcept -> allocator_type
      {
         return m_underlying.allocator();
      }
 
      constexpr auto lookup(size_type index) -> reference { return m_underlying.lookup(index); }
      constexpr auto lookup(size_type index) const -> const_reference
      {
         return m_underlying.lookup(index);
      }
 
      constexpr auto data() noexcept -> pointer { return m_underlying.data(); }
      constexpr auto data() const noexcept -> const_pointer { return m_underlying.data(); }
 
      constexpr auto begin() noexcept -> iterator { return m_underlying.begin(); }
      constexpr auto begin() const noexcept -> const_iterator { return m_underlying.begin(); }
      constexpr auto cbegin() const noexcept -> const_iterator { return m_underlying.cbegin(); }
 
      constexpr auto end() noexcept -> iterator { return m_underlying.end(); }
      constexpr auto end() const noexcept -> const_iterator { return m_underlying.end(); }
      constexpr auto cend() const noexcept -> const_iterator { return m_underlying.cend(); }
 
      constexpr auto rbegin() noexcept -> reverse_iterator { return m_underlying.rbegin(); }
      constexpr auto rbegin() const noexcept -> const_reverse_iterator
      {
         return m_underlying.rbegin();
      }
      constexpr auto rcbegin() const noexcept -> const_reverse_iterator
      {
         return m_underlying.rcbegin();
      }
 
      constexpr auto rend() noexcept -> reverse_iterator { return m_underlying.end(); }
      constexpr auto rend() const noexcept -> const_reverse_iterator { return m_underlying.rend(); }
      constexpr auto rcend() const noexcept -> const_reverse_iterator
      {
         return m_underlying.rcend();
      }
 
      [[nodiscard]] constexpr auto empty() const noexcept -> bool { return m_underlying.empty(); };
      [[nodiscard]] constexpr auto size() const noexcept -> size_type
      {
         return m_underlying.size();
      };
      [[nodiscard]] constexpr auto capacity() const noexcept -> size_type
      {
         return m_underlying.capacity();
      };
      constexpr void reserve(size_type new_cap) { m_underlying.reserve(new_cap); }
 
      constexpr void clear() noexcept { m_underlying.clear(); }
 
      constexpr auto insert(const_iterator pos, const_reference value) -> iterator
      {
         return m_underlying.insert(pos, value);
      }
 
      constexpr auto insert(const_iterator pos, value_type&& value) -> iterator
      {
         return m_underlying.insert(pos, std::move(value));
      }
      template <typename... Args>
      constexpr auto insert(const_iterator pos, Args... args) -> iterator
      {
         return m_underlying.insert(pos, std::forward<Args>(args)...);
      }
      constexpr auto insert(const_iterator pos, size_type count, const_reference value) -> iterator
      {
         return m_underlying.insert(pos, count, value);
      }
 
      template <std::input_iterator InputIt>
      constexpr auto insert(const_iterator pos, InputIt first, InputIt last) -> iterator
      {
         return m_underlying.insert(pos, first, last);
      }
 
      constexpr auto insert(const_iterator pos, std::initializer_list<value_type> init_list)
         -> iterator
      {
         return m_underlying(pos, init_list);
      }
 
      constexpr auto erase(const_iterator pos) -> iterator { return m_underlying.erase(pos); }
      constexpr auto erase(const_iterator first, const_iterator last) -> iterator
      {
         return m_underlying.erase(first, last);
      }
 
      constexpr void append(const value_type& value) { m_underlying.append(value); }
      constexpr void append(value_type&& value) { m_underlying.append(std::move(value)); }
      template <typename... Args>
      requires std::constructible_from<value_type, Args...> constexpr auto append(in_place_t,
                                                                                  Args&&... args)
         -> reference
      {
         return m_underlying.append(in_place, std::forward<Args>(args)...);
      }
 
      constexpr void pop_back() { return m_underlying.pop_back(); };
 
      constexpr void resize(size_type count) { m_underlying.resize(count); }
      constexpr void resize(size_type count, const_reference value)
      {
         m_underlying.resize(count, value);
      }
 
   private:
      underlying_type m_underlying;
   };
 
   template <std::equality_comparable Any>
   constexpr auto operator==(const dynamic_array<Any>& lhs, const dynamic_array<Any>& rhs) -> bool
   {
      return std::equal(std::begin(lhs), std::end(lhs), std::begin(rhs), std::end(rhs));
   }
 
   template <typename Any>
   constexpr auto operator<=>(const dynamic_array<Any>& lhs, const dynamic_array<Any>& rhs)
   {
      return std::lexicographical_compare_three_way(std::begin(lhs), std::end(lhs), std::begin(rhs),
                                                    std::end(rhs), detail::synth_three_way);
   }
 
   template <typename Iter>
   dynamic_array(Iter, Iter) -> dynamic_array<typename std::iterator_traits<Iter>::value_type>;
} // namespace caramel