-
Notifications
You must be signed in to change notification settings - Fork 3
/
constexpr_hash_map.hpp
175 lines (152 loc) · 6.51 KB
/
constexpr_hash_map.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#ifndef CONSTEXPR_HASH_MAP_CONSTEXPR_HASH_MAP_HPP
#define CONSTEXPR_HASH_MAP_CONSTEXPR_HASH_MAP_HPP
#include <array>
#include <cstddef>
#include <iterator>
#include <utility>
namespace burda::ct
{
/// @brief Compile-time hash-map (associative key-value container) that performs all operations in constexpr context.
/// This means that keys and values have to be constexpr and noexcept constructible and provide constexpr noexcept operator=.
/// @brief Behaviour is undefined, if there are multiple same keys.
/// @brief There's actually no hash function needed, see details section.
/// @details Implemented as an std::array containing pairs, so no hashing is involved.
/// @tparam N total number of elements
/// @tparam K data type for keys
/// @tparam V data type for values
template <std::size_t N, typename K, typename V>
class hash_map
{
public:
/// @see std::unordered_map<...>::key_type
using key_type = K;
/// @see std::unordered_map<...>::value_type
using value_type = V;
/// @see std::unordered_map<...>::size_type
using size_type = decltype(N);
/// @brief underlying structure used for the actual implementation
using data_type = std::array<std::pair<K, V>, N>;
/// @see std::array<...>::const_iterator
using const_iterator = typename data_type::const_iterator;
/// @brief The only construction that might be used, all keys and values must be provided in the constructor.
/// @tparam R variadic arguments automatically deduced by the compiler
/// @param elements series of std::pair<K, V>, cannot be empty
template<typename... E>
explicit constexpr hash_map(E&&... elements) noexcept
: data{std::forward<E>(elements)...}
{
static_assert(N > 0, "N should be positive");
static_assert(N == sizeof...(elements), "Elements size doesn't match expected size of a hash-map");
}
/// @brief Searches map for a given key and returns iterator.
/// @param key key to be searched for
/// @return constant iterator to an element (cend, if not found)
[[nodiscard]] constexpr const_iterator find(const K& key) const noexcept
{
return search<0, N>(key);
}
/// @brief Searches for a given key, aimed to return associated value with it.
/// @param key key to be searched for
/// @return pair, where first denotes whether element was found, second given value
/// @details Deliberately not throwing an exception, and returning pair instead,
/// as this generates much shorter assembly on clang and msvc
[[nodiscard]] constexpr std::pair<bool, const V&> at(const K& key) const noexcept
{
const auto it = find(key);
if (it != cend())
{
return {true, it->second};
}
return {false, {}};
}
/// @brief Retrieves reference to constant to a value.
/// Doesn't perform any bounds checking, behaviour is undefined if the key doesn't exist.
/// @param key key to be searched for
/// @return reference to constant to a value associated with the key
// NOLINTNEXTLINE(fuchsia-overloaded-operator)
[[nodiscard]] constexpr const V& operator[](const K& key) const noexcept
{
return find(key)->second;
}
/// @brief Checks if element with given key exists.
/// @param key key to be searched for
/// @return boolean that denotes key's existence
[[nodiscard]] constexpr bool contains(const K& key) const noexcept
{
return search<0, N>(key) != cend();
}
/// @brief Retrieves size of a hash-map, might also be called indirectly using the std::size(...).
/// @return total size of a container
[[nodiscard]] constexpr size_type size() const noexcept
{
return data.size();
}
/// @brief Gives constant iterator to a beginning, needed for the C++11 for-each cycle or the std::for_each.
/// @return constant iterator to a beginning
/// @see cbegin()
[[nodiscard]] constexpr const_iterator begin() const noexcept
{
return cbegin();
}
/// @brief Gives constant iterator to a beginning, might be also called using std::cbegin(...).
/// @return constant iterator to a beginning
/// @see std::unordered_map<...>::cbegin()
[[nodiscard]] constexpr const_iterator cbegin() const noexcept
{
return std::cbegin(data);
}
/// @brief Gives constant iterator to an end, needed for the C++11 for-each cycle or the std::for_each.
/// @return constant iterator to an end (past the last element)
/// @see cend()
[[nodiscard]] constexpr const_iterator end() const noexcept
{
return cend();
}
/// @brief Gives constant iterator to a beginning, might be also called using std::cend(...).
/// @return constant iterator to an end (past the last element)
/// @see std::unordered_map<...>::cend()
[[nodiscard]] constexpr const_iterator cend() const noexcept
{
return std::cend(data);
}
/// @brief Hash-map cannot be empty; this might also be called using std::empty(...).
/// @return false -- cannot be empty
/// @see std::unordered_map<...>::empty()
[[nodiscard]] constexpr bool empty() const noexcept
{
return false;
}
protected:
/// @private type used for indexing elements
using index_type = size_type;
/// @private function that does a constexpr recursive searching of the array from left to right
template <index_type L, index_type R>
[[nodiscard]] constexpr const_iterator search(const K& key) const noexcept
{
if constexpr (L < R)
{
if (equal(data[L].first, key))
{
return std::next(cbegin(), L);
}
return search<L+1, R>(key);
}
return cend();
}
/// @private generic implementation that compares keys
template <typename T = K>
[[nodiscard]] constexpr bool equal(const T& lhs, const T& rhs) const noexcept
{
return lhs == rhs;
}
/// @private specific implementation for "const char*" equality is needed; uses recursion
[[nodiscard]] constexpr bool equal(const char* lhs, const char* rhs) const noexcept
{
// NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
return *lhs == *rhs && (*lhs == '\0' || equal(lhs + 1, rhs + 1));
}
private:
data_type data;
};
} // namespace burda::ct
#endif // CONSTEXPR_HASH_MAP_CONSTEXPR_HASH_MAP_HPP