From f08512d1cddcf43de64f0b3f8b0e6c9fe31bcaea Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Tue, 24 Mar 2026 13:03:15 +0100 Subject: kstd/vector: add basic insert overloads --- libs/kstd/include/kstd/vector | 130 +++++++++++++++++++++++++++++++++--------- 1 file changed, 102 insertions(+), 28 deletions(-) (limited to 'libs/kstd/include') diff --git a/libs/kstd/include/kstd/vector b/libs/kstd/include/kstd/vector index 5655854..0d4aac8 100644 --- a/libs/kstd/include/kstd/vector +++ b/libs/kstd/include/kstd/vector @@ -259,7 +259,7 @@ namespace kstd if (capacity() >= other.size()) { auto const overlap = std::min(m_size, other.m_size); - copy_elements(other.begin(), begin(), overlap); + std::ranges::copy(other.begin(), other.begin() + overlap, begin()); if (m_size < other.m_size) { @@ -317,7 +317,7 @@ namespace kstd if (capacity() >= other.size()) { auto const overlap = std::min(size(), other.size()); - move_elements(other.begin(), begin(), overlap); + std::ranges::move(other.begin(), other.begin() + overlap, begin()); if (size() < other.size()) { @@ -590,6 +590,106 @@ namespace kstd m_size = 0; } + //! Insert an element at a given position. + //! + //! @param position The position to insert the element at. + //! @param value The value to insert. + //! @return An iterator to the inserted element. + constexpr auto insert(const_iterator position, value_type const & value) -> iterator + { + auto prefix_size = std::ranges::distance(begin(), position); + auto suffix_size = std::ranges::distance(position, end()); + + if (position == end()) + { + push_back(value); + return begin() + prefix_size; + } + + if (m_capacity == m_size) + { + auto new_capacity = m_capacity == 0 ? 1 : m_capacity * 2; + auto new_data = allocate_n(new_capacity); + auto old_size = size(); + std::allocator_traits::construct(m_allocator, new_data + prefix_size, value); + uninitialized_move_with_allocator(begin(), new_data, prefix_size); + uninitialized_move_with_allocator(begin() + prefix_size, new_data + prefix_size + 1, suffix_size); + destroy_n(begin(), old_size); + deallocate(); + m_data = new_data; + m_capacity = new_capacity; + m_size = old_size; + } + else if (&value >= begin() && &value < end()) + { + auto value_copy = value; + auto insert_position = begin() + prefix_size; + std::allocator_traits::construct(m_allocator, end(), std::move(*(end() - 1))); + std::ranges::move_backward(insert_position, end() - 1, end()); + *insert_position = std::move(value_copy); + } + else + { + auto insert_position = begin() + prefix_size; + std::allocator_traits::construct(m_allocator, end(), std::move(*(end() - 1))); + std::ranges::move_backward(insert_position, end() - 1, end()); + *insert_position = value; + } + + ++m_size; + return begin() + prefix_size; + } + + //! Insert an element at a given position. + //! + //! @param position The position to insert the element at. + //! @param value The value to insert. + //! @return An iterator to the inserted element. + constexpr auto insert(const_iterator position, value_type && value) -> iterator + { + auto prefix_size = std::ranges::distance(begin(), position); + auto suffix_size = std::ranges::distance(position, end()); + + if (position == end()) + { + push_back(std::move(value)); + return begin() + prefix_size; + } + + if (m_capacity == m_size) + { + auto new_capacity = m_capacity == 0 ? 1 : m_capacity * 2; + auto new_data = allocate_n(new_capacity); + auto old_size = size(); + std::allocator_traits::construct(m_allocator, new_data + prefix_size, std::move(value)); + uninitialized_move_with_allocator(begin(), new_data, prefix_size); + uninitialized_move_with_allocator(begin() + prefix_size, new_data + prefix_size + 1, suffix_size); + destroy_n(begin(), old_size); + deallocate(); + m_data = new_data; + m_capacity = new_capacity; + m_size = old_size; + } + else if (&value >= begin() && &value < end()) + { + auto value_copy = std::move(value); + auto insert_position = begin() + prefix_size; + std::allocator_traits::construct(m_allocator, end(), std::move(*(end() - 1))); + std::ranges::move_backward(insert_position, end() - 1, end()); + *insert_position = std::move(value_copy); + } + else + { + auto insert_position = begin() + prefix_size; + std::allocator_traits::construct(m_allocator, end(), std::move(*(end() - 1))); + std::ranges::move_backward(insert_position, end() - 1, end()); + *insert_position = std::move(value); + } + + ++m_size; + return begin() + prefix_size; + } + //! Append a given element to this vector via copy construction. constexpr auto push_back(value_type const & value) -> void { @@ -690,19 +790,6 @@ namespace kstd deallocate(); } - //! Copy a number of elements from one storage location to another. - //! - //! @param from The start of the source range. - //! @param to The start of the target range. - //! @param count The number of element to copy. - constexpr auto static copy_elements(const_iterator from, iterator to, size_type count) -> void - { - for (auto i = 0uz; i < count; ++i) - { - *to++ = *from++; - } - } - //! Release the memory of this vector. constexpr auto deallocate() { @@ -726,19 +813,6 @@ namespace kstd }); } - //! Move a number of elements from one storage location to another. - //! - //! @param from The start of the source range. - //! @param to The start of the target range. - //! @param count The number of element to copy. - constexpr auto static move_elements(iterator from, iterator to, size_t count) - { - for (auto i = 0uz; i < count; ++i) - { - *to++ = std::move(*from++); - } - } - //! Panic the kernel if the given index is out of bounds. //! //! @param index The index to check. -- cgit v1.2.3