1 | // |
2 | // immer: immutable data structures for C++ |
3 | // Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente |
4 | // |
5 | // This software is distributed under the Boost Software License, Version 1.0. |
6 | // See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt |
7 | // |
8 | |
9 | #pragma once |
10 | |
11 | #include <immer/memory_policy.hpp> |
12 | #include <immer/detail/hamts/champ.hpp> |
13 | #include <immer/detail/hamts/champ_iterator.hpp> |
14 | |
15 | #include <functional> |
16 | |
17 | namespace immer { |
18 | |
19 | template <typename K, |
20 | typename T, |
21 | typename Hash, |
22 | typename Equal, |
23 | typename MemoryPolicy, |
24 | detail::hamts::bits_t B> |
25 | class map_transient; |
26 | |
27 | /*! |
28 | * Immutable unordered mapping of values from type `K` to type `T`. |
29 | * |
30 | * @tparam K The type of the keys. |
31 | * @tparam T The type of the values to be stored in the container. |
32 | * @tparam Hash The type of a function object capable of hashing |
33 | * values of type `T`. |
34 | * @tparam Equal The type of a function object capable of comparing |
35 | * values of type `T`. |
36 | * @tparam MemoryPolicy Memory management policy. See @ref |
37 | * memory_policy. |
38 | * |
39 | * @rst |
40 | * |
41 | * This cotainer provides a good trade-off between cache locality, |
42 | * search, update performance and structural sharing. It does so by |
43 | * storing the data in contiguous chunks of :math:`2^{B}` elements. |
44 | * When storing big objects, the size of these contiguous chunks can |
45 | * become too big, damaging performance. If this is measured to be |
46 | * problematic for a specific use-case, it can be solved by using a |
47 | * `immer::box` to wrap the type `T`. |
48 | * |
49 | * **Example** |
50 | * .. literalinclude:: ../example/map/intro.cpp |
51 | * :language: c++ |
52 | * :start-after: intro/start |
53 | * :end-before: intro/end |
54 | * |
55 | * @endrst |
56 | * |
57 | */ |
58 | template <typename K, |
59 | typename T, |
60 | typename Hash = std::hash<K>, |
61 | typename Equal = std::equal_to<K>, |
62 | typename MemoryPolicy = default_memory_policy, |
63 | detail::hamts::bits_t B = default_bits> |
64 | class map |
65 | { |
66 | using value_t = std::pair<K, T>; |
67 | |
68 | struct project_value |
69 | { |
70 | const T& operator() (const value_t& v) const noexcept |
71 | { |
72 | return v.second; |
73 | } |
74 | }; |
75 | |
76 | struct project_value_ptr |
77 | { |
78 | const T* operator() (const value_t& v) const noexcept |
79 | { |
80 | return &v.second; |
81 | } |
82 | }; |
83 | |
84 | struct combine_value |
85 | { |
86 | template <typename Kf, typename Tf> |
87 | value_t operator() (Kf&& k, Tf&& v) const |
88 | { |
89 | return { std::forward<Kf>(k), std::forward<Tf>(v) }; |
90 | } |
91 | }; |
92 | |
93 | struct default_value |
94 | { |
95 | const T& operator() () const |
96 | { |
97 | static T v{}; |
98 | return v; |
99 | } |
100 | }; |
101 | |
102 | struct error_value |
103 | { |
104 | const T& operator() () const |
105 | { |
106 | throw std::out_of_range{"key not found" }; |
107 | } |
108 | }; |
109 | |
110 | struct hash_key |
111 | { |
112 | auto operator() (const value_t& v) |
113 | { return Hash{}(v.first); } |
114 | |
115 | auto operator() (const K& v) |
116 | { return Hash{}(v); } |
117 | }; |
118 | |
119 | struct equal_key |
120 | { |
121 | auto operator() (const value_t& a, const value_t& b) |
122 | { return Equal{}(a.first, b.first); } |
123 | |
124 | auto operator() (const value_t& a, const K& b) |
125 | { return Equal{}(a.first, b); } |
126 | }; |
127 | |
128 | struct equal_value |
129 | { |
130 | auto operator() (const value_t& a, const value_t& b) |
131 | { return Equal{}(a.first, b.first) && a.second == b.second; } |
132 | }; |
133 | |
134 | using impl_t = detail::hamts::champ< |
135 | value_t, hash_key, equal_key, MemoryPolicy, B>; |
136 | |
137 | public: |
138 | using key_type = K; |
139 | using mapped_type = T; |
140 | using value_type = std::pair<K, T>; |
141 | using size_type = detail::hamts::size_t; |
142 | using diference_type = std::ptrdiff_t; |
143 | using hasher = Hash; |
144 | using key_equal = Equal; |
145 | using reference = const value_type&; |
146 | using const_reference = const value_type&; |
147 | |
148 | using iterator = detail::hamts::champ_iterator< |
149 | value_t, hash_key, equal_key, MemoryPolicy, B>; |
150 | using const_iterator = iterator; |
151 | |
152 | using transient_type = map_transient<K, T, Hash, Equal, MemoryPolicy, B>; |
153 | |
154 | /*! |
155 | * Default constructor. It creates a set of `size() == 0`. It |
156 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
157 | */ |
158 | map() = default; |
159 | |
160 | /*! |
161 | * Returns an iterator pointing at the first element of the |
162 | * collection. It does not allocate memory and its complexity is |
163 | * @f$ O(1) @f$. |
164 | */ |
165 | IMMER_NODISCARD iterator begin() const { return {impl_}; } |
166 | |
167 | /*! |
168 | * Returns an iterator pointing just after the last element of the |
169 | * collection. It does not allocate and its complexity is @f$ O(1) @f$. |
170 | */ |
171 | IMMER_NODISCARD iterator end() const { return {impl_, typename iterator::end_t{}}; } |
172 | |
173 | /*! |
174 | * Returns the number of elements in the container. It does |
175 | * not allocate memory and its complexity is @f$ O(1) @f$. |
176 | */ |
177 | IMMER_NODISCARD size_type size() const { return impl_.size; } |
178 | |
179 | /*! |
180 | * Returns `true` if there are no elements in the container. It |
181 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
182 | */ |
183 | IMMER_NODISCARD bool empty() const { return impl_.size == 0; } |
184 | |
185 | /*! |
186 | * Returns `1` when the key `k` is contained in the map or `0` |
187 | * otherwise. It won't allocate memory and its complexity is |
188 | * *effectively* @f$ O(1) @f$. |
189 | */ |
190 | IMMER_NODISCARD size_type count(const K& k) const |
191 | { return impl_.template get<detail::constantly<size_type, 1>, |
192 | detail::constantly<size_type, 0>>(k); } |
193 | |
194 | /*! |
195 | * Returns a `const` reference to the values associated to the key |
196 | * `k`. If the key is not contained in the map, it returns a |
197 | * default constructed value. It does not allocate memory and its |
198 | * complexity is *effectively* @f$ O(1) @f$. |
199 | */ |
200 | IMMER_NODISCARD const T& operator[] (const K& k) const |
201 | { return impl_.template get<project_value, default_value>(k); } |
202 | |
203 | /*! |
204 | * Returns a `const` reference to the values associated to the key |
205 | * `k`. If the key is not contained in the map, throws an |
206 | * `std::out_of_range` error. It does not allocate memory and its |
207 | * complexity is *effectively* @f$ O(1) @f$. |
208 | */ |
209 | const T& at(const K& k) const |
210 | { return impl_.template get<project_value, error_value>(k); } |
211 | |
212 | |
213 | /*! |
214 | * Returns a pointer to the value associated with the key `k`. If |
215 | * the key is not contained in the map, a `nullptr` is returned. |
216 | * It does not allocate memory and its complexity is *effectively* |
217 | * @f$ O(1) @f$. |
218 | * |
219 | * @rst |
220 | * |
221 | * .. admonition:: Why doesn't this function return an iterator? |
222 | * |
223 | * Associative containers from the C++ standard library provide a |
224 | * ``find`` method that returns an iterator pointing to the |
225 | * element in the container or ``end()`` when the key is missing. |
226 | * In the case of an unordered container, the only meaningful |
227 | * thing one may do with it is to compare it with the end, to |
228 | * test if the find was succesfull, and dereference it. This |
229 | * comparison is cumbersome compared to testing for a non-empty |
230 | * optional value. Furthermore, for an immutable container, |
231 | * returning an iterator would have some additional performance |
232 | * cost, with no benefits otherwise. |
233 | * |
234 | * In our opinion, this function should return a |
235 | * ``std::optional<const T&>`` but this construction is not valid |
236 | * in any current standard. As a compromise we return a |
237 | * pointer, which has similar syntactic properties yet it is |
238 | * unfortunatelly unnecessarily unrestricted. |
239 | * |
240 | * @endrst |
241 | */ |
242 | IMMER_NODISCARD const T* find(const K& k) const |
243 | { return impl_.template get<project_value_ptr, |
244 | detail::constantly<const T*, nullptr>>(k); } |
245 | |
246 | /*! |
247 | * Returns whether the sets are equal. |
248 | */ |
249 | IMMER_NODISCARD bool operator==(const map& other) const |
250 | { return impl_.template equals<equal_value>(other.impl_); } |
251 | IMMER_NODISCARD bool operator!=(const map& other) const |
252 | { return !(*this == other); } |
253 | |
254 | /*! |
255 | * Returns a map containing the association `value`. If the key is |
256 | * already in the map, it replaces its association in the map. |
257 | * It may allocate memory and its complexity is *effectively* @f$ |
258 | * O(1) @f$. |
259 | */ |
260 | IMMER_NODISCARD map insert(value_type value) const |
261 | { return impl_.add(std::move(value)); } |
262 | |
263 | /*! |
264 | * Returns a map containing the association `(k, v)`. If the key |
265 | * is already in the map, it replaces its association in the map. |
266 | * It may allocate memory and its complexity is *effectively* @f$ |
267 | * O(1) @f$. |
268 | */ |
269 | IMMER_NODISCARD map set(key_type k, mapped_type v) const |
270 | { return impl_.add({std::move(k), std::move(v)}); } |
271 | |
272 | /*! |
273 | * Returns a map replacing the association `(k, v)` by the |
274 | * association new association `(k, fn(v))`, where `v` is the |
275 | * currently associated value for `k` in the map or a default |
276 | * constructed value otherwise. It may allocate memory |
277 | * and its complexity is *effectively* @f$ O(1) @f$. |
278 | */ |
279 | template <typename Fn> |
280 | IMMER_NODISCARD map update(key_type k, Fn&& fn) const |
281 | { |
282 | return impl_ |
283 | .template update<project_value, default_value, combine_value>( |
284 | std::move(k), std::forward<Fn>(fn)); |
285 | } |
286 | |
287 | /*! |
288 | * Returns a map without the key `k`. If the key is not |
289 | * associated in the map it returns the same map. It may allocate |
290 | * memory and its complexity is *effectively* @f$ O(1) @f$. |
291 | */ |
292 | IMMER_NODISCARD map erase(const K& k) const |
293 | { return impl_.sub(k); } |
294 | |
295 | /*! |
296 | * Returns an @a transient form of this container, a |
297 | * `immer::map_transient`. |
298 | */ |
299 | IMMER_NODISCARD transient_type transient() const& |
300 | { return transient_type{ impl_ }; } |
301 | IMMER_NODISCARD transient_type transient() && |
302 | { return transient_type{ std::move(impl_) }; } |
303 | |
304 | // Semi-private |
305 | const impl_t& impl() const { return impl_; } |
306 | |
307 | private: |
308 | friend transient_type; |
309 | |
310 | map(impl_t impl) |
311 | : impl_(std::move(impl)) |
312 | {} |
313 | |
314 | impl_t impl_ = impl_t::empty(); |
315 | }; |
316 | |
317 | } // namespace immer |
318 | |