Movatterモバイル変換

[0]ホーム
URL:

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 #ifndefTSL_ARRAY_MAP_H
25 #defineTSL_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 namespacetsl {
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 classarray_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 explicitarray_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 #ifdefTSL_AH_HAS_STRING_VIEW
110 array_map(std::initializer_list<std::pair<std::basic_string_view<CharT>,T>>init,
111 size_typebucket_count =ht::DEFAULT_INIT_BUCKET_COUNT,
112 constHash&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 #ifdefTSL_AH_HAS_STRING_VIEW
128 array_map&operator=(std::initializer_list<std::pair<std::basic_string_view<CharT>,T>>ilist) {
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  iteratorbegin()noexcept {return m_ht.begin(); }
153  const_iteratorbegin()constnoexcept {return m_ht.begin(); }
154  const_iteratorcbegin()constnoexcept {return m_ht.cbegin(); }
155 
156  iteratorend()noexcept {return m_ht.end(); }
157  const_iteratorend()constnoexcept {return m_ht.end(); }
158  const_iteratorcend()constnoexcept {return m_ht.cend(); }
159 
160 
161 
162 /*
163  * Capacity
164  */
165 boolempty()constnoexcept {return m_ht.empty(); }
166  size_typesize()constnoexcept {return m_ht.size(); }
167  size_typemax_size()constnoexcept {return m_ht.max_size(); }
168  size_typemax_key_size()constnoexcept {return m_ht.max_key_size(); }
169 voidshrink_to_fit() { m_ht.shrink_to_fit(); }
170 
171 
172 
173 /*
174  * Modifiers
175  */
176 voidclear()noexcept { m_ht.clear(); }
177 
178 
179 
180 #ifdefTSL_AH_HAS_STRING_VIEW
181 std::pair<iterator,bool>insert(conststd::basic_string_view<CharT>&key,constT&value) {
182 returnm_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 #ifdefTSL_AH_HAS_STRING_VIEW
200 std::pair<iterator,bool>insert(conststd::basic_string_view<CharT>&key,T&&value) {
201 returnm_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 voidinsert(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 constauto 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 #ifdefTSL_AH_HAS_STRING_VIEW
239 voidinsert(std::initializer_list<std::pair<std::basic_string_view<CharT>,T>>ilist) {
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 #ifdefTSL_AH_HAS_STRING_VIEW
251 template<classM>
252 std::pair<iterator,bool>insert_or_assign(conststd::basic_string_view<CharT>&key,M&&obj) {
253 returnm_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 #ifdefTSL_AH_HAS_STRING_VIEW
274 template<class...Args>
275 std::pair<iterator,bool>emplace(conststd::basic_string_view<CharT>&key,Args&&...args) {
276 returnm_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  iteratorerase(const_iterator pos) {return m_ht.erase(pos); }
306 
307 /**
308  * @copydoc erase(const_iterator pos)
309  */
310  iteratorerase(const_iterator first, const_iterator last) {return m_ht.erase(first, last); }
311 
312 
313 
314 #ifdefTSL_AH_HAS_STRING_VIEW
315 /**
316  * @copydoc erase(const_iterator pos)
317  */
318 size_typeerase(conststd::basic_string_view<CharT>&key) {
319 returnm_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_typeerase_ks(const CharT* key, size_type key_size) {
340 return m_ht.erase(key, key_size);
341  }
342 
343 
344 
345 #ifdefTSL_AH_HAS_STRING_VIEW
346 /**
347  * @copydoc erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
348  */
349 size_typeerase(conststd::basic_string_view<CharT>&key,std::size_tprecalculated_hash) {
350 returnm_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_typeerase_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 voidswap(array_map& other) { other.m_ht.swap(m_ht); }
380 
381 
382 
383 /*
384  * Lookup
385  */
386 #ifdefTSL_AH_HAS_STRING_VIEW
387 T&at(conststd::basic_string_view<CharT>&key) {
388 returnm_ht.at(key.data(),key.size());
389  }
390 
391 constT&at(conststd::basic_string_view<CharT>&key)const {
392 returnm_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 #ifdefTSL_AH_HAS_STRING_VIEW
422 /**
423  * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
424  */
425 T&at(conststd::basic_string_view<CharT>&key,std::size_tprecalculated_hash) {
426 returnm_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 constT&at(conststd::basic_string_view<CharT>&key,std::size_tprecalculated_hash)const {
433 returnm_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 #ifdefTSL_AH_HAS_STRING_VIEW
482 T&operator[](conststd::basic_string_view<CharT>&key) {returnm_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 #ifdefTSL_AH_HAS_STRING_VIEW
491 size_typecount(conststd::basic_string_view<CharT>&key)const {
492 returnm_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_typecount_ks(const CharT* key, size_type key_size)const {
504 return m_ht.count(key, key_size);
505  }
506 
507 
508 
509 #ifdefTSL_AH_HAS_STRING_VIEW
510 /**
511  * @copydoc count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const
512  */
513 size_typecount(conststd::basic_string_view<CharT>&key,std::size_tprecalculated_hash)const {
514 returnm_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_typecount_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 #ifdefTSL_AH_HAS_STRING_VIEW
542 iteratorfind(conststd::basic_string_view<CharT>&key) {
543 returnm_ht.find(key.data(),key.size());
544  }
545 
546 const_iteratorfind(conststd::basic_string_view<CharT>&key)const {
547 returnm_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  iteratorfind_ks(const CharT* key, size_type key_size) {
567 return m_ht.find(key, key_size);
568  }
569 
570  const_iteratorfind_ks(const CharT* key, size_type key_size)const {
571 return m_ht.find(key, key_size);
572  }
573 
574 
575 
576 #ifdefTSL_AH_HAS_STRING_VIEW
577 /**
578  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
579  */
580 iteratorfind(conststd::basic_string_view<CharT>&key,std::size_tprecalculated_hash) {
581 returnm_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  */
587 const_iteratorfind(conststd::basic_string_view<CharT>&key,std::size_tprecalculated_hash)const {
588 returnm_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  iteratorfind_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_iteratorfind_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 #ifdefTSL_AH_HAS_STRING_VIEW
637 std::pair<iterator,iterator>equal_range(conststd::basic_string_view<CharT>&key) {
638 returnm_ht.equal_range(key.data(),key.size());
639  }
640 
641 std::pair<const_iterator,const_iterator>equal_range(conststd::basic_string_view<CharT>&key)const {
642 returnm_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 #ifdefTSL_AH_HAS_STRING_VIEW
672 /**
673  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
674  */
675 std::pair<iterator,iterator>equal_range(conststd::basic_string_view<CharT>&key,std::size_tprecalculated_hash) {
676 returnm_ht.equal_range(key.data(),key.size(),precalculated_hash);
677  }
678 
679 /**
680  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
681  */
682 std::pair<const_iterator,const_iterator>equal_range(conststd::basic_string_view<CharT>&key,std::size_tprecalculated_hash)const {
683 returnm_ht.equal_range(key.data(),key.size(),precalculated_hash);
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_typebucket_count()const {return m_ht.bucket_count(); }
735  size_typemax_bucket_count()const {return m_ht.max_bucket_count(); }
736 
737 
738 /*
739  * Hash policy
740  */
741 floatload_factor()const {return m_ht.load_factor(); }
742 floatmax_load_factor()const {return m_ht.max_load_factor(); }
743 voidmax_load_factor(float ml) { m_ht.max_load_factor(ml); }
744 
745 voidrehash(size_type count) { m_ht.rehash(count); }
746 voidreserve(size_type count) { m_ht.reserve(count); }
747 
748 
749 /*
750  * Observers
751  */
752  hasherhash_function()const {return m_ht.hash_function(); }
753  key_equalkey_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  iteratormutable_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 voidserialize(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 staticarray_mapdeserialize(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 friendbooloperator==(constarray_map& lhs,constarray_map& rhs) {
806 if(lhs.size() != rhs.size()) {
807 returnfalse;
808  }
809 
810 for(auto it = lhs.cbegin(); it != lhs.cend(); ++it) {
811 constauto 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 returnfalse;
814  }
815  }
816 
817 returntrue;
818  }
819 
820 friendbooloperator!=(constarray_map& lhs,constarray_map& rhs) {
821 return !operator==(lhs, rhs);
822  }
823 
824 friendvoidswap(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 staticconst size_typeMAX_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
tsl::array_map::erase_ks
size_type erase_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash)
Definition: array_map.h:373
tsl::array_map::insert_ks
std::pair< iterator, bool > insert_ks(const CharT *key, size_type key_size, const T &value)
Definition: array_map.h:193
tsl::ah
Definition: array_growth_policy.h:40
tsl::array_map::array_map
array_map(size_type bucket_count, const Hash &hash=Hash())
Definition: array_map.h:94
tsl::array_map::MAX_KEY_SIZE
static const size_type MAX_KEY_SIZE
Definition: array_map.h:840
tsl::array_map::swap
void swap(array_map &other)
Definition: array_map.h:379
tsl
Definition: array_growth_policy.h:39
tsl::array_map::equal_range_ks
std::pair< const_iterator, const_iterator > equal_range_ks(const CharT *key, size_type key_size) const
Definition: array_map.h:665
tsl::array_map::count_ks
size_type count_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash) const
Definition: array_map.h:535
tsl::array_map::load_factor
float load_factor() const
Definition: array_map.h:741
tsl::array_map::clear
void clear() noexcept
Definition: array_map.h:176
tsl::detail_array_hash
Definition: array_hash.h:117
tsl::array_map::max_bucket_count
size_type max_bucket_count() const
Definition: array_map.h:735
tsl::array_map::emplace_ks
std::pair< iterator, bool > emplace_ks(const CharT *key, size_type key_size, Args &&... args)
Definition: array_map.h:290
tsl::array_map::size
size_type size() const noexcept
Definition: array_map.h:166
tsl::array_map::max_size
size_type max_size() const noexcept
Definition: array_map.h:167
tsl::array_map::reserve
void reserve(size_type count)
Definition: array_map.h:746
tsl::array_map::end
iterator end() noexcept
Definition: array_map.h:156
tsl::array_map::bucket_count
size_type bucket_count() const
Definition: array_map.h:734
tsl::ah::str_equal
Definition: array_hash.h:102
tsl::array_map::hash_function
hasher hash_function() const
Definition: array_map.h:752
tsl::array_map::swap
friend void swap(array_map &lhs, array_map &rhs)
Definition: array_map.h:824
tsl::array_map::find_ks
iterator find_ks(const CharT *key, size_type key_size)
Definition: array_map.h:566
tsl::array_map::mutable_iterator
iterator mutable_iterator(const_iterator it) noexcept
Definition: array_map.h:762
tsl::array_map::deserialize
static array_map deserialize(Deserializer &deserializer, bool hash_compatible=false)
Definition: array_map.h:798
tsl::array_map::erase
iterator erase(const_iterator pos)
Definition: array_map.h:305
tsl::array_map::equal_range_ks
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
tsl::array_map::find_ks
iterator find_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash)
Definition: array_map.h:623
tsl::array_map::at_ks
T & at_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash)
Definition: array_map.h:468
tsl::array_map::rehash
void rehash(size_type count)
Definition: array_map.h:745
tsl::array_map::at_ks
const T & at_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash) const
Definition: array_map.h:475
tsl::array_map::max_load_factor
void max_load_factor(float ml)
Definition: array_map.h:743
tsl::array_map::insert
void insert(InputIt first, InputIt last)
Definition: array_map.h:219
tsl::array_map::cend
const_iterator cend() const noexcept
Definition: array_map.h:158
tsl::array_map::equal_range_ks
std::pair< iterator, iterator > equal_range_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash)
Definition: array_map.h:718
tsl::array_map::array_map
array_map(InputIt first, InputIt last, size_type bucket_count=ht::DEFAULT_INIT_BUCKET_COUNT, const Hash &hash=Hash())
Definition: array_map.h:100
tsl::array_map::cbegin
const_iterator cbegin() const noexcept
Definition: array_map.h:154
tsl::array_map::erase_ks
size_type erase_ks(const CharT *key, size_type key_size)
Definition: array_map.h:339
tsl::array_map::operator!=
friend bool operator!=(const array_map &lhs, const array_map &rhs)
Definition: array_map.h:820
tsl::array_map::operator==
friend bool operator==(const array_map &lhs, const array_map &rhs)
Definition: array_map.h:805
tsl::array_map::at_ks
T & at_ks(const CharT *key, size_type key_size)
Definition: array_map.h:411
tsl::ah::str_hash::operator()
std::size_t operator()(const CharT *key, std::size_t key_size) const
Definition: array_hash.h:79
tsl::ah::power_of_two_growth_policy
Definition: array_growth_policy.h:49
tsl::ah::prime_growth_policy
Definition: array_growth_policy.h:247
tsl::array_map::key_eq
key_equal key_eq() const
Definition: array_map.h:753
tsl::array_map::end
const_iterator end() const noexcept
Definition: array_map.h:157
tsl::array_map::max_load_factor
float max_load_factor() const
Definition: array_map.h:742
tsl::array_map::count_ks
size_type count_ks(const CharT *key, size_type key_size) const
Definition: array_map.h:503
tsl::array_map::array_map
array_map()
Definition: array_map.h:91
tsl::array_map::erase
iterator erase(const_iterator first, const_iterator last)
Definition: array_map.h:310
tsl::array_map::insert_ks
std::pair< iterator, bool > insert_ks(const CharT *key, size_type key_size, T &&value)
Definition: array_map.h:212
tsl::array_map::serialize
void serialize(Serializer &serializer) const
Definition: array_map.h:775
tsl::array_map::empty
bool empty() const noexcept
Definition: array_map.h:165
tsl::detail_array_hash::array_hash
Definition: array_hash.h:742
tsl::array_map::at_ks
const T & at_ks(const CharT *key, size_type key_size) const
Definition: array_map.h:415
tsl::array_map::equal_range_ks
std::pair< iterator, iterator > equal_range_ks(const CharT *key, size_type key_size)
Definition: array_map.h:661
tsl::array_map::find_ks
const_iterator find_ks(const CharT *key, size_type key_size) const
Definition: array_map.h:570
tsl::array_map::begin
const_iterator begin() const noexcept
Definition: array_map.h:153
tsl::array_map::insert_or_assign_ks
std::pair< iterator, bool > insert_or_assign_ks(const CharT *key, size_type key_size, M &&obj)
Definition: array_map.h:267
tsl::array_map::find_ks
const_iterator find_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash) const
Definition: array_map.h:630
tsl::array_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const std::basic_string_view< CharT > &key, std::size_t precalculated_hash) const
Definition: array_map.h:682
tsl::array_map::shrink_to_fit
void shrink_to_fit()
Definition: array_map.h:169
tsl::array_map::begin
iterator begin() noexcept
Definition: array_map.h:152
tsl::array_map::max_key_size
size_type max_key_size() const noexcept
Definition: array_map.h:168
Generated by  doxygen 1.8.13
[8]ページ先頭
©2009-2025 Movatter.jp