From de24d7bcee796d2fd2e86a3f4e64cc890747a198 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 17 Aug 2026 13:26:19 +0200 Subject: kstd: reduce some duplication in flat map --- libs/kstd/kstd/flat_map.hpp | 116 ++++++++++++++------------------------------ 1 file changed, 36 insertions(+), 80 deletions(-) (limited to 'libs') diff --git a/libs/kstd/kstd/flat_map.hpp b/libs/kstd/kstd/flat_map.hpp index 71e142f7..f3cf827a 100644 --- a/libs/kstd/kstd/flat_map.hpp +++ b/libs/kstd/kstd/flat_map.hpp @@ -443,13 +443,7 @@ namespace kstd //! @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"); + return at(key); } //! Get a reference to the mapped value associated with the given key. @@ -459,29 +453,22 @@ namespace kstd //! @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"); + return at(key); } //! Get a reference to the mapped value associated with the given key. //! //! @warning This function will panic if the key is not found. - //! @param x The key to look up. + //! @param key The key to look up. //! @return A reference to the mapped value. template - requires bits::transparent - [[nodiscard]] constexpr auto at(K const & x) -> mapped_type & + requires std::same_as> || bits::transparent + [[nodiscard]] constexpr auto at(K const & key) -> mapped_type & { - auto found = find(x); + auto found = find(key); if (found != end()) { - auto offset = std::distance(m_containers.keys.begin(), found.key_iterator()); - return *(m_containers.values.begin() + offset); + return found->second; } os::panic("[kstd::flat_map] Key not found"); } @@ -489,17 +476,16 @@ namespace kstd //! Get a reference to the mapped value associated with the given key. //! //! @warning This function will panic if the key is not found. - //! @param x The key to look up. + //! @param key The key to look up. //! @return A const reference to the mapped value. template - requires bits::transparent - [[nodiscard]] auto at(K const & x) const -> mapped_type const & + requires std::same_as> || bits::transparent + [[nodiscard]] auto at(K const & key) const -> mapped_type const & { - auto found = find(x); - if (found != end()) + auto found = find(key); + if (found != cend()) { - auto offset = std::distance(m_containers.keys.cbegin(), found.key_iterator()); - return *(m_containers.values.cbegin() + offset); + return found->second; } os::panic("[kstd::flat_map] Key not found"); } @@ -828,13 +814,7 @@ namespace kstd //! @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, offset}; - } - return end(); + return find(key); } //! Find an element with an equivalent key. @@ -843,21 +823,15 @@ namespace kstd //! @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, offset}; - } - return cend(); + return find(key); } //! 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 - requires bits::transparent + requires std::same_as> || bits::transparent [[nodiscard]] auto find(K const & x) noexcept -> iterator { auto found = std::ranges::lower_bound(m_containers.keys, x, m_comparator); @@ -870,11 +844,11 @@ namespace kstd } //! 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 - requires bits::transparent + requires std::same_as> || bits::transparent [[nodiscard]] auto find(K const & x) const noexcept -> const_iterator { auto found = std::ranges::lower_bound(m_containers.keys, x, m_comparator); @@ -892,11 +866,7 @@ namespace kstd //! @return 0 if the key does not exist, 1 otherwise. [[nodiscard]] constexpr auto count(key_type const & key) const noexcept -> std::size_t { - if (contains(key)) - { - return 1; - } - return 0; + return count(key); } //! Count the number of occurrences of keys equivalent to a given key in this flat map. @@ -905,8 +875,8 @@ namespace kstd //! @param key The key to look for. //! @return 0 if the key does not exist, 1 otherwise. template - requires bits::transparent - [[nodiscard]] constexpr auto count(key_type const & key) const noexcept -> std::size_t + requires std::same_as> || bits::transparent + [[nodiscard]] constexpr auto count(K const & key) const noexcept -> std::size_t { if (contains(key)) { @@ -921,7 +891,7 @@ namespace kstd //! @return true iff. the key is found, false otherwise. [[nodiscard]] constexpr auto contains(key_type const & key) const noexcept -> bool { - return find(key) != cend(); + return contains(key); } //! Check if the map contains a key equivalent to the given one. @@ -930,7 +900,7 @@ namespace kstd //! @param key The key to check. //! @return true iff. the key is found, false otherwise. template - requires bits::transparent + requires std::same_as> || bits::transparent [[nodiscard]] constexpr auto contains(K const & key) const noexcept -> bool { return find(key) != cend(); @@ -943,9 +913,7 @@ namespace kstd //! iterator otherwise. [[nodiscard]] constexpr auto lower_bound(key_type const & key) noexcept -> iterator { - auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); - auto offset = static_cast(std::ranges::distance(m_containers.keys.begin(), found)); - return iterator{m_containers, offset}; + return lower_bound(key); } //! Get an iterator to the first element not less than the given key. @@ -955,9 +923,7 @@ namespace kstd //! iterator otherwise. [[nodiscard]] constexpr auto lower_bound(key_type const & key) const noexcept -> const_iterator { - auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); - auto offset = static_cast(std::ranges::distance(m_containers.keys.begin(), found)); - return const_iterator{m_containers, offset}; + return lower_bound(key); } //! Get an iterator to the first element not less than the given key. @@ -966,7 +932,7 @@ namespace kstd //! @return An iterator to the first element not less than the given key iff. such an element exists, the end //! iterator otherwise. template - requires bits::transparent + requires std::same_as> || bits::transparent [[nodiscard]] constexpr auto lower_bound(K const & key) noexcept -> iterator { auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); @@ -980,7 +946,7 @@ namespace kstd //! @return An iterator to the first element not less than the given key iff. such an element exists, the end //! iterator otherwise. template - requires bits::transparent + requires std::same_as> || bits::transparent [[nodiscard]] constexpr auto lower_bound(K const & key) const noexcept -> const_iterator { auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); @@ -995,9 +961,7 @@ namespace kstd //! otherwise. [[nodiscard]] constexpr auto upper_bound(key_type const & key) noexcept -> iterator { - auto found = std::ranges::upper_bound(m_containers.keys, key, m_comparator); - auto offset = static_cast(std::ranges::distance(m_containers.keys.begin(), found)); - return iterator{m_containers, offset}; + return upper_bound(key); } //! Get an iterator to the first element greater than the given key. @@ -1007,9 +971,7 @@ namespace kstd //! otherwise. [[nodiscard]] constexpr auto upper_bound(key_type const & key) const noexcept -> const_iterator { - auto found = std::ranges::upper_bound(m_containers.keys, key, m_comparator); - auto offset = static_cast(std::ranges::distance(m_containers.keys.begin(), found)); - return const_iterator{m_containers, offset}; + return upper_bound(key); } //! Get an iterator to the first element greater than the given key. @@ -1018,7 +980,7 @@ namespace kstd //! @return An iterator to the first element greater than the given iff. such an element exists, the end iterator //! otherwise. template - requires bits::transparent + requires std::same_as> || bits::transparent [[nodiscard]] constexpr auto upper_bound(K const & key) noexcept -> iterator { auto found = std::ranges::upper_bound(m_containers.keys, key, m_comparator); @@ -1032,7 +994,7 @@ namespace kstd //! @return An iterator to the first element greater than the given iff. such an element exists, the end iterator //! otherwise. template - requires bits::transparent + requires std::same_as> || bits::transparent [[nodiscard]] constexpr auto upper_bound(K const & key) const noexcept -> const_iterator { auto found = std::ranges::upper_bound(m_containers.keys, key, m_comparator); @@ -1046,10 +1008,7 @@ namespace kstd //! @return A pair of iterators describing the, possibly empty, range of elements. [[nodiscard]] constexpr auto equal_range(key_type const & key) noexcept -> std::pair { - auto found = std::ranges::equal_range(m_containers.keys, key, m_comparator); - auto start_offset = static_cast(std::ranges::distance(m_containers.keys.begin(), found.begin())); - auto end_offset = static_cast(std::ranges::distance(m_containers.keys.begin(), found.end())); - return std::make_pair(iterator{m_containers, start_offset}, iterator{m_containers, end_offset}); + return equal_range(key); } //! Get a range of elements whose keys compare equal to the given key. @@ -1059,10 +1018,7 @@ namespace kstd [[nodiscard]] constexpr auto equal_range(key_type const & key) const noexcept -> std::pair { - auto found = std::ranges::equal_range(m_containers.keys, key, m_comparator); - auto start_offset = static_cast(std::ranges::distance(m_containers.keys.begin(), found.begin())); - auto end_offset = static_cast(std::ranges::distance(m_containers.keys.begin(), found.end())); - return std::make_pair(iterator{m_containers, start_offset}, iterator{m_containers, end_offset}); + return equal_range(key); } //! Get a range of elements whose keys compare equal to the given key. @@ -1070,7 +1026,7 @@ namespace kstd //! @param key The key to look for. //! @return A pair of iterators describing the, possibly empty, range of elements. template - requires bits::transparent + requires std::same_as> || bits::transparent [[nodiscard]] constexpr auto equal_range(K const & key) noexcept -> std::pair { auto found = std::ranges::equal_range(m_containers.keys, key, m_comparator); @@ -1084,7 +1040,7 @@ namespace kstd //! @param key The key to look for. //! @return A pair of iterators describing the, possibly empty, range of elements. template - requires bits::transparent + requires std::same_as> || bits::transparent [[nodiscard]] constexpr auto equal_range(K const & key) const noexcept -> std::pair { auto found = std::ranges::equal_range(m_containers.keys, key, m_comparator); -- cgit v1.2.3