MayaFlux 1.0.0
Digital-First Multimedia Processing Framework
Loading...
Searching...
No Matches
FlatMap.hpp
Go to the documentation of this file.
1#pragma once
2
3namespace MayaFlux::Memory {
4
5/**
6 * @class FlatMap
7 * @brief Map kept as one sorted vector, cheap to copy.
8 *
9 * Meant as the value of a SnapshotCell, which copies the whole value on every
10 * update. Lookup is a binary search, and insert and erase shift the tail, so it
11 * suits maps of up to a few thousand entries that are read far more often than
12 * they change.
13 *
14 * Iteration is in key order. Insert and erase invalidate iterators.
15 *
16 * @tparam K Key type.
17 * @tparam V Mapped type.
18 * @tparam Compare Strict weak ordering on K.
19 */
20template <typename K, typename V, typename Compare = std::less<K>>
21class FlatMap {
22public:
23 using value_type = std::pair<K, V>;
24 using const_iterator = typename std::vector<value_type>::const_iterator;
25
26 [[nodiscard]] const_iterator begin() const noexcept { return m_items.begin(); }
27 [[nodiscard]] const_iterator end() const noexcept { return m_items.end(); }
28 [[nodiscard]] size_t size() const noexcept { return m_items.size(); }
29 [[nodiscard]] bool empty() const noexcept { return m_items.empty(); }
30
31 /** @brief The entry for @p key, or end() when absent. */
32 [[nodiscard]] const_iterator find(const K& key) const
33 {
34 const size_t index = lower_index(key);
35 return index < m_items.size() && !m_less(key, m_items[index].first)
36 ? m_items.begin() + static_cast<std::ptrdiff_t>(index)
37 : m_items.end();
38 }
39
40 /**
41 * @brief Sets the value for @p key, adding the entry if it is absent.
42 * @return true if the entry was added, false if an existing one was overwritten.
43 */
44 bool insert_or_assign(const K& key, V value)
45 {
46 const size_t index = lower_index(key);
47 if (index < m_items.size() && !m_less(key, m_items[index].first)) {
48 m_items[index].second = std::move(value);
49 return false;
50 }
51 m_items.insert(m_items.begin() + static_cast<std::ptrdiff_t>(index), value_type(key, std::move(value)));
52 return true;
53 }
54
55 /**
56 * @brief The entry for a key of another type, or end() when absent.
57 *
58 * Available when the comparator is transparent, such as std::less<>, so a
59 * std::string_view or a literal finds a std::string key without making one.
60 */
61 template <typename Q>
62 requires(!std::same_as<Q, K> && requires { typename Compare::is_transparent; })
63 [[nodiscard]] const_iterator find(const Q& key) const
64 {
65 const size_t index = lower_index(key);
66 return index < m_items.size() && !m_less(key, m_items[index].first)
67 ? m_items.begin() + static_cast<std::ptrdiff_t>(index)
68 : m_items.end();
69 }
70
71 /** @brief Removes the entry for @p key. @return true if there was one. */
72 bool erase(const K& key)
73 {
74 const size_t index = lower_index(key);
75 if (index >= m_items.size() || m_less(key, m_items[index].first)) {
76 return false;
77 }
78 m_items.erase(m_items.begin() + static_cast<std::ptrdiff_t>(index));
79 return true;
80 }
81
82 /** @brief Removes the entry for a key of another type, as find does for lookup. */
83 template <typename Q>
84 requires(!std::same_as<Q, K> && requires { typename Compare::is_transparent; })
85 bool erase(const Q& key)
86 {
87 const size_t index = lower_index(key);
88 if (index >= m_items.size() || m_less(key, m_items[index].first)) {
89 return false;
90 }
91 m_items.erase(m_items.begin() + static_cast<std::ptrdiff_t>(index));
92 return true;
93 }
94
95 /**
96 * @brief Adds every entry of @p other under a name prefix.
97 *
98 * For maps keyed by name, so a catalog can be combined with another without
99 * their names colliding.
100 *
101 * @param prefix Prepended to each key; empty keeps the keys.
102 * @param error Receives the first colliding name when false is returned.
103 * @param replace True to overwrite existing entries instead of failing.
104 * @return true on success. A failed merge leaves this map unchanged.
105 */
106 bool merge_prefixed(const FlatMap& other, std::string_view prefix,
107 std::string& error, bool replace = false)
108 requires std::same_as<K, std::string>
109 {
110 if (!replace) {
111 for (const auto& entry : other.m_items) {
112 const std::string target = std::string(prefix) + entry.first;
113 if (find(target) != end()) {
114 error = "already has an entry named " + target;
115 return false;
116 }
117 }
118 }
119 for (const auto& entry : other.m_items) {
120 insert_or_assign(std::string(prefix) + entry.first, entry.second);
121 }
122 return true;
123 }
124
125 void clear() noexcept { m_items.clear(); }
126
127private:
128 template <typename Q = K>
129 [[nodiscard]] size_t lower_index(const Q& key) const
130 {
131 const auto it = std::ranges::lower_bound(m_items, key, m_less, &value_type::first);
132 return static_cast<size_t>(it - m_items.begin());
133 }
134
135 std::vector<value_type> m_items;
136 [[no_unique_address]] Compare m_less {};
137};
138
139} // namespace MayaFlux::Memory
size_t size() const noexcept
Definition FlatMap.hpp:28
size_t lower_index(const Q &key) const
Definition FlatMap.hpp:129
void clear() noexcept
Definition FlatMap.hpp:125
bool empty() const noexcept
Definition FlatMap.hpp:29
const_iterator end() const noexcept
Definition FlatMap.hpp:27
bool insert_or_assign(const K &key, V value)
Sets the value for key, adding the entry if it is absent.
Definition FlatMap.hpp:44
std::pair< VkDeviceMemory, vk::DeviceSize > value_type
Definition FlatMap.hpp:23
bool merge_prefixed(const FlatMap &other, std::string_view prefix, std::string &error, bool replace=false)
Adds every entry of other under a name prefix.
Definition FlatMap.hpp:106
const_iterator find(const K &key) const
The entry for key, or end() when absent.
Definition FlatMap.hpp:32
typename std::vector< value_type >::const_iterator const_iterator
Definition FlatMap.hpp:24
bool erase(const K &key)
Removes the entry for key.
Definition FlatMap.hpp:72
const_iterator find(const Q &key) const
The entry for a key of another type, or end() when absent.
Definition FlatMap.hpp:63
const_iterator begin() const noexcept
Definition FlatMap.hpp:26
bool erase(const Q &key)
Removes the entry for a key of another type, as find does for lookup.
Definition FlatMap.hpp:85
Map kept as one sorted vector, cheap to copy.
Definition FlatMap.hpp:21