diff options
| -rw-r--r-- | libs/kstd/kstd/bits/flat_map.hpp | 186 | ||||
| -rw-r--r-- | libs/kstd/kstd/flat_map.hpp | 299 | ||||
| -rw-r--r-- | libs/kstd/kstd/flat_map.tests.cpp | 86 |
3 files changed, 352 insertions, 219 deletions
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 <concepts> -#include <cstddef> -#include <iterator> -#include <memory> -#include <tuple> -#include <type_traits> -#include <utility> - -namespace kstd::bits -{ - - template<typename KeyType, typename MappedType> - 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<typename TupleLikeType> - requires(std::tuple_size_v<std::remove_cvref_t<TupleLikeType>> == 2) - constexpr auto operator=(TupleLikeType && tuple) const -> flat_map_reference const & - { - second = std::forward<TupleLikeType>(tuple).second; - return *this; - } - - template<std::size_t Index> - 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<typename Reference> - 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<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 = flat_map_reference<KeyType, MappedType>; - using pointer = flat_map_pointer<reference>; - - 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<typename OtherMappedType, typename OtherKeyIterator, typename OtherMappedIterator> - requires(std::convertible_to<OtherKeyIterator, KeyIterator> && - std::convertible_to<OtherMappedIterator, MappedIterator>) - constexpr flat_map_iterator( - flat_map_iterator<KeyType, OtherMappedType, OtherKeyIterator, OtherMappedIterator> 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<typename K, typename M> -struct std::tuple_size<kstd::bits::flat_map_reference<K, M>> : std::integral_constant<std::size_t, 2> -{ -}; - -template<typename K, typename M> -struct std::tuple_element<0, kstd::bits::flat_map_reference<K, M>> -{ - using type = K const &; -}; - -template<typename K, typename M> -struct std::tuple_element<1, kstd::bits::flat_map_reference<K, M>> -{ - 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 <kstd/bits/flat_map.hpp> #include <kstd/os/error.hpp> #include <kstd/vector.hpp> @@ -10,6 +9,10 @@ #include <cstddef> #include <functional> #include <iterator> +#include <limits> +#include <memory> +#include <ranges> +#include <type_traits> #include <utility> namespace kstd @@ -19,6 +22,9 @@ namespace kstd typename KeyContainerType = kstd::vector<KeyType>, typename MappedContainerType = kstd::vector<MappedType>> struct flat_map { + template<bool IsConst> + 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<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 iterator = flat_map_iterator<false>; + using const_iterator = flat_map_iterator<true>; using reverse_iterator = std::reverse_iterator<iterator>; using const_reverse_iterator = std::reverse_iterator<const_iterator>; - using containers = struct + + struct containers { key_container_type keys; mapped_container_type values; @@ -63,11 +67,225 @@ namespace kstd } }; + template<bool IsConst> + 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 &, std::conditional_t<IsConst, MappedType const, MappedType> &>; + + 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<!IsConst> 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<!IsConst>; + + 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<IsConst, containers const, containers> * m_containers; + std::size_t m_index{std::numeric_limits<std::size_t>::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<typename Allocator> + requires(std::uses_allocator_v<key_container_type, Allocator> && + std::uses_allocator_v<mapped_container_type, Allocator>) + constexpr flat_map(flat_map const & other, Allocator const & allocator) + : m_containers{std::make_obj_using_allocator<key_container_type>(allocator, other.m_containers.keys), + std::make_obj_using_allocator<mapped_container_type>(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<typename Allocator> + requires(std::uses_allocator_v<key_container_type, Allocator> && + std::uses_allocator_v<mapped_container_type, Allocator>) + constexpr flat_map(flat_map && other, Allocator const & allocator) + : m_containers{ + std::make_obj_using_allocator<key_container_type>(allocator, std::move(other.m_containers.keys)), + std::make_obj_using_allocator<mapped_container_type>(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<typename Allocator> + requires(std::uses_allocator_v<key_container_type, Allocator> && + std::uses_allocator_v<mapped_container_type, Allocator>) + constexpr flat_map(key_container_type const & keys, mapped_container_type const & mapped, + Allocator const & allocator) + : m_containers{std::make_obj_using_allocator<key_container_type>(allocator, keys), + std::make_obj_using_allocator<mapped_container_type>(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>(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<typename KeyContainer, typename MappedContainer, + typename Compare = std::less<typename KeyContainer::value_type>> + flat_map(KeyContainer, MappedContainer, Compare = Compare{}) + -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type, Compare, KeyContainer, + MappedContainer>; + } // 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 <kstd/flat_map.hpp> +#include <kstd/allocator.hpp> #include <kstd/test_support/os_panic.hpp> +#include <kstd/vector.hpp> #include <catch2/catch_test_macros.hpp> +#include <algorithm> #include <functional> #include <type_traits> -#include <utility> 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<int, int>{}; + map.emplace(1, 10); + map.emplace(2, 20); + map.emplace(3, 30); + + WHEN("contstructing by copy using an allocator") + { + auto copy = kstd::flat_map<int, int>{map, kstd::allocator<int>{}}; + + 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(); |