Debian Codegraph @

third_party/hat-trie/tsl/array-hash/array_set.h

raw
1 /**
2 * MIT License
3 *
4 * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <[email protected]>
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
103 array_set(std::initializer_list<std::basic_string_view<CharT>> init,
104 size_type bucket_count = ht::DEFAULT_INIT_BUCKET_COUNT,
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
121 array_set& operator=(std::initializer_list<std::basic_string_view<CharT>> ilist) {
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
170 std::pair<iterator, bool> insert(const std::basic_string_view<CharT>& key) {
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
209 void insert(std::initializer_list<std::basic_string_view<CharT>> ilist) {
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 */
224 std::pair<iterator, bool> emplace(const std::basic_string_view<CharT>& key) {
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
255 size_type erase(const std::basic_string_view<CharT>& key) {
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 */
277 size_type erase(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) {
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). Useful 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 */
326 size_type count(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) const {
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). Useful 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
355 iterator find(const std::basic_string_view<CharT>& key) {
356 return m_ht.find(key.data(), key.size());
357 }
358
359 const_iterator find(const std::basic_string_view<CharT>& key) const {
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 */
393 iterator find(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) {
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 */
400 const_iterator find(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) const {
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). Useful 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
450 std::pair<iterator, iterator> equal_range(const std::basic_string_view<CharT>& key) {
451 return m_ht.equal_range(key.data(), key.size());
452 }
453
454 std::pair<const_iterator, const_iterator> equal_range(const std::basic_string_view<CharT>& key) const {
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 */
488 std::pair<iterator, iterator> equal_range(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) {
489 return m_ht.equal_range(key.data(), key.size(), precalculated_hash);
490 }
491
492 /**
493 * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
494 */
495 std::pair<const_iterator, const_iterator> equal_range(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) const {
496 return m_ht.equal_range(key.data(), key.size(), precalculated_hash);
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). Useful 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 * - `template<typename U> 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 compatibility (endianness, IEEE 754 for floats, ...) of the types it serializes
585 * in the hands of the `Serializer` function object if compatibility is required.
586 */
587 template<class Serializer>
588 void serialize(Serializer& serializer) const {
589 m_ht.serialize(serializer);
590 }
591
592 /**
593 * Deserialize a previously 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` and `float` 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 ones used on the
602 * serialized 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 * type used during serialization.
606 *
607 * The implementation leaves binary compatibility (endianness, IEEE 754 for floats, size of int, ...) of the types it
608 * deserializes in the hands of the `Deserializer` function object if compatibility 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