diff options
Diffstat (limited to 'libs')
| -rw-r--r-- | libs/kstd/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | libs/kstd/include/kstd/bits/flat_map.hpp | 82 | ||||
| -rw-r--r-- | libs/kstd/include/kstd/flat_map | 320 | ||||
| -rw-r--r-- | libs/kstd/include/kstd/vector | 45 | ||||
| -rw-r--r-- | libs/kstd/tests/src/flat_map.cpp | 288 | ||||
| -rw-r--r-- | libs/kstd/tests/src/vector.cpp | 223 |
6 files changed, 958 insertions, 1 deletions
diff --git a/libs/kstd/CMakeLists.txt b/libs/kstd/CMakeLists.txt index d4f415f..7169aa8 100644 --- a/libs/kstd/CMakeLists.txt +++ b/libs/kstd/CMakeLists.txt @@ -44,6 +44,7 @@ endif() if(NOT CMAKE_CROSSCOMPILING) add_executable("kstd_tests" + "tests/src/flat_map.cpp" "tests/src/vector.cpp" "tests/src/os_panic.cpp" "tests/src/string.cpp" diff --git a/libs/kstd/include/kstd/bits/flat_map.hpp b/libs/kstd/include/kstd/bits/flat_map.hpp new file mode 100644 index 0000000..903841e --- /dev/null +++ b/libs/kstd/include/kstd/bits/flat_map.hpp @@ -0,0 +1,82 @@ +#ifndef KSTD_BITS_FLAT_MAP_HPP +#define KSTD_BITS_FLAT_MAP_HPP + +#include <cstddef> +#include <iterator> +#include <utility> + +namespace kstd::bits +{ + + template<typename KeyType, typename MappedType, typename KeyIterator, typename MappedIterator> + struct flat_map_iterator + { + using iterator_category = std::random_access_iterator_tag; + using value_type = std::pair<KeyType, MappedType>; + using difference_type = std::ptrdiff_t; + using reference = std::pair<KeyType const &, MappedType &>; + using pointer = void; + + constexpr flat_map_iterator(KeyIterator key_iterator, MappedIterator mapped_iterator) + : m_key_iterator{key_iterator} + , m_mapped_iterator{mapped_iterator} + {} + + [[nodiscard]] auto key_iterator() const noexcept -> KeyIterator + { + return m_key_iterator; + } + + [[nodiscard]] constexpr auto operator*() const noexcept -> reference + { + return {*m_key_iterator, *m_mapped_iterator}; + } + + constexpr auto operator++() noexcept -> flat_map_iterator & + { + ++m_key_iterator; + ++m_mapped_iterator; + return *this; + } + + constexpr auto operator++(int) noexcept -> flat_map_iterator + { + auto copy = *this; + ++(*this); + return copy; + } + + constexpr auto operator--() noexcept -> flat_map_iterator & + { + --m_key_iterator; + --m_mapped_iterator; + return *this; + } + + constexpr auto operator--(int) noexcept -> flat_map_iterator + { + auto copy = *this; + --(*this); + return copy; + } + + [[nodiscard]] constexpr auto operator+(difference_type offset) const noexcept -> flat_map_iterator + { + return {m_key_iterator + offset, m_mapped_iterator + offset}; + } + + [[nodiscard]] constexpr auto operator-(flat_map_iterator const & other) const noexcept -> difference_type + { + return m_key_iterator - other.m_key_iterator; + } + + [[nodiscard]] constexpr auto operator<=>(flat_map_iterator const & other) const noexcept = default; + + private: + KeyIterator m_key_iterator{}; + MappedIterator m_mapped_iterator{}; + }; + +} // namespace kstd::bits + +#endif
\ No newline at end of file diff --git a/libs/kstd/include/kstd/flat_map b/libs/kstd/include/kstd/flat_map new file mode 100644 index 0000000..6ffbbcf --- /dev/null +++ b/libs/kstd/include/kstd/flat_map @@ -0,0 +1,320 @@ +#ifndef KSTD_FLAT_MAP_HPP +#define KSTD_FLAT_MAP_HPP + +#include <kstd/bits/flat_map.hpp> +#include <kstd/os/error.hpp> +#include <kstd/vector> + +#include <algorithm> +#include <concepts> +#include <cstddef> +#include <functional> +#include <iterator> +#include <utility> + +namespace kstd +{ + + template<typename KeyType, typename MappedType, typename KeyCompare = std::less<KeyType>, + typename KeyContainerType = kstd::vector<KeyType>, typename MappedContainerType = kstd::vector<MappedType>> + struct flat_map + { + using key_container_type = KeyContainerType; + using mapped_container_type = MappedContainerType; + using key_type = KeyType; + using mapped_type = MappedType; + using value_type = std::pair<key_type, mapped_type>; + using key_compare = KeyCompare; + using reference = std::pair<key_type const &, mapped_type &>; + using const_reference = std::pair<key_type const &, mapped_type const &>; + using size_type = std::size_t; + using difference_type = std::ptrdiff_t; + using iterator = bits::flat_map_iterator<KeyType, MappedType, typename key_container_type::iterator, + typename mapped_container_type::iterator>; + using const_iterator = + bits::flat_map_iterator<KeyType, MappedType const, typename key_container_type::const_iterator, + typename mapped_container_type::const_iterator>; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + using containers = struct + { + key_container_type keys; + mapped_container_type values; + }; + + //! Compare two object of type value_type. + struct value_compare + { + constexpr auto operator()(const_reference lhs, const_reference rhs) const -> bool + { + return lhs.first < rhs.first; + } + }; + + //! Construct an empty flat map. + constexpr flat_map() + : flat_map{key_compare{}} + {} + + //! Construct an empty flat map using the given custom comparator. + //! + //! @param comparator The comparator to use for comparing keys. + constexpr explicit flat_map(key_compare const & comparator) + : m_containers{} + , m_comparator{comparator} + {} + + //! Get a reference to the mapped value associated with the given key. + //! + //! @warning This function will panic if the key is not found. + //! @param key The key to look up. + //! @return A reference to the mapped value. + [[nodiscard]] constexpr auto at(key_type const & key) -> mapped_type & + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return *(m_containers.values.begin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get a reference to the mapped value associated with the given key. + //! + //! @warning This function will panic if the key is not found. + //! @param key The key to look up. + //! @return A const reference to the mapped value. + [[nodiscard]] constexpr auto at(key_type const & key) const -> mapped_type const & + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.cbegin(), found); + return *(m_containers.values.cbegin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get a reference to the mapped value associated with the given key. + //! + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @warning This function will panic if the key is not found. + //! @param x The key to look up. + //! @return A reference to the mapped value. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] constexpr auto at(K const & x) -> mapped_type & + { + auto found = find(x); + if (found != end()) + { + auto offset = std::distance(m_containers.keys.begin(), found.key_iterator()); + return *(m_containers.values.begin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get a reference to the mapped value associated with the given key. + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @warning This function will panic if the key is not found. + //! @param x The key to look up. + //! @return A const reference to the mapped value. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] auto at(K const & x) const -> mapped_type const & + { + auto found = find(x); + if (found != end()) + { + auto offset = std::distance(m_containers.keys.cbegin(), found.key_iterator()); + return *(m_containers.values.cbegin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get an iterator to the first element. + [[nodiscard]] auto begin() noexcept -> iterator + { + return iterator{m_containers.keys.begin(), m_containers.values.begin()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto begin() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cbegin(), m_containers.values.cbegin()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto cbegin() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cbegin(), m_containers.values.cbegin()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto end() noexcept -> iterator + { + return iterator{m_containers.keys.end(), m_containers.values.end()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto end() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cend(), m_containers.values.cend()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto cend() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cend(), m_containers.values.cend()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto rbegin() noexcept -> reverse_iterator + { + return reverse_iterator{end()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto rbegin() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cend()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto crbegin() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cend()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto rend() noexcept -> reverse_iterator + { + return reverse_iterator{begin()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto rend() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cbegin()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto crend() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cbegin()}; + } + + //! Try to insert a new key-value pair into the map. + //! + //! @param args Arguments to use for constructing the key-value pair. + //! @return A pair of an iterator to the inserted element and a boolean indicating whether the insertion took place. + template<typename... Args> + auto emplace(Args &&... args) -> std::pair<iterator, bool> + requires std::constructible_from<value_type, Args...> + { + auto value = value_type{std::forward<Args>(args)...}; + auto found = std::ranges::lower_bound(m_containers.keys, value.first, m_comparator); + + if (found != m_containers.keys.cend() && !m_comparator(value.first, *found) && !m_comparator(*found, value.first)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return { + iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset}, + false + }; + } + + auto offset = std::distance(m_containers.keys.begin(), found); + auto key_iterator = m_containers.keys.begin() + offset; + auto mapped_iterator = m_containers.values.begin() + offset; + + auto inserted_key = m_containers.keys.insert(key_iterator, std::move(value.first)); + auto inserted_mapped = m_containers.values.insert(mapped_iterator, std::move(value.second)); + + return { + iterator{inserted_key, inserted_mapped}, + true + }; + } + + //! Find an element with an equivalent key. + //! + //! @param key The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + [[nodiscard]] auto find(key_type const & key) noexcept -> iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset}; + } + return end(); + } + + //! Find an element with an equivalent key. + //! + //! @param key The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + [[nodiscard]] auto find(key_type const & key) const noexcept -> const_iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.cbegin(), found); + return const_iterator{m_containers.keys.cbegin() + offset, m_containers.values.cbegin() + offset}; + } + return cend(); + } + + //! Find an element with an equivalent key. + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @param x The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] auto find(K const & x) noexcept -> iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, x, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(x, *found) && !m_comparator(*found, x)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset}; + } + return end(); + } + + //! Find an element with an equivalent key. + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @param x The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] auto find(K const & x) const noexcept -> const_iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, x, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(x, *found) && !m_comparator(*found, x)) + { + auto offset = std::distance(m_containers.keys.cbegin(), found); + return const_iterator{m_containers.keys.cbegin() + offset, m_containers.values.cbegin() + offset}; + } + return cend(); + } + + //! Check if the map contains the given key. + //! + //! @param key The key to check. + //! @return true iff. the key is found, false otherwise. + [[nodiscard]] constexpr auto contains(key_type const & key) const noexcept -> bool + { + return find(key) != cend(); + } + + private: + containers m_containers; + key_compare m_comparator; + }; +} // namespace kstd + +#endif
\ No newline at end of file diff --git a/libs/kstd/include/kstd/vector b/libs/kstd/include/kstd/vector index 0d4aac8..9e41cb6 100644 --- a/libs/kstd/include/kstd/vector +++ b/libs/kstd/include/kstd/vector @@ -548,7 +548,6 @@ namespace kstd if (new_capacity > max_size()) { kstd::os::panic("[kstd:vector] Tried to reserve more space than theoretically possible."); - return; } auto new_data = allocate_n(new_capacity); @@ -690,6 +689,50 @@ namespace kstd return begin() + prefix_size; } + //! Erase an element at a given position. + //! + //! @note This function will panic if position == end() + //! + //! @param position An interator pointing to the element to delete + //! @return An iterator pointing to the element after the deleted element + constexpr auto erase(const_iterator position) -> iterator + { + if (position == end()) + { + os::panic("[kstd:vector] Attempted to erase end()!"); + } + + auto prefix_size = std::ranges::distance(cbegin(), position); + + std::ranges::move(begin() + prefix_size + 1, end(), begin() + prefix_size); + std::allocator_traits<allocator_type>::destroy(m_allocator, end() - 1); + --m_size; + + return begin() + prefix_size; + } + + //! Erase a range of elements from this vector. + //! + //! @param first The start of the range to erase. + //! @param last The end of the range to erase. + //! @return An iterator pointing to the element after the last deleted element. + constexpr auto erase(const_iterator first, const_iterator last) -> iterator + { + if (first == last) + { + return begin() + std::ranges::distance(cbegin(), first); + } + + auto prefix_size = std::ranges::distance(cbegin(), first); + auto element_count = std::ranges::distance(first, last); + + std::ranges::move(begin() + prefix_size + element_count, end(), begin() + prefix_size); + destroy_n(end() - element_count, element_count); + m_size -= element_count; + + return begin() + prefix_size; + } + //! Append a given element to this vector via copy construction. constexpr auto push_back(value_type const & value) -> void { diff --git a/libs/kstd/tests/src/flat_map.cpp b/libs/kstd/tests/src/flat_map.cpp new file mode 100644 index 0000000..cde136a --- /dev/null +++ b/libs/kstd/tests/src/flat_map.cpp @@ -0,0 +1,288 @@ +#include <kstd/flat_map> +#include <kstd/tests/os_panic.hpp> + +#include <catch2/catch_test_macros.hpp> + +#include <functional> + +SCENARIO("Flat Map initialization and construction", "[flat_map]") +{ + GIVEN("An empty context") + { + WHEN("constructing by default") + { + auto map = kstd::flat_map<int, int>{}; + + THEN("the Flat Map does not contain elements") + { + REQUIRE_FALSE(map.contains(1)); + } + } + } +} + +SCENARIO("Flat Map modifiers", "[flat_map]") +{ + GIVEN("An empty Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + + WHEN("emplacing a new element") + { + auto [it, inserted] = map.emplace(1, 100); + + THEN("the map contains the new element") + { + REQUIRE(inserted); + REQUIRE(map.contains(1)); + } + } + + WHEN("emplacing an existing element") + { + map.emplace(1, 100); + auto [it, inserted] = map.emplace(1, 200); + + THEN("the map does not insert the duplicate") + { + REQUIRE_FALSE(inserted); + REQUIRE(map.contains(1)); + } + } + } +} + +SCENARIO("Flat Map element access", "[flat_map]") +{ + GIVEN("A populated Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + map.emplace(1, 10); + map.emplace(2, 20); + map.emplace(3, 30); + + WHEN("accessing an existing element with at()") + { + auto & val = map.at(2); + + THEN("it returns a reference to the mapped value") + { + REQUIRE(val == 20); + } + + THEN("the mapped value can be modified") + { + val = 200; + REQUIRE(map.at(2) == 200); + } + } + + WHEN("accessing a non-existent element with at()") + { + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(4), kstd::tests::os_panic); + } + } + } + + GIVEN("A const populated Flat Map") + { + auto map_builder = kstd::flat_map<int, int>{}; + map_builder.emplace(1, 10); + map_builder.emplace(2, 20); + auto const map = map_builder; + + WHEN("accessing an existing element with const at()") + { + auto const & val = map.at(2); + + THEN("it returns a const reference to the mapped value") + { + REQUIRE(val == 20); + } + } + + WHEN("accessing a non-existent element with const at()") + { + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(4), kstd::tests::os_panic); + } + } + } +} + +SCENARIO("Flat Map iterators", "[flat_map]") +{ + GIVEN("A populated Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + map.emplace(1, 10); + map.emplace(2, 20); + map.emplace(3, 30); + + WHEN("using forward iterators") + { + THEN("they navigate the elements in the correct forward order") + { + auto it = map.begin(); + REQUIRE(it != map.end()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it != map.end()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.end()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it == map.end()); + } + + THEN("const forward iterators provide correct access") + { + auto it = map.cbegin(); + REQUIRE(it != map.cend()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it != map.cend()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.cend()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it == map.cend()); + } + } + + WHEN("using reverse iterators") + { + THEN("they navigate the elements in the correct reverse order") + { + auto it = map.rbegin(); + REQUIRE(it != map.rend()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it != map.rend()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.rend()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it == map.rend()); + } + + THEN("const reverse iterators provide correct access") + { + auto it = map.crbegin(); + REQUIRE(it != map.crend()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it != map.crend()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.crend()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it == map.crend()); + } + } + } + + GIVEN("an empty Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + + WHEN("getting iterators") + { + THEN("begin() equals end() and cbegin() equals cend()") + { + REQUIRE(map.begin() == map.end()); + REQUIRE(map.cbegin() == map.cend()); + } + + THEN("rbegin() equals rend() and crbegin() equals crend()") + { + REQUIRE(map.rbegin() == map.rend()); + REQUIRE(map.crbegin() == map.crend()); + } + } + } +} + +SCENARIO("Flat Map heterogeneous element access", "[flat_map]") +{ + GIVEN("A populated Flat Map with a transparent comparator") + { + auto map = kstd::flat_map<int, int, std::less<void>>{}; + map.emplace(1, 10); + map.emplace(2, 20); + map.emplace(3, 30); + + WHEN("accessing an existing element with a different key type via at()") + { + long const key = 2L; + auto & val = map.at(key); + + THEN("it returns a reference to the mapped value") + { + REQUIRE(val == 20); + } + + THEN("the mapped value can be modified") + { + val = 200; + REQUIRE(map.at(2L) == 200); + } + } + + WHEN("accessing a non-existent element with a different key type via at()") + { + long const key = 4L; + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(key), kstd::tests::os_panic); + } + } + } + + GIVEN("A const populated Flat Map with a transparent comparator") + { + auto map_builder = kstd::flat_map<int, int, std::less<void>>{}; + map_builder.emplace(1, 10); + map_builder.emplace(2, 20); + auto const map = map_builder; + + WHEN("accessing an existing element with a different key type via const at()") + { + long const key = 2L; + auto const & val = map.at(key); + + THEN("it returns a const reference to the mapped value") + { + REQUIRE(val == 20); + } + } + + WHEN("accessing a non-existent element with a different key type via const at()") + { + long const key = 4L; + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(key), kstd::tests::os_panic); + } + } + } +} diff --git a/libs/kstd/tests/src/vector.cpp b/libs/kstd/tests/src/vector.cpp index 0735c9a..b7971f4 100644 --- a/libs/kstd/tests/src/vector.cpp +++ b/libs/kstd/tests/src/vector.cpp @@ -475,6 +475,20 @@ SCENARIO("Vector modifiers", "[vector]") REQUIRE(it == v.begin()); } } + + WHEN("inserting an lvalue element") + { + auto const value = 42; + auto it = v.insert(v.cbegin(), value); + + THEN("the size and capacity increase and the element is inserted") + { + REQUIRE(v.size() == 1); + REQUIRE(v.capacity() >= 1); + REQUIRE(v[0] == 42); + REQUIRE(it == v.begin()); + } + } } GIVEN("A populated vector") @@ -597,6 +611,22 @@ SCENARIO("Vector modifiers", "[vector]") } } + WHEN("inserting an lvalue at the end") + { + auto const value = 40; + auto it = v.insert(v.cend(), value); + + THEN("the element is inserted at the back") + { + REQUIRE(v.size() == 4); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 20); + REQUIRE(v[2] == 30); + REQUIRE(v[3] == 40); + REQUIRE(it == v.begin() + 3); + } + } + WHEN("inserting when capacity is sufficient") { v.reserve(10); @@ -649,6 +679,114 @@ SCENARIO("Vector modifiers", "[vector]") REQUIRE(it == v.begin() + 1); } } + + WHEN("inserting an rvalue reference to an existing element with reallocation") + { + v.shrink_to_fit(); + REQUIRE(v.capacity() == v.size()); + auto it = v.insert(v.cbegin() + 1, std::move(v[2])); + + THEN("the element is correctly moved and inserted") + { + REQUIRE(v.size() == 4); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 30); + REQUIRE(v[2] == 20); + REQUIRE(v[3] == 30); + REQUIRE(it == v.begin() + 1); + } + } + + WHEN("inserting an rvalue reference to an existing element without reallocation") + { + v.reserve(10); + REQUIRE(v.capacity() > v.size()); + auto it = v.insert(v.cbegin() + 1, std::move(v[2])); + + THEN("the element is correctly moved and inserted") + { + REQUIRE(v.size() == 4); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 30); + REQUIRE(v[2] == 20); + REQUIRE(v[3] == 30); + REQUIRE(it == v.begin() + 1); + } + } + + WHEN("erasing the first element") + { + auto it = v.erase(v.cbegin()); + + THEN("the first element is removed and the size decreases") + { + REQUIRE(v.size() == 2); + REQUIRE(v[0] == 20); + REQUIRE(v[1] == 30); + REQUIRE(it == v.begin()); + } + } + + WHEN("erasing a middle element") + { + auto it = v.erase(v.cbegin() + 1); + + THEN("the middle element is removed and the size decreases") + { + REQUIRE(v.size() == 2); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 30); + REQUIRE(it == v.begin() + 1); + } + } + + WHEN("erasing the last element") + { + auto it = v.erase(v.cend() - 1); + + THEN("the last element is removed and the size decreases") + { + REQUIRE(v.size() == 2); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 20); + REQUIRE(it == v.end()); + } + } + + WHEN("erasing the end() iterator") + { + THEN("a panic is triggered") + { + REQUIRE_THROWS_AS(v.erase(v.end()), kstd::tests::os_panic); + } + } + + WHEN("erasing a range of elements") + { + auto it = v.erase(v.cbegin() + 1, v.cend() - 1); + + THEN("the specified range is removed and the size decreases") + { + REQUIRE(v.size() == 2); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 30); + REQUIRE(it == v.begin() + 1); + } + } + + WHEN("erasing an empty range") + { + auto it = v.erase(v.cbegin() + 1, v.cbegin() + 1); + + THEN("the vector is unchanged") + { + REQUIRE(v.size() == 3); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 20); + REQUIRE(v[2] == 30); + REQUIRE(it == v.begin() + 1); + } + } } } @@ -868,6 +1006,91 @@ SCENARIO("Vector modifier move semantics", "[vector]") REQUIRE(v[3].was_moved); } } + + WHEN("erasing an element in the middle") + { + for (auto & elem : v) + { + elem.was_copied = false; + elem.was_moved = false; + } + + auto it = v.erase(v.cbegin() + 1); + + THEN("the subsequent elements are move-assigned leftwards") + { + REQUIRE(v.size() == 2); + + REQUIRE(v[0].value == 10); + REQUIRE_FALSE(v[0].was_moved); + REQUIRE_FALSE(v[0].was_copied); + + REQUIRE(v[1].value == 30); + REQUIRE(v[1].was_moved); + REQUIRE_FALSE(v[1].was_copied); + + REQUIRE(it == v.begin() + 1); + } + } + + WHEN("erasing the last element") + { + for (auto & elem : v) + { + elem.was_copied = false; + elem.was_moved = false; + } + + auto it = v.erase(v.cend() - 1); + + THEN("no elements are moved, just the last element destroyed") + { + REQUIRE(v.size() == 2); + + REQUIRE(v[0].value == 10); + REQUIRE_FALSE(v[0].was_moved); + REQUIRE_FALSE(v[0].was_copied); + + REQUIRE(v[1].value == 20); + REQUIRE_FALSE(v[1].was_moved); + REQUIRE_FALSE(v[1].was_copied); + + REQUIRE(it == v.end()); + } + } + + WHEN("erasing a range of elements in the middle") + { + v.emplace_back(40); + v.emplace_back(50); + + for (auto & elem : v) + { + elem.was_copied = false; + elem.was_moved = false; + } + + auto it = v.erase(v.cbegin() + 1, v.cbegin() + 3); + + THEN("the specified elements are destroyed and subsequent elements are move-assigned leftwards") + { + REQUIRE(v.size() == 3); + + REQUIRE(v[0].value == 10); + REQUIRE_FALSE(v[0].was_moved); + REQUIRE_FALSE(v[0].was_copied); + + REQUIRE(v[1].value == 40); + REQUIRE(v[1].was_moved); + REQUIRE_FALSE(v[1].was_copied); + + REQUIRE(v[2].value == 50); + REQUIRE(v[2].was_moved); + REQUIRE_FALSE(v[2].was_copied); + + REQUIRE(it == v.begin() + 1); + } + } } } |