hat-trie
htrie_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_HTRIE_MAP_H
25 #define TSL_HTRIE_MAP_H
26 
27 #include <cstddef>
28 #include <cstring>
29 #include <initializer_list>
30 #include <string>
31 #include <utility>
32 #include "htrie_hash.h"
33 
34 namespace tsl {
35 
36 /**
37  * Implementation of a hat-trie map.
38  *
39  * The value T must be either nothrow move-constructible/assignable, copy-constuctible or both.
40  *
41  * The size of a key string is limited to std::numeric_limits<KeySizeT>::max() - 1.
42  * That is 65 535 characters by default, but can be raised with the KeySizeT template parameter.
43  * See max_key_size() for an easy access to this limit.
44  *
45  * Iterators invalidation:
46  * - clear, operator=: always invalidate the iterators.
47  * - insert, emplace, operator[]: always invalidate the iterators.
48  * - erase: always invalidate the iterators.
49  */
50 template<class CharT,
51  class T,
52  class Hash = tsl::ah::str_hash<CharT>,
53  class KeySizeT = std::uint16_t>
54 class htrie_map {
55 private:
56  template<typename U>
57  using is_iterator = tsl::detail_array_hash::is_iterator<U>;
58 
59  using ht = tsl::detail_htrie_hash::htrie_hash<CharT, T, Hash, KeySizeT>;
60 
61 public:
62  using char_type = typename ht::char_type;
63  using mapped_type = T;
64  using key_size_type = typename ht::key_size_type;
65  using size_type = typename ht::size_type;
66  using hasher = typename ht::hasher;
67  using iterator = typename ht::iterator;
68  using const_iterator = typename ht::const_iterator;
69  using prefix_iterator = typename ht::prefix_iterator;
70  using const_prefix_iterator = typename ht::const_prefix_iterator;
71 
72 public:
73  explicit htrie_map(const Hash& hash = Hash()): m_ht(hash, ht::HASH_NODE_DEFAULT_MAX_LOAD_FACTOR,
74  ht::DEFAULT_BURST_THRESHOLD)
75  {
76  }
77 
78  explicit htrie_map(size_type burst_threshold,
79  const Hash& hash = Hash()): m_ht(hash, ht::HASH_NODE_DEFAULT_MAX_LOAD_FACTOR,
80  burst_threshold)
81  {
82  }
83 
84  template<class InputIt, typename std::enable_if<is_iterator<InputIt>::value>::type* = nullptr>
85  htrie_map(InputIt first, InputIt last,
86  const Hash& hash = Hash()): htrie_map(hash)
87  {
88  insert(first, last);
89  }
90 
91 
92 
93 #ifdef TSL_HT_HAS_STRING_VIEW
95  const Hash& hash = Hash()): htrie_map(hash)
96  {
97  insert(init);
98  }
99 #else
100  htrie_map(std::initializer_list<std::pair<const CharT*, T>> init,
101  const Hash& hash = Hash()): htrie_map(hash)
102  {
103  insert(init);
104  }
105 #endif
106 
107 
108 
109 #ifdef TSL_HT_HAS_STRING_VIEW
111  clear();
112  insert(ilist);
113 
114  return *this;
115  }
116 #else
117  htrie_map& operator=(std::initializer_list<std::pair<const CharT*, T>> ilist) {
118  clear();
119  insert(ilist);
120 
121  return *this;
122  }
123 #endif
124 
125 
126 
127  /*
128  * Iterators
129  */
130  iterator begin() noexcept { return m_ht.begin(); }
131  const_iterator begin() const noexcept { return m_ht.begin(); }
132  const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
133 
134  iterator end() noexcept { return m_ht.end(); }
135  const_iterator end() const noexcept { return m_ht.end(); }
136  const_iterator cend() const noexcept { return m_ht.cend(); }
137 
138 
139  /*
140  * Capacity
141  */
142  bool empty() const noexcept { return m_ht.empty(); }
143  size_type size() const noexcept { return m_ht.size(); }
144  size_type max_size() const noexcept { return m_ht.max_size(); }
145  size_type max_key_size() const noexcept { return m_ht.max_key_size(); }
146 
147  /**
148  * Call shrink_to_fit() on each hash node of the hat-trie to reduce its size.
149  */
150  void shrink_to_fit() { m_ht.shrink_to_fit(); }
151 
152 
153  /*
154  * Modifiers
155  */
156  void clear() noexcept { m_ht.clear(); }
157 
158 
159 
160  std::pair<iterator, bool> insert_ks(const CharT* key, size_type key_size, const T& value) {
161  return m_ht.insert(key, key_size, value);
162  }
163 #ifdef TSL_HT_HAS_STRING_VIEW
164  std::pair<iterator, bool> insert(const std::basic_string_view<CharT>& key, const T& value) {
165  return m_ht.insert(key.data(), key.size(), value);
166  }
167 #else
168  std::pair<iterator, bool> insert(const CharT* key, const T& value) {
169  return m_ht.insert(key, std::strlen(key), value);
170  }
171 
172  std::pair<iterator, bool> insert(const std::basic_string<CharT>& key, const T& value) {
173  return m_ht.insert(key.data(), key.size(), value);
174  }
175 #endif
176 
177 
178 
179  std::pair<iterator, bool> insert_ks(const CharT* key, size_type key_size, T&& value) {
180  return m_ht.insert(key, key_size, std::move(value));
181  }
182 #ifdef TSL_HT_HAS_STRING_VIEW
183  std::pair<iterator, bool> insert(const std::basic_string_view<CharT>& key, T&& value) {
184  return m_ht.insert(key.data(), key.size(), std::move(value));
185  }
186 #else
187  std::pair<iterator, bool> insert(const CharT* key, T&& value) {
188  return m_ht.insert(key, std::strlen(key), std::move(value));
189  }
190 
191  std::pair<iterator, bool> insert(const std::basic_string<CharT>& key, T&& value) {
192  return m_ht.insert(key.data(), key.size(), std::move(value));
193  }
194 #endif
195 
196 
197 
198  template<class InputIt, typename std::enable_if<is_iterator<InputIt>::value>::type* = nullptr>
199  void insert(InputIt first, InputIt last) {
200  for(auto it = first; it != last; ++it) {
201  insert_pair(*it);
202  }
203  }
204 
205 
206 
207 #ifdef TSL_HT_HAS_STRING_VIEW
209  insert(ilist.begin(), ilist.end());
210  }
211 #else
212  void insert(std::initializer_list<std::pair<const CharT*, T>> ilist) {
213  insert(ilist.begin(), ilist.end());
214  }
215 #endif
216 
217 
218 
219  template<class... Args>
220  std::pair<iterator, bool> emplace_ks(const CharT* key, size_type key_size, Args&&... args) {
221  return m_ht.insert(key, key_size, std::forward<Args>(args)...);
222  }
223 #ifdef TSL_HT_HAS_STRING_VIEW
224  template<class... Args>
225  std::pair<iterator, bool> emplace(const std::basic_string_view<CharT>& key, Args&&... args) {
226  return m_ht.insert(key.data(), key.size(), std::forward<Args>(args)...);
227  }
228 #else
229  template<class... Args>
230  std::pair<iterator, bool> emplace(const CharT* key, Args&&... args) {
231  return m_ht.insert(key, std::strlen(key), std::forward<Args>(args)...);
232  }
233 
234  template<class... Args>
235  std::pair<iterator, bool> emplace(const std::basic_string<CharT>& key, Args&&... args) {
236  return m_ht.insert(key.data(), key.size(), std::forward<Args>(args)...);
237  }
238 #endif
239 
240 
241 
242  iterator erase(const_iterator pos) { return m_ht.erase(pos); }
243  iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
244 
245 
246 
247  size_type erase_ks(const CharT* key, size_type key_size) {
248  return m_ht.erase(key, key_size);
249  }
250 #ifdef TSL_HT_HAS_STRING_VIEW
252  return m_ht.erase(key.data(), key.size());
253  }
254 #else
255  size_type erase(const CharT* key) {
256  return m_ht.erase(key, std::strlen(key));
257  }
258 
259  size_type erase(const std::basic_string<CharT>& key) {
260  return m_ht.erase(key.data(), key.size());
261  }
262 #endif
263 
264 
265 
266  /**
267  * Erase all the elements which have 'prefix' as prefix. Return the number of erase elements.
268  */
269  size_type erase_prefix_ks(const CharT* prefix, size_type prefix_size) {
270  return m_ht.erase_prefix(prefix, prefix_size);
271  }
272 #ifdef TSL_HT_HAS_STRING_VIEW
273  /**
274  * @copydoc erase_prefix_ks(const CharT* prefix, size_type prefix_size)
275  */
277  return m_ht.erase_prefix(prefix.data(), prefix.size());
278  }
279 #else
280  /**
281  * @copydoc erase_prefix_ks(const CharT* prefix, size_type prefix_size)
282  */
283  size_type erase_prefix(const CharT* prefix) {
284  return m_ht.erase_prefix(prefix, std::strlen(prefix));
285  }
286 
287  /**
288  * @copydoc erase_prefix_ks(const CharT* prefix, size_type prefix_size)
289  */
290  size_type erase_prefix(const std::basic_string<CharT>& prefix) {
291  return m_ht.erase_prefix(prefix.data(), prefix.size());
292  }
293 #endif
294 
295 
296 
297  void swap(htrie_map& other) { other.m_ht.swap(m_ht); }
298 
299  /*
300  * Lookup
301  */
302  T& at_ks(const CharT* key, size_type key_size) { return m_ht.at(key, key_size); }
303  const T& at_ks(const CharT* key, size_type key_size) const { return m_ht.at(key, key_size); }
304 
305 #ifdef TSL_HT_HAS_STRING_VIEW
306  T& at(const std::basic_string_view<CharT>& key) { return m_ht.at(key.data(), key.size()); }
307  const T& at(const std::basic_string_view<CharT>& key) const { return m_ht.at(key.data(), key.size()); }
308 #else
309  T& at(const CharT* key) { return m_ht.at(key, std::strlen(key)); }
310  const T& at(const CharT* key) const { return m_ht.at(key, std::strlen(key)); }
311 
312  T& at(const std::basic_string<CharT>& key) { return m_ht.at(key.data(), key.size()); }
313  const T& at(const std::basic_string<CharT>& key) const { return m_ht.at(key.data(), key.size()); }
314 #endif
315 
316 
317 
318 #ifdef TSL_HT_HAS_STRING_VIEW
319  T& operator[](const std::basic_string_view<CharT>& key) { return m_ht.access_operator(key.data(), key.size()); }
320 #else
321  T& operator[](const CharT* key) { return m_ht.access_operator(key, std::strlen(key)); }
322  T& operator[](const std::basic_string<CharT>& key) { return m_ht.access_operator(key.data(), key.size()); }
323 #endif
324 
325 
326 
327  size_type count_ks(const CharT* key, size_type key_size) const { return m_ht.count(key, key_size); }
328 #ifdef TSL_HT_HAS_STRING_VIEW
329  size_type count(const std::basic_string_view<CharT>& key) const { return m_ht.count(key.data(), key.size()); }
330 #else
331  size_type count(const CharT* key) const { return m_ht.count(key, std::strlen(key)); }
332  size_type count(const std::basic_string<CharT>& key) const { return m_ht.count(key.data(), key.size()); }
333 #endif
334 
335 
336 
337  iterator find_ks(const CharT* key, size_type key_size) {
338  return m_ht.find(key, key_size);
339  }
340 
341  const_iterator find_ks(const CharT* key, size_type key_size) const {
342  return m_ht.find(key, key_size);
343  }
344 #ifdef TSL_HT_HAS_STRING_VIEW
346  return m_ht.find(key.data(), key.size());
347  }
348 
350  return m_ht.find(key.data(), key.size());
351  }
352 #else
353  iterator find(const CharT* key) {
354  return m_ht.find(key, std::strlen(key));
355  }
356 
357  const_iterator find(const CharT* key) const {
358  return m_ht.find(key, std::strlen(key));
359  }
360 
361  iterator find(const std::basic_string<CharT>& key) {
362  return m_ht.find(key.data(), key.size());
363  }
364 
365  const_iterator find(const std::basic_string<CharT>& key) const {
366  return m_ht.find(key.data(), key.size());
367  }
368 #endif
369 
370 
371 
372  std::pair<iterator, iterator> equal_range_ks(const CharT* key, size_type key_size) {
373  return m_ht.equal_range(key, key_size);
374  }
375 
376  std::pair<const_iterator, const_iterator> equal_range_ks(const CharT* key, size_type key_size) const {
377  return m_ht.equal_range(key, key_size);
378  }
379 #ifdef TSL_HT_HAS_STRING_VIEW
381  return m_ht.equal_range(key.data(), key.size());
382  }
383 
385  return m_ht.equal_range(key.data(), key.size());
386  }
387 #else
388  std::pair<iterator, iterator> equal_range(const CharT* key) {
389  return m_ht.equal_range(key, std::strlen(key));
390  }
391 
392  std::pair<const_iterator, const_iterator> equal_range(const CharT* key) const {
393  return m_ht.equal_range(key, std::strlen(key));
394  }
395 
396  std::pair<iterator, iterator> equal_range(const std::basic_string<CharT>& key) {
397  return m_ht.equal_range(key.data(), key.size());
398  }
399 
400  std::pair<const_iterator, const_iterator> equal_range(const std::basic_string<CharT>& key) const {
401  return m_ht.equal_range(key.data(), key.size());
402  }
403 #endif
404 
405 
406  /**
407  * Return a range containing all the elements which have 'prefix' as prefix. The range is defined by a pair
408  * of iterator, the first being the begin iterator and the second being the end iterator.
409  */
410  std::pair<prefix_iterator, prefix_iterator> equal_prefix_range_ks(const CharT* prefix, size_type prefix_size) {
411  return m_ht.equal_prefix_range(prefix, prefix_size);
412  }
413 
414  /**
415  * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
416  */
417  std::pair<const_prefix_iterator, const_prefix_iterator> equal_prefix_range_ks(const CharT* prefix, size_type prefix_size) const {
418  return m_ht.equal_prefix_range(prefix, prefix_size);
419  }
420 #ifdef TSL_HT_HAS_STRING_VIEW
421  /**
422  * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
423  */
426  }
427 
428  /**
429  * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
430  */
433  }
434 #else
435  /**
436  * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
437  */
438  std::pair<prefix_iterator, prefix_iterator> equal_prefix_range(const CharT* prefix) {
439  return m_ht.equal_prefix_range(prefix, std::strlen(prefix));
440  }
441 
442  /**
443  * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
444  */
445  std::pair<const_prefix_iterator, const_prefix_iterator> equal_prefix_range(const CharT* prefix) const {
446  return m_ht.equal_prefix_range(prefix, std::strlen(prefix));
447  }
448 
449  /**
450  * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
451  */
452  std::pair<prefix_iterator, prefix_iterator> equal_prefix_range(const std::basic_string<CharT>& prefix) {
453  return m_ht.equal_prefix_range(prefix.data(), prefix.size());
454  }
455 
456  /**
457  * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
458  */
459  std::pair<const_prefix_iterator, const_prefix_iterator> equal_prefix_range(const std::basic_string<CharT>& prefix) const {
460  return m_ht.equal_prefix_range(prefix.data(), prefix.size());
461  }
462 #endif
463 
464 
465 
466  /**
467  * Return the element in the trie which is the longest prefix of `key`. If no
468  * element in the trie is a prefix of `key`, the end iterator is returned.
469  *
470  * Example:
471  *
472  * tsl::htrie_map<char, int> map = {{"/foo", 1}, {"/foo/bar", 1}};
473  *
474  * map.longest_prefix("/foo"); // returns {"/foo", 1}
475  * map.longest_prefix("/foo/baz"); // returns {"/foo", 1}
476  * map.longest_prefix("/foo/bar/baz"); // returns {"/foo/bar", 1}
477  * map.longest_prefix("/foo/bar/"); // returns {"/foo/bar", 1}
478  * map.longest_prefix("/bar"); // returns end()
479  * map.longest_prefix(""); // returns end()
480  */
481  iterator longest_prefix_ks(const CharT* key, size_type key_size) {
482  return m_ht.longest_prefix(key, key_size);
483  }
484 
485  /**
486  * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
487  */
488  const_iterator longest_prefix_ks(const CharT* key, size_type key_size) const {
489  return m_ht.longest_prefix(key, key_size);
490  }
491 #ifdef TSL_HT_HAS_STRING_VIEW
492  /**
493  * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
494  */
496  return m_ht.longest_prefix(key.data(), key.size());
497  }
498 
499  /**
500  * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
501  */
503  return m_ht.longest_prefix(key.data(), key.size());
504  }
505 #else
506  /**
507  * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
508  */
509  iterator longest_prefix(const CharT* key) {
510  return m_ht.longest_prefix(key, std::strlen(key));
511  }
512 
513  /**
514  * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
515  */
516  const_iterator longest_prefix(const CharT* key) const {
517  return m_ht.longest_prefix(key, std::strlen(key));
518  }
519 
520  /**
521  * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
522  */
523  iterator longest_prefix(const std::basic_string<CharT>& key) {
524  return m_ht.longest_prefix(key.data(), key.size());
525  }
526 
527  /**
528  * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
529  */
530  const_iterator longest_prefix(const std::basic_string<CharT>& key) const {
531  return m_ht.longest_prefix(key.data(), key.size());
532  }
533 #endif
534 
535 
536 
537  /*
538  * Hash policy
539  */
540  float max_load_factor() const { return m_ht.max_load_factor(); }
541  void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
542 
543 
544  /*
545  * Burst policy
546  */
547  size_type burst_threshold() const { return m_ht.burst_threshold(); }
548  void burst_threshold(size_type threshold) { m_ht.burst_threshold(threshold); }
549 
550 
551  /*
552  * Observers
553  */
554  hasher hash_function() const { return m_ht.hash_function(); }
555 
556 
557 
558  /*
559  * Other
560  */
561 
562  /**
563  * Serialize the map through the `serializer` parameter.
564  *
565  * The `serializer` parameter must be a function object that supports the following calls:
566  * - `void operator()(const U& value);` where the types `std::uint64_t`, `float` and `T` must be supported for U.
567  * - `void operator()(const CharT* value, std::size_t value_size);`
568  *
569  * The implementation leaves binary compatibilty (endianness, IEEE 754 for floats, ...) of the types it serializes
570  * in the hands of the `Serializer` function object if compatibilty is required.
571  */
572  template<class Serializer>
573  void serialize(Serializer& serializer) const {
574  m_ht.serialize(serializer);
575  }
576 
577 
578  /**
579  * Deserialize a previouly serialized map through the `deserializer` parameter.
580  *
581  * The `deserializer` parameter must be a function object that supports the following calls:
582  * - `template<typename U> U operator()();` where the types `std::uint64_t`, `float` and `T` must be supported for U.
583  * - `void operator()(CharT* value_out, std::size_t value_size);`
584  *
585  * If the deserialized hash map part of the hat-trie is hash compatible with the serialized map, the deserialization process
586  * can be sped up by setting `hash_compatible` to true. To be hash compatible, the Hash (take care of the 32-bits vs 64 bits),
587  * and KeySizeT must behave the same than the ones used in the serialized map. Otherwise the behaviour is undefined
588  * with `hash_compatible` sets to true.
589  *
590  * The behaviour is undefined if the type `CharT` and `T` of the `htrie_map` are not the same as the
591  * types used during serialization.
592  *
593  * The implementation leaves binary compatibilty (endianness, IEEE 754 for floats, size of int, ...) of the types it
594  * deserializes in the hands of the `Deserializer` function object if compatibilty is required.
595  */
596  template<class Deserializer>
597  static htrie_map deserialize(Deserializer& deserializer, bool hash_compatible = false) {
598  htrie_map map;
599  map.m_ht.deserialize(deserializer, hash_compatible);
600 
601  return map;
602  }
603 
604  friend bool operator==(const htrie_map& lhs, const htrie_map& rhs) {
605  if(lhs.size() != rhs.size()) {
606  return false;
607  }
608 
609  std::string key_buffer;
610  for(auto it = lhs.cbegin(); it != lhs.cend(); ++it) {
611  it.key(key_buffer);
612 
613  const auto it_element_rhs = rhs.find(key_buffer);
614  if(it_element_rhs == rhs.cend() || it.value() != it_element_rhs.value()) {
615  return false;
616  }
617  }
618 
619  return true;
620  }
621 
622  friend bool operator!=(const htrie_map& lhs, const htrie_map& rhs) {
623  return !operator==(lhs, rhs);
624  }
625 
626  friend void swap(htrie_map& lhs, htrie_map& rhs) {
627  lhs.swap(rhs);
628  }
629 
630 private:
631  template<class U, class V>
632  void insert_pair(const std::pair<U, V>& value) {
633  insert(value.first, value.second);
634  }
635 
636  template<class U, class V>
637  void insert_pair(std::pair<U, V>&& value) {
638  insert(value.first, std::move(value.second));
639  }
640 
641 private:
642  ht m_ht;
643 };
644 
645 } // end namespace tsl
646 
647 #endif
std::pair< iterator, iterator > equal_range_ks(const CharT *key, size_type key_size)
Definition: htrie_map.h:372
std::pair< iterator, bool > emplace(const std::basic_string< CharT > &key, Args &&... args)
Definition: htrie_map.h:235
iterator erase(const_iterator first, const_iterator last)
Definition: htrie_map.h:243
htrie_map(const Hash &hash=Hash())
Definition: htrie_map.h:73
iterator find_ks(const CharT *key, size_type key_size)
Definition: htrie_map.h:337
std::pair< iterator, bool > emplace(const CharT *key, Args &&... args)
Definition: htrie_map.h:230
const_iterator find_ks(const CharT *key, size_type key_size) const
Definition: htrie_map.h:341
iterator longest_prefix(const std::basic_string< CharT > &key)
Definition: htrie_map.h:523
const_iterator longest_prefix(const std::basic_string< CharT > &key) const
Definition: htrie_map.h:530
iterator find(const std::basic_string< CharT > &key)
Definition: htrie_map.h:361
const_iterator find(const CharT *key) const
Definition: htrie_map.h:357
friend void swap(htrie_map &lhs, htrie_map &rhs)
Definition: htrie_map.h:626
std::pair< prefix_iterator, prefix_iterator > equal_prefix_range(const CharT *prefix)
Definition: htrie_map.h:438
Definition: htrie_hash.h:68
iterator longest_prefix(const CharT *key)
Definition: htrie_map.h:509
float max_load_factor() const
Definition: htrie_map.h:540
std::pair< const_prefix_iterator, const_prefix_iterator > equal_prefix_range(const std::basic_string< CharT > &prefix) const
Definition: htrie_map.h:459
iterator longest_prefix_ks(const CharT *key, size_type key_size)
Definition: htrie_map.h:481
size_type erase(const std::basic_string< CharT > &key)
Definition: htrie_map.h:259
std::pair< iterator, bool > insert_ks(const CharT *key, size_type key_size, T &&value)
Definition: htrie_map.h:179
hasher hash_function() const
Definition: htrie_map.h:554
std::pair< prefix_iterator, prefix_iterator > equal_prefix_range(const std::basic_string< CharT > &prefix)
Definition: htrie_map.h:452
const_iterator find(const std::basic_string< CharT > &key) const
Definition: htrie_map.h:365
void serialize(Serializer &serializer) const
Definition: htrie_map.h:573
Definition: htrie_map.h:54
std::pair< iterator, iterator > equal_range(const CharT *key)
Definition: htrie_map.h:388
iterator erase(const_iterator pos)
Definition: htrie_map.h:242
std::pair< iterator, bool > insert(const std::basic_string< CharT > &key, const T &value)
Definition: htrie_map.h:172
std::pair< iterator, bool > insert(const std::basic_string< CharT > &key, T &&value)
Definition: htrie_map.h:191
size_type count(const CharT *key) const
Definition: htrie_map.h:331
size_type max_key_size() const noexcept
Definition: htrie_map.h:145
T & at(const CharT *key)
Definition: htrie_map.h:309
size_type max_size() const noexcept
Definition: htrie_map.h:144
std::pair< iterator, bool > insert(const CharT *key, T &&value)
Definition: htrie_map.h:187
std::pair< iterator, iterator > equal_range(const std::basic_string< CharT > &key)
Definition: htrie_map.h:396
const_iterator cbegin() const noexcept
Definition: htrie_map.h:132
const T & at_ks(const CharT *key, size_type key_size) const
Definition: htrie_map.h:303
size_type erase(const CharT *key)
Definition: htrie_map.h:255
std::pair< prefix_iterator, prefix_iterator > equal_prefix_range_ks(const CharT *prefix, size_type prefix_size)
Definition: htrie_map.h:410
const T & at(const CharT *key) const
Definition: htrie_map.h:310
std::pair< iterator, bool > emplace_ks(const CharT *key, size_type key_size, Args &&... args)
Definition: htrie_map.h:220
htrie_map & operator=(std::initializer_list< std::pair< const CharT *, T >> ilist)
Definition: htrie_map.h:117
T & at(const std::basic_string< CharT > &key)
Definition: htrie_map.h:312
const T & at(const std::basic_string< CharT > &key) const
Definition: htrie_map.h:313
T & operator[](const std::basic_string< CharT > &key)
Definition: htrie_map.h:322
const_iterator end() const noexcept
Definition: htrie_map.h:135
size_type erase_prefix(const CharT *prefix)
Definition: htrie_map.h:283
std::pair< const_iterator, const_iterator > equal_range_ks(const CharT *key, size_type key_size) const
Definition: htrie_map.h:376
iterator begin() noexcept
Definition: htrie_map.h:130
htrie_map(std::initializer_list< std::pair< const CharT *, T >> init, const Hash &hash=Hash())
Definition: htrie_map.h:100
T & operator[](const CharT *key)
Definition: htrie_map.h:321
void max_load_factor(float ml)
Definition: htrie_map.h:541
void clear() noexcept
Definition: htrie_map.h:156
std::pair< const_iterator, const_iterator > equal_range(const std::basic_string< CharT > &key) const
Definition: htrie_map.h:400
std::pair< const_iterator, const_iterator > equal_range(const CharT *key) const
Definition: htrie_map.h:392
size_type erase_ks(const CharT *key, size_type key_size)
Definition: htrie_map.h:247
size_type erase_prefix(const std::basic_string< CharT > &prefix)
Definition: htrie_map.h:290
size_type burst_threshold() const
Definition: htrie_map.h:547
size_type count(const std::basic_string< CharT > &key) const
Definition: htrie_map.h:332
size_type erase_prefix_ks(const CharT *prefix, size_type prefix_size)
Definition: htrie_map.h:269
const_iterator cend() const noexcept
Definition: htrie_map.h:136
const_iterator longest_prefix(const CharT *key) const
Definition: htrie_map.h:516
const_iterator begin() const noexcept
Definition: htrie_map.h:131
htrie_map(InputIt first, InputIt last, const Hash &hash=Hash())
Definition: htrie_map.h:85
const_iterator longest_prefix_ks(const CharT *key, size_type key_size) const
Definition: htrie_map.h:488
static htrie_map deserialize(Deserializer &deserializer, bool hash_compatible=false)
Definition: htrie_map.h:597
bool empty() const noexcept
Definition: htrie_map.h:142
htrie_map(size_type burst_threshold, const Hash &hash=Hash())
Definition: htrie_map.h:78
void insert(std::initializer_list< std::pair< const CharT *, T >> ilist)
Definition: htrie_map.h:212
size_type size() const noexcept
Definition: htrie_map.h:143
std::pair< const_prefix_iterator, const_prefix_iterator > equal_prefix_range(const CharT *prefix) const
Definition: htrie_map.h:445
std::pair< const_prefix_iterator, const_prefix_iterator > equal_prefix_range_ks(const CharT *prefix, size_type prefix_size) const
Definition: htrie_map.h:417
iterator find(const CharT *key)
Definition: htrie_map.h:353
Definition: htrie_hash.h:130
std::pair< iterator, bool > insert_ks(const CharT *key, size_type key_size, const T &value)
Definition: htrie_map.h:160
friend bool operator==(const htrie_map &lhs, const htrie_map &rhs)
Definition: htrie_map.h:604
Definition: htrie_hash.h:70
friend bool operator!=(const htrie_map &lhs, const htrie_map &rhs)
Definition: htrie_map.h:622
T & at_ks(const CharT *key, size_type key_size)
Definition: htrie_map.h:302
std::pair< iterator, bool > insert(const CharT *key, const T &value)
Definition: htrie_map.h:168
size_type count_ks(const CharT *key, size_type key_size) const
Definition: htrie_map.h:327
void shrink_to_fit()
Definition: htrie_map.h:150
void swap(htrie_map &other)
Definition: htrie_map.h:297
void insert(InputIt first, InputIt last)
Definition: htrie_map.h:199
iterator end() noexcept
Definition: htrie_map.h:134
void burst_threshold(size_type threshold)
Definition: htrie_map.h:548