array-hash
array_set.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_SET_H
25 #define TSL_ARRAY_SET_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  * Implementation of a cache-conscious string hash set.
40  *
41  * The set stores the strings as `const CharT*`. If `StoreNullTerminator` is true,
42  * the strings are stored with the a null-terminator (the `key()` method of the iterators
43  * will return a pointer to this null-terminated string). Otherwise the null character
44  * is not stored (which allow an economy of 1 byte per string).
45  *
46  * The size of a key string is limited to `std::numeric_limits<KeySizeT>::max() - 1`.
47  * That is 65 535 characters by default, but can be raised with the `KeySizeT` template parameter.
48  * See `max_key_size()` for an easy access to this limit.
49  *
50  * The number of elements in the set is limited to `std::numeric_limits<IndexSizeT>::max()`.
51  * That is 4 294 967 296 elements, but can be raised with the `IndexSizeT` template parameter.
52  * See `max_size()` for an easy access to this limit.
53  *
54  * Iterators invalidation:
55  * - clear, operator=: always invalidate the iterators.
56  * - insert, emplace, operator[]: always invalidate the iterators.
57  * - erase: always invalidate the iterators.
58  * - shrink_to_fit: always invalidate the iterators.
59  */
60 template<class CharT,
61  class Hash = tsl::ah::str_hash<CharT>,
62  class KeyEqual = tsl::ah::str_equal<CharT>,
63  bool StoreNullTerminator = true,
64  class KeySizeT = std::uint16_t,
65  class IndexSizeT = std::uint32_t,
66  class GrowthPolicy = tsl::ah::power_of_two_growth_policy<2>>
67 class array_set {
68 private:
69  template<typename U>
70  using is_iterator = tsl::detail_array_hash::is_iterator<U>;
71 
72  using ht = tsl::detail_array_hash::array_hash<CharT, void, Hash, KeyEqual, StoreNullTerminator,
73  KeySizeT, IndexSizeT, GrowthPolicy>;
74 
75 public:
76  using char_type = typename ht::char_type;
77  using key_size_type = typename ht::key_size_type;
78  using index_size_type = typename ht::index_size_type;
79  using size_type = typename ht::size_type;
80  using hasher = typename ht::hasher;
81  using key_equal = typename ht::key_equal;
82  using iterator = typename ht::iterator;
83  using const_iterator = typename ht::const_iterator;
84 
85  array_set(): array_set(ht::DEFAULT_INIT_BUCKET_COUNT) {
86  }
87 
88  explicit array_set(size_type bucket_count,
89  const Hash& hash = Hash()): m_ht(bucket_count, hash, ht::DEFAULT_MAX_LOAD_FACTOR)
90  {
91  }
92 
93  template<class InputIt, typename std::enable_if<is_iterator<InputIt>::value>::type* = nullptr>
94  array_set(InputIt first, InputIt last,
95  size_type bucket_count = ht::DEFAULT_INIT_BUCKET_COUNT,
96  const Hash& hash = Hash()): array_set(bucket_count, hash)
97  {
98  insert(first, last);
99  }
100 
101 
102 #ifdef TSL_AH_HAS_STRING_VIEW
105  const Hash& hash = Hash()): array_set(bucket_count, hash)
106  {
107  insert(init);
108  }
109 #else
110  array_set(std::initializer_list<const CharT*> init,
111  size_type bucket_count = ht::DEFAULT_INIT_BUCKET_COUNT,
112  const Hash& hash = Hash()): array_set(bucket_count, hash)
113  {
114  insert(init);
115  }
116 #endif
117 
118 
119 
120 #ifdef TSL_AH_HAS_STRING_VIEW
122  clear();
123 
124  reserve(ilist.size());
125  insert(ilist);
126 
127  return *this;
128  }
129 #else
130  array_set& operator=(std::initializer_list<const CharT*> ilist) {
131  clear();
132 
133  reserve(ilist.size());
134  insert(ilist);
135 
136  return *this;
137  }
138 #endif
139 
140  /*
141  * Iterators
142  */
143  iterator begin() noexcept { return m_ht.begin(); }
144  const_iterator begin() const noexcept { return m_ht.begin(); }
145  const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
146 
147  iterator end() noexcept { return m_ht.end(); }
148  const_iterator end() const noexcept { return m_ht.end(); }
149  const_iterator cend() const noexcept { return m_ht.cend(); }
150 
151 
152  /*
153  * Capacity
154  */
155  bool empty() const noexcept { return m_ht.empty(); }
156  size_type size() const noexcept { return m_ht.size(); }
157  size_type max_size() const noexcept { return m_ht.max_size(); }
158  size_type max_key_size() const noexcept { return m_ht.max_key_size(); }
159  void shrink_to_fit() { m_ht.shrink_to_fit(); }
160 
161 
162  /*
163  * Modifiers
164  */
165  void clear() noexcept { m_ht.clear(); }
166 
167 
168 
169 #ifdef TSL_AH_HAS_STRING_VIEW
171  return m_ht.emplace(key.data(), key.size());
172  }
173 #else
174  std::pair<iterator, bool> insert(const CharT* key) {
175  return m_ht.emplace(key, std::char_traits<CharT>::length(key));
176  }
177 
178  std::pair<iterator, bool> insert(const std::basic_string<CharT>& key) {
179  return m_ht.emplace(key.data(), key.size());
180  }
181 #endif
182  std::pair<iterator, bool> insert_ks(const CharT* key, size_type key_size) {
183  return m_ht.emplace(key, key_size);
184  }
185 
186 
187 
188  template<class InputIt, typename std::enable_if<is_iterator<InputIt>::value>::type* = nullptr>
189  void insert(InputIt first, InputIt last) {
190  if(std::is_base_of<std::forward_iterator_tag,
191  typename std::iterator_traits<InputIt>::iterator_category>::value)
192  {
193  const auto nb_elements_insert = std::distance(first, last);
194  const std::size_t nb_free_buckets = std::size_t(float(bucket_count())*max_load_factor()) - size();
195 
196  if(nb_elements_insert > 0 && nb_free_buckets < std::size_t(nb_elements_insert)) {
197  reserve(size() + std::size_t(nb_elements_insert));
198  }
199  }
200 
201  for(auto it = first; it != last; ++it) {
202  insert(*it);
203  }
204  }
205 
206 
207 
208 #ifdef TSL_AH_HAS_STRING_VIEW
210  insert(ilist.begin(), ilist.end());
211  }
212 #else
213  void insert(std::initializer_list<const CharT*> ilist) {
214  insert(ilist.begin(), ilist.end());
215  }
216 #endif
217 
218 
219 
220 #ifdef TSL_AH_HAS_STRING_VIEW
221  /**
222  * @copydoc emplace_ks(const CharT* key, size_type key_size)
223  */
225  return m_ht.emplace(key.data(), key.size());
226  }
227 #else
228  /**
229  * @copydoc emplace_ks(const CharT* key, size_type key_size)
230  */
231  std::pair<iterator, bool> emplace(const CharT* key) {
232  return m_ht.emplace(key, std::char_traits<CharT>::length(key));
233  }
234 
235  /**
236  * @copydoc emplace_ks(const CharT* key, size_type key_size)
237  */
238  std::pair<iterator, bool> emplace(const std::basic_string<CharT>& key) {
239  return m_ht.emplace(key.data(), key.size());
240  }
241 #endif
242  /**
243  * No difference compared to the insert method. Mainly here for coherence with array_map.
244  */
245  std::pair<iterator, bool> emplace_ks(const CharT* key, size_type key_size) {
246  return m_ht.emplace(key, key_size);
247  }
248 
249 
250 
251  iterator erase(const_iterator pos) { return m_ht.erase(pos); }
252  iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
253 
254 #ifdef TSL_AH_HAS_STRING_VIEW
256  return m_ht.erase(key.data(), key.size());
257  }
258 #else
259  size_type erase(const CharT* key) {
260  return m_ht.erase(key, std::char_traits<CharT>::length(key));
261  }
262 
263  size_type erase(const std::basic_string<CharT>& key) {
264  return m_ht.erase(key.data(), key.size());
265  }
266 #endif
267  size_type erase_ks(const CharT* key, size_type key_size) {
268  return m_ht.erase(key, key_size);
269  }
270 
271 
272 
273 #ifdef TSL_AH_HAS_STRING_VIEW
274  /**
275  * @copydoc erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
276  */
278  return m_ht.erase(key.data(), key.size(), precalculated_hash);
279  }
280 #else
281  /**
282  * @copydoc erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
283  */
284  size_type erase(const CharT* key, std::size_t precalculated_hash) {
285  return m_ht.erase(key, std::char_traits<CharT>::length(key), precalculated_hash);
286  }
287 
288  /**
289  * @copydoc erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
290  */
291  size_type erase(const std::basic_string<CharT>& key, std::size_t precalculated_hash) {
292  return m_ht.erase(key.data(), key.size(), precalculated_hash);
293  }
294 #endif
295  /**
296  * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
297  * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
298  */
299  size_type erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) {
300  return m_ht.erase(key, key_size, precalculated_hash);
301  }
302 
303 
304 
305  void swap(array_set& other) { other.m_ht.swap(m_ht); }
306 
307 
308 
309  /*
310  * Lookup
311  */
312 #ifdef TSL_AH_HAS_STRING_VIEW
313  size_type count(const std::basic_string_view<CharT>& key) const { return m_ht.count(key.data(), key.size()); }
314 #else
315  size_type count(const CharT* key) const { return m_ht.count(key, std::char_traits<CharT>::length(key)); }
316  size_type count(const std::basic_string<CharT>& key) const { return m_ht.count(key.data(), key.size()); }
317 #endif
318  size_type count_ks(const CharT* key, size_type key_size) const { return m_ht.count(key, key_size); }
319 
320 
321 
322 #ifdef TSL_AH_HAS_STRING_VIEW
323  /**
324  * @copydoc count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const
325  */
327  return m_ht.count(key.data(), key.size(), precalculated_hash);
328  }
329 #else
330  /**
331  * @copydoc count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const
332  */
333  size_type count(const CharT* key, std::size_t precalculated_hash) const {
334  return m_ht.count(key, std::char_traits<CharT>::length(key), precalculated_hash);
335  }
336 
337  /**
338  * @copydoc count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const
339  */
340  size_type count(const std::basic_string<CharT>& key, std::size_t precalculated_hash) const {
341  return m_ht.count(key.data(), key.size(), precalculated_hash);
342  }
343 #endif
344  /**
345  * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
346  * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
347  */
348  size_type count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const {
349  return m_ht.count(key, key_size, precalculated_hash);
350  }
351 
352 
353 
354 #ifdef TSL_AH_HAS_STRING_VIEW
356  return m_ht.find(key.data(), key.size());
357  }
358 
360  return m_ht.find(key.data(), key.size());
361  }
362 #else
363  iterator find(const CharT* key) {
364  return m_ht.find(key, std::char_traits<CharT>::length(key));
365  }
366 
367  const_iterator find(const CharT* key) const {
368  return m_ht.find(key, std::char_traits<CharT>::length(key));
369  }
370 
371  iterator find(const std::basic_string<CharT>& key) {
372  return m_ht.find(key.data(), key.size());
373  }
374 
375  const_iterator find(const std::basic_string<CharT>& key) const {
376  return m_ht.find(key.data(), key.size());
377  }
378 #endif
379  iterator find_ks(const CharT* key, size_type key_size) {
380  return m_ht.find(key, key_size);
381  }
382 
383  const_iterator find_ks(const CharT* key, size_type key_size) const {
384  return m_ht.find(key, key_size);
385  }
386 
387 
388 
389 #ifdef TSL_AH_HAS_STRING_VIEW
390  /**
391  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
392  */
394  return m_ht.find(key.data(), key.size(), precalculated_hash);
395  }
396 
397  /**
398  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
399  */
401  return m_ht.find(key.data(), key.size(), precalculated_hash);
402  }
403 #else
404  /**
405  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
406  */
407  iterator find(const CharT* key, std::size_t precalculated_hash) {
408  return m_ht.find(key, std::char_traits<CharT>::length(key), precalculated_hash);
409  }
410 
411  /**
412  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
413  */
414  const_iterator find(const CharT* key, std::size_t precalculated_hash) const {
415  return m_ht.find(key, std::char_traits<CharT>::length(key), precalculated_hash);
416  }
417 
418  /**
419  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
420  */
421  iterator find(const std::basic_string<CharT>& key, std::size_t precalculated_hash) {
422  return m_ht.find(key.data(), key.size(), precalculated_hash);
423  }
424 
425  /**
426  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
427  */
428  const_iterator find(const std::basic_string<CharT>& key, std::size_t precalculated_hash) const {
429  return m_ht.find(key.data(), key.size(), precalculated_hash);
430  }
431 #endif
432  /**
433  * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
434  * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
435  */
436  iterator find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) {
437  return m_ht.find(key, key_size, precalculated_hash);
438  }
439 
440  /**
441  * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
442  */
443  const_iterator find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const {
444  return m_ht.find(key, key_size, precalculated_hash);
445  }
446 
447 
448 
449 #ifdef TSL_AH_HAS_STRING_VIEW
451  return m_ht.equal_range(key.data(), key.size());
452  }
453 
455  return m_ht.equal_range(key.data(), key.size());
456  }
457 #else
458  std::pair<iterator, iterator> equal_range(const CharT* key) {
459  return m_ht.equal_range(key, std::char_traits<CharT>::length(key));
460  }
461 
462  std::pair<const_iterator, const_iterator> equal_range(const CharT* key) const {
463  return m_ht.equal_range(key, std::char_traits<CharT>::length(key));
464  }
465 
466  std::pair<iterator, iterator> equal_range(const std::basic_string<CharT>& key) {
467  return m_ht.equal_range(key.data(), key.size());
468  }
469 
470  std::pair<const_iterator, const_iterator> equal_range(const std::basic_string<CharT>& key) const {
471  return m_ht.equal_range(key.data(), key.size());
472  }
473 #endif
474  std::pair<iterator, iterator> equal_range_ks(const CharT* key, size_type key_size) {
475  return m_ht.equal_range(key, key_size);
476  }
477 
478  std::pair<const_iterator, const_iterator> equal_range_ks(const CharT* key, size_type key_size) const {
479  return m_ht.equal_range(key, key_size);
480  }
481 
482 
483 
484 #ifdef TSL_AH_HAS_STRING_VIEW
485  /**
486  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
487  */
490  }
491 
492  /**
493  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
494  */
497  }
498 #else
499  /**
500  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
501  */
502  std::pair<iterator, iterator> equal_range(const CharT* key, std::size_t precalculated_hash) {
503  return m_ht.equal_range(key, std::char_traits<CharT>::length(key), precalculated_hash);
504  }
505 
506  /**
507  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
508  */
509  std::pair<const_iterator, const_iterator> equal_range(const CharT* key, std::size_t precalculated_hash) const {
510  return m_ht.equal_range(key, std::char_traits<CharT>::length(key), precalculated_hash);
511  }
512 
513  /**
514  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
515  */
516  std::pair<iterator, iterator> equal_range(const std::basic_string<CharT>& key, std::size_t precalculated_hash) {
517  return m_ht.equal_range(key.data(), key.size(), precalculated_hash);
518  }
519 
520  /**
521  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
522  */
523  std::pair<const_iterator, const_iterator> equal_range(const std::basic_string<CharT>& key, std::size_t precalculated_hash) const {
524  return m_ht.equal_range(key.data(), key.size(), precalculated_hash);
525  }
526 #endif
527  /**
528  * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
529  * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
530  */
531  std::pair<iterator, iterator> equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) {
532  return m_ht.equal_range(key, key_size, precalculated_hash);
533  }
534 
535  /**
536  * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
537  */
538  std::pair<const_iterator, const_iterator> equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const {
539  return m_ht.equal_range(key, key_size, precalculated_hash);
540  }
541 
542 
543 
544  /*
545  * Bucket interface
546  */
547  size_type bucket_count() const { return m_ht.bucket_count(); }
548  size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
549 
550 
551  /*
552  * Hash policy
553  */
554  float load_factor() const { return m_ht.load_factor(); }
555  float max_load_factor() const { return m_ht.max_load_factor(); }
556  void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
557 
558  void rehash(size_type count) { m_ht.rehash(count); }
559  void reserve(size_type count) { m_ht.reserve(count); }
560 
561 
562  /*
563  * Observers
564  */
565  hasher hash_function() const { return m_ht.hash_function(); }
566  key_equal key_eq() const { return m_ht.key_eq(); }
567 
568 
569  /*
570  * Other
571  */
572  /**
573  * Return the `const_iterator it` as an `iterator`.
574  */
575  iterator mutable_iterator(const_iterator it) noexcept { return m_ht.mutable_iterator(it); }
576 
577  /**
578  * Serialize the set through the `serializer` parameter.
579  *
580  * The `serializer` parameter must be a function object that supports the following calls:
581  * - `void operator()(const U& value);` where the types `std::uint64_t` and `float` must be supported for U.
582  * - `void operator()(const CharT* value, std::size_t value_size);`
583  *
584  * The implementation leaves binary compatibilty (endianness, IEEE 754 for floats, ...) of the types it serializes
585  * in the hands of the `Serializer` function object if compatibilty is required.
586  */
587  template<class Serializer>
588  void serialize(Serializer& serializer) const {
589  m_ht.serialize(serializer);
590  }
591 
592  /**
593  * Deserialize a previouly serialized set through the `deserializer` parameter.
594  *
595  * The `deserializer` parameter must be a function object that supports the following calls:
596  * - `template<typename U> U operator()();` where the types `std::uint64_t`, `float` and `T` must be supported for U.
597  * - `void operator()(CharT* value_out, std::size_t value_size);`
598  *
599  * If the deserialized hash set type is hash compatible with the serialized set, the deserialization process can be
600  * sped up by setting `hash_compatible` to true. To be hash compatible, the Hash (take care of the 32-bits vs 64 bits),
601  * KeyEqual, GrowthPolicy, StoreNullTerminator, KeySizeT and IndexSizeT must behave the same than the one used on the
602  * serialazed set. Otherwise the behaviour is undefined with `hash_compatible` sets to true, .
603  *
604  * The behaviour is undefined if the type `CharT` of the `array_set` is not the same as the
605  * types used during serialization.
606  *
607  * The implementation leaves binary compatibilty (endianness, IEEE 754 for floats, ...) of the types it deserializes
608  * in the hands of the `Deserializer` function object if compatibilty is required.
609  */
610  template<class Deserializer>
611  static array_set deserialize(Deserializer& deserializer, bool hash_compatible = false) {
612  array_set set(0);
613  set.m_ht.deserialize(deserializer, hash_compatible);
614 
615  return set;
616  }
617 
618  friend bool operator==(const array_set& lhs, const array_set& rhs) {
619  if(lhs.size() != rhs.size()) {
620  return false;
621  }
622 
623  for(auto it = lhs.cbegin(); it != lhs.cend(); ++it) {
624  const auto it_element_rhs = rhs.find_ks(it.key(), it.key_size());
625  if(it_element_rhs == rhs.cend()) {
626  return false;
627  }
628  }
629 
630  return true;
631  }
632 
633  friend bool operator!=(const array_set& lhs, const array_set& rhs) {
634  return !operator==(lhs, rhs);
635  }
636 
637  friend void swap(array_set& lhs, array_set& rhs) {
638  lhs.swap(rhs);
639  }
640 
641 public:
642  static const size_type MAX_KEY_SIZE = ht::MAX_KEY_SIZE;
643 
644 private:
645  ht m_ht;
646 };
647 
648 
649 /**
650  * Same as
651  * `tsl::array_set<CharT, Hash, KeyEqual, StoreNullTerminator, KeySizeT, IndexSizeT, tsl::ah::prime_growth_policy>`.
652  */
653 template<class CharT,
654  class Hash = tsl::ah::str_hash<CharT>,
655  class KeyEqual = tsl::ah::str_equal<CharT>,
656  bool StoreNullTerminator = true,
657  class KeySizeT = std::uint16_t,
658  class IndexSizeT = std::uint32_t>
659 using array_pg_set = array_set<CharT, Hash, KeyEqual, StoreNullTerminator,
660  KeySizeT, IndexSizeT, tsl::ah::prime_growth_policy>;
661 
662 } //end namespace tsl
663 
664 #endif
iterator find_ks(const CharT *key, size_type key_size)
Definition: array_set.h:379
bool empty() const noexcept
Definition: array_set.h:155
std::pair< const_iterator, const_iterator > equal_range_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash) const
Definition: array_set.h:538
void reserve(size_type count)
Definition: array_set.h:559
iterator find_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash)
Definition: array_set.h:436
const_iterator end() const noexcept
Definition: array_set.h:148
friend bool operator==(const array_set &lhs, const array_set &rhs)
Definition: array_set.h:618
array_set()
Definition: array_set.h:85
Definition: array_growth_policy.h:40
void rehash(size_type count)
Definition: array_set.h:558
Definition: array_growth_policy.h:39
void max_load_factor(float ml)
Definition: array_set.h:556
void serialize(Serializer &serializer) const
Definition: array_set.h:588
void clear() noexcept
Definition: array_set.h:165
Definition: array_hash.h:117
void shrink_to_fit()
Definition: array_set.h:159
const_iterator find_ks(const CharT *key, size_type key_size) const
Definition: array_set.h:383
size_type count_ks(const CharT *key, size_type key_size) const
Definition: array_set.h:318
iterator begin() noexcept
Definition: array_set.h:143
Definition: array_hash.h:102
iterator erase(const_iterator first, const_iterator last)
Definition: array_set.h:252
std::pair< iterator, bool > insert_ks(const CharT *key, size_type key_size)
Definition: array_set.h:182
hasher hash_function() const
Definition: array_set.h:565
std::pair< iterator, iterator > equal_range_ks(const CharT *key, size_type key_size)
Definition: array_set.h:474
size_type erase_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash)
Definition: array_set.h:299
array_set(size_type bucket_count, const Hash &hash=Hash())
Definition: array_set.h:88
std::pair< iterator, iterator > equal_range_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash)
Definition: array_set.h:531
const_iterator cbegin() const noexcept
Definition: array_set.h:145
friend void swap(array_set &lhs, array_set &rhs)
Definition: array_set.h:637
iterator mutable_iterator(const_iterator it) noexcept
Definition: array_set.h:575
size_type max_size() const noexcept
Definition: array_set.h:157
size_type erase_ks(const CharT *key, size_type key_size)
Definition: array_set.h:267
float load_factor() const
Definition: array_set.h:554
iterator erase(const_iterator pos)
Definition: array_set.h:251
std::size_t operator()(const CharT *key, std::size_t key_size) const
Definition: array_hash.h:79
float max_load_factor() const
Definition: array_set.h:555
const_iterator find_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash) const
Definition: array_set.h:443
Definition: array_growth_policy.h:49
Definition: array_growth_policy.h:247
void swap(array_set &other)
Definition: array_set.h:305
static array_set deserialize(Deserializer &deserializer, bool hash_compatible=false)
Definition: array_set.h:611
std::pair< const_iterator, const_iterator > equal_range_ks(const CharT *key, size_type key_size) const
Definition: array_set.h:478
const_iterator begin() const noexcept
Definition: array_set.h:144
static const size_type MAX_KEY_SIZE
Definition: array_set.h:642
const_iterator cend() const noexcept
Definition: array_set.h:149
size_type count_ks(const CharT *key, size_type key_size, std::size_t precalculated_hash) const
Definition: array_set.h:348
size_type max_key_size() const noexcept
Definition: array_set.h:158
key_equal key_eq() const
Definition: array_set.h:566
size_type max_bucket_count() const
Definition: array_set.h:548
size_type bucket_count() const
Definition: array_set.h:547
size_type size() const noexcept
Definition: array_set.h:156
std::pair< const_iterator, const_iterator > equal_range(const std::basic_string_view< CharT > &key, std::size_t precalculated_hash) const
Definition: array_set.h:495
Definition: array_hash.h:742
std::pair< iterator, bool > emplace_ks(const CharT *key, size_type key_size)
Definition: array_set.h:245
array_set(InputIt first, InputIt last, size_type bucket_count=ht::DEFAULT_INIT_BUCKET_COUNT, const Hash &hash=Hash())
Definition: array_set.h:94
friend bool operator!=(const array_set &lhs, const array_set &rhs)
Definition: array_set.h:633
iterator end() noexcept
Definition: array_set.h:147
void insert(InputIt first, InputIt last)
Definition: array_set.h:189