aboutsummaryrefslogtreecommitdiff
path: root/libs
diff options
context:
space:
mode:
Diffstat (limited to 'libs')
-rw-r--r--libs/kstd/kstd/vector257
1 files changed, 91 insertions, 166 deletions
diff --git a/libs/kstd/kstd/vector b/libs/kstd/kstd/vector
index c714957..736b854 100644
--- a/libs/kstd/kstd/vector
+++ b/libs/kstd/kstd/vector
@@ -551,13 +551,7 @@ namespace kstd
kstd::os::panic("[kstd:vector] Tried to reserve more space than theoretically possible.");
}
- auto new_data = allocate_n(new_capacity);
- auto old_size = size();
- uninitialized_move_with_allocator(begin(), new_data, size());
- clear_and_deallocate();
- m_data = new_data;
- m_capacity = new_capacity;
- m_size = old_size;
+ reallocate_exactly(new_capacity);
}
//! Resize this vector to contain @p new_size elements.
@@ -613,13 +607,7 @@ namespace kstd
return;
}
- auto new_data = allocate_n(m_size);
- auto old_size = size();
- uninitialized_move_with_allocator(begin(), new_data, old_size);
- clear_and_deallocate();
- std::exchange(m_data, new_data);
- m_capacity = old_size;
- m_size = old_size;
+ reallocate_exactly(m_size);
}
//! Clear the contents of this vector.
@@ -636,47 +624,7 @@ namespace kstd
//! @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<allocator_type>::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<allocator_type>::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<allocator_type>::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;
+ return do_insert(position, value);
}
//! Insert an element at a given position.
@@ -686,47 +634,7 @@ namespace kstd
//! @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<allocator_type>::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<allocator_type>::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<allocator_type>::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;
+ return do_insert(position, std::move(value));
}
//! Insert the element of a given range into the vector at a given position.
@@ -801,39 +709,24 @@ namespace kstd
template<typename... Args>
constexpr auto emplace(const_iterator position, Args &&... args) -> iterator
{
- auto prefix_size = std::ranges::distance(begin(), position);
- auto suffix_size = std::ranges::distance(position, end());
-
- if (position == end())
+ auto prefix_size = std::ranges::distance(cbegin(), position);
+ if (position == cend())
{
emplace_back(std::forward<Args>(args)...);
- return begin() + prefix_size;
}
-
- if (m_capacity == m_size)
+ else 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<allocator_type>::construct(m_allocator, new_data + prefix_size,
- std::forward<Args>(args)...);
- 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;
+ reallocate_and_insert(begin() + prefix_size, std::forward<Args>(args)...);
}
else
{
+ auto to_insert = value_type{std::forward<Args>(args)...};
auto insert_position = begin() + prefix_size;
- std::allocator_traits<allocator_type>::construct(m_allocator, end(), std::move(*(end() - 1)));
- std::ranges::move_backward(insert_position, end() - 1, end());
- *insert_position = value_type{std::forward<Args>(args)...};
+ shift_back(insert_position);
+ *insert_position = std::move(to_insert);
+ ++m_size;
}
- ++m_size;
return begin() + prefix_size;
}
@@ -884,47 +777,13 @@ namespace kstd
//! Append a given element to this vector via copy construction.
constexpr auto push_back(value_type const & value) -> void
{
- 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<allocator_type>::construct(m_allocator, new_data + m_size, value);
- uninitialized_move_with_allocator(begin(), new_data, size());
- destroy_n(begin(), size());
- deallocate();
- m_data = new_data;
- m_capacity = new_capacity;
- m_size = old_size;
- }
- else
- {
- std::allocator_traits<allocator_type>::construct(m_allocator, data() + size(), value);
- }
- ++m_size;
+ emplace_back(value);
}
//! Append a given element to this vector via move construction.
constexpr auto push_back(value_type && value) -> void
{
- 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<allocator_type>::construct(m_allocator, new_data + m_size, std::move(value));
- uninitialized_move_with_allocator(begin(), new_data, size());
- destroy_n(begin(), size());
- deallocate();
- m_data = new_data;
- m_capacity = new_capacity;
- m_size = old_size;
- }
- else
- {
- std::allocator_traits<allocator_type>::construct(m_allocator, data() + size(), std::move(value));
- }
- ++m_size;
+ emplace_back(std::move(value));
}
//! Append a given element to this vector via direct construction.
@@ -933,22 +792,13 @@ namespace kstd
{
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<allocator_type>::construct(m_allocator, new_data + m_size, std::forward<Args>(args)...);
- uninitialized_move_with_allocator(begin(), new_data, size());
- destroy_n(begin(), size());
- deallocate();
- m_data = new_data;
- m_capacity = new_capacity;
- m_size = old_size;
+ reallocate_and_insert(end(), std::forward<Args>(args)...);
}
else
{
std::allocator_traits<allocator_type>::construct(m_allocator, data() + size(), std::forward<Args>(args)...);
+ ++m_size;
}
- ++m_size;
return this->back();
}
@@ -1055,6 +905,38 @@ namespace kstd
}
}
+ //! Insert an element into this vector at the given position.
+ //!
+ //! @param position The position to insert the element at.
+ //! @param value The value to insert.
+ template<typename U>
+ constexpr auto do_insert(const_iterator position, U && value)
+ {
+ auto prefix_size = std::ranges::distance(cbegin(), position);
+ if (position == cend())
+ {
+ push_back(std::forward<U>(value));
+ }
+ else if (m_capacity == m_size)
+ {
+ reallocate_and_insert(begin() + prefix_size, std::forward<U>(value));
+ }
+ else if (&value >= cbegin() && &value < cend())
+ {
+ auto temporary = std::forward<U>(value);
+ shift_back(begin() + prefix_size);
+ *(begin() + prefix_size) = std::move(temporary);
+ ++m_size;
+ }
+ else
+ {
+ shift_back(begin() + prefix_size);
+ *(begin() + prefix_size) = std::forward<U>(value);
+ ++m_size;
+ }
+ return begin() + prefix_size;
+ }
+
//! Destroy a number of elements in this vector.
//!
//! @param first The start of the range of the elements to be destroyed.
@@ -1105,6 +987,49 @@ namespace kstd
}
}
+ //! Reallocate the storage space to be exactly as large as the given size.
+ constexpr auto reallocate_exactly(size_type new_capacity) -> void
+ {
+ auto new_data = allocate_n(new_capacity);
+ auto old_size = size();
+ uninitialized_move_with_allocator(begin(), new_data, old_size);
+ clear_and_deallocate();
+ m_data = new_data;
+ m_capacity = new_capacity;
+ m_size = old_size;
+ }
+
+ //! Shift all elements, starting the given position, one position back inside the vector.
+ constexpr auto shift_back(iterator starting_at)
+ {
+ std::allocator_traits<allocator_type>::construct(m_allocator, end(), std::move(*(end() - 1)));
+ std::ranges::move_backward(starting_at, end() - 1, end());
+ }
+
+ //! Reallocate the storage of this vector and insert an element at the given position.
+ //!
+ //! @param position The position to insert the element at.
+ //! @param args The constructor arguments for the inserted element.
+ template<typename... Args>
+ constexpr auto reallocate_and_insert(iterator position, Args &&... args)
+ {
+ auto prefix_size = std::ranges::distance(begin(), position);
+ auto suffix_size = std::ranges::distance(position, end());
+ auto new_capacity = m_capacity == 0 ? 1 : m_capacity * 2;
+ auto new_data = allocate_n(new_capacity);
+ auto old_size = size();
+
+ std::allocator_traits<allocator_type>::construct(m_allocator, new_data + prefix_size,
+ std::forward<Args>(args)...);
+ 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 + 1;
+ }
+
//! The allocator used by this vector.
[[no_unique_address]] allocator_type m_allocator{};
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-20 10:11:11 +0000