Line data Source code
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/config.hpp>
12 : #include <immer/detail/hamts/champ.hpp>
13 : #include <immer/detail/hamts/champ_iterator.hpp>
14 : #include <immer/memory_policy.hpp>
15 :
16 : #include <cassert>
17 : #include <stdexcept>
18 : #include <functional>
19 :
20 : namespace immer {
21 :
22 : template <typename K,
23 : typename T,
24 : typename Hash,
25 : typename Equal,
26 : typename MemoryPolicy,
27 : detail::hamts::bits_t B>
28 : class map_transient;
29 :
30 : /*!
31 : * Immutable unordered mapping of values from type `K` to type `T`.
32 : *
33 : * @tparam K The type of the keys.
34 : * @tparam T The type of the values to be stored in the container.
35 : * @tparam Hash The type of a function object capable of hashing
36 : * values of type `T`.
37 : * @tparam Equal The type of a function object capable of comparing
38 : * values of type `T`.
39 : * @tparam MemoryPolicy Memory management policy. See @ref
40 : * memory_policy.
41 : *
42 : * @rst
43 : *
44 : * This cotainer provides a good trade-off between cache locality,
45 : * search, update performance and structural sharing. It does so by
46 : * storing the data in contiguous chunks of :math:`2^{B}` elements.
47 : * When storing big objects, the size of these contiguous chunks can
48 : * become too big, damaging performance. If this is measured to be
49 : * problematic for a specific use-case, it can be solved by using a
50 : * `immer::box` to wrap the type `T`.
51 : *
52 : * **Example**
53 : * .. literalinclude:: ../example/map/intro.cpp
54 : * :language: c++
55 : * :start-after: intro/start
56 : * :end-before: intro/end
57 : *
58 : * @endrst
59 : *
60 : */
61 : template <typename K,
62 : typename T,
63 : typename Hash = std::hash<K>,
64 : typename Equal = std::equal_to<K>,
65 : typename MemoryPolicy = default_memory_policy,
66 : detail::hamts::bits_t B = default_bits>
67 56451 : class map
68 : {
69 : using value_t = std::pair<K, T>;
70 :
71 : struct project_value
72 : {
73 : const T& operator()(const value_t& v) const noexcept
74 : {
75 : return v.second;
76 : }
77 : };
78 :
79 : struct project_value_ptr
80 : {
81 196588 : const T* operator()(const value_t& v) const noexcept
82 : {
83 196588 : return &v.second;
84 : }
85 : };
86 :
87 : struct combine_value
88 : {
89 : template <typename Kf, typename Tf>
90 : value_t operator()(Kf&& k, Tf&& v) const
91 : {
92 : return {std::forward<Kf>(k), std::forward<Tf>(v)};
93 : }
94 : };
95 :
96 : struct default_value
97 : {
98 : const T& operator()() const
99 : {
100 : static T v{};
101 : return v;
102 : }
103 : };
104 :
105 : struct error_value
106 : {
107 : const T& operator()() const
108 : {
109 : IMMER_THROW(std::out_of_range{"key not found"});
110 : }
111 : };
112 :
113 : struct hash_key
114 : {
115 29900 : auto operator()(const value_t& v) { return Hash{}(v.first); }
116 :
117 : template<typename Key>
118 767368 : auto operator()(const Key& v) { return Hash{}(v); }
119 : };
120 :
121 : struct equal_key
122 : {
123 23310 : auto operator()(const value_t& a, const value_t& b)
124 : {
125 23310 : return Equal{}(a.first, b.first);
126 : }
127 :
128 : template<typename Key>
129 447 : auto operator()(const value_t& a, const Key& b)
130 : {
131 228275 : return Equal{}(a.first, b);
132 : }
133 : };
134 :
135 : struct equal_value
136 : {
137 : auto operator()(const value_t& a, const value_t& b)
138 : {
139 : return Equal{}(a.first, b.first) && a.second == b.second;
140 : }
141 : };
142 :
143 : using impl_t =
144 : detail::hamts::champ<value_t, hash_key, equal_key, MemoryPolicy, B>;
145 :
146 : public:
147 : using key_type = K;
148 : using mapped_type = T;
149 : using value_type = std::pair<K, T>;
150 : using size_type = detail::hamts::size_t;
151 : using diference_type = std::ptrdiff_t;
152 : using hasher = Hash;
153 : using key_equal = Equal;
154 : using reference = const value_type&;
155 : using const_reference = const value_type&;
156 :
157 : using iterator = detail::hamts::
158 : champ_iterator<value_t, hash_key, equal_key, MemoryPolicy, B>;
159 : using const_iterator = iterator;
160 :
161 : using transient_type = map_transient<K, T, Hash, Equal, MemoryPolicy, B>;
162 :
163 : /*!
164 : * Default constructor. It creates a set of `size() == 0`. It
165 : * does not allocate memory and its complexity is @f$ O(1) @f$.
166 : */
167 415729 : map() = default;
168 :
169 : /*!
170 : * Returns an iterator pointing at the first element of the
171 : * collection. It does not allocate memory and its complexity is
172 : * @f$ O(1) @f$.
173 : */
174 79356 : IMMER_NODISCARD iterator begin() const { return {impl_}; }
175 :
176 : /*!
177 : * Returns an iterator pointing just after the last element of the
178 : * collection. It does not allocate and its complexity is @f$ O(1) @f$.
179 : */
180 79356 : IMMER_NODISCARD iterator end() const
181 : {
182 79356 : return {impl_, typename iterator::end_t{}};
183 : }
184 :
185 : /*!
186 : * Returns the number of elements in the container. It does
187 : * not allocate memory and its complexity is @f$ O(1) @f$.
188 : */
189 23594 : IMMER_NODISCARD size_type size() const { return impl_.size; }
190 :
191 : /*!
192 : * Returns `true` if there are no elements in the container. It
193 : * does not allocate memory and its complexity is @f$ O(1) @f$.
194 : */
195 : IMMER_NODISCARD bool empty() const { return impl_.size == 0; }
196 :
197 : /*!
198 : * Returns `1` when the key `k` is contained in the map or `0`
199 : * otherwise. It won't allocate memory and its complexity is
200 : * *effectively* @f$ O(1) @f$.
201 : *
202 : * This overload participates in overload resolution only if
203 : * `Hash::is_transparent` is valid and denotes a type.
204 : */
205 : template<typename Key, typename U = Hash, typename = typename U::is_transparent>
206 : IMMER_NODISCARD size_type count(const Key& k) const
207 : {
208 : return impl_.template get<detail::constantly<size_type, 1>,
209 : detail::constantly<size_type, 0>>(k);
210 : }
211 :
212 : /*!
213 : * Returns `1` when the key `k` is contained in the map or `0`
214 : * otherwise. It won't allocate memory and its complexity is
215 : * *effectively* @f$ O(1) @f$.
216 : */
217 29629 : IMMER_NODISCARD size_type count(const K& k) const
218 : {
219 : return impl_.template get<detail::constantly<size_type, 1>,
220 29629 : detail::constantly<size_type, 0>>(k);
221 : }
222 :
223 : /*!
224 : * Returns a `const` reference to the values associated to the key
225 : * `k`. If the key is not contained in the map, it returns a
226 : * default constructed value. It does not allocate memory and its
227 : * complexity is *effectively* @f$ O(1) @f$.
228 : *
229 : * This overload participates in overload resolution only if
230 : * `Hash::is_transparent` is valid and denotes a type.
231 : */
232 : template<typename Key, typename U = Hash, typename = typename U::is_transparent>
233 : IMMER_NODISCARD const T& operator[](const Key& k) const
234 : {
235 : return impl_.template get<project_value, default_value>(k);
236 : }
237 :
238 : /*!
239 : * Returns a `const` reference to the values associated to the key
240 : * `k`. If the key is not contained in the map, it returns a
241 : * default constructed value. It does not allocate memory and its
242 : * complexity is *effectively* @f$ O(1) @f$.
243 : */
244 : IMMER_NODISCARD const T& operator[](const K& k) const
245 : {
246 : return impl_.template get<project_value, default_value>(k);
247 : }
248 :
249 : /*!
250 : * Returns a `const` reference to the values associated to the key
251 : * `k`. If the key is not contained in the map, throws an
252 : * `std::out_of_range` error. It does not allocate memory and its
253 : * complexity is *effectively* @f$ O(1) @f$.
254 : */
255 : template<typename Key, typename U = Hash, typename = typename U::is_transparent>
256 : const T& at(const Key& k) const
257 : {
258 : return impl_.template get<project_value, error_value>(k);
259 : }
260 :
261 : /*!
262 : * Returns a `const` reference to the values associated to the key
263 : * `k`. If the key is not contained in the map, throws an
264 : * `std::out_of_range` error. It does not allocate memory and its
265 : * complexity is *effectively* @f$ O(1) @f$.
266 : *
267 : * This overload participates in overload resolution only if
268 : * `Hash::is_transparent` is valid and denotes a type.
269 : */
270 : const T& at(const K& k) const
271 : {
272 : return impl_.template get<project_value, error_value>(k);
273 : }
274 :
275 : /*!
276 : * Returns a pointer to the value associated with the key `k`. If
277 : * the key is not contained in the map, a `nullptr` is returned.
278 : * It does not allocate memory and its complexity is *effectively*
279 : * @f$ O(1) @f$.
280 : *
281 : * @rst
282 : *
283 : * .. admonition:: Why doesn't this function return an iterator?
284 : *
285 : * Associative containers from the C++ standard library provide a
286 : * ``find`` method that returns an iterator pointing to the
287 : * element in the container or ``end()`` when the key is missing.
288 : * In the case of an unordered container, the only meaningful
289 : * thing one may do with it is to compare it with the end, to
290 : * test if the find was succesfull, and dereference it. This
291 : * comparison is cumbersome compared to testing for a non-empty
292 : * optional value. Furthermore, for an immutable container,
293 : * returning an iterator would have some additional performance
294 : * cost, with no benefits otherwise.
295 : *
296 : * In our opinion, this function should return a
297 : * ``std::optional<const T&>`` but this construction is not valid
298 : * in any current standard. As a compromise we return a
299 : * pointer, which has similar syntactic properties yet it is
300 : * unfortunatelly unnecessarily unrestricted.
301 : *
302 : * @endrst
303 : */
304 737292 : IMMER_NODISCARD const T* find(const K& k) const
305 : {
306 : return impl_.template get<project_value_ptr,
307 737292 : detail::constantly<const T*, nullptr>>(k);
308 : }
309 :
310 :
311 : /*!
312 : * Returns a pointer to the value associated with the key `k`. If
313 : * the key is not contained in the map, a `nullptr` is returned.
314 : * It does not allocate memory and its complexity is *effectively*
315 : * @f$ O(1) @f$.
316 : *
317 : * This overload participates in overload resolution only if
318 : * `Hash::is_transparent` is valid and denotes a type.
319 : */
320 : template<typename Key, typename U = Hash, typename = typename U::is_transparent>
321 : IMMER_NODISCARD const T* find(const Key& k) const
322 : {
323 : return impl_.template get<project_value_ptr,
324 : detail::constantly<const T*, nullptr>>(k);
325 : }
326 :
327 : /*!
328 : * Returns whether the sets are equal.
329 : */
330 : IMMER_NODISCARD bool operator==(const map& other) const
331 : {
332 : return impl_.template equals<equal_value>(other.impl_);
333 : }
334 : IMMER_NODISCARD bool operator!=(const map& other) const
335 : {
336 : return !(*this == other);
337 : }
338 :
339 : /*!
340 : * Returns a map containing the association `value`. If the key is
341 : * already in the map, it replaces its association in the map.
342 : * It may allocate memory and its complexity is *effectively* @f$
343 : * O(1) @f$.
344 : */
345 : IMMER_NODISCARD map insert(value_type value) const
346 : {
347 : return impl_.add(std::move(value));
348 : }
349 :
350 : /*!
351 : * Returns a map containing the association `(k, v)`. If the key
352 : * is already in the map, it replaces its association in the map.
353 : * It may allocate memory and its complexity is *effectively* @f$
354 : * O(1) @f$.
355 : */
356 28564 : IMMER_NODISCARD map set(key_type k, mapped_type v) const
357 : {
358 57128 : return impl_.add({std::move(k), std::move(v)});
359 : }
360 :
361 : /*!
362 : * Returns a map replacing the association `(k, v)` by the
363 : * association new association `(k, fn(v))`, where `v` is the
364 : * currently associated value for `k` in the map or a default
365 : * constructed value otherwise. It may allocate memory
366 : * and its complexity is *effectively* @f$ O(1) @f$.
367 : */
368 : template <typename Fn>
369 : IMMER_NODISCARD map update(key_type k, Fn&& fn) const
370 : {
371 : return impl_
372 : .template update<project_value, default_value, combine_value>(
373 : std::move(k), std::forward<Fn>(fn));
374 : }
375 :
376 : /*!
377 : * Returns a map without the key `k`. If the key is not
378 : * associated in the map it returns the same map. It may allocate
379 : * memory and its complexity is *effectively* @f$ O(1) @f$.
380 : */
381 894 : IMMER_NODISCARD map erase(const K& k) const { return impl_.sub(k); }
382 :
383 : /*!
384 : * Returns an @a transient form of this container, a
385 : * `immer::map_transient`.
386 : */
387 : IMMER_NODISCARD transient_type transient() const&
388 : {
389 : return transient_type{impl_};
390 : }
391 : IMMER_NODISCARD transient_type transient() &&
392 : {
393 : return transient_type{std::move(impl_)};
394 : }
395 :
396 : // Semi-private
397 : const impl_t& impl() const { return impl_; }
398 :
399 : private:
400 : friend transient_type;
401 :
402 29011 : map(impl_t impl)
403 29011 : : impl_(std::move(impl))
404 : {}
405 :
406 : impl_t impl_ = impl_t::empty();
407 : };
408 :
409 : } // namespace immer
|
