aboutsummaryrefslogtreecommitdiff
path: root/libs
diff options
context:
space:
mode:
Diffstat (limited to 'libs')
-rw-r--r--libs/kstd/kstd/flat_map.hpp53
-rw-r--r--libs/kstd/kstd/flat_map.tests.cpp94
2 files changed, 133 insertions, 14 deletions
diff --git a/libs/kstd/kstd/flat_map.hpp b/libs/kstd/kstd/flat_map.hpp
index f00956a5..dcf73392 100644
--- a/libs/kstd/kstd/flat_map.hpp
+++ b/libs/kstd/kstd/flat_map.hpp
@@ -872,6 +872,59 @@ namespace kstd
return iterator{m_containers, offset};
}
+ //! Get a range of elements whose keys compare equal to the given key.
+ //!
+ //! @param key The key to look for.
+ //! @return A pair of iterators describing the, possibly empty, range of elements.
+ [[nodiscard]] constexpr auto equal_range(key_type const & key) noexcept -> std::pair<iterator, iterator>
+ {
+ auto found = std::ranges::equal_range(m_containers.keys, key, m_comparator);
+ auto start_offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found.begin()));
+ auto end_offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found.end()));
+ return std::make_pair(iterator{m_containers, start_offset}, iterator{m_containers, end_offset});
+ }
+
+ //! Get a range of elements whose keys compare equal to the given key.
+ //!
+ //! @param key The key to look for.
+ //! @return A pair of iterators describing the, possibly empty, range of elements.
+ [[nodiscard]] constexpr auto equal_range(key_type const & key) const noexcept
+ -> std::pair<const_iterator, const_iterator>
+ {
+ auto found = std::ranges::equal_range(m_containers.keys, key, m_comparator);
+ auto start_offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found.begin()));
+ auto end_offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found.end()));
+ return std::make_pair(iterator{m_containers, start_offset}, iterator{m_containers, end_offset});
+ }
+
+ //! Get a range of elements whose keys compare equal to the given key.
+ //!
+ //! @param key The key to look for.
+ //! @return A pair of iterators describing the, possibly empty, range of elements.
+ template<typename K>
+ requires requires { typename key_compare::is_transparent; }
+ [[nodiscard]] constexpr auto equal_range(K const & key) noexcept -> std::pair<iterator, iterator>
+ {
+ auto found = std::ranges::equal_range(m_containers.keys, key, m_comparator);
+ auto start_offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found.begin()));
+ auto end_offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found.end()));
+ return std::make_pair(iterator{m_containers, start_offset}, iterator{m_containers, end_offset});
+ }
+
+ //! Get a range of elements whose keys compare equal to the given key.
+ //!
+ //! @param key The key to look for.
+ //! @return A pair of iterators describing the, possibly empty, range of elements.
+ template<typename K>
+ requires requires { typename key_compare::is_transparent; }
+ [[nodiscard]] constexpr auto equal_range(K const & key) const noexcept -> std::pair<const_iterator, const_iterator>
+ {
+ auto found = std::ranges::equal_range(m_containers.keys, key, m_comparator);
+ auto start_offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found.begin()));
+ auto end_offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found.end()));
+ return std::make_pair(iterator{m_containers, start_offset}, iterator{m_containers, end_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 41281e93..6a1b6f2a 100644
--- a/libs/kstd/kstd/flat_map.tests.cpp
+++ b/libs/kstd/kstd/flat_map.tests.cpp
@@ -726,24 +726,24 @@ SCENARIO("Flat Map queries", "[flat_map]")
{
auto map = kstd::flat_map<char, int>{};
map.emplace('b', 10);
- map.emplace('c', 20);
- map.emplace('d', 30);
+ map.emplace('d', 20);
+ map.emplace('f', 30);
WHEN("finding the lower bound of a key present in the map")
{
- auto it = map.lower_bound('c');
+ auto it = map.lower_bound('d');
THEN("it returns an iterator to the element")
{
REQUIRE(it != map.end());
- REQUIRE(it->first == 'c');
+ REQUIRE(it->first == 'd');
REQUIRE(it->second == 20);
}
}
WHEN("finding the lower bound of a key larger than any in the map")
{
- auto it = map.lower_bound('e');
+ auto it = map.lower_bound('g');
THEN("it returns an iterator to the end of the map")
{
@@ -768,14 +768,14 @@ SCENARIO("Flat Map queries", "[flat_map]")
THEN("it returns an iterator to the next element")
{
REQUIRE(it != map.end());
- REQUIRE(it->first == 'c');
+ REQUIRE(it->first == 'd');
REQUIRE(it->second == 20);
}
}
WHEN("finding the upper bound of a key larger than any in the map")
{
- auto it = map.upper_bound('e');
+ auto it = map.upper_bound('g');
THEN("it returns an iterator to the end of the map")
{
@@ -792,30 +792,63 @@ SCENARIO("Flat Map queries", "[flat_map]")
REQUIRE(it == map.begin());
}
}
+
+ WHEN("fiding the equal range of a key present in the map")
+ {
+ auto [begin, end] = map.equal_range('b');
+
+ THEN("it returns an iterator pair to the element")
+ {
+ REQUIRE(begin == map.begin());
+ REQUIRE(end == map.begin() + 1);
+ }
+ }
+
+ WHEN("fiding the equal range of a key between two elements in the map")
+ {
+ auto [begin, end] = map.equal_range('c');
+
+ THEN("it returns an iterator pair to the element")
+ {
+ REQUIRE(begin->first == 'd');
+ REQUIRE(end->first == 'd');
+ }
+ }
+
+ WHEN("fiding the equal range of a key outside the elements of the map")
+ {
+ auto [begin, end] = map.equal_range('g');
+
+ THEN("it returns an iterator pair to the element")
+ {
+ REQUIRE(begin == map.end());
+ REQUIRE(end == map.end());
+ }
+ }
}
GIVEN("A populated Flat Map with a transparent comparator")
{
auto map = kstd::flat_map<std::string, int, std::less<>>{};
map.emplace("b", 10);
- map.emplace("c", 20);
- map.emplace("d", 30);
+ map.emplace("d", 20);
+ map.emplace("f", 30);
WHEN("finding the lower bound of a key present in the map")
{
- auto it = map.lower_bound("c");
+ auto it = map.lower_bound("d");
THEN("it returns an iterator to the element")
{
REQUIRE(it != map.end());
- REQUIRE(it->first == "c");
+ REQUIRE(it->first == "d");
REQUIRE(it->second == 20);
}
}
WHEN("finding the lower bound of a key larger than any in the map")
{
- auto it = map.lower_bound("e");
+ auto it = map.lower_bound("g");
THEN("it returns an iterator to the end of the map")
{
@@ -840,14 +873,14 @@ SCENARIO("Flat Map queries", "[flat_map]")
THEN("it returns an iterator to the next element")
{
REQUIRE(it != map.end());
- REQUIRE(it->first == "c");
+ REQUIRE(it->first == "d");
REQUIRE(it->second == 20);
}
}
WHEN("finding the upper bound of a key larger than any in the map")
{
- auto it = map.upper_bound("e");
+ auto it = map.upper_bound("g");
THEN("it returns an iterator to the end of the map")
{
@@ -864,5 +897,38 @@ SCENARIO("Flat Map queries", "[flat_map]")
REQUIRE(it == map.begin());
}
}
+
+ WHEN("fiding the equal range of a key present in the map")
+ {
+ auto [begin, end] = map.equal_range("b");
+
+ THEN("it returns an iterator pair to the element")
+ {
+ REQUIRE(begin == map.begin());
+ REQUIRE(end == map.begin() + 1);
+ }
+ }
+
+ WHEN("fiding the equal range of a key between two elements in the map")
+ {
+ auto [begin, end] = map.equal_range("c");
+
+ THEN("it returns an iterator pair to the element")
+ {
+ REQUIRE(begin->first == "d");
+ REQUIRE(end->first == "d");
+ }
+ }
+
+ WHEN("fiding the equal range of a key outside the elements of the map")
+ {
+ auto [begin, end] = map.equal_range("g");
+
+ THEN("it returns an iterator pair to the element")
+ {
+ REQUIRE(begin == map.end());
+ REQUIRE(end == map.end());
+ }
+ }
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2026-08-30 09:43:23 +0000