From c049d767c7d41d04226f2c6b01ee2e07aae7ea1f Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 19 Mar 2026 07:16:58 +0100 Subject: kstd: prepare vector to be allocator aware --- libs/kstd/include/kstd/vector | 426 ++++++++++++++++++++++++++++-------------- 1 file changed, 289 insertions(+), 137 deletions(-) (limited to 'libs') 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 #include #include +#include +#include +#include +#include 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 + template> 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; + using const_reverse_iterator = std::reverse_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::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 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::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 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 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::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 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::destroy(m_allocator, std::addressof(element)); + }); + std::allocator_traits::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 & { - 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::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::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::destroy(m_allocator, m_data + i); + } + } + } + else + { + auto new_data = std::allocator_traits::allocate(m_allocator, other.m_size); + for (auto i = 0uz; i < other.m_size; ++i) + { + std::allocator_traits::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 & { - delete[] _data; + if (this == std::addressof(other)) + { + return *this; + } + + if constexpr (std::allocator_traits::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::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::destroy(m_allocator, m_data + i); + } + } + } + else + { + auto new_data = std::allocator_traits::allocate(m_allocator, other.m_size); + for (auto i = 0uz; i < other.m_size; ++i) + { + std::allocator_traits::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::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(value); - (void)_size++; + std::allocator_traits::construct(m_allocator, &(*this)[m_size], std::forward(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).... + * @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).... * * 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)...}; - auto const index = _size++; - return _data[index]; + std::allocator_traits::construct(m_allocator, &(*this)[m_size], std::forward(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::pointer + { + if (count) + { + return std::allocator_traits::allocate(m_allocator, count); + } + return nullptr; + } + + auto clear_and_deallocate() -> void + { + std::ranges::for_each(std::views::reverse(*this), [&](auto & element) { + std::allocator_traits::destroy(m_allocator, std::addressof(element)); + }); + std::allocator_traits::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 -- cgit v1.2.3 From cc55324b0f3a988befaecff15e0ff87e3c6a4dee Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 19 Mar 2026 08:08:32 +0100 Subject: kstd: implement default allocator --- libs/kstd/include/kstd/allocator | 64 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+) create mode 100644 libs/kstd/include/kstd/allocator (limited to 'libs') diff --git a/libs/kstd/include/kstd/allocator b/libs/kstd/include/kstd/allocator new file mode 100644 index 0000000..0de0e10 --- /dev/null +++ b/libs/kstd/include/kstd/allocator @@ -0,0 +1,64 @@ +#ifndef KSTD_ALLOCATOR_HPP +#define KSTD_ALLOCATOR_HPP + +#include +#include +#include + +#if __has_builtin(__builtin_operator_new) >= 201'802L +#define KSTD_OPERATOR_NEW __builtin_operator_new +#define KSTD_OPERATOR_DELETE __builtin_operator_delete +#else +#define KSTD_OPERATOR_NEW ::operator new +#define KSTD_OPERATOR_DELETE ::operator delete +#endif + +namespace kstd +{ + + template + struct allocator + { + using value_type = T; + using size_type = std::size_t; + using difference_type = std::ptrdiff_t; + using propagate_on_container_move_assignment = std::true_type; + using is_always_equal = std::true_type; + + constexpr allocator() noexcept = default; + + template + constexpr allocator(allocator const &) noexcept + {} + + constexpr auto allocate(std::size_t n) -> T * + { + if (alignof(T) > __STDCPP_DEFAULT_NEW_ALIGNMENT__) + { + return static_cast(KSTD_OPERATOR_NEW(n * sizeof(T), std::align_val_t{alignof(T)})); + } + return static_cast(KSTD_OPERATOR_NEW(n * sizeof(T))); + } + + constexpr void deallocate(T * p, std::size_t n) noexcept + { + if (alignof(T) > __STDCPP_DEFAULT_NEW_ALIGNMENT__) + { + KSTD_OPERATOR_DELETE(p, n * sizeof(T), std::align_val_t{alignof(T)}); + } + KSTD_OPERATOR_DELETE(p, n * sizeof(T)); + } + }; + + template + constexpr auto operator==(allocator const &, allocator const &) noexcept -> bool + { + return true; + } + +} // namespace kstd + +#undef KSTD_OPERATOR_NEW +#undef KSTD_OPERATOR_DELETE + +#endif \ No newline at end of file -- cgit v1.2.3 From ae2a264b117ecf556f742d8e9c357f906cb3fd83 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 19 Mar 2026 13:00:08 +0100 Subject: kstd: finish preliminary vector implementation --- libs/kstd/include/kstd/ranges | 21 ++ libs/kstd/include/kstd/vector | 810 ++++++++++++++++++++---------------------- 2 files changed, 401 insertions(+), 430 deletions(-) create mode 100644 libs/kstd/include/kstd/ranges (limited to 'libs') diff --git a/libs/kstd/include/kstd/ranges b/libs/kstd/include/kstd/ranges new file mode 100644 index 0000000..78c3adb --- /dev/null +++ b/libs/kstd/include/kstd/ranges @@ -0,0 +1,21 @@ +#ifndef KSTD_RANGES +#define KSTD_RANGES + +#include // IWYU pragma: export + +namespace kstd +{ +#if __glibcxx_ranges_to_container + using std::from_range; + using std::from_range_t; +#else + struct from_range_t + { + explicit from_range_t() = default; + }; + constexpr auto inline from_range = from_range_t{}; +#endif + +} // namespace kstd + +#endif \ No newline at end of file diff --git a/libs/kstd/include/kstd/vector b/libs/kstd/include/kstd/vector index b87756a..9709c2a 100644 --- a/libs/kstd/include/kstd/vector +++ b/libs/kstd/include/kstd/vector @@ -1,14 +1,19 @@ #ifndef KSTD_VECTOR_HPP #define KSTD_VECTOR_HPP +#include #include +#include #include +#include +#include #include #include #include #include #include +#include #include namespace kstd @@ -20,7 +25,7 @@ namespace kstd * @tparam T Element the vector instance should contain. * @tparam Allocator The allocator to use when allocating new elements. */ - template> + template> struct vector { using value_type = T; ///< Type of the elements contained in the container. @@ -37,20 +42,51 @@ namespace kstd using const_reverse_iterator = std::reverse_iterator; //! Construct a new, empty vector. - vector() = default; + vector() noexcept(std::is_nothrow_default_constructible_v) + : vector(allocator_type{}) + {} + + //! Construct a new, empty vector with a given allocator. + //! + //! @param allocator The allocator to use in the vector. + explicit constexpr vector(allocator_type const & allocator) noexcept( + std::is_nothrow_copy_constructible_v) + : m_allocator{allocator} + {} + + //! Construct a new vector and fill it with the given number of default constructed elements. + //! + //! @param count The number of element to create the vector with. + //! @param allocator The allocator to use in the vector. + explicit constexpr vector(size_type count, allocator_type const & allocator = allocator_type{}) noexcept( + std::is_nothrow_copy_constructible_v) + : m_allocator{allocator} + , m_size{count} + , m_capacity{count} + , m_data{allocate_n(m_capacity)} + { + for (auto i = 0uz; i < count; ++i) + { + std::allocator_traits::construct(m_allocator, m_data + i); + } + } - //! Construct a new vector, with the given number of element and initialize them to the given value. + //! Construct a new vector and fill it with the given number of copy constructed elements. //! - //! @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{}) - : m_size{n} - , m_capacity{n} + //! @param count The number of element to create the vector with. + //! @param value The value to copy for each element + //! @param allocator The allocator to use in the vector. + constexpr vector(size_type count, const_reference value, + allocator_type const & allocator = + allocator_type{}) noexcept(std::is_nothrow_copy_constructible_v) + : m_allocator{allocator} + , m_size{count} + , m_capacity{m_size} , m_data{allocate_n(m_capacity)} { - for (auto i = 0uz; i < n; ++i) + for (auto i = 0uz; i < count; ++i) { - std::allocator_traits::construct(m_allocator, m_data + i, initial); + std::allocator_traits::construct(m_allocator, m_data + i, value); } } @@ -59,66 +95,103 @@ namespace kstd //! @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 - explicit vector(InputIterator first, InputIterator last) - : m_allocator{} + template + constexpr vector(InputIterator first, InputIterator last, + allocator_type const & allocator = + allocator_type{}) noexcept(std::is_nothrow_copy_constructible_v) + : m_allocator{allocator} , m_size{std::ranges::distance(first, last)} - , m_capacity{std::ranges::distance(first, last)} + , m_capacity{m_size} , m_data{allocate_n(m_capacity)} { - for (auto destination = begin(); first != last; ++first, ++destination) + for (auto destination = m_data; first != last; ++first, ++destination) { std::allocator_traits::construct(m_allocator, destination, *first); } } - //! Construct a new vector and initialize it's content by copying all elements in the given initializer list. + //! Construct a new vector and initialize it's content by copying all elements in the given range. //! - //! @param list The initializer list containing the source objects. - explicit vector(std::initializer_list list) - : vector{std::ranges::begin(list), std::ranges::end(list)} - {} + //! + template + requires(std::ranges::input_range && std::convertible_to, T>) + constexpr vector(kstd::from_range_t, Range && range, allocator_type const & allocator = allocator_type{}) + : m_allocator{allocator} + , m_size{std::ranges::size(range)} + , m_capacity{m_size} + , m_data{allocate_n(m_capacity)} + { + auto destination = m_data; + for (auto && element : std::forward(range)) + { + std::allocator_traits::construct(m_allocator, destination++, + std::forward>(element)); + } + } //! 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) + constexpr 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::construct(m_allocator, destination, *first); - } + uninitialized_copy_with_allocator(other.begin(), begin(), other.size()); } //! 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{})} + constexpr vector(vector && other) noexcept + : m_allocator{std::move(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)) {} + //! Construct a new vector and initialize it's content by copying from a given vector. + //! + //! @param other The source vector. + //! @param allocator The allocator to use in the vector. + constexpr vector(vector const & other, std::type_identity_t const & allocator) + : m_allocator{allocator} + , m_size{other.m_size} + , m_capacity{other.m_capacity} + , m_data{allocate_n(m_capacity)} + { + uninitialized_copy_with_allocator(other.begin(), begin(), other.size()); + } + + //! Construct a new vector and initialize it's content by copying from a given vector. + //! + //! @param other The source vector. + //! @param allocator The allocator to use in the vector. + constexpr vector(vector && other, std::type_identity_t const & allocator) + : m_allocator{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)) + {} + + //! 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 list, allocator_type const & allocator = allocator_type{}) + : vector{std::ranges::begin(list), std::ranges::end(list), allocator} + {} + //! Destroy this vector. - ~vector() + constexpr ~vector() { - std::ranges::for_each(std::views::reverse(*this), [&](auto & element) { - std::allocator_traits::destroy(m_allocator, std::addressof(element)); - }); - std::allocator_traits::deallocate(m_allocator, m_data, m_capacity); + clear_and_deallocate(); } //! 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 & + constexpr auto operator=(vector const & other) -> vector & { if (this == std::addressof(other)) { @@ -127,58 +200,49 @@ namespace kstd if constexpr (std::allocator_traits::propagate_on_container_move_assignment::value) { - if (m_allocator != other.m_allocator) + if (get_allocator() != other.get_allocator()) { clear_and_deallocate(); } - m_allocator = other.m_allocator; + m_allocator = other.get_allocator(); } - if (m_capacity >= other.m_size) + if (capacity() >= other.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; - } + copy_elements(other.begin(), begin(), overlap); if (m_size < other.m_size) { - for (auto i = m_size; i < other.m_size; ++first, ++i) - { - std::allocator_traits::construct(m_allocator, m_data + i, *first); - } + uninitialized_copy_with_allocator(other.begin() + size(), begin() + size(), other.m_size - size()); } else if (m_size > other.m_size) { - for (auto i = other.m_size; i < m_size; ++i) - { - std::allocator_traits::destroy(m_allocator, m_data + i); - } + destroy_n(begin() + other.size(), size() - other.size()); } } else { - auto new_data = std::allocator_traits::allocate(m_allocator, other.m_size); - for (auto i = 0uz; i < other.m_size; ++i) - { - std::allocator_traits::construct(m_allocator, new_data + i, other.m_data[i]); - } + auto new_data = std::allocator_traits::allocate(m_allocator, other.size()); + uninitialized_copy_with_allocator(other.begin(), new_data, other.size()); clear_and_deallocate(); - std::exchange(m_data, new_data); - m_capacity = other.m_size; + m_data = new_data; + m_capacity = other.size(); } - m_size = other.m_size; + m_size = other.size(); return *this; } //! Replace the contents fo this vector by moving from the given source. //! //! @param other The source vector. - auto operator=(vector && other) noexcept -> vector & + constexpr auto operator=(vector && other) noexcept( + std::allocator_traits::propagate_on_container_move_assignment::value || + std::allocator_traits::is_always_equal::value) -> vector & { + using std::swap; + if (this == std::addressof(other)) { return *this; @@ -187,478 +251,338 @@ namespace kstd if constexpr (std::allocator_traits::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); + swap(m_allocator, other.m_allocator); + swap(m_size, other.m_size); + swap(m_capacity, other.m_capacity); + swap(m_data, other.m_data); } - else if (m_allocator != other.m_allocator) + 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); + swap(m_size, other.m_size); + swap(m_capacity, other.m_capacity); + swap(m_data, other.m_data); } else { - if (m_capacity >= other.m_size) + if (capacity() >= other.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); - } + auto const overlap = std::min(size(), other.size()); + move_elements(other.begin(), begin(), overlap); - if (m_size < other.m_size) + if (size() < other.size()) { - for (auto i = m_size; i < other.m_size; ++first, ++i) - { - std::allocator_traits::construct(m_allocator, m_data + i, std::move(*first)); - } + uninitialized_move_with_allocator(other.begin() + size(), begin() + size(), other.size() - size()); } - else if (m_size > other.m_size) + else if (size() > other.size()) { - for (auto i = other.m_size; i < m_size; ++i) - { - std::allocator_traits::destroy(m_allocator, m_data + i); - } + destroy_n(begin() + other.size(), size() - other.size()); } } else { - auto new_data = std::allocator_traits::allocate(m_allocator, other.m_size); - for (auto i = 0uz; i < other.m_size; ++i) - { - std::allocator_traits::destroy(m_allocator, m_data + i); - } + auto new_data = std::allocator_traits::allocate(get_allocator(), other.size()); + uninitialized_move_with_allocator(other.begin(), new_data, other.size()); clear_and_deallocate(); - std::exchange(m_data, new_data); + m_data = new_data; m_capacity = other.m_size; } - for (auto i = 0uz; i < other.m_size; ++i) - { - std::allocator_traits::destroy(other.m_allocator, other.m_data + i); - } + + other.destroy_n(other.begin(), other.size()); 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. - * - * @return Current amount of elements. - */ - [[nodiscard]] auto size() const -> size_type + //! Get a copy of the allocator associated with this vector. + [[nodiscard]] constexpr auto get_allocator() const noexcept(std::is_nothrow_copy_constructible_v) + -> allocator_type { - return m_size; + return m_allocator; } - /** - * @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 + //! Get a reference to the element at the given index. + //! + //! This function will panic if the index is out of bounds for this vector. + //! + //! @param index The index of the element to retrieve. + //! @return A reference to the element at the specified index. + [[nodiscard]] constexpr auto at(size_type index) -> reference { - return m_capacity; + panic_if_out_of_bounds(index); + return (*this)[index]; } - /** - * @brief Array indexing operator. Allowing to access element at the given index. - * - * @note Does not do any bounds checks use at() for that. - * - * @param index Index we want to access elements at. - * @return Reference to the underlying element. - */ - auto operator[](size_type index) -> reference - { - return m_data[index]; - } - - /** - * @brief Array indexing operator. Allowing to access element at the given index. - * - * @note Does not do any bounds checks use at() for that. - * - * @param index Index we want to access elements at. - * @return Reference to the underlying element. - */ - auto operator[](size_type index) const -> const_reference - { - 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. - * - * @param index Index we want to access elements at. - * @return Reference to the underlying element. - */ - auto at(size_type index) -> reference - { - throw_if_out_of_range(index); + //! Get a reference to the element at the given index. + //! + //! This function will panic if the index is out of bounds for this vector. + //! + //! @param index The index of the element to retrieve. + //! @return A reference to the element at the specified index. + [[nodiscard]] constexpr auto at(size_type index) const -> const_reference + { + panic_if_out_of_bounds(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. - * - * @param index Index we want to access elements at. - * @return Reference to the underlying element. - */ - [[nodiscard]] auto at(size_type index) const -> const_reference + //! Get a reference to the element at the given index. + //! + //! The behavior is undefined if the index is out of bounds for this vector. + //! + //! @param index The index of the element to retrieve. + //! @return A reference to the element at the specified index. + [[nodiscard]] constexpr auto operator[](size_type index) -> reference { - throw_if_out_of_range(index); - return (*this)[index]; + return data()[index]; } - /** - * @brief Appends the given element value to the end of the container. The element is assigned through the - * assignment operator of the template type. The value is forwarded to the constructor as - * std::forward(value), meaning it is either moved (rvalue) or copied (lvalue). - * - * @note 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 the end() iterator is invalidated. Uses a forward reference for the actual value passed, which - * allows the template method to be used by both lvalue and rvalues and compile a different implementation. - * - * @param value The value of the element to append. - */ - template - auto push_back(U && value) -> void + //! Get a reference to the element at the given index. + //! + //! The behavior is undefined if the index is out of bounds for this vector. + //! + //! @param index The index of the element to retrieve. + //! @return A reference to the element at the specified index. + [[nodiscard]] constexpr auto operator[](size_type index) const -> const_reference { - increase_capacity_if_full(); - std::allocator_traits::construct(m_allocator, &(*this)[m_size], std::forward(value)); - ++m_size; + return data()[index]; } - /** - * @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).... - * - * 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 - * the end() iterator is invalidated. Uses a forward reference for the actual value passed, which - * allows the template method to be used by both lvalue and rvalues and compile a different implementation. - * - * @tparam Args - * @param args Arguments to forward to the constructor of the element - * @return value_type& - */ - template - auto emplace_back(Args &&... args) -> value_type & + //! Get a reference to the first element of this vector. + //! + //! The behavior is undefined if this vector is empty. + [[nodiscard]] constexpr auto front() -> reference { - increase_capacity_if_full(); - std::allocator_traits::construct(m_allocator, &(*this)[m_size], std::forward(args)...); - ++m_size; - return this->back(); + return *begin(); } - /** - * @brief Removes the last element of the container. Calling pop_back on an empty container results in halting the - * further execution. Iterators and references to the last element are invalidated. The end() - * iterator is also invalidated. - */ - auto pop_back() -> void + //! Get a reference to the first element of this vector. + //! + //! The behavior is undefined if this vector is empty. + [[nodiscard]] auto front() const -> const_reference { - throw_if_empty(); - (void)m_size--; + return *begin(); } - /** - * @brief Returns an iterator to the first element of the vector. - * If the vector is empty, the returned iterator will be equal to end(). - * - * @return Iterator to the first element. - */ - auto begin() noexcept -> pointer + //! Get a reference to the last element of this vector. + //! + //! The behavior is undefined if this vector is empty. + [[nodiscard]] constexpr auto back() -> reference { - return m_data; + return *rbegin(); + } + + //! Get a reference to the last element of this vector. + //! + //! The behavior is undefined if this vector is empty. + [[nodiscard]] constexpr auto back() const -> const_reference + { + return *rbegin(); } - /** - * @brief Returns an iterator to the first element of the vector. - * If the vector is empty, the returned iterator will be equal to end(). - * - * @return Iterator to the first element. - */ - [[nodiscard]] auto begin() const noexcept -> const_pointer + //! Get a pointer to the beginning of the underlying contiguous storage. + [[nodiscard]] constexpr auto data() noexcept -> pointer { return m_data; } - /** - * @brief Returns an iterator to the first element of the vector. - * If the vector is empty, the returned iterator will be equal to end(). - * - * @return Iterator to the first element. - */ - [[nodiscard]] auto cbegin() const noexcept -> const_pointer + //! Get a pointer to the beginning of the underlying contiguous storage. + [[nodiscard]] constexpr auto data() const noexcept -> const_pointer { - return begin(); + return m_data; } - /** - * @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 + //! Get an iterator to the first element of this vector. + //! + //! @return An iterator to the first element of this container, or end() if the container is empty. + [[nodiscard]] constexpr auto begin() noexcept -> iterator { - return m_data + m_size - 1; + return empty() ? end() : data(); } - /** - * @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 + //! Get an iterator to the first element of this vector. + //! + //! @return An iterator to the first element of this container, or end() if the container is empty. + [[nodiscard]] constexpr auto begin() const noexcept -> const_iterator { - return m_data + m_size - 1; + return empty() ? end() : data(); } - /** - * @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 crbegin() const noexcept -> const_pointer + //! Get an iterator to the first element of this vector. + //! + //! @return An iterator to the first element of this container, or end() if the container is empty. + [[nodiscard]] constexpr auto cbegin() const noexcept -> const_iterator { - return rbegin(); + return begin(); } - /** - * @brief Returns an iterator to the element following the last element of the vector. This element acts as a - * placeholder, attempting to access it results in undefined behavior. - * - * @return Iterator to the element following the last element. - */ - auto end() noexcept -> pointer + //! Get an iterator past the last element of this vector. + [[nodiscard]] constexpr auto end() noexcept -> pointer { - return m_data + m_size; + return capacity() ? data() + size() : nullptr; } - /** - * @brief Returns an iterator to the element following the last element of the vector. This element acts as a - * placeholder, attempting to access it results in undefined behavior. - * - * @return Iterator to the element following the last element. - */ - [[nodiscard]] auto end() const noexcept -> const_pointer + //! Get an iterator past the last element of this vector. + [[nodiscard]] constexpr auto end() const noexcept -> const_pointer { - return m_data + m_size; + return capacity() ? data() + size() : nullptr; } - /** - * @brief Returns an iterator to the element following the last element of the vector. This element acts as a - * placeholder, attempting to access it results in undefined behavior. - * - * @return Iterator to the element following the last element. - */ - [[nodiscard]] auto cend() const noexcept -> const_pointer + //! Get an iterator past the last element of this vector. + [[nodiscard]] constexpr auto cend() const noexcept -> const_pointer { return end(); } - /** - * @brief Returns a reverse iterator to the element following the last element of the reversed vector. It - * corresponds to the element preceding the first element of the non-reversed vector. This element acts as a - * placeholder, attempting to access it results in undefined behavior. - * - * @return Reverse iterator to the element following the last element. - */ - auto rend() noexcept -> pointer + //! Get a reverse iterator to the reverse beginning. + [[nodiscard]] constexpr auto rbegin() noexcept -> reverse_iterator { - return m_data + size() - 1; + return empty() ? rend() : reverse_iterator{begin() + (m_size - 1)}; } - /** - * @brief Returns a reverse iterator to the element following the last element of the reversed vector. It - * corresponds to the element preceding the first element of the non-reversed vector. This element acts as a - * placeholder, attempting to access it results in undefined behavior. - * - * @return Reverse iterator to the element following the last element. - */ - [[nodiscard]] auto rend() const noexcept -> const_pointer + //! Get a reverse iterator to the reverse beginning. + [[nodiscard]] constexpr auto rbegin() const noexcept -> const_reverse_iterator { - return m_data + size() - 1; + return empty() ? rend() : const_reverse_iterator{begin() + (m_size - 1)}; } - /** - * @brief Returns a reverse iterator to the element following the last element of the reversed vector. It - * corresponds to the element preceding the first element of the non-reversed vector. This element acts as a - * placeholder, attempting to access it results in undefined behavior. - * - * @return Reverse iterator to the element following the last element. - */ - [[nodiscard]] auto crend() const noexcept -> const_pointer + //! Get a reverse iterator to the reverse beginning. + [[nodiscard]] constexpr auto crbegin() const noexcept -> const_reverse_iterator { return rbegin(); } - /** - * @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). - * - * @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 + //! Get a reverse iterator to the reverse end. + [[nodiscard]] constexpr auto rend() noexcept -> reverse_iterator { - return m_data; + return reverse_iterator{capacity() ? data() - 1 : nullptr}; } - /** - * @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). - * - * @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 + //! Get a reverse iterator to the reverse end. + [[nodiscard]] auto rend() const noexcept -> const_reverse_iterator { - return m_data; + return const_reverse_iterator{capacity() ? data() - 1 : nullptr}; } - /** - * @brief Returns a reference to the first element in the container. Calling front on an empty container causes - * undefined behavior. - * - * @return Reference to the first element. - */ - auto front() -> reference + //! Get a reverse iterator to the reverse end. + [[nodiscard]] auto crend() const noexcept -> const_reverse_iterator { - throw_if_empty(); - return *begin(); + return rend(); } - /** - * @brief Returns a reference to the first element in the container. Calling front on an empty container causes - * undefined behavior. - * - * @return Reference to the first element. - */ - [[nodiscard]] auto front() const -> const_reference + //! Check whether this vector is empty. + [[nodiscard]] constexpr auto empty() const noexcept -> bool { - throw_if_empty(); - return *begin(); + return !size(); } - /** - * @brief Returns a reference to the last element in the container. Calling back on an empty container causes - * undefined behavior. - * - * @return Reference to the last element. - */ - auto back() -> reference + //! Get the number of elements present in this vector. + [[nodiscard]] constexpr auto size() const noexcept -> size_type { - throw_if_empty(); - return *rbegin(); + return m_size; } - /** - * @brief Returns a reference to the last element in the container. Calling back on an empty container causes - * undefined behavior. - * - * @return Reference to the last element. - */ - [[nodiscard]] auto back() const -> const_reference + //! Get the maximum possible number of element for this vector. + [[nodiscard]] constexpr auto max_size() const noexcept -> size_type { - throw_if_empty(); - return *rbegin(); + return std::allocator_traits::max_size(m_allocator); } - /** - * @brief Increase the capacity of the vector (the total number of elements that the vector can hold without - * requiring reallocation) to a value that's greater or equal to new_cap. If new_cap is greater than the current - * capacity(), new storage is allocated, otherwise the function does nothing. - * - * reserve() does not change the size of the vector. - * - * If new_cap is greater than capacity(), all iterators (including the end() iterator) and all references to the - * elements are invalidated. Otherwise, no iterators or references are invalidated. - * - * After a call to reserve(), insertions will not trigger reallocation unless the insertion would make the size of - * 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 expon