kstd: prepare vector to be allocator aware

1 files changed, 289 insertions, 137 deletions

diff --git a/libs/kstd/include/kstd/vector b/libs/kstd/include/kstd/vector
index 6af7c12..b87756a 100644
--- a/libs/kstd/include/kstd/vector
+++ b/libs/kstd/include/kstd/vector
@@ -6,6 +6,10 @@
 #include <algorithm>
 #include <cstddef>
 #include <initializer_list>
+#include <iterator>
+#include <memory>
+#include <ranges>
+#include <utility>
 
 namespace kstd
 {
@@ -14,129 +18,254 @@ namespace kstd
    * custom memory management.
    *
    * @tparam T Element the vector instance should contain.
+   * @tparam Allocator The allocator to use when allocating new elements.
    */
-  template<typename T>
+  template<typename T, typename Allocator = std::allocator<T>>
   struct vector
   {
     using value_type = T;                        ///< Type of the elements contained in the container.
+    using allocator_type = Allocator;            ///< Type of the allocator used by the container.
     using size_type = std::size_t;               ///< Type of the size in the container.
+    using difference_type = std::ptrdiff_t;      ///< Type of the difference between two iterators.
     using reference = value_type &;              ///< Type of reference to the elements.
     using const_reference = value_type const &;  ///< Type of constant reference to the elements.
     using pointer = value_type *;                ///< Type of pointer to the elements.
     using const_pointer = value_type const *;    ///< Type of constant pointer to the elements.
+    using iterator = pointer;                    ///< Type of iterator to the elements.
+    using const_iterator = const_pointer;        ///< Type of constant iterator to the elements.
+    using reverse_iterator = std::reverse_iterator<iterator>;
+    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
-    /**
-     * @brief Default Constructor.
-     */
+    //! Construct a new, empty vector.
     vector() = default;
 
-    /**
-     * @brief Constructs data with the given amount of elements containing the given value or alternatively the default
-     * constructed value.
-     *
-     * @param n Amount of elements we want to create and set the given value for.
-     * @param initial Inital value of all elements in the underlying data array.
-     */
+    //! Construct a new vector, with the given number of element and initialize them to the given value.
+    //!
+    //! @param n The number of elements to construct the container with.
+    //! @param initial The value to initialize each element to.
     explicit vector(size_type n, value_type initial = value_type{})
-        : _size(n)
-        , _capacity(n)
-        , _data(_capacity ? new value_type[_capacity]{} : nullptr)
+        : m_size{n}
+        , m_capacity{n}
+        , m_data{allocate_n(m_capacity)}
     {
-      std::ranges::fill(*this, initial);
+      for (auto i = 0uz; i < n; ++i)
+      {
+        std::allocator_traits<allocator_type>::construct(m_allocator, m_data + i, initial);
+      }
     }
 
-    /**
-     * @brief Constructs data by copying all element from the given exclusive range.
-     *
-     * @tparam InputIterator Template that should have atleast input iterator characteristics.
-     * @param first Input iterator to the first element in the range we want to copy from.
-     * @param last Input iterator to one past the last element in the range we want to copy from.
-     */
+    //! Construct a new vector and initialize it's content by copying all elements in the given range.
+    //!
+    //! @tparam InputIterator An iterator type used to describe the source range.
+    //! @param first The start of the source range.
+    //! @param last The end of the source range.
     template<typename InputIterator>
     explicit vector(InputIterator first, InputIterator last)
-        : _size(std::distance(first, last))
-        , _capacity(std::distance(first, last))
-        , _data(_capacity ? new value_type[_capacity]() : nullptr)
+        : m_allocator{}
+        , m_size{std::ranges::distance(first, last)}
+        , m_capacity{std::ranges::distance(first, last)}
+        , m_data{allocate_n(m_capacity)}
     {
-      std::ranges::copy(first, last, _data);
+      for (auto destination = begin(); first != last; ++first, ++destination)
+      {
+        std::allocator_traits<allocator_type>::construct(m_allocator, destination, *first);
+      }
     }
 
-    /**
-     * @brief Construct data by copying all elements from the initializer list.
-     *
-     * @param initializer_list List we want to copy all elements from.
-     */
-    explicit vector(std::initializer_list<value_type> initializer_list)
-        : _size(initializer_list.size())
-        , _capacity(initializer_list.size())
-        , _data(_capacity ? new value_type[_capacity]() : nullptr)
-    {
-      std::ranges::copy(initializer_list, _data);
+    //! Construct a new vector and initialize it's content by copying all elements in the given initializer list.
+    //!
+    //! @param list The initializer list containing the source objects.
+    explicit vector(std::initializer_list<value_type> list)
+        : vector{std::ranges::begin(list), std::ranges::end(list)}
+    {}
+
+    //! Construct a new vector and initialize it's content by copying all elements from a given vector.
+    //!
+    //! @param other The source vector.
+    vector(vector const & other)
+        : m_allocator{other.m_allocator}
+        , m_size{other.m_size}
+        , m_capacity{other.m_capacity}
+        , m_data(allocate_n(m_capacity))
+    {
+      auto first = std::ranges::begin(other);
+      auto last = std::ranges::end(other);
+      for (auto destination = begin(); first != last; ++first, ++destination)
+      {
+        std::allocator_traits<allocator_type>::construct(m_allocator, destination, *first);
+      }
     }
 
-    /**
-     * @brief Copy constructor.
-     *
-     * @note Allocates underlying data container with the same capacity as vector we are copying from and copies all
-     * elements from it.
-     *
-     * @param other Other instance of vector we want to copy the data from.
-     */
-    vector(vector<value_type> const & other)
-        : _size(other._size)
-        , _capacity(other._capacity)
-        , _data(_capacity ? new value_type[_capacity]() : nullptr)
+    //! Construct a new vector and initialize it's content by moving from a given vector.
+    //!
+    //! @param other The source vector.
+    vector(vector && other) noexcept
+        : m_allocator{std::exchange(other.m_allocator, allocator_type{})}
+        , m_size{std::exchange(other.m_size, size_type{})}
+        , m_capacity(std::exchange(other.m_capacity, size_type{}))
+        , m_data(std::exchange(other.m_data, nullptr))
+    {}
+
+    //! Destroy this vector.
+    ~vector()
     {
-      std::ranges::copy(other, _data);
+      std::ranges::for_each(std::views::reverse(*this), [&](auto & element) {
+        std::allocator_traits<allocator_type>::destroy(m_allocator, std::addressof(element));
+      });
+      std::allocator_traits<allocator_type>::deallocate(m_allocator, m_data, m_capacity);
     }
 
-    /**
-     * @brief Copy assignment operator.
-     *
-     * @note Allocates underlying data container with the same capacity as vector we are copying from and copies all
-     * elements from it.
-     *
-     * @param other Other instance of vector we want to copy the data from.
-     * @return Newly created copy.
-     */
+    //! Replace the contents of this vector by the copying from the given source vector.
+    //!
+    //! @param other The source vector.
     auto operator=(vector const & other) -> vector<value_type> &
     {
-      delete[] _data;
-      _size = other._size;
-      _capacity = other._capacity;
-      _data = _capacity ? new value_type[_capacity]() : nullptr;
-      std::ranges::copy(other, _data);
+      if (this == std::addressof(other))
+      {
+        return *this;
+      }
+
+      if constexpr (std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value)
+      {
+        if (m_allocator != other.m_allocator)
+        {
+          clear_and_deallocate();
+        }
+        m_allocator = other.m_allocator;
+      }
+
+      if (m_capacity >= other.m_size)
+      {
+        auto const overlap = std::min(m_size, other.m_size);
+        auto first = std::ranges::begin(other);
+        for (auto i = 0uz; i < overlap; ++first, ++i)
+        {
+          m_data[i] = *first;
+        }
+
+        if (m_size < other.m_size)
+        {
+          for (auto i = m_size; i < other.m_size; ++first, ++i)
+          {
+            std::allocator_traits<allocator_type>::construct(m_allocator, m_data + i, *first);
+          }
+        }
+        else if (m_size > other.m_size)
+        {
+          for (auto i = other.m_size; i < m_size; ++i)
+          {
+            std::allocator_traits<allocator_type>::destroy(m_allocator, m_data + i);
+          }
+        }
+      }
+      else
+      {
+        auto new_data = std::allocator_traits<allocator_type>::allocate(m_allocator, other.m_size);
+        for (auto i = 0uz; i < other.m_size; ++i)
+        {
+          std::allocator_traits<allocator_type>::construct(m_allocator, new_data + i, other.m_data[i]);
+        }
+        clear_and_deallocate();
+        std::exchange(m_data, new_data);
+        m_capacity = other.m_size;
+      }
+
+      m_size = other.m_size;
       return *this;
     }
 
-    /**
-     * @brief Destructor.
-     */
-    ~vector()
+    //! Replace the contents fo this vector by moving from the given source.
+    //!
+    //! @param other The source vector.
+    auto operator=(vector && other) noexcept -> vector<value_type> &
     {
-      delete[] _data;
+      if (this == std::addressof(other))
+      {
+        return *this;
+      }
+
+      if constexpr (std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value)
+      {
+        clear_and_deallocate();
+        m_allocator = std::move(other.m_allocator);
+        m_size = std::exchange(other.m_size, size_type{});
+        m_capacity = std::exchange(other.m_capacity, size_type{});
+        m_data = std::exchange(other.m_data, nullptr);
+      }
+      else if (m_allocator != other.m_allocator)
+      {
+        clear_and_deallocate();
+        m_size = std::exchange(other.m_size, size_type{});
+        m_capacity = std::exchange(other.m_capacity, size_type{});
+        m_data = std::exchange(other.m_data, nullptr);
+      }
+      else
+      {
+        if (m_capacity >= other.m_size)
+        {
+          auto const overlap = std::min(m_size, other.m_size);
+          auto first = std::ranges::begin(other);
+          for (auto i = 0uz; i < overlap; ++first, ++i)
+          {
+            m_data[i] = std::move(*first);
+          }
+
+          if (m_size < other.m_size)
+          {
+            for (auto i = m_size; i < other.m_size; ++first, ++i)
+            {
+              std::allocator_traits<allocator_type>::construct(m_allocator, m_data + i, std::move(*first));
+            }
+          }
+          else if (m_size > other.m_size)
+          {
+            for (auto i = other.m_size; i < m_size; ++i)
+            {
+              std::allocator_traits<allocator_type>::destroy(m_allocator, m_data + i);
+            }
+          }
+        }
+        else
+        {
+          auto new_data = std::allocator_traits<allocator_type>::allocate(m_allocator, other.m_size);
+          for (auto i = 0uz; i < other.m_size; ++i)
+          {
+            std::allocator_traits<allocator_type>::destroy(m_allocator, m_data + i);
+          }
+          clear_and_deallocate();
+          std::exchange(m_data, new_data);
+          m_capacity = other.m_size;
+        }
+        for (auto i = 0uz; i < other.m_size; ++i)
+        {
+          std::allocator_traits<allocator_type>::destroy(other.m_allocator, other.m_data + i);
+        }
+        m_size = std::exchange(other.m_size, size_type{});
+      }
+
+      return *this;
     }
 
     /**
-     * @brief Amount of elements currently contained in this vector, will fill up until we have reached the capacity. If
-     * that is the case the capacity is increased automatically.
+     * @brief Amount of elements currently contained in this vector, will fill up until we have reached the capacity.
+     * If that is the case the capacity is increased automatically.
      *
      * @return Current amount of elements.
      */
     [[nodiscard]] auto size() const -> size_type
     {
-      return _size;
+      return m_size;
     }
 
     /**
-     * @brief Amount of space the vector currently has, can be different than the size, because we allocate more than we
-     * exactly require to decrease the amount of allocations and deallocation to improve speed.
+     * @brief Amount of space the vector currently has, can be different than the size, because we allocate more than
+     * we exactly require to decrease the amount of allocations and deallocation to improve speed.
      *
      * @return Current amount of space the vector has for elements.
      */
     [[nodiscard]] auto capacity() const -> size_type
     {
-      return _capacity;
+      return m_capacity;
     }
 
     /**
@@ -149,7 +278,7 @@ namespace kstd
      */
     auto operator[](size_type index) -> reference
     {
-      return _data[index];
+      return m_data[index];
     }
 
     /**
@@ -162,13 +291,14 @@ namespace kstd
      */
     auto operator[](size_type index) const -> const_reference
     {
-      return _data[index];
+      return m_data[index];
     }
 
     /**
      * @brief Array indexing operator. Allowing to access element at the given index.
      *
-     * @note Ensures we do not access element outside of the bounds of the array, if we do further execution is halted.
+     * @note Ensures we do not access element outside of the bounds of the array, if we do further execution is
+     * halted.
      *
      * @param index Index we want to access elements at.
      * @return Reference to the underlying element.
@@ -176,13 +306,14 @@ namespace kstd
     auto at(size_type index) -> reference
     {
       throw_if_out_of_range(index);
-      return this->operator[](index);
+      return (*this)[index];
     }
 
     /**
      * @brief Array indexing operator. Allowing to access element at the given index.
      *
-     * @note Ensures we do not access element outside of the bounds of the array, if we do further execution is halted.
+     * @note Ensures we do not access element outside of the bounds of the array, if we do further execution is
+     * halted.
      *
      * @param index Index we want to access elements at.
      * @return Reference to the underlying element.
@@ -190,7 +321,7 @@ namespace kstd
     [[nodiscard]] auto at(size_type index) const -> const_reference
     {
       throw_if_out_of_range(index);
-      return this->operator[](index);
+      return (*this)[index];
     }
 
     /**
@@ -209,13 +340,13 @@ namespace kstd
     auto push_back(U && value) -> void
     {
       increase_capacity_if_full();
-      _data[_size] = std::forward<U>(value);
-      (void)_size++;
+      std::allocator_traits<allocator_type>::construct(m_allocator, &(*this)[m_size], std::forward<U>(value));
+      ++m_size;
     }
 
     /**
-     * @brief Appends a new element to the end of the container. The element is constructed through a constructor of the
-     * template type. The arguments args... are forwarded to the constructor as std::forward<Args>(args)....
+     * @brief Appends a new element to the end of the container. The element is constructed through a constructor of
+     * the template type. The arguments args... are forwarded to the constructor as std::forward<Args>(args)....
      *
      * If after the operation the new size() is greater than old capacity() a reallocation takes place, in which case
      * all iterators (including the end() iterator) and all references to the elements are invalidated. Otherwise only
@@ -230,9 +361,9 @@ namespace kstd
     auto emplace_back(Args &&... args) -> value_type &
     {
       increase_capacity_if_full();
-      _data[_size] = value_type{std::forward<Args>(args)...};
-      auto const index = _size++;
-      return _data[index];
+      std::allocator_traits<allocator_type>::construct(m_allocator, &(*this)[m_size], std::forward<Args>(args)...);
+      ++m_size;
+      return this->back();
     }
 
     /**
@@ -243,7 +374,7 @@ namespace kstd
     auto pop_back() -> void
     {
       throw_if_empty();
-      (void)_size--;
+      (void)m_size--;
     }
 
     /**
@@ -254,7 +385,7 @@ namespace kstd
      */
     auto begin() noexcept -> pointer
     {
-      return _data;
+      return m_data;
     }
 
     /**
@@ -265,7 +396,7 @@ namespace kstd
      */
     [[nodiscard]] auto begin() const noexcept -> const_pointer
     {
-      return _data;
+      return m_data;
     }
 
     /**
@@ -280,30 +411,30 @@ namespace kstd
     }
 
     /**
-     * @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last element
-     * of the non-reversed vector. If the vector is empty, the returned iterator will be equal to rend().
+     * @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last
+     * element of the non-reversed vector. If the vector is empty, the returned iterator will be equal to rend().
      *
      * @return Reverse iterator to the first element.
      */
     auto rbegin() noexcept -> pointer
     {
-      return _data + _size - 1;
+      return m_data + m_size - 1;
     }
 
     /**
-     * @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last element
-     * of the non-reversed vector. If the vector is empty, the returned iterator will be equal to rend().
+     * @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last
+     * element of the non-reversed vector. If the vector is empty, the returned iterator will be equal to rend().
      *
      * @return Reverse iterator to the first element.
      */
     [[nodiscard]] auto rbegin() const noexcept -> const_pointer
     {
-      return _data + _size - 1;
+      return m_data + m_size - 1;
     }
 
     /**
-     * @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last element
-     * of the non-reversed vector. If the vector is empty, the returned iterator will be equal to rend().
+     * @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last
+     * element of the non-reversed vector. If the vector is empty, the returned iterator will be equal to rend().
      *
      * @return Reverse iterator to the first element.
      */
@@ -320,7 +451,7 @@ namespace kstd
      */
     auto end() noexcept -> pointer
     {
-      return _data + _size;
+      return m_data + m_size;
     }
 
     /**
@@ -331,7 +462,7 @@ namespace kstd
      */
     [[nodiscard]] auto end() const noexcept -> const_pointer
     {
-      return _data + _size;
+      return m_data + m_size;
     }
 
     /**
@@ -354,7 +485,7 @@ namespace kstd
      */
     auto rend() noexcept -> pointer
     {
-      return _data + size() - 1;
+      return m_data + size() - 1;
     }
 
     /**
@@ -366,7 +497,7 @@ namespace kstd
      */
     [[nodiscard]] auto rend() const noexcept -> const_pointer
     {
-      return _data + size() - 1;
+      return m_data + size() - 1;
     }
 
     /**
@@ -383,28 +514,28 @@ namespace kstd
 
     /**
      * @brief Returns a pointer to the underlying array serving as element storage. The pointer is such that range
-     * [data(), data() + size()) is always a valid range, even if the container is empty (data() is not dereferenceable
-     * in that case).
+     * [data(), data() + size()) is always a valid range, even if the container is empty (data() is not
+     * dereferenceable in that case).
      *
-     * @return Pointer to the underlying element storage. For non-empty containers, the returned pointer compares equal
-     * to the address of the first element.
+     * @return Pointer to the underlying element storage. For non-empty containers, the returned pointer compares
+     * equal to the address of the first element.
      */
     auto data() -> pointer
     {
-      return _data;
+      return m_data;
     }
 
     /**
      * @brief Returns a pointer to the underlying array serving as element storage. The pointer is such that range
-     * [data(), data() + size()) is always a valid range, even if the container is empty (data() is not dereferenceable
-     * in that case).
+     * [data(), data() + size()) is always a valid range, even if the container is empty (data() is not
+     * dereferenceable in that case).
      *
-     * @return Pointer to the underlying element storage. For non-empty containers, the returned pointer compares equal
-     * to the address of the first element.
+     * @return Pointer to the underlying element storage. For non-empty containers, the returned pointer compares
+     * equal to the address of the first element.
      */
     [[nodiscard]] auto data() const -> const_pointer
     {
-      return _data;
+      return m_data;
     }
 
     /**
@@ -469,11 +600,11 @@ namespace kstd
      * the vector greater than the value of capacity().
      *
      * @note Correctly using reserve() can prevent unnecessary reallocations, but inappropriate uses of reserve() (for
-     * instance, calling it before every push_back() call) may actually increase the number of reallocations (by causing
-     * the capacity to grow linearly rather than exponentially) and result in increased computational complexity and
-     * decreased performance. For example, a function that receives an arbitrary vector by reference and appends
-     * elements to it should usually not call reserve() on the vector, since it does not know of the vector's usage
-     * characteristics.
+     * instance, calling it before every push_back() call) may actually increase the number of reallocations (by
+     * causing the capacity to grow linearly rather than exponentially) and result in increased computational
+     * complexity and decreased performance. For example, a function that receives an arbitrary vector by reference
+     * and appends elements to it should usually not call reserve() on the vector, since it does not know of the
+     * vector's usage characteristics.
      *
      * When inserting a range, the range version of insert() is generally preferable as it preserves the correct
      * capacity growth behavior, unlike reserve() followed by a series of push_back()s.
@@ -484,16 +615,16 @@ namespace kstd
      */
     auto reserve(size_type new_capacity) -> void
     {
-      if (new_capacity <= _capacity)
+      if (new_capacity <= m_capacity)
       {
         return;
       }
 
-      _capacity = new_capacity;
-      auto temp = new value_type[_capacity]();
+      m_capacity = new_capacity;
+      auto temp = new value_type[m_capacity]();
       std::ranges::copy(begin(), end(), temp);
-      delete[] _data;
-      _data = temp;
+      delete[] m_data;
+      m_data = temp;
     }
 
     /**
@@ -504,16 +635,16 @@ namespace kstd
      */
     auto shrink_to_fit() -> void
     {
-      if (_size == _capacity)
+      if (m_size == m_capacity)
       {
         return;
       }
 
-      _capacity = _size;
-      auto temp = new value_type[_capacity]{};
+      m_capacity = m_size;
+      auto temp = new value_type[m_capacity]{};
       std::ranges::copy(begin(), end(), temp);
-      delete[] _data;
-      _data = temp;
+      delete[] m_data;
+      m_data = temp;
     }
 
     /**
@@ -523,10 +654,30 @@ namespace kstd
      */
     [[nodiscard]] auto empty() const -> bool
     {
-      return _size <= 0;
+      return m_size <= 0;
     }
 
   private:
+    auto allocate_n(std::size_t count) -> std::allocator_traits<allocator_type>::pointer
+    {
+      if (count)
+      {
+        return std::allocator_traits<allocator_type>::allocate(m_allocator, count);
+      }
+      return nullptr;
+    }
+
+    auto clear_and_deallocate() -> void
+    {
+      std::ranges::for_each(std::views::reverse(*this), [&](auto & element) {
+        std::allocator_traits<allocator_type>::destroy(m_allocator, std::addressof(element));
+      });
+      std::allocator_traits<allocator_type>::deallocate(m_allocator, m_data, m_capacity);
+      m_capacity = 0;
+      m_size = 0;
+      m_data = nullptr;
+    }
+
     /**
      * @brief Halts the execution of the application if the data container is currently empty.
      */
@@ -540,7 +691,7 @@ namespace kstd
 
     auto throw_if_out_of_range(size_type index) const -> void
     {
-      if (index >= _size)
+      if (index >= m_size)
       {
         os::panic("[Vector] Attempted to read element at invalid index");
       }
@@ -548,20 +699,21 @@ namespace kstd
 
     /**
      * @brief Increases the internal capacity to 1 if it was previously 0 and to * 2 after that, meaning exponential
-     * growth. This is done to decrease the amount of single allocations done and because a power of 2 in memory size is
-     * normally perferable for the cache.
+     * growth. This is done to decrease the amount of single allocations done and because a power of 2 in memory size
+     * is normally perferable for the cache.
      */
     auto increase_capacity_if_full() -> void
     {
-      if (_size == _capacity)
+      if (m_size == m_capacity)
       {
-        reserve(_capacity == 0U ? 1U : _capacity * 2U);
+        reserve(m_capacity == 0U ? 1U : m_capacity * 2U);
       }
     }
 
-    size_type _size = {};      ///< Amount of elements in the underlying data container
-    size_type _capacity = {};  ///< Amount of space for elements in the underlying data container
-    value_type * _data = {};   ///< Pointer to the first element in the underlying data container
+    [[no_unique_address]] allocator_type m_allocator{};
+    size_type m_size{};      ///< Amount of elements in the underlying data container
+    size_type m_capacity{};  ///< Amount of space for elements in the underlying data container
+    value_type * m_data{};   ///< Pointer to the first element in the underlying data container
   };
 
 }  // namespace kstd