From 26223cf25fa38804eca224df2f0cdaea28f6e1a1 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Tue, 11 Aug 2026 14:17:51 -0400 Subject: kstd: add more flat_map ctors and move iterator implementation --- libs/kstd/kstd/bits/flat_map.hpp | 186 ------------------------ libs/kstd/kstd/flat_map.hpp | 299 +++++++++++++++++++++++++++++++++++--- libs/kstd/kstd/flat_map.tests.cpp | 86 +++++++++-- 3 files changed, 352 insertions(+), 219 deletions(-) delete mode 100644 libs/kstd/kstd/bits/flat_map.hpp (limited to 'libs/kstd') diff --git a/libs/kstd/kstd/bits/flat_map.hpp b/libs/kstd/kstd/bits/flat_map.hpp deleted file mode 100644 index fe462034..00000000 --- a/libs/kstd/kstd/bits/flat_map.hpp +++ /dev/null @@ -1,186 +0,0 @@ -#ifndef KSTD_BITS_FLAT_MAP_HPP -#define KSTD_BITS_FLAT_MAP_HPP - -#include -#include -#include -#include -#include -#include -#include - -namespace kstd::bits -{ - - template - struct flat_map_reference - { - using key_type = KeyType; - using mapped_type = MappedType; - - constexpr flat_map_reference(key_type const & key, mapped_type & mapped) - : first{key} - , second{mapped} - {} - - constexpr auto operator=(flat_map_reference const & other) const -> flat_map_reference const & - { - second = other.second; - return *this; - } - - constexpr auto operator=(flat_map_reference && other) const -> flat_map_reference const & - { - second = std::move(other.second); - return *this; - } - - template - requires(std::tuple_size_v> == 2) - constexpr auto operator=(TupleLikeType && tuple) const -> flat_map_reference const & - { - second = std::forward(tuple).second; - return *this; - } - - template - requires(Index >= 0 && Index <= 1) - [[nodiscard]] constexpr auto get() const noexcept -> decltype(auto) - { - if constexpr (Index == 0) - { - return (first); - } - else - { - return (second); - } - } - - key_type const & first; // NOLINT(cppcoreguidelines-avoid-const-or-ref-data-members) - mapped_type & second; // NOLINT(cppcoreguidelines-avoid-const-or-ref-data-members) - }; - - template - struct flat_map_pointer - { - Reference reference; - - [[nodiscard]] constexpr auto operator->() noexcept -> Reference * - { - return std::addressof(reference); - } - - [[nodiscard]] constexpr auto operator->() const noexcept -> Reference const * - { - return std::addressof(reference); - } - }; - - template - struct flat_map_iterator - { - using iterator_category = std::random_access_iterator_tag; - using value_type = std::pair; - using difference_type = std::ptrdiff_t; - using reference = flat_map_reference; - using pointer = flat_map_pointer; - - constexpr flat_map_iterator() = default; - - constexpr flat_map_iterator(KeyIterator key_iterator, MappedIterator mapped_iterator) - : m_key_iterator{key_iterator} - , m_mapped_iterator{mapped_iterator} - {} - - template - requires(std::convertible_to && - std::convertible_to) - constexpr flat_map_iterator( - flat_map_iterator const & other) noexcept - : m_key_iterator{other.m_key_iterator} - , m_mapped_iterator{other.m_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}; - } - - [[nodiscard]] constexpr auto operator->() const noexcept -> pointer - { - 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 - -template -struct std::tuple_size> : std::integral_constant -{ -}; - -template -struct std::tuple_element<0, kstd::bits::flat_map_reference> -{ - using type = K const &; -}; - -template -struct std::tuple_element<1, kstd::bits::flat_map_reference> -{ - using type = M &; -}; - -#endif \ No newline at end of file diff --git a/libs/kstd/kstd/flat_map.hpp b/libs/kstd/kstd/flat_map.hpp index 31557760..2502b7e7 100644 --- a/libs/kstd/kstd/flat_map.hpp +++ b/libs/kstd/kstd/flat_map.hpp @@ -1,7 +1,6 @@ #ifndef KSTD_FLAT_MAP_HPP #define KSTD_FLAT_MAP_HPP -#include #include #include @@ -10,6 +9,10 @@ #include #include #include +#include +#include +#include +#include #include namespace kstd @@ -19,6 +22,9 @@ namespace kstd typename KeyContainerType = kstd::vector, typename MappedContainerType = kstd::vector> struct flat_map { + template + struct flat_map_iterator; + //! The type of container used to store the map keys. using key_container_type = KeyContainerType; @@ -28,7 +34,7 @@ namespace kstd //! The type of the map keys. using key_type = KeyType; - //! The type of the mappe values. + //! The type of the mapped values. using mapped_type = MappedType; //! The type of a single key-value value in the map. @@ -41,14 +47,12 @@ namespace kstd using const_reference = std::pair; using size_type = std::size_t; using difference_type = std::ptrdiff_t; - using iterator = bits::flat_map_iterator; - using const_iterator = - bits::flat_map_iterator; + using iterator = flat_map_iterator; + using const_iterator = flat_map_iterator; using reverse_iterator = std::reverse_iterator; using const_reverse_iterator = std::reverse_iterator; - using containers = struct + + struct containers { key_container_type keys; mapped_container_type values; @@ -63,11 +67,225 @@ namespace kstd } }; + template + struct flat_map_iterator + { + using iterator_category = std::random_access_iterator_tag; + using value_type = std::pair; + using difference_type = std::ptrdiff_t; + using reference = std::pair &>; + + struct pointer + { + reference ref; + + auto operator->() const noexcept -> reference const * + { + return std::addressof(ref); + } + }; + + constexpr flat_map_iterator() = default; + + constexpr flat_map_iterator(flat_map_iterator it) + requires IsConst + : m_containers{it.m_containers} + , m_index{it.m_index} + {} + + [[nodiscard]] constexpr auto operator*() const noexcept -> reference + { + if (m_index >= m_containers->keys.size()) + { + os::panic("[kstd::flat_map] Iterator out of range"); + } + return {m_containers->keys[m_index], m_containers->values[m_index]}; + } + + [[nodiscard]] constexpr auto operator->() const noexcept -> pointer + { + return {operator*()}; + } + + [[nodiscard]] constexpr auto operator[](difference_type offset) const noexcept -> reference + { + return *(*this + offset); + } + + constexpr auto operator++() noexcept -> flat_map_iterator & + { + ++m_index; + return *this; + } + + constexpr auto operator++(int) noexcept -> flat_map_iterator + { + auto copy = *this; + ++(*this); + return copy; + } + + constexpr auto operator--() noexcept -> flat_map_iterator & + { + --m_index; + return *this; + } + + constexpr auto operator--(int) noexcept -> flat_map_iterator + { + auto copy = *this; + --(*this); + return copy; + } + + constexpr auto operator+=(difference_type offset) noexcept -> flat_map_iterator & + { + m_index += offset; + return *this; + } + + [[nodiscard]] constexpr auto friend operator+(flat_map_iterator it, difference_type offset) noexcept + -> flat_map_iterator + { + it += offset; + return it; + } + + [[nodiscard]] constexpr auto friend operator+(difference_type offset, flat_map_iterator it) noexcept + -> flat_map_iterator + { + it += offset; + return it; + } + + constexpr auto operator-=(difference_type offset) noexcept -> flat_map_iterator & + { + m_index -= offset; + return *this; + } + + [[nodiscard]] constexpr auto friend operator-(flat_map_iterator it, difference_type offset) noexcept + -> flat_map_iterator + { + it -= offset; + return it; + } + + [[nodiscard]] constexpr auto friend operator-(flat_map_iterator const & lhs, + flat_map_iterator const & rhs) noexcept -> difference_type + { + return lhs.m_index - rhs.m_index; + } + + [[nodiscard]] constexpr auto friend operator<=>(flat_map_iterator const &, + flat_map_iterator const &) noexcept = default; + + private: + friend struct flat_map; + friend flat_map_iterator; + + constexpr flat_map_iterator(containers & containers, std::size_t index) + requires(!IsConst) + : m_containers{&containers} + , m_index{index} + {} + + constexpr flat_map_iterator(containers const & containers, std::size_t index) + requires(IsConst) + : m_containers{&containers} + , m_index{index} + {} + + [[nodiscard]] constexpr auto key_iterator() const noexcept + { + return m_containers->keys.begin() + m_index; + } + + std::conditional_t * m_containers; + std::size_t m_index{std::numeric_limits::max()}; + }; + //! Construct an empty flat map. constexpr flat_map() : flat_map{key_compare{}} {} + //! Construct a new flat map by copying from an existing one. + //! + //! @note This constructor only participates in overload resolution if both the key and the mapped container use + //! allocator construction using the given allocator. + //! + //! @tparam Allocator The type of the allocator to use for the underlying containers. + //! @param other An existing flat map. + //! @param allocator The allocator to use for the underlying containers. + template + requires(std::uses_allocator_v && + std::uses_allocator_v) + constexpr flat_map(flat_map const & other, Allocator const & allocator) + : m_containers{std::make_obj_using_allocator(allocator, other.m_containers.keys), + std::make_obj_using_allocator(allocator, other.m_containers.values)} + , m_comparator{other.m_comparator} + {} + + //! Construct a new flat map by copying from an existing one. + //! + //! @note This constructor only participates in overload resolution if both the key and the mapped container use + //! allocator construction using the given allocator. + //! + //! @tparam Allocator The type of the allocator to use for the underlying containers. + //! @param other An existing flat map. + //! @param allocator The allocator to use for the underlying containers. + template + requires(std::uses_allocator_v && + std::uses_allocator_v) + constexpr flat_map(flat_map && other, Allocator const & allocator) + : m_containers{ + std::make_obj_using_allocator(allocator, std::move(other.m_containers.keys)), + std::make_obj_using_allocator(allocator, std::move(other.m_containers.values))} + , m_comparator{other.m_comparator} + {} + + //! Construct a new flat map using the supplied keys and values. + //! + //! After moving the keys and mapped values, this constructor sorts the value pairs using the comparator of this + //! flat map and then erases duplicate keys. + //! + //! @param keys The container containing the keys of the new flat map. + //! @param mapped The container containing the mapped values of the new flat map. + //! @param comparator The comparator to use for sorting the keys. + constexpr flat_map(key_container_type keys, mapped_container_type mapped, key_compare comparator = key_compare{}) + : m_containers{std::move(keys), std::move(mapped)} + , m_comparator{comparator} + { + do_sort(); + do_unique(); + } + + //! Construct a new flat map using the supplied keys and values, using the given allocator. + //! + //! After copying the and mapped values, this constructor sorts the value pairs using the the comparator of this + //! flat map and then erases the duplicate keys. + //! + //! @note This constructor only participates in overload resolution if both the key and the mapped container use + //! allocator construction using the given allocator. + //! + //! @tparam Allocator The type of the allocator to use for the underlying containers. + //! @param keys The container containing the keys of the new flat map. + //! @param mapped The container containing the mapped values of the new flat map. + //! @param allocator The allocator to use for the underlying containers. + template + requires(std::uses_allocator_v && + std::uses_allocator_v) + constexpr flat_map(key_container_type const & keys, mapped_container_type const & mapped, + Allocator const & allocator) + : m_containers{std::make_obj_using_allocator(allocator, keys), + std::make_obj_using_allocator(allocator, mapped)} + , m_comparator{} + { + do_sort(); + do_unique(); + } + //! Construct an empty flat map using the given custom comparator. //! //! @param comparator The comparator to use for comparing keys. @@ -161,37 +379,37 @@ namespace kstd //! Get an iterator to the first element. [[nodiscard]] auto begin() noexcept -> iterator { - return iterator{m_containers.keys.begin(), m_containers.values.begin()}; + return iterator{m_containers, 0}; } //! 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()}; + return const_iterator{m_containers, 0}; } //! 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()}; + return const_iterator{m_containers, 0}; } //! 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()}; + return iterator{m_containers, size()}; } //! 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()}; + return const_iterator{m_containers, size()}; } //! 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()}; + return const_iterator{m_containers, size()}; } //! Get an iterator to the first element. @@ -263,7 +481,7 @@ namespace kstd { auto offset = std::distance(m_containers.keys.begin(), found); return { - iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset}, + iterator{m_containers, offset}, false }; } @@ -276,7 +494,7 @@ namespace kstd auto inserted_mapped = m_containers.values.insert(mapped_iterator, std::move(value.second)); return { - iterator{inserted_key, inserted_mapped}, + iterator{m_containers, inserted_key - m_containers.keys.begin()}, true }; } @@ -297,13 +515,13 @@ namespace kstd } auto offset = std::distance(m_containers.keys.cbegin(), found); - auto intersertion_point = m_containers.value.begin() + offset; + auto insertion_point = m_containers.value.begin() + offset; auto inserted_key = m_containers.keys.emplace(key); auto inserted_mapped = m_containers.values.emplace(std::forward(args)...); return { - iterator{inserted_key, inserted_mapped}, + iterator{m_containers, inserted_key - m_containers.keys.begin()}, true }; } @@ -318,7 +536,7 @@ namespace kstd 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 iterator{m_containers, offset}; } return end(); } @@ -333,7 +551,7 @@ namespace kstd 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 const_iterator{m_containers, offset}; } return cend(); } @@ -350,7 +568,7 @@ namespace kstd 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 iterator{m_containers, offset}; } return end(); } @@ -367,7 +585,7 @@ namespace kstd 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 const_iterator{m_containers, offset}; } return cend(); } @@ -398,9 +616,46 @@ namespace kstd } private: + struct key_equivalent + { + constexpr key_equivalent(key_compare comparator) + : m_comparator{comparator} + {} + + constexpr auto operator()(const_reference lhs, const_reference rhs) const noexcept -> bool + { + return !m_comparator(lhs.first, rhs.first) && !m_comparator(rhs.first, lhs.first); + } + + private: + key_compare m_comparator; + }; + + constexpr auto do_sort() -> void + { + auto zipped = std::views::zip(m_containers.keys, m_containers.values); + std::ranges::sort(zipped, value_compare{}); + } + + constexpr auto do_unique() -> void + { + auto zipped = std::views::zip(m_containers.keys, m_containers.values); + auto unique = std::ranges::unique(zipped, key_equivalent{m_comparator}).begin(); + auto erase_begin = std::ranges::distance(zipped.begin(), unique); + m_containers.keys.erase(m_containers.keys.begin() + erase_begin, m_containers.keys.end()); + m_containers.values.erase(m_containers.values.begin() + erase_begin, m_containers.values.end()); + } + containers m_containers; key_compare m_comparator; }; + + template> + flat_map(KeyContainer, MappedContainer, Compare = Compare{}) + -> flat_map; + } // namespace kstd #endif \ No newline at end of file diff --git a/libs/kstd/kstd/flat_map.tests.cpp b/libs/kstd/kstd/flat_map.tests.cpp index bfd02303..22f4c570 100644 --- a/libs/kstd/kstd/flat_map.tests.cpp +++ b/libs/kstd/kstd/flat_map.tests.cpp @@ -1,12 +1,14 @@ #include +#include #include +#include #include +#include #include #include -#include SCENARIO("Flat Map initialization and construction", "[flat_map]") { @@ -32,6 +34,78 @@ SCENARIO("Flat Map initialization and construction", "[flat_map]") } } } + + GIVEN("A populated flat map") + { + auto map = kstd::flat_map{}; + map.emplace(1, 10); + map.emplace(2, 20); + map.emplace(3, 30); + + WHEN("contstructing by copy using an allocator") + { + auto copy = kstd::flat_map{map, kstd::allocator{}}; + + THEN("the map compare equal") + { + REQUIRE(std::ranges::equal(map, copy)); + } + } + } + + GIVEN("An unsorted key container and an unsorted value container") + { + auto keys = kstd::vector{0, 5, 3, 4, 1, 2}; + auto values = kstd::vector{'a', 'f', 'd', 'e', 'b', 'c'}; + + WHEN("constructing using the containers") + { + auto map = kstd::flat_map{keys, values}; + + THEN("the flat map has size 6") + { + REQUIRE(map.size() == 6); + + REQUIRE((map.cend() - map.begin()) == 6); + } + + THEN("the flat map contains all pairs in order") + { + REQUIRE(map.at(0) == 'a'); + REQUIRE(map.at(1) == 'b'); + REQUIRE(map.at(2) == 'c'); + REQUIRE(map.at(3) == 'd'); + REQUIRE(map.at(4) == 'e'); + REQUIRE(map.at(5) == 'f'); + } + } + } + + GIVEN("An unsorted key container and an unsorted value container, with duplicate keys") + { + auto keys = kstd::vector{0, 5, 5, 3, 4, 1, 2}; + auto values = kstd::vector{'a', 'f', 'g', 'd', 'e', 'b', 'c'}; + + WHEN("constructing using the containers") + { + auto map = kstd::flat_map{keys, values}; + + THEN("the flat map has size 6") + { + REQUIRE(map.size() == 6); + } + + THEN("the flat map contains all pairs in order") + { + REQUIRE(map.at(0) == 'a'); + REQUIRE(map.at(1) == 'b'); + REQUIRE(map.at(2) == 'c'); + REQUIRE(map.at(3) == 'd'); + REQUIRE(map.at(4) == 'e'); + REQUIRE(map.at(5) == 'f'); + } + } + } } SCENARIO("Flat Map modifiers", "[flat_map]") @@ -200,16 +274,6 @@ SCENARIO("Flat Map iterators", "[flat_map]") REQUIRE(it == map.cend()); } - THEN("assignment through the proxy modifies the mapped value") - { - auto it = map.begin(); - - *it = std::pair{1, 100}; - - REQUIRE(it->second == 100); - REQUIRE(map.at(1) == 100); - } - THEN("structured bindings evaluate correctly") { auto it = map.cbegin(); -- cgit v1.2.3