From 9c3a1a89a79e506f472275f42ac6b34e6a7a172e Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Sun, 16 Aug 2026 17:00:18 +0200 Subject: kstd: implement flat map upper bound --- libs/kstd/kstd/flat_map.hpp | 52 ++++++++++++++++++++++++++++ libs/kstd/kstd/flat_map.tests.cpp | 72 ++++++++++++++++++++++++++++++++++++--- 2 files changed, 120 insertions(+), 4 deletions(-) diff --git a/libs/kstd/kstd/flat_map.hpp b/libs/kstd/kstd/flat_map.hpp index 3eda42d8..f00956a5 100644 --- a/libs/kstd/kstd/flat_map.hpp +++ b/libs/kstd/kstd/flat_map.hpp @@ -820,6 +820,58 @@ namespace kstd return const_iterator{m_containers, offset}; } + //! Get an iterator to the first element greater than the given key. + //! + //! @param key The key to look for. + //! @return An iterator to the first element greater than the given iff. such an element exists, the end iterator + //! 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}; + } + + //! Get an iterator to the first element greater than the given key. + //! + //! @param key The key to look for. + //! @return An iterator to the first element greater than the given iff. such an element exists, the end iterator + //! 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}; + } + + //! Get an iterator to the first element greater than the given key. + //! + //! @param key The key to look for. + //! @return An iterator to the first element greater than the given iff. such an element exists, the end iterator + //! otherwise. + template + requires requires { typename key_compare::is_transparent; } + [[nodiscard]] constexpr auto upper_bound(K 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}; + } + + //! Get an iterator to the first element greater than the given key. + //! + //! @param key The key to look for. + //! @return An iterator to the first element greater than the given iff. such an element exists, the end iterator + //! otherwise. + template + requires requires { typename key_compare::is_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); + auto offset = static_cast(std::ranges::distance(m_containers.keys.begin(), found)); + return iterator{m_containers, offset}; + } + //! Get the key comparator of this flat map. //! //! @return The key comparator of this flat map. diff --git a/libs/kstd/kstd/flat_map.tests.cpp b/libs/kstd/kstd/flat_map.tests.cpp index 5f29fa14..41281e93 100644 --- a/libs/kstd/kstd/flat_map.tests.cpp +++ b/libs/kstd/kstd/flat_map.tests.cpp @@ -736,8 +736,8 @@ SCENARIO("Flat Map queries", "[flat_map]") THEN("it returns an iterator to the element") { REQUIRE(it != map.end()); - REQUIRE((*it).first == 'c'); - REQUIRE((*it).second == 20); + REQUIRE(it->first == 'c'); + REQUIRE(it->second == 20); } } @@ -760,6 +760,38 @@ SCENARIO("Flat Map queries", "[flat_map]") REQUIRE(it == map.begin()); } } + + WHEN("finding the upper bound of a key present in the map") + { + auto it = map.upper_bound('b'); + + THEN("it returns an iterator to the next element") + { + REQUIRE(it != map.end()); + REQUIRE(it->first == 'c'); + REQUIRE(it->second == 20); + } + } + + WHEN("finding the upper bound of a key larger than any in the map") + { + auto it = map.upper_bound('e'); + + THEN("it returns an iterator to the end of the map") + { + REQUIRE(it == map.end()); + } + } + + WHEN("finding the upper bound of a key smaller than any in the map") + { + auto it = map.upper_bound('a'); + + THEN("it returns an iterator to the first element") + { + REQUIRE(it == map.begin()); + } + } } GIVEN("A populated Flat Map with a transparent comparator") @@ -776,8 +808,8 @@ SCENARIO("Flat Map queries", "[flat_map]") THEN("it returns an iterator to the element") { REQUIRE(it != map.end()); - REQUIRE((*it).first == "c"); - REQUIRE((*it).second == 20); + REQUIRE(it->first == "c"); + REQUIRE(it->second == 20); } } @@ -800,5 +832,37 @@ SCENARIO("Flat Map queries", "[flat_map]") REQUIRE(it == map.begin()); } } + + WHEN("finding the upper bound of a key present in the map") + { + auto it = map.upper_bound("b"); + + THEN("it returns an iterator to the next element") + { + REQUIRE(it != map.end()); + REQUIRE(it->first == "c"); + REQUIRE(it->second == 20); + } + } + + WHEN("finding the upper bound of a key larger than any in the map") + { + auto it = map.upper_bound("e"); + + THEN("it returns an iterator to the end of the map") + { + REQUIRE(it == map.end()); + } + } + + WHEN("finding the upper bound of a key smaller than any in the map") + { + auto it = map.upper_bound("a"); + + THEN("it returns an iterator to the first element") + { + REQUIRE(it == map.begin()); + } + } } } -- cgit v1.2.3