diff options
Diffstat (limited to 'libs/kstd/kstd/flat_map.hpp')
| -rw-r--r-- | libs/kstd/kstd/flat_map.hpp | 299 |
1 files changed, 277 insertions, 22 deletions
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 |