aboutsummaryrefslogtreecommitdiff
path: root/libs
diff options
context:
space:
mode:
Diffstat (limited to 'libs')
-rw-r--r--libs/kstd/include/kstd/vector7
-rw-r--r--libs/kstd/tests/src/vector.cpp511
2 files changed, 488 insertions, 30 deletions
diff --git a/libs/kstd/include/kstd/vector b/libs/kstd/include/kstd/vector
index 1242489..5655854 100644
--- a/libs/kstd/include/kstd/vector
+++ b/libs/kstd/include/kstd/vector
@@ -60,6 +60,9 @@ namespace kstd
explicit constexpr vector(allocator_type const & allocator) noexcept(
std::is_nothrow_copy_constructible_v<allocator_type>)
: m_allocator{allocator}
+ , m_size{0}
+ , m_capacity{0}
+ , m_data{allocate_n(m_capacity)}
{}
//! Construct a new vector and fill it with the given number of default constructed elements.
@@ -237,7 +240,7 @@ namespace kstd
//! Replace the contents of this vector by the copying from the given source vector.
//!
//! @param other The source vector.
- constexpr auto operator=(vector const & other) -> vector<value_type> &
+ constexpr auto operator=(vector const & other) -> vector &
{
if (this == std::addressof(other))
{
@@ -285,7 +288,7 @@ namespace kstd
//! @param other The source vector.
constexpr auto operator=(vector && other) noexcept(
std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value ||
- std::allocator_traits<allocator_type>::is_always_equal::value) -> vector<value_type> &
+ std::allocator_traits<allocator_type>::is_always_equal::value) -> vector &
{
using std::swap;
diff --git a/libs/kstd/tests/src/vector.cpp b/libs/kstd/tests/src/vector.cpp
index 1427ce8..713f6ab 100644
--- a/libs/kstd/tests/src/vector.cpp
+++ b/libs/kstd/tests/src/vector.cpp
@@ -7,6 +7,7 @@
#include <array>
#include <cstddef>
+#include <iterator>
#include <ranges>
#include <utility>
@@ -16,7 +17,7 @@ SCENARIO("Vector initialization and construction", "[vector]")
{
WHEN("constructing by default")
{
- kstd::vector<int> v;
+ auto v = kstd::vector<int>{};
THEN("the vector is empty")
{
@@ -32,7 +33,7 @@ SCENARIO("Vector initialization and construction", "[vector]")
WHEN("constructing with a specific size")
{
- kstd::vector<int> v(10);
+ auto v = kstd::vector<int>(10);
THEN("the vector is not empty")
{
@@ -48,7 +49,7 @@ SCENARIO("Vector initialization and construction", "[vector]")
WHEN("constructing from an initializer list")
{
- kstd::vector<int> v = {1, 2, 3, 4, 5};
+ auto v = kstd::vector<int>{1, 2, 3, 4, 5};
THEN("the vector is not empty")
{
@@ -125,11 +126,11 @@ SCENARIO("Vector initialization and construction", "[vector]")
GIVEN("A populated vector")
{
- kstd::vector<int> source = {1, 2, 3, 4, 5};
+ auto source = kstd::vector<int>{1, 2, 3, 4, 5};
WHEN("copy constructing a new vector")
{
- kstd::vector<int> copy(source);
+ auto copy = kstd::vector<int>(source);
THEN("the copy matches the original")
{
@@ -156,7 +157,7 @@ SCENARIO("Vector initialization and construction", "[vector]")
WHEN("move constructing a new vector")
{
- kstd::vector<int> moved(std::move(source));
+ auto moved = kstd::vector<int>(std::move(source));
THEN("The new vector has the original elements")
{
@@ -183,7 +184,7 @@ SCENARIO("Vector element access", "[vector]")
{
GIVEN("A populated vector")
{
- kstd::vector<int> v = {10, 20, 30};
+ auto v = kstd::vector<int>{10, 20, 30};
WHEN("accessing elements for reading")
{
@@ -239,7 +240,7 @@ SCENARIO("Vector iterators", "[vector]")
{
GIVEN("A populated vector")
{
- kstd::vector<int> v = {1, 2, 3};
+ auto v = kstd::vector<int>{1, 2, 3};
WHEN("using forward iterators")
{
@@ -322,7 +323,7 @@ SCENARIO("Vector iterators", "[vector]")
GIVEN("an empty vector")
{
- kstd::vector<int> v;
+ auto v = kstd::vector<int>{};
WHEN("getting iterators")
{
@@ -345,7 +346,7 @@ SCENARIO("Vector capacity management", "[vector]")
{
GIVEN("An empty vector")
{
- kstd::vector<int> v;
+ auto v = kstd::vector<int>{};
WHEN("reserving space")
{
@@ -366,11 +367,31 @@ SCENARIO("Vector capacity management", "[vector]")
REQUIRE(v.empty());
}
}
+
+ WHEN("reserving space less than or equal to current capacity")
+ {
+ v.reserve(10);
+ auto const current_capacity = v.capacity();
+ v.reserve(5);
+
+ THEN("the capacity remains unchanged")
+ {
+ REQUIRE(v.capacity() == current_capacity);
+ }
+ }
+
+ WHEN("reserving space greater than max_size")
+ {
+ THEN("a panic is triggered")
+ {
+ REQUIRE_THROWS_AS(v.reserve(v.max_size() + 1), kstd::tests::os_panic);
+ }
+ }
}
GIVEN("A populated vector with excess capacity")
{
- kstd::vector<int> v{1, 2, 3};
+ auto v = kstd::vector<int>{1, 2, 3};
v.reserve(10);
REQUIRE(v.capacity() == 10);
@@ -399,7 +420,7 @@ SCENARIO("Vector modifiers", "[vector]")
{
GIVEN("An empty vector")
{
- kstd::vector<int> v;
+ auto v = kstd::vector<int>{};
WHEN("push_back is called with a value")
{
@@ -424,11 +445,28 @@ SCENARIO("Vector modifiers", "[vector]")
REQUIRE(v.back() == 20);
}
}
+
+ WHEN("elements are added while capacity is sufficient")
+ {
+ v.reserve(10);
+ auto const capacity = v.capacity();
+
+ v.push_back(10);
+ v.emplace_back(20);
+
+ THEN("the elements are added without reallocation")
+ {
+ REQUIRE(v.size() == 2);
+ REQUIRE(v.capacity() == capacity);
+ REQUIRE(v[0] == 10);
+ REQUIRE(v[1] == 20);
+ }
+ }
}
GIVEN("A populated vector")
{
- kstd::vector<int> v = {10, 20, 30};
+ auto v = kstd::vector<int>{10, 20, 30};
auto initial_capacity = v.capacity();
WHEN("push_back is called")
@@ -461,6 +499,21 @@ SCENARIO("Vector modifiers", "[vector]")
}
}
+ WHEN("push_back is called with a reference to an internal element")
+ {
+ v.shrink_to_fit();
+ auto const original_value = v[0];
+
+ v.push_back(v[0]);
+
+ THEN("reallocation handles the internal reference safely without dangling")
+ {
+ REQUIRE(v.size() == 4);
+ REQUIRE(v[0] == original_value);
+ REQUIRE(v.back() == original_value);
+ }
+ }
+
WHEN("pop_back is called")
{
v.pop_back();
@@ -492,8 +545,8 @@ SCENARIO("Vector comparison", "[vector]")
{
GIVEN("Two identical vectors")
{
- kstd::vector<int> v1 = {1, 2, 3};
- kstd::vector<int> v2 = {1, 2, 3};
+ auto v1 = kstd::vector<int>{1, 2, 3};
+ auto v2 = kstd::vector<int>{1, 2, 3};
WHEN("comparing for equality")
{
@@ -521,8 +574,8 @@ SCENARIO("Vector comparison", "[vector]")
GIVEN("Two vectors of different sizes")
{
- kstd::vector<int> v1 = {1, 2, 3};
- kstd::vector<int> v2 = {1, 2, 3, 4};
+ auto v1 = kstd::vector<int>{1, 2, 3};
+ auto v2 = kstd::vector<int>{1, 2, 3, 4};
WHEN("comparing for equality")
{
@@ -549,8 +602,8 @@ SCENARIO("Vector comparison", "[vector]")
GIVEN("Two vectors of the same size but different elements")
{
- kstd::vector<int> v1 = {1, 2, 3};
- kstd::vector<int> v2 = {1, 2, 4};
+ auto v1 = kstd::vector<int>{1, 2, 3};
+ auto v2 = kstd::vector<int>{1, 2, 4};
WHEN("comparing for ordering")
{
@@ -580,7 +633,7 @@ SCENARIO("Vector with non-default-constructible types", "[vector]")
{
WHEN("constructing an empty vector")
{
- kstd::vector<non_default_constructible> v;
+ auto v = kstd::vector<non_default_constructible>{};
THEN("the vector is empty")
{
@@ -590,7 +643,7 @@ SCENARIO("Vector with non-default-constructible types", "[vector]")
WHEN("using emplace_back")
{
- kstd::vector<non_default_constructible> v;
+ auto v = kstd::vector<non_default_constructible>{};
v.emplace_back(42);
THEN("the element is added and the size and capacity increase")
@@ -632,10 +685,29 @@ struct tracking_allocator
::operator delete(p, n * sizeof(T));
}
- bool operator==(tracking_allocator const & other)
+ bool operator==(tracking_allocator const & other) const
{
return allocation_count == other.allocation_count;
}
+
+ bool operator!=(tracking_allocator const & other) const
+ {
+ return allocation_count != other.allocation_count;
+ }
+};
+
+template<typename T>
+struct propagating_allocator : tracking_allocator<T>
+{
+ using propagate_on_container_copy_assignment = std::true_type;
+ propagating_allocator(int * counter)
+ : tracking_allocator<T>{counter}
+ {}
+
+ template<typename U>
+ propagating_allocator(propagating_allocator<U> const & other) noexcept
+ : tracking_allocator<T>{other.allocation_count}
+ {}
};
SCENARIO("Vector with custom allocator", "[vector]")
@@ -643,11 +715,11 @@ SCENARIO("Vector with custom allocator", "[vector]")
GIVEN("a tracking allocator acting as the vector's memory manager")
{
auto allocations = 0;
- tracking_allocator<int> allocator{&allocations};
+ auto allocator = tracking_allocator<int>{&allocations};
WHEN("a vector uses this allocator to allocate memory")
{
- kstd::vector<int, tracking_allocator<int>> v{allocator};
+ auto v = kstd::vector<int, tracking_allocator<int>>(allocator);
REQUIRE(allocations == 0);
v.reserve(10);
@@ -707,8 +779,8 @@ SCENARIO("Vector modifier move semantics", "[vector]")
{
GIVEN("An empty vector and a move tracker element")
{
- kstd::vector<move_tracker> v;
- move_tracker tracker{42};
+ auto v = kstd::vector<move_tracker>{};
+ auto tracker = move_tracker{42};
WHEN("push_back is called with the move tracker")
{
@@ -731,7 +803,7 @@ SCENARIO("Vector modifier move semantics", "[vector]")
GIVEN("An empty vector")
{
- kstd::vector<move_tracker> v;
+ auto v = kstd::vector<move_tracker>{};
WHEN("emplace_back is called with constructor arguments")
{
@@ -746,4 +818,387 @@ SCENARIO("Vector modifier move semantics", "[vector]")
}
}
}
-} \ No newline at end of file
+}
+
+struct test_input_iterator
+{
+ using iterator_concept = std::input_iterator_tag;
+ using difference_type = std::ptrdiff_t;
+ using value_type = int;
+
+ int const * current;
+ int operator*() const
+ {
+ return *current;
+ }
+ test_input_iterator & operator++()
+ {
+ ++current;
+ return *this;
+ }
+ void operator++(int)
+ {
+ ++current;
+ }
+ bool operator==(test_input_iterator const & other) const
+ {
+ return current == other.current;
+ }
+};
+
+SCENARIO("Vector advanced construction", "[vector]")
+{
+ GIVEN("A count and a default value")
+ {
+ WHEN("constructing with count and default argument")
+ {
+ auto const count = 5uz;
+ auto const value = 42;
+ auto v = kstd::vector<int>(count, value);
+
+ THEN("the vector is initialized with count copies of value")
+ {
+ REQUIRE(v.size() == 5);
+ REQUIRE(v.capacity() == 5);
+ REQUIRE(v.front() == 42);
+ REQUIRE(v.back() == 42);
+ }
+ }
+ }
+
+ GIVEN("A pure input iterator range")
+ {
+ WHEN("constructing from input iterators")
+ {
+ auto const arr = std::array<int, 3>{1, 2, 3};
+ auto const first = test_input_iterator{arr.data()};
+ auto const last = test_input_iterator{arr.data() + arr.size()};
+
+ auto v = kstd::vector<int>(first, last);
+
+ THEN("the vector is generated dynamically and initialized correctly")
+ {
+ REQUIRE(v.size() == 3);
+ REQUIRE(v[0] == 1);
+ REQUIRE(v[2] == 3);
+ }
+ }
+ }
+
+ GIVEN("A tracking allocator and a source vector")
+ {
+ auto allocs = 0;
+ auto allocator = tracking_allocator<int>{&allocs};
+ auto source = kstd::vector<int, tracking_allocator<int>>{allocator};
+ source.push_back(1);
+ source.push_back(2);
+ source.push_back(3);
+
+ allocs = 0;
+
+ WHEN("copy constructing with an allocator")
+ {
+ auto copy = kstd::vector<int, tracking_allocator<int>>(source, allocator);
+
+ THEN("the copy succeeds and the allocator is used")
+ {
+ REQUIRE(copy.size() == 3);
+ REQUIRE(allocs > 0);
+ REQUIRE(copy[0] == 1);
+ REQUIRE(copy[2] == 3);
+ }
+ }
+
+ WHEN("move constructing with an identically comparing allocator")
+ {
+ auto moved = kstd::vector<int, tracking_allocator<int>>(std::move(source), allocator);
+
+ THEN("the move succeeds and no new allocations are made (memory is stolen)")
+ {
+ REQUIRE(moved.size() == 3);
+ REQUIRE(allocs == 0);
+ REQUIRE(moved[0] == 1);
+ REQUIRE(moved[2] == 3);
+ }
+ }
+
+ WHEN("move constructing with a non-equal allocator")
+ {
+ auto allocs2 = 0;
+ auto allocator2 = tracking_allocator<int>{&allocs2};
+
+ auto moved = kstd::vector<int, tracking_allocator<int>>(std::move(source), allocator2);
+
+ THEN("the move allocates new memory and moves elements")
+ {
+ REQUIRE(allocs2 > 0);
+ REQUIRE(moved.size() == 3);
+ REQUIRE(source.empty());
+ }
+ }
+ }
+}
+
+SCENARIO("Vector assignment operators", "[vector]")
+{
+ GIVEN("A source vector and an empty target vector")
+ {
+ auto source = kstd::vector<int>{1, 2, 3};
+ auto target = kstd::vector<int>{};
+
+ WHEN("copy assigning")
+ {
+ target = source;
+
+ THEN("the target matches the source")
+ {
+ REQUIRE(target.size() == 3);
+ REQUIRE(target[0] == 1);
+ REQUIRE(target[2] == 3);
+ REQUIRE(source.size() == 3);
+ }
+ }
+
+ WHEN("move assigning")
+ {
+ target = std::move(source);
+
+ THEN("the target assumes the source's data")
+ {
+ REQUIRE(target.size() == 3);
+ REQUIRE(target[0] == 1);
+ REQUIRE(target[2] == 3);
+ REQUIRE(source.empty());
+ }
+ }
+ }
+
+ GIVEN("Vectors with propagating copy allocator")
+ {
+ auto allocs1 = 0;
+ auto allocs2 = 0;
+ auto alloc1 = propagating_allocator<int>{&allocs1};
+ auto alloc2 = propagating_allocator<int>{&allocs2};
+
+ auto v1 = kstd::vector<int, propagating_allocator<int>>{alloc1};
+ v1.push_back(1);
+ v1.push_back(2);
+ auto v2 = kstd::vector<int, propagating_allocator<int>>{alloc2};
+
+ WHEN("copy assigning")
+ {
+ v2 = v1;
+ THEN("the allocator propagates")
+ {
+ REQUIRE(v2.get_allocator() == v1.get_allocator());
+ }
+ }
+ }
+
+ GIVEN("Vectors for copy assignment overlap")
+ {
+ auto v1 = kstd::vector<int>{1, 2, 3};
+ auto v2 = kstd::vector<int>{4, 5};
+ v2.reserve(10);
+
+ WHEN("copy assigning a larger vector to a smaller one with enough capacity")
+ {
+ v2 = v1;
+ THEN("elements are copied and size is updated")
+ {
+ REQUIRE(v2.size() == 3);
+ REQUIRE(v2.capacity() >= 10);
+ REQUIRE(v2[2] == 3);
+ }
+ }
+
+ auto v3 = kstd::vector<int>{1, 2, 3, 4};
+ v3.reserve(10);
+ WHEN("copy assigning a smaller vector to a larger one")
+ {
+ v3 = v1;
+ THEN("excess elements are destroyed")
+ {
+ REQUIRE(v3.size() == 3);
+ REQUIRE(v3[0] == 1);
+ }
+ }
+ }
+
+ GIVEN("Vectors with the same tracking allocator")
+ {
+ auto allocs = 0;
+ auto alloc = tracking_allocator<int>{&allocs};
+ auto v1 = kstd::vector<int, tracking_allocator<int>>{alloc};
+ v1.push_back(1);
+ auto v2 = kstd::vector<int, tracking_allocator<int>>{alloc};
+
+ WHEN("move assigning")
+ {
+ v2 = std::move(v1);
+ THEN("memory is stolen without allocation")
+ {
+ REQUIRE(v2.size() == 1);
+ REQUIRE(allocs == 1);
+ }
+ }
+ }
+
+ GIVEN("Vectors with different non-propagating tracking allocators")
+ {
+ auto allocs1 = 0;
+ auto allocs2 = 0;
+ auto alloc1 = tracking_allocator<int>{&allocs1};
+ auto alloc2 = tracking_allocator<int>{&allocs2};
+
+ auto v1 = kstd::vector<int, tracking_allocator<int>>{alloc1};
+ v1.push_back(1);
+ v1.push_back(2);
+ v1.push_back(3);
+
+ auto v2 = kstd::vector<int, tracking_allocator<int>>{alloc2};
+ v2.push_back(4);
+ v2.push_back(5);
+
+ WHEN("move assigning a larger vector to a smaller one without enough capacity")
+ {
+ v2.shrink_to_fit();
+ v2 = std::move(v1);
+ THEN("memory is reallocated and elements are moved")
+ {
+ REQUIRE(v2.size() == 3);
+ REQUIRE(allocs2 > 2);
+ }
+ }
+
+ auto v3 = kstd::vector<int, tracking_allocator<int>>{alloc2};
+ v3.reserve(10);
+ v3.push_back(4);
+ v3.push_back(5);
+ WHEN("move assigning a larger vector to a smaller one with enough capacity")
+ {
+ v3 = std::move(v1);
+ THEN("elements are move-assigned over overlap and move-constructed over remainder")
+ {
+ REQUIRE(v3.size() == 3);
+ }
+ }
+
+ auto v4 = kstd::vector<int, tracking_allocator<int>>{alloc2};
+ v4.reserve(10);
+ v4.push_back(4);
+ v4.push_back(5);
+ v4.push_back(6);
+ v4.push_back(7);
+ WHEN("move assigning a smaller vector to a larger one with enough capacity")
+ {
+ v4 = std::move(v1);
+ THEN("overlap is moved and excess is destroyed")
+ {
+ REQUIRE(v4.size() == 3);
+ }
+ }
+ }
+}
+
+SCENARIO("Vector self-assignment operators", "[vector]")
+{
+ GIVEN("A populated vector")
+ {
+ auto v = kstd::vector<int>{1, 2, 3};
+ auto const initial_capacity = v.capacity();
+ auto const * initial_data = v.data();
+
+ WHEN("copy assigning to itself")
+ {
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wpragmas"
+#pragma GCC diagnostic ignored "-Wunknown-warning-option"
+#pragma GCC diagnostic ignored "-Wself-assign-overloaded"
+ v = v;
+#pragma GCC diagnostic pop
+
+ THEN("the vector remains unchanged")
+ {
+ REQUIRE(v.size() == 3);
+ REQUIRE(v.capacity() == initial_capacity);
+ REQUIRE(v.data() == initial_data);
+ REQUIRE(v[0] == 1);
+ REQUIRE(v[2] == 3);
+ }
+ }
+
+ WHEN("move assigning to itself")
+ {
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wpragmas"
+#pragma GCC diagnostic ignored "-Wunknown-warning-option"
+#pragma GCC diagnostic ignored "-Wself-move"
+ v = std::move(v);
+#pragma GCC diagnostic pop
+
+ THEN("the vector remains unchanged")
+ {
+ REQUIRE(v.size() == 3);
+ REQUIRE(v.capacity() == initial_capacity);
+ REQUIRE(v.data() == initial_data);
+ REQUIRE(v[0] == 1);
+ REQUIRE(v[2] == 3);
+ }
+ }
+ }
+}
+
+SCENARIO("Vector const accessors and copy insertion", "[vector]")
+{
+ GIVEN("A const populated vector")
+ {
+ auto const v = kstd::vector<int>{10, 20, 30};
+
+ WHEN("calling const accessors")
+ {
+ THEN("elements are read correctly as const references")
+ {
+ REQUIRE(v.front() == 10);
+ REQUIRE(v.back() == 30);
+ REQUIRE(v[1] == 20);
+ REQUIRE(v.at(1) == 20);
+ }
+ }
+ }
+
+ GIVEN("An empty vector and a const lvalue tracker")
+ {
+ auto v = kstd::vector<move_tracker>{};
+ auto const tracker = move_tracker{42};
+
+ WHEN("push_back is called with the const lvalue")
+ {
+ v.push_back(tracker);
+
+ THEN("the element is gracefully copy-constructed")
+ {
+ REQUIRE(v.size() == 1);
+ REQUIRE(v.back().value == 42);
+ REQUIRE(v.back().was_copied);
+ REQUIRE_FALSE(v.back().was_moved);
+ }
+ }
+
+ WHEN("push_back is called with a const lvalue when capacity is sufficient")
+ {
+ v.reserve(10);
+ auto const current_capacity = v.capacity();
+ v.push_back(tracker);
+
+ THEN("the element is copy-constructed without reallocation")
+ {
+ REQUIRE(v.size() == 1);
+ REQUIRE(v.capacity() == current_capacity);
+ REQUIRE(v.back().value == 42);
+ REQUIRE(v.back().was_copied);
+ REQUIRE_FALSE(v.back().was_moved);
+ }
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-04-17 07:58:52 +0000