array-hash
array_map.h
Go to the documentation of this file.
1 /**
2  * MIT License
3  *
4  * Copyright (c) 2017 Tessil
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a copy
7  * of this software and associated documentation files (the "Software"), to deal
8  * in the Software without restriction, including without limitation the rights
9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10  * copies of the Software, and to permit persons to whom the Software is
11  * furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in all
14  * copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  * SOFTWARE.
23  */
24 #ifndef TSL_ARRAY_MAP_H
25 #define TSL_ARRAY_MAP_H
26 
27 #include <cstddef>
28 #include <cstdint>
29 #include <initializer_list>
30 #include <iterator>
31 #include <string>
32 #include <type_traits>
33 #include <utility>
34 #include "array_hash.h"
35 
36 namespace tsl {
37 
38 
39 /**
40  * Implementation of a cache-conscious string hash map.
41  *
42  * The map stores the strings as `const CharT*`. If `StoreNullTerminator` is true,
43  * the strings are stored with the a null-terminator (the `key()` method of the iterators
44  * will return a pointer to this null-terminated string). Otherwise the null character
45  * is not stored (which allow an economy of 1 byte per string).
46  *
47  * The value `T` must be either nothrow move-constructible, copy-constuctible or both.
48  *
49  * The size of a key string is limited to `std::numeric_limits<KeySizeT>::max() - 1`.
50  * That is 65 535 characters by default, but can be raised with the `KeySizeT` template parameter.
51  * See `max_key_size()` for an easy access to this limit.
52  *
53  * The number of elements in the map is limited to `std::numeric_limits<IndexSizeT>::max()`.
54  * That is 4 294 967 296 elements, but can be raised with the `IndexSizeT` template parameter.
55  * See `max_size()` for an easy access to this limit.
56  *
57  * Iterators invalidation:
58  * - clear, operator=: always invalidate the iterators.
59  * - insert, emplace, operator[]: always invalidate the iterators.
60  * - erase: always invalidate the iterators.
61  * - shrink_to_fit: always invalidate the iterators.
62  */
63 template<class CharT,
64  class T,
65  class Hash = tsl::ah::str_hash<CharT>,
66  class KeyEqual = tsl::ah::str_equal<CharT>,
67  bool StoreNullTerminator = true,
68  class KeySizeT = std::uint16_t,
69  class IndexSizeT = std::uint32_t,
70  class GrowthPolicy = tsl::ah::power_of_two_growth_policy<2>>
71 class array_map {
72 private:
73  template<typename U>
74  using is_iterator = tsl::detail_array_hash::is_iterator<U>;
75 
76  using ht = tsl::detail_array_hash::array_hash<CharT, T, Hash, KeyEqual, StoreNullTerminator,
77  KeySizeT, IndexSizeT, GrowthPolicy>;
78 
79 public:
80  using char_type = typename ht::char_type;
81  using mapped_type = T;
82  using key_size_type = typename ht::key_size_type;
83  using index_size_type = typename ht::index_size_type;
84  using size_type = typename ht::size_type;
85  using hasher = typename ht::hasher;
86  using key_equal = typename ht::key_equal;
87  using iterator = typename ht::iterator;
88  using const_iterator = typename ht::const_iterator;
89 
90 public:
91  array_map(): array_map(ht::DEFAULT_INIT_BUCKET_COUNT) {
92  }
93 
94  explicit array_map(size_type bucket_count,
95  const Hash& hash = Hash()): m_ht(bucket_count, hash, ht::DEFAULT_MAX_LOAD_FACTOR)
96  {
97  }
98 
99  template<class InputIt, typename std::enable_if<is_iterator<InputIt>::value>::type* = nullptr>
100  array_map(InputIt first, InputIt last,
101  size_type bucket_count = ht::DEFAULT_INIT_BUCKET_COUNT,
102  const Hash& hash = Hash()): array_map(bucket_count, hash)
103  {
104  insert(first, last);
105  }
106 
107 
108 
109 #ifdef TSL_AH_HAS_STRING_VIEW
112  const Hash& hash = Hash()): array_map(bucket_count, hash)
113  {
114  insert(init);
115  }
116 #else
117  array_map(std::initializer_list<std::pair<const CharT*, T>> init,
118  size_type bucket_count = ht::DEFAULT_INIT_BUCKET_COUNT,
119  const Hash& hash = Hash()): array_map(bucket_count, hash)
120  {
121  insert(init);
122  }
123 #endif
124 
125 
126 
127 #ifdef TSL_AH_HAS_STRING_VIEW
129  clear();
130 
131  reserve(ilist.size());
132  insert(ilist);
133 
134  return *this;
135  }
136 #else
137  array_map& operator=(std::initializer_list<std::pair<const CharT*, T>> ilist) {
138  clear();
139 
140  reserve(ilist.size());
141  insert(ilist);
142 
143  return *this;
144  }
145 #endif
146 
147 
148 
149  /*
150  * Iterators
151  */
152  iterator begin() noexcept { return m_ht.begin(); }
153  const_iterator begin() const noexcept { return m_ht.begin(); }
154  const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
155 
156  iterator end() noexcept { return m_ht.end(); }
157  const_iterator end() const noexcept { return m_ht.end(); }
158  const_iterator cend() const noexcept { return m_ht.cend(); }
159 
160 
161 
162  /*
163  * Capacity
164  */
165  bool empty() const noexcept { return m_ht.empty(); }
166  size_type size() const noexcept { return m_ht.size(); }
167  size_type max_size() const noexcept { return m_ht.max_size(); }
168  size_type max_key_size() const noexcept { return m_ht.max_key_size(); }
169  void shrink_to_fit() { m_ht.shrink_to_fit(); }
170 
171 
172 
173  /*
174  * Modifiers
175  */
176  void clear() noexcept { m_ht.clear(); }
177 
178 
179 
180 #ifdef TSL_AH_HAS_STRING_VIEW
181  std::pair<iterator, bool> insert(const std::basic_string_view<CharT>& key, const T& value) {
182  return m_ht.emplace(key.data(), key.size(), value);
183  }
184 #else
185  std::pair<iterator, bool> insert(const CharT* key, const T& value) {
186  return m_ht.emplace(key, std::char_traits<CharT>::length(key), value);
187  }
188 
189  std::pair<iterator, bool> insert(const std::basic_string<CharT>& key, const T& value) {
190  return m_ht.emplace(key.data(), key.size(), value);
191  }
192 #endif
193  std::pair<iterator, bool> insert_ks(const CharT* key, size_type key_size, const T& value) {
194  return m_ht.emplace(key, key_size, value);
195  }
196 
197 
198 
199 #ifdef TSL_AH_HAS_STRING_VIEW
200  std::pair<iterator, bool> insert(const std::basic_string_view<CharT>& key, T&& value) {
201  return m_ht.emplace(key.data(), key.size(), std::move(value));
202  }
203 #else
204  std::pair<iterator, bool> insert(const CharT* key, T&& value) {
205  return m_ht.emplace(key, std::char_traits<CharT>::length(key), std::move(value));
206  }
207 
208  std::pair<iterator, bool> insert(const std::basic_string<CharT>& key, T&& value) {
209  return m_ht.emplace(key.data(), key.size(), std::move(value));
210  }
211 #endif
212  std::pair<iterator, bool> insert_ks(const CharT* key, size_type key_size, T&& value) {
213  return m_ht.emplace(key, key_size, std::move(value));
214  }
215 
216 
217 
218  template<class InputIt, typename std::enable_if<is_iterator<InputIt>::value>::type* = nullptr>
219  void insert(InputIt first, InputIt last) {
220  if(std::is_base_of<std::forward_iterator_tag,
221  typename std::iterator_traits<InputIt>::iterator_category>::value)
222  {
223  const auto nb_elements_insert = std::distance(first, last);
224  const std::size_t nb_free_buckets = std::size_t(float(bucket_count())*max_load_factor()) - size();
225 
226  if(nb_elements_insert > 0 && nb_free_buckets < std::size_t(nb_elements_insert)) {
227  reserve(size() + std::size_t(nb_elements_insert));
228  }
229  }
230 
231  for(auto it = first; it != last; ++it) {
232  insert_pair(*it);
233  }
234  }
235 
236 
237 
238 #ifdef TSL_AH_HAS_STRING_VIEW
240  insert(ilist.begin(), ilist.end());
241  }
242 #else
243  void insert(std::initializer_list<std::pair<const CharT*, T>> ilist) {
244  insert(ilist.begin(), ilist.end());
245  }
246 #endif
247 
248 
249 
250 #ifdef TSL_AH_HAS_STRING_VIEW
251  template<class M>
253  return m_ht.insert_or_assign(key.data(), key.size(), std::forward<M>(obj));
254  }
255 #else
256  template<class M>
257  std::pair<iterator, bool> insert_or_assign(const CharT* key, M&& obj) {
258  return m_ht.insert_or_assign(key, std::char_traits<CharT>::length(key), std::forward<M>(obj));
259  }
260 
261  template<class M>
262  std::pair<iterator, bool> insert_or_assign(const std::basic_string<CharT>& key, M&& obj) {
263  return m_ht.insert_or_assign(key.data(), key.size(), std::forward<M>(obj));
264  }
265 #endif
266  template<class M>
267  std::pair<iterator, bool> insert_or_assign_ks(const CharT* key, size_type key_size, M&& obj) {
268  return m_ht.insert_or_assign(key, key_size, std::forward<M>(obj));
269  }
270 
271 
272 
273 #ifdef TSL_AH_HAS_STRING_VIEW
274  template<class... Args>
275  std::pair<iterator, bool> emplace(const std::basic_string_view<CharT>& key, Args&&... args) {
276  return m_ht.emplace(key.data(), key.size(), std::forward<Args>(args)...);
277  }
278 #else
279  template<class... Args>
280  std::pair<iterator, bool> emplace(const CharT* key, Args&&... args) {
281  return m_ht.emplace(key, std::char_traits<CharT>::length(key), std::forward<Args>(args)...);
282  }
283 
284  template<class... Args>
285  std::pair<iterator, bool> emplace(const std::basic_string<CharT>& key, Args&&... args) {
286  return m_ht.emplace(key.data(), key.size(), std::forward<Args>(args)...);
287  }
288 #endif
289  template<class... Args>
290  std::pair<iterator, bool> emplace_ks(const CharT* key, size_type key_size, Args&&... args) {
291  return m_ht.emplace(key, key_size, std::forward<Args>(args)...);
292  }
293 
294 
295 
296  /**
297  * Erase has an amortized O(1) runtime complexity, but even if it removes the key immediatly,
298  * it doesn't do the same for the associated value T.
299  *
300  * T will only be removed when the ratio between the size of the map and
301  * the size of the map + the number of deleted values still stored is low enough.
302  *
303  * To force the deletion you can call shrink_to_fit.
304  */
305  iterator erase(const_iterator pos) { return m_ht.erase(pos); }
306 
307  /**
308  * @copydoc erase(const_iterator pos)
309  */
310  iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
311 
312 
313 
314 #ifdef TSL_AH_HAS_STRING_VIEW
315  /**
316  * @copydoc erase(const_iterator pos)
317  */
319  return m_ht.erase(key.data(), key.size());
320  }
321 #else
322  /**
323  * @copydoc erase(const_iterator pos)
324  */
325  size_type erase(const CharT* key) {
326  return m_ht.erase(key, std::char_traits<CharT>::length(key));
327  }
328 
329  /**
330  * @copydoc erase(const_iterator pos)
331  */
332  size_type erase(const std::basic_string<CharT>& key) {
333  return m_ht.erase(key.data(), key.size());
334  }
335 #endif
336  /**
337  * @copydoc erase(const_iterator pos)
338  */
339  size_type erase_ks(const CharT* key, size_type key_size) {
340  return m_ht.erase(key, key_size);
341  }
342 
343 
344 
345 #ifdef TSL_AH_HAS_STRING_VIEW
346  /**
347  * @copydoc erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
348  */
350  return m_ht.erase(key.data(), key.size(), precalculated_hash);
351  }
352 #else
353  /**
354  * @copydoc erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
355  */
356  size_type erase(const CharT* key, std::size_t precalculated_hash) {
357  return m_ht.erase(key, std::char_traits<CharT>::length(key), precalculated_hash);
358  }
359 
360  /**
361  * @copydoc erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
362  */
363  size_type erase(const std::basic_string<CharT>& key, std::size_t precalculated_hash) {
364  return m_ht.erase(key.data(), key.size(), precalculated_hash);
365  }
366 #endif
367  /**
368  * @copydoc erase(const_iterator pos)
369  *
370  * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
371  * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
372  */
373  size_type erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) {
374  return m_ht.erase(key, key_size, precalculated_hash);
375  }
376 
377 
378 
379  void swap(array_map& other) { other.m_ht.swap(m_ht); }
380 
381 
382 
383  /*
384  * Lookup
385  */
386 #ifdef TSL_AH_HAS_STRING_VIEW
387  T& at(const std::basic_string_view<CharT>& key) {
388  return m_ht.at(key.data(), key.size());
389  }
390 
391  const T& at(const std::basic_string_view<CharT>& key) const {
392  return m_ht.at(key.data(), key.size());
393  }
394 #else
395  T& at(const CharT* key) {
396  return m_ht.at(key, std::char_traits<CharT>::length(key));
397  }
398 
399  const T& at(const CharT* key) const {
400  return m_ht.at(key, std::char_traits<CharT>::length(key));
401  }
402 
403  T& at(const std::basic_string<CharT>& key) {
404  return m_ht.at(key.data(), key.size());
405  }
406 
407  const T& at(const std::basic_string<CharT>& key) const {
408  return m_ht.at(key.data(), key.size());
409  }
410 #endif
411  T& at_ks(const CharT* key, size_type key_size) {
412  return m_ht.at(key, key_size);
413  }
414 
415  const T& at_ks(const CharT* key, size_type key_size) const {
416  return m_ht.at(key, key_size);
417  }
418 
419 
420 
421 #ifdef TSL_AH_HAS_STRING_VIEW
422  /**
423  * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
424  */
426  return m_ht.at(key.data(), key.size(), precalculated_hash);
427  }
428 
429  /**
430  * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
431  */
432  const T& at(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) const {
433  return m_ht.at(key.data(), key.size(), precalculated_hash);
434  }
435 #else
436  /**
437  * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
438  */
439  T& at(const CharT* key, std::size_t precalculated_hash) {
440  return m_ht.at(key, std::char_traits<CharT>::length(key), precalculated_hash);
441  }
442 
443  /**
444  * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
445  */
446  const T& at(const CharT* key, std::size_t precalculated_hash) const {
447  return m_ht.at(key, std::char_traits<CharT>::length(key), precalculated_hash);
448  }
449 
450  /**
451  * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
452  */
453  T& at(const std::basic_string<CharT>& key, std::size_t precalculated_hash) {
454  return m_ht.at(key.data(), key.size(), precalculated_hash);
455  }
456 
457  /**
458  * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
459  */
460  const T& at(const std::basic_string<CharT>& key, std::size_t precalculated_hash) const {
461  return m_ht.at(key.data(), key.size(), precalculated_hash);
462  }
463 #endif
464  /**
465  * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
466  * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
467  */
468  T& at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) {
469  return m_ht.at(key, key_size, precalculated_hash);
470  }
471 
472  /**
473  * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
474  */
475  const T& at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const {
476  return m_ht.at(key, key_size, precalculated_hash);
477  }
478 
479 
480 
481 #ifdef TSL_AH_HAS_STRING_VIEW
482  T& operator[](const std::basic_string_view<CharT>& key) { return m_ht.access_operator(key.data(), key.size()); }
483 #else
484  T& operator[](const CharT* key) { return m_ht.access_operator(key, std::char_traits<CharT>::length(key)); }
485  T& operator[](const std::basic_string<CharT>& key) { return m_ht.access_operator(key.data(), key.size()); }
486 #endif
487 
488 
489 
490 #ifdef TSL_AH_HAS_STRING_VIEW
491  size_type count(const std::basic_string_view<CharT>& key) const {
492  return m_ht.count(key.data(), key.size());
493  }
494 #else
495  size_type count(const CharT* key) const {
496  return m_ht.count(key, std::char_traits<CharT>::length(key));
497  }
498 
499  size_type count(const std::basic_string<CharT>& key) const {
500  return m_ht.count(key.data(), key.size());
501  }
502 #endif
503  size_type count_ks(const CharT* key, size_type key_size) const {
504  return m_ht.count(key, key_size);
505  }
506 
507 
508 
509 #ifdef TSL_AH_HAS_STRING_VIEW
510  /**
511  * @copydoc count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const
512  */
514  return m_ht.count(key.data(), key.size(), precalculated_hash);
515  }
516 #else
517  /**
518  * @copydoc count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const
519  */
520  size_type count(const CharT* key, std::size_t precalculated_hash) const {
521  return m_ht.count(key, std::char_traits<CharT>::length(key), precalculated_hash);
522  }
523 
524  /**
525  * @copydoc count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const
526  */
527  size_type count(const std::basic_string<CharT>& key, std::size_t precalculated_hash) const {
528  return m_ht.count(key.data(), key.size(), precalculated_hash);
529  }
530 #endif
531  /**
532  * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
533  * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
534  */
535  size_type count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const {
536  return m_ht.count(key, key_size, precalculated_hash);
537  }
538 
539 
540 
541 #ifdef TSL_AH_HAS_STRING_VIEW
543  return m_ht.find(key.data(), key.size());
544  }
545 
547  return m_ht.find(key.data(), key.size());
548  }
549 #else
550  iterator find(const CharT* key) {
551  return m_ht.find(key, std::char_traits<CharT>::length(key));
552  }
553 
554  const_iterator find(const CharT* key) const {
555  return m_ht.find(key, std::char_traits<CharT>::length(key));
556  }
557 
558  iterator find(const std::basic_string<CharT>& key) {
559  return m_ht.find(key.data(), key.size());
560  }
561 
562  const_iterator find(const std::basic_string<CharT>& key) const {
563  return m_ht.find(key.data(), key.size());
564  }
565 #endif
566  iterator find_ks(const CharT* key, size_type key_size) {
567  return m_ht.find(key, key_size);
568  }
569 
570  const_iterator find_ks(const CharT* key, size_type key_size) const {
571  return m_ht.find(key, key_size);
572  }
573 
574 
575 
576 #ifdef TSL_AH_HAS_STRING_VIEW
577  /**
578  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
579  */
581  return m_ht.find(key.data(), key.size(), precalculated_hash);
582  }
583 
584  /**
585  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
586  */
588  return m_ht.find(key.data(), key.size(), precalculated_hash);
589  }
590 #else
591  /**
592  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
593  */
594  iterator find(const CharT* key, std::size_t precalculated_hash) {
595  return m_ht.find(key, std::char_traits<CharT>::length(key), precalculated_hash);
596  }
597 
598  /**
599  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
600  */
601  const_iterator find(const CharT* key, std::size_t precalculated_hash) const {
602  return m_ht.find(key, std::char_traits<CharT>::length(key), precalculated_hash);
603  }
604 
605  /**
606  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
607  */
608  iterator find(const std::basic_string<CharT>& key, std::size_t precalculated_hash) {
609  return m_ht.find(key.data(), key.size(), precalculated_hash);
610  }
611 
612  /**
613  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
614  */
615  const_iterator find(const std::basic_string<CharT>& key, std::size_t precalculated_hash) const {
616  return m_ht.find(key.data(), key.size(), precalculated_hash);
617  }
618 #endif
619  /**
620  * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
621  * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
622  */
623  iterator find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) {
624  return m_ht.find(key, key_size, precalculated_hash);
625  }
626 
627  /**
628  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
629  */
630  const_iterator find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const {
631  return m_ht.find(key, key_size, precalculated_hash);
632  }
633 
634 
635 
636 #ifdef TSL_AH_HAS_STRING_VIEW
638  return m_ht.equal_range(key.data(), key.size());
639  }
640 
642  return m_ht.equal_range(key.data(), key.size());
643  }
644 #else
645  std::pair<iterator, iterator> equal_range(const CharT* key) {
646  return m_ht.equal_range(key, std::char_traits<CharT>::length(key));
647  }
648 
649  std::pair<const_iterator, const_iterator> equal_range(const CharT* key) const {
650  return m_ht.equal_range(key, std::char_traits<CharT>::length(key));
651  }
652 
653  std::pair<iterator, iterator> equal_range(const std::basic_string<CharT>& key) {
654  return m_ht.equal_range(key.data(), key.size());
655  }
656 
657  std::pair<const_iterator, const_iterator> equal_range(const std::basic_string<CharT>& key) const {
658  return m_ht.equal_range(key.data(), key.size());
659  }
660 #endif
661  std::pair<iterator, iterator> equal_range_ks(const CharT* key, size_type key_size) {
662  return m_ht.equal_range(key, key_size);
663  }
664 
665  std::pair<const_iterator, const_iterator> equal_range_ks(const CharT* key, size_type key_size) const {
666  return m_ht.equal_range(key, key_size);
667  }
668 
669 
670 
671 #ifdef TSL_AH_HAS_STRING_VIEW
672  /**
673  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
674  */
677  }
678 
679  /**
680  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
681  */
684  }
685 #else
686  /**
687  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
688  */
689  std::pair<iterator, iterator> equal_range(const CharT* key, std::size_t precalculated_hash) {
690  return m_ht.equal_range(key, std::char_traits<CharT>::length(key), precalculated_hash);
691  }
692 
693  /**
694  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
695  */
696  std::pair<const_iterator, const_iterator> equal_range(const CharT* key, std::size_t precalculated_hash) const {
697  return m_ht.equal_range(key, std::char_traits<CharT>::length(key), precalculated_hash);
698  }
699 
700  /**
701  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
702  */
703  std::pair<iterator, iterator> equal_range(const std::basic_string<CharT>& key, std::size_t precalculated_hash) {
704  return m_ht.equal_range(key.data(), key.size(), precalculated_hash);
705  }
706 
707  /**
708  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
709  */
710  std::pair<const_iterator, const_iterator> equal_range(const std::basic_string<CharT>& key, std::size_t precalculated_hash) const {
711  return m_ht.equal_range(key.data(), key.size(), precalculated_hash);
712  }
713 #endif
714  /**
715  * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
716  * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
717  */
718  std::pair<iterator, iterator> equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) {
719  return m_ht.equal_range(key, key_size, precalculated_hash);
720  }
721 
722  /**
723  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
724  */
725  std::pair<const_iterator, const_iterator> equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const {
726  return m_ht.equal_range(key, key_size, precalculated_hash);
727  }
728 
729 
730 
731  /*
732  * Bucket interface
733  */
734  size_type bucket_count() const { return m_ht.bucket_count(); }
735  size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
736 
737 
738  /*
739  * Hash policy
740  */
741  float load_factor() const { return m_ht.load_factor(); }
742  float max_load_factor() const { return m_ht.max_load_factor(); }
743  void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
744 
745  void rehash(size_type count) { m_ht.rehash(count); }
746  void reserve(size_type count) { m_ht.reserve(count); }
747 
748 
749  /*
750  * Observers
751  */
752  hasher hash_function() const { return m_ht.hash_function(); }
753  key_equal key_eq() const { return m_ht.key_eq(); }
754 
755 
756  /*
757  * Other
758  */
759  /**
760  * Return the `const_iterator it` as an `iterator`.
761  */
762  iterator mutable_iterator(const_iterator it) noexcept { return m_ht.mutable_iterator(it); }
763 
764  /**
765  * Serialize the map through the `serializer` parameter.
766  *
767  * The `serializer` parameter must be a function object that supports the following calls:
768  * - `void operator()(const U& value);` where the types `std::uint64_t`, `float` and `T` must be supported for U.
769  * - `void operator()(const CharT* value, std::size_t value_size);`
770  *
771  * The implementation leaves binary compatibilty (endianness, IEEE 754 for floats, ...) of the types it serializes
772  * in the hands of the `Serializer` function object if compatibilty is required.
773  */
774  template<class Serializer>
775  void serialize(Serializer& serializer) const {
776  m_ht.serialize(serializer);
777  }
778 
779  /**
780  * Deserialize a previouly serialized map through the `deserializer` parameter.
781  *
782  * The `deserializer` parameter must be a function object that supports the following calls:
783  * - `template<typename U> U operator()();` where the types `std::uint64_t`, `float` and `T` must be supported for U.
784  * - `void operator()(CharT* value_out, std::size_t value_size);`
785  *
786  * If the deserialized hash map type is hash compatible with the serialized map, the deserialization process can be
787  * sped up by setting `hash_compatible` to true. To be hash compatible, the Hash (take care of the 32-bits vs 64 bits),
788  * KeyEqual, GrowthPolicy, StoreNullTerminator, KeySizeT and IndexSizeT must behave the same than the one used on the
789  * serialazed map. Otherwise the behaviour is undefined with `hash_compatible` sets to true, .
790  *
791  * The behaviour is undefined if the type `CharT` and `T` of the `array_map` are not the same as the
792  * types used during serialization.
793  *
794  * The implementation leaves binary compatibilty (endianness, IEEE 754 for floats, ...) of the types it deserializes
795  * in the hands of the `Deserializer` function object if compatibilty is required.
796  */
797  template<class Deserializer>
798  static array_map deserialize(Deserializer& deserializer, bool hash_compatible = false) {
799  array_map map(0);
800  map.m_ht.deserialize(deserializer, hash_compatible);
801 
802  return map;
803  }
804 
805  friend bool operator==(const array_map& lhs, const array_map& rhs) {
806  if(lhs.size() != rhs.size()) {
807  return false;
808  }
809 
810  for(auto it = lhs.cbegin(); it != lhs.cend(); ++it) {
811  const auto it_element_rhs = rhs.find_ks(it.key(), it.key_size());
812  if(it_element_rhs == rhs.cend() || it.value() != it_element_rhs.value()) {
813  return false;
814  }
815  }
816 
817  return true;
818  }
819 
820  friend bool operator!=(const array_map& lhs, const array_map& rhs) {
821  return !operator==(lhs, rhs);
822  }
823 
824  friend void swap(array_map& lhs, array_map& rhs) {
825  lhs.swap(rhs);
826  }
827 
828 private:
829  template<class U, class V>
830  void insert_pair(const std::pair<U, V>& value) {
831  insert(value.first, value.second);
832  }
833 
834  template<class U, class V>
835  void insert_pair(std::pair<U, V>&& value) {
836  insert(value.first, std::move(value.second));
837  }
838 
839 public:
840  static const size_type MAX_KEY_SIZE = ht::MAX_KEY_SIZE;
841 
842 private:
843  ht m_ht;
844 };
845 
846 
847 /**
848  * Same as
849  * `tsl::array_map<CharT, T, Hash, KeyEqual, StoreNullTerminator, KeySizeT, IndexSizeT, tsl::ah::prime_growth_policy>`.
850  */
851 template<class CharT,
852  class T,
853  class Hash = tsl::ah::str_hash<CharT>,
854  class KeyEqual = tsl::ah::str_equal<CharT>,
855  bool StoreNullTerminator = true,
856  class KeySizeT = std::uint16_t,
857  class IndexSizeT = std::uint32_t>
858 using array_pg_map = array_map<CharT, T, Hash, KeyEqual, StoreNullTerminator,
859  KeySizeT, IndexSizeT, tsl::ah::prime_growth_policy>;
860 
861 } //end namespace tsl
862 
863 #endif
size_type erase_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash)
Definition: array_map.h:373
std::pair< const_iterator, const_iterator > equal_range(const CharT *key) const
Definition: array_map.h:649
T & at(const CharT *key, std::size_t precalculated_hash)
Definition: array_map.h:439
iterator find(const std::basic_string< CharT > &key, std::size_t precalculated_hash)
Definition: array_map.h:608
std::pair< iterator, bool > insert(const std::basic_string< CharT > &key, T &&value)
Definition: array_map.h:208
std::pair< iterator, bool > insert_ks(const CharT *key, size_type key_size, const T &value)
Definition: array_map.h:193
Definition: array_growth_policy.h:40
const T & at(const std::basic_string< CharT > &key, std::size_t precalculated_hash) const
Definition: array_map.h:460
size_type erase(const std::basic_string< CharT > &key)
Definition: array_map.h:332
array_map(size_type bucket_count, const Hash &hash=Hash())
Definition: array_map.h:94
size_type count(const std::basic_string< CharT > &key) const
Definition: array_map.h:499
array_map(std::initializer_list< std::pair< const CharT *, T >> init, size_type bucket_count=ht::DEFAULT_INIT_BUCKET_COUNT, const Hash &hash=Hash())
Definition: array_map.h:117
static const size_type MAX_KEY_SIZE
Definition: array_map.h:840
iterator find(const std::basic_string< CharT > &key)
Definition: array_map.h:558
T & at(const CharT *key)
Definition: array_map.h:395
void swap(array_map &other)
Definition: array_map.h:379
Definition: array_growth_policy.h:39
std::pair< const_iterator, const_iterator > equal_range_ks(const CharT *key, size_type key_size) const
Definition: array_map.h:665
size_type count_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash) const
Definition: array_map.h:535
const_iterator find(const std::basic_string< CharT > &key) const
Definition: array_map.h:562
float load_factor() const
Definition: array_map.h:741
void clear() noexcept
Definition: array_map.h:176
Definition: array_hash.h:117
size_type max_bucket_count() const
Definition: array_map.h:735
std::pair< iterator, bool > emplace_ks(const CharT *key, size_type key_size, Args &&... args)
Definition: array_map.h:290
std::pair< iterator, iterator > equal_range(const std::basic_string< CharT > &key)
Definition: array_map.h:653
size_type size() const noexcept
Definition: array_map.h:166
const T & at(const CharT *key) const
Definition: array_map.h:399
size_type max_size() const noexcept
Definition: array_map.h:167
const_iterator find(const CharT *key) const
Definition: array_map.h:554
std::pair< iterator, iterator > equal_range(const CharT *key)
Definition: array_map.h:645
std::pair< iterator, bool > insert_or_assign(const CharT *key, M &&obj)
Definition: array_map.h:257
void reserve(size_type count)
Definition: array_map.h:746
iterator end() noexcept
Definition: array_map.h:156
size_type bucket_count() const
Definition: array_map.h:734
Definition: array_hash.h:102
hasher hash_function() const
Definition: array_map.h:752
friend void swap(array_map &lhs, array_map &rhs)
Definition: array_map.h:824
T & operator[](const CharT *key)
Definition: array_map.h:484
T & at(const std::basic_string< CharT > &key)
Definition: array_map.h:403
std::pair< iterator, bool > insert(const std::basic_string< CharT > &key, const T &value)
Definition: array_map.h:189
iterator find_ks(const CharT *key, size_type key_size)
Definition: array_map.h:566
Definition: array_map.h:71
iterator mutable_iterator(const_iterator it) noexcept
Definition: array_map.h:762
std::pair< iterator, bool > insert_or_assign(const std::basic_string< CharT > &key, M &&obj)
Definition: array_map.h:262
std::pair< iterator, iterator > equal_range(const std::basic_string< CharT > &key, std::size_t precalculated_hash)
Definition: array_map.h:703
static array_map deserialize(Deserializer &deserializer, bool hash_compatible=false)
Definition: array_map.h:798
const_iterator find(const CharT *key, std::size_t precalculated_hash) const
Definition: array_map.h:601
size_type erase(const std::basic_string< CharT > &key, std::size_t precalculated_hash)
Definition: array_map.h:363
std::pair< iterator, bool > insert(const CharT *key, const T &value)
Definition: array_map.h:185
std::pair< iterator, iterator > equal_range(const CharT *key, std::size_t precalculated_hash)
Definition: array_map.h:689
void insert(std::initializer_list< std::pair< const CharT *, T >> ilist)
Definition: array_map.h:243
iterator erase(const_iterator pos)
Definition: array_map.h:305
std::pair< const_iterator, const_iterator > equal_range_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash) const
Definition: array_map.h:725
iterator find_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash)
Definition: array_map.h:623
T & at_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash)
Definition: array_map.h:468
std::pair< iterator, bool > emplace(const CharT *key, Args &&... args)
Definition: array_map.h:280
void rehash(size_type count)
Definition: array_map.h:745
const T & at_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash) const
Definition: array_map.h:475
T & at(const std::basic_string< CharT > &key, std::size_t precalculated_hash)
Definition: array_map.h:453
size_type count(const CharT *key, std::size_t precalculated_hash) const
Definition: array_map.h:520
void max_load_factor(float ml)
Definition: array_map.h:743
T & operator[](const std::basic_string< CharT > &key)
Definition: array_map.h:485
void insert(InputIt first, InputIt last)
Definition: array_map.h:219
const_iterator cend() const noexcept
Definition: array_map.h:158
std::pair< iterator, iterator > equal_range_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash)
Definition: array_map.h:718
array_map(InputIt first, InputIt last, size_type bucket_count=ht::DEFAULT_INIT_BUCKET_COUNT, const Hash &hash=Hash())
Definition: array_map.h:100
const_iterator cbegin() const noexcept
Definition: array_map.h:154
size_type erase_ks(const CharT *key, size_type key_size)
Definition: array_map.h:339
friend bool operator!=(const array_map &lhs, const array_map &rhs)
Definition: array_map.h:820
friend bool operator==(const array_map &lhs, const array_map &rhs)
Definition: array_map.h:805
T & at_ks(const CharT *key, size_type key_size)
Definition: array_map.h:411
std::pair< const_iterator, const_iterator > equal_range(const std::basic_string< CharT > &key) const
Definition: array_map.h:657
iterator find(const CharT *key)
Definition: array_map.h:550
const_iterator find(const std::basic_string< CharT > &key, std::size_t precalculated_hash) const
Definition: array_map.h:615
Definition: array_growth_policy.h:49
Definition: array_growth_policy.h:247
key_equal key_eq() const
Definition: array_map.h:753
const_iterator end() const noexcept
Definition: array_map.h:157
size_type erase(const CharT *key, std::size_t precalculated_hash)
Definition: array_map.h:356
std::pair< iterator, bool > insert(const CharT *key, T &&value)
Definition: array_map.h:204
float max_load_factor() const
Definition: array_map.h:742
array_map & operator=(std::initializer_list< std::pair< const CharT *, T >> ilist)
Definition: array_map.h:137
const T & at(const CharT *key, std::size_t precalculated_hash) const
Definition: array_map.h:446
size_type count_ks(const CharT *key, size_type key_size) const
Definition: array_map.h:503
std::pair< const_iterator, const_iterator > equal_range(const std::basic_string< CharT > &key, std::size_t precalculated_hash) const
Definition: array_map.h:710
array_map()
Definition: array_map.h:91
iterator erase(const_iterator first, const_iterator last)
Definition: array_map.h:310
size_type count(const std::basic_string< CharT > &key, std::size_t precalculated_hash) const
Definition: array_map.h:527
size_type count(const CharT *key) const
Definition: array_map.h:495
std::pair< iterator, bool > insert_ks(const CharT *key, size_type key_size, T &&value)
Definition: array_map.h:212
void serialize(Serializer &serializer) const
Definition: array_map.h:775
bool empty() const noexcept
Definition: array_map.h:165
Definition: array_hash.h:742
const T & at_ks(const CharT *key, size_type key_size) const
Definition: array_map.h:415
std::pair< iterator, iterator > equal_range_ks(const CharT *key, size_type key_size)
Definition: array_map.h:661
const_iterator find_ks(const CharT *key, size_type key_size) const
Definition: array_map.h:570
const_iterator begin() const noexcept
Definition: array_map.h:153
std::pair< const_iterator, const_iterator > equal_range(const CharT *key, std::size_t precalculated_hash) const
Definition: array_map.h:696
iterator find(const CharT *key, std::size_t precalculated_hash)
Definition: array_map.h:594
const T & at(const std::basic_string< CharT > &key) const
Definition: array_map.h:407
Definition: array_hash.h:77
std::pair< iterator, bool > insert_or_assign_ks(const CharT *key, size_type key_size, M &&obj)
Definition: array_map.h:267
size_type erase(const CharT *key)
Definition: array_map.h:325
const_iterator find_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash) const
Definition: array_map.h:630
void shrink_to_fit()
Definition: array_map.h:169
std::pair< iterator, bool > emplace(const std::basic_string< CharT > &key, Args &&... args)
Definition: array_map.h:285
iterator begin() noexcept
Definition: array_map.h:152
size_type max_key_size() const noexcept
Definition: array_map.h:168