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_ORDERED_SET_H
25#define TSL_ORDERED_SET_H
26
27
28#include <cstddef>
29#include <deque>
30#include <functional>
31#include <initializer_list>
32#include <memory>
33#include <type_traits>
34#include <utility>
35#include <vector>
36#include "ordered_hash.h"
37
38
39namespace tsl {
40
41
42/**
43 * Implementation of an hash set using open adressing with robin hood with backshift delete to resolve collisions.
44 *
45 * The particularity of this hash set is that it remembers the order in which the elements were added and
46 * provide a way to access the structure which stores these values through the 'values_container()' method.
47 * The used container is defined by ValueTypeContainer, by default a std::deque is used (grows faster) but
48 * a std::vector may be used. In this case the set provides a 'data()' method which give a direct access
49 * to the memory used to store the values (which can be usefull to communicate with C API's).
50 *
51 * The Key must be copy constructible and/or move constructible. To use `unordered_erase` it also must be swappable.
52 *
53 * The behaviour of the hash set is undefinded if the destructor of Key throws an exception.
54 *
55 * Iterators invalidation:
56 * - clear, operator=, reserve, rehash: always invalidate the iterators (also invalidate end()).
57 * - insert, emplace, emplace_hint, operator[]: when a std::vector is used as ValueTypeContainer
58 * and if size() < capacity(), only end().
59 * Otherwise all the iterators are invalidated if an insert occurs.
60 * - erase, unordered_erase: when a std::vector is used as ValueTypeContainer invalidate the iterator of
61 * the erased element and all the ones after the erased element (including end()).
62 * Otherwise all the iterators are invalidated if an erase occurs.
63 */
64template<class Key,
65 class Hash = std::hash<Key>,
66 class KeyEqual = std::equal_to<Key>,
67 class Allocator = std::allocator<Key>,
68 class ValueTypeContainer = std::deque<Key, Allocator>>
69class ordered_set {
70private:
71 template<typename U>
72 using has_is_transparent = tsl::detail_ordered_hash::has_is_transparent<U>;
73
74 class KeySelect {
75 public:
76 using key_type = Key;
77
78 const key_type& operator()(const Key& key) const noexcept {
79 return key;
80 }
81
82 key_type& operator()(Key& key) noexcept {
83 return key;
84 }
85 };
86
87 using ht = detail_ordered_hash::ordered_hash<Key, KeySelect, void,
88 Hash, KeyEqual, Allocator, ValueTypeContainer>;
89
90public:
91 using key_type = typename ht::key_type;
92 using value_type = typename ht::value_type;
93 using size_type = typename ht::size_type;
94 using difference_type = typename ht::difference_type;
95 using hasher = typename ht::hasher;
96 using key_equal = typename ht::key_equal;
97 using allocator_type = typename ht::allocator_type;
98 using reference = typename ht::reference;
99 using const_reference = typename ht::const_reference;
100 using pointer = typename ht::pointer;
101 using const_pointer = typename ht::const_pointer;
102 using iterator = typename ht::iterator;
103 using const_iterator = typename ht::const_iterator;
104 using reverse_iterator = typename ht::reverse_iterator;
105 using const_reverse_iterator = typename ht::const_reverse_iterator;
106
107 using values_container_type = typename ht::values_container_type;
108
109
110 /*
111 * Constructors
112 */
113 ordered_set(): ordered_set(ht::DEFAULT_INIT_BUCKETS_SIZE) {
114 }
115
116 explicit ordered_set(size_type bucket_count,
117 const Hash& hash = Hash(),
118 const KeyEqual& equal = KeyEqual(),
119 const Allocator& alloc = Allocator()):
120 m_ht(bucket_count, hash, equal, alloc, ht::DEFAULT_MAX_LOAD_FACTOR)
121 {
122 }
123
124 ordered_set(size_type bucket_count,
125 const Allocator& alloc): ordered_set(bucket_count, Hash(), KeyEqual(), alloc)
126 {
127 }
128
129 ordered_set(size_type bucket_count,
130 const Hash& hash,
131 const Allocator& alloc): ordered_set(bucket_count, hash, KeyEqual(), alloc)
132 {
133 }
134
135 explicit ordered_set(const Allocator& alloc): ordered_set(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {
136 }
137
138 template<class InputIt>
139 ordered_set(InputIt first, InputIt last,
140 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
141 const Hash& hash = Hash(),
142 const KeyEqual& equal = KeyEqual(),
143 const Allocator& alloc = Allocator()): ordered_set(bucket_count, hash, equal, alloc)
144 {
145 insert(first, last);
146 }
147
148 template<class InputIt>
149 ordered_set(InputIt first, InputIt last,
150 size_type bucket_count,
151 const Allocator& alloc): ordered_set(first, last, bucket_count, Hash(), KeyEqual(), alloc)
152 {
153 }
154
155 template<class InputIt>
156 ordered_set(InputIt first, InputIt last,
157 size_type bucket_count,
158 const Hash& hash,
159 const Allocator& alloc): ordered_set(first, last, bucket_count, hash, KeyEqual(), alloc)
160 {
161 }
162
163 ordered_set(std::initializer_list<value_type> init,
164 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
165 const Hash& hash = Hash(),
166 const KeyEqual& equal = KeyEqual(),
167 const Allocator& alloc = Allocator()):
168 ordered_set(init.begin(), init.end(), bucket_count, hash, equal, alloc)
169 {
170 }
171
172 ordered_set(std::initializer_list<value_type> init,
173 size_type bucket_count,
174 const Allocator& alloc):
175 ordered_set(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(), alloc)
176 {
177 }
178
179 ordered_set(std::initializer_list<value_type> init,
180 size_type bucket_count,
181 const Hash& hash,
182 const Allocator& alloc):
183 ordered_set(init.begin(), init.end(), bucket_count, hash, KeyEqual(), alloc)
184 {
185 }
186
187
188 ordered_set& operator=(std::initializer_list<value_type> ilist) {
189 m_ht.clear();
190
191 m_ht.reserve(ilist.size());
192 m_ht.insert(ilist.begin(), ilist.end());
193
194 return *this;
195 }
196
197 allocator_type get_allocator() const { return m_ht.get_allocator(); }
198
199
200 /*
201 * Iterators
202 */
203 iterator begin() noexcept { return m_ht.begin(); }
204 const_iterator begin() const noexcept { return m_ht.begin(); }
205 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
206
207 iterator end() noexcept { return m_ht.end(); }
208 const_iterator end() const noexcept { return m_ht.end(); }
209 const_iterator cend() const noexcept { return m_ht.cend(); }
210
211 reverse_iterator rbegin() noexcept { return m_ht.rbegin(); }
212 const_reverse_iterator rbegin() const noexcept { return m_ht.rbegin(); }
213 const_reverse_iterator rcbegin() const noexcept { return m_ht.rcbegin(); }
214
215 reverse_iterator rend() noexcept { return m_ht.rend(); }
216 const_reverse_iterator rend() const noexcept { return m_ht.rend(); }
217 const_reverse_iterator rcend() const noexcept { return m_ht.rcend(); }
218
219
220 /*
221 * Capacity
222 */
223 bool empty() const noexcept { return m_ht.empty(); }
224 size_type size() const noexcept { return m_ht.size(); }
225 size_type max_size() const noexcept { return m_ht.max_size(); }
226
227 /*
228 * Modifiers
229 */
230 void clear() noexcept { m_ht.clear(); }
231
232
233
234 std::pair<iterator, bool> insert(const value_type& value) { return m_ht.insert(value); }
235 std::pair<iterator, bool> insert(value_type&& value) { return m_ht.insert(std::move(value)); }
236
237 iterator insert(const_iterator hint, const value_type& value) {
238 return m_ht.insert(hint, value);
239 }
240
241 iterator insert(const_iterator hint, value_type&& value) {
242 return m_ht.insert(hint, std::move(value));
243 }
244
245 template<class InputIt>
246 void insert(InputIt first, InputIt last) { m_ht.insert(first, last); }
247 void insert(std::initializer_list<value_type> ilist) { m_ht.insert(ilist.begin(), ilist.end()); }
248
249
250
251 /**
252 * Due to the way elements are stored, emplace will need to move or copy the key-value once.
253 * The method is equivalent to insert(value_type(std::forward<Args>(args)...));
254 *
255 * Mainly here for compatibility with the std::unordered_map interface.
256 */
257 template<class... Args>
258 std::pair<iterator, bool> emplace(Args&&... args) { return m_ht.emplace(std::forward<Args>(args)...); }
259
260 /**
261 * Due to the way elements are stored, emplace_hint will need to move or copy the key-value once.
262 * The method is equivalent to insert(hint, value_type(std::forward<Args>(args)...));
263 *
264 * Mainly here for compatibility with the std::unordered_map interface.
265 */
266 template<class... Args>
267 iterator emplace_hint(const_iterator hint, Args&&... args) {
268 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
269 }
270
271 /**
272 * When erasing an element, the insert order will be preserved and no holes will be present in the container
273 * returned by 'values_container()'.
274 *
275 * The method is in O(n), if the order is not important 'unordered_erase(...)' method is faster with an O(1)
276 * average complexity.
277 */
278 iterator erase(iterator pos) { return m_ht.erase(pos); }
279
280 /**
281 * @copydoc erase(iterator pos)
282 */
283 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
284
285 /**
286 * @copydoc erase(iterator pos)
287 */
288 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
289
290 /**
291 * @copydoc erase(iterator pos)
292 */
293 size_type erase(const key_type& key) { return m_ht.erase(key); }
294
295 /**
296 * @copydoc erase(iterator pos)
297 *
298 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
299 * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
300 */
301 size_type erase(const key_type& key, std::size_t precalculated_hash) {
302 return m_ht.erase(key, precalculated_hash);
303 }
304
305 /**
306 * @copydoc erase(iterator pos)
307 *
308 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
309 * If so, K must be hashable and comparable to Key.
310 */
311 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
312 size_type erase(const K& key) { return m_ht.erase(key); }
313
314 /**
315 * @copydoc erase(const key_type& key, std::size_t precalculated_hash)
316 *
317 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
318 * If so, K must be hashable and comparable to Key.
319 */
320 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
321 size_type erase(const K& key, std::size_t precalculated_hash) {
322 return m_ht.erase(key, precalculated_hash);
323 }
324
325
326
327 void swap(ordered_set& other) { other.m_ht.swap(m_ht); }
328
329 /*
330 * Lookup
331 */
332 size_type count(const Key& key) const { return m_ht.count(key); }
333
334 /**
335 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
336 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
337 */
338 size_type count(const Key& key, std::size_t precalculated_hash) const {
339 return m_ht.count(key, precalculated_hash);
340 }
341
342 /**
343 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
344 * If so, K must be hashable and comparable to Key.
345 */
346 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
347 size_type count(const K& key) const { return m_ht.count(key); }
348
349 /**
350 * @copydoc count(const K& key) const
351 *
352 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
353 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
354 */
355 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
356 size_type count(const K& key, std::size_t precalculated_hash) const {
357 return m_ht.count(key, precalculated_hash);
358 }
359
360
361
362
363 iterator find(const Key& key) { return m_ht.find(key); }
364
365 /**
366 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
367 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
368 */
369 iterator find(const Key& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); }
370
371 const_iterator find(const Key& key) const { return m_ht.find(key); }
372
373 /**
374 * @copydoc find(const Key& key, std::size_t precalculated_hash)
375 */
376 const_iterator find(const Key& key, std::size_t precalculated_hash) const {
377 return m_ht.find(key, precalculated_hash);
378 }
379
380 /**
381 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
382 * If so, K must be hashable and comparable to Key.
383 */
384 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
385 iterator find(const K& key) { return m_ht.find(key); }
386
387 /**
388 * @copydoc find(const K& key)
389 *
390 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
391 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
392 */
393 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
394 iterator find(const K& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); }
395
396 /**
397 * @copydoc find(const K& key)
398 */
399 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
400 const_iterator find(const K& key) const { return m_ht.find(key); }
401
402 /**
403 * @copydoc find(const K& key)
404 *
405 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
406 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
407 */
408 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
409 const_iterator find(const K& key, std::size_t precalculated_hash) const {
410 return m_ht.find(key, precalculated_hash);
411 }
412
413
414
415 std::pair<iterator, iterator> equal_range(const Key& key) { return m_ht.equal_range(key); }
416
417 /**
418 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
419 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
420 */
421 std::pair<iterator, iterator> equal_range(const Key& key, std::size_t precalculated_hash) {
422 return m_ht.equal_range(key, precalculated_hash);
423 }
424
425 std::pair<const_iterator, const_iterator> equal_range(const Key& key) const { return m_ht.equal_range(key); }
426
427 /**
428 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
429 */
430 std::pair<const_iterator, const_iterator> equal_range(const Key& key, std::size_t precalculated_hash) const {
431 return m_ht.equal_range(key, precalculated_hash);
432 }
433
434 /**
435 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
436 * If so, K must be hashable and comparable to Key.
437 */
438 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
439 std::pair<iterator, iterator> equal_range(const K& key) { return m_ht.equal_range(key); }
440
441 /**
442 * @copydoc equal_range(const K& key)
443 *
444 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
445 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
446 */
447 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
448 std::pair<iterator, iterator> equal_range(const K& key, std::size_t precalculated_hash) {
449 return m_ht.equal_range(key, precalculated_hash);
450 }
451
452 /**
453 * @copydoc equal_range(const K& key)
454 */
455 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
456 std::pair<const_iterator, const_iterator> equal_range(const K& key) const { return m_ht.equal_range(key); }
457
458 /**
459 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
460 */
461 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
462 std::pair<const_iterator, const_iterator> equal_range(const K& key, std::size_t precalculated_hash) const {
463 return m_ht.equal_range(key, precalculated_hash);
464 }
465
466
467 /*
468 * Bucket interface
469 */
470 size_type bucket_count() const { return m_ht.bucket_count(); }
471 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
472
473
474 /*
475 * Hash policy
476 */
477 float load_factor() const { return m_ht.load_factor(); }
478 float max_load_factor() const { return m_ht.max_load_factor(); }
479 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
480
481 void rehash(size_type count) { m_ht.rehash(count); }
482 void reserve(size_type count) { m_ht.reserve(count); }
483
484
485 /*
486 * Observers
487 */
488 hasher hash_function() const { return m_ht.hash_function(); }
489 key_equal key_eq() const { return m_ht.key_eq(); }
490
491
492 /*
493 * Other
494 */
495
496 /**
497 * Convert a const_iterator to an iterator.
498 */
499 iterator mutable_iterator(const_iterator pos) {
500 return m_ht.mutable_iterator(pos);
501 }
502
503 /**
504 * Requires index <= size().
505 *
506 * Return an iterator to the element at index. Return end() if index == size().
507 */
508 iterator nth(size_type index) { return m_ht.nth(index); }
509
510 /**
511 * @copydoc nth(size_type index)
512 */
513 const_iterator nth(size_type index) const { return m_ht.nth(index); }
514
515
516 /**
517 * Return const_reference to the first element. Requires the container to not be empty.
518 */
519 const_reference front() const { return m_ht.front(); }
520
521 /**
522 * Return const_reference to the last element. Requires the container to not be empty.
523 */
524 const_reference back() const { return m_ht.back(); }
525
526
527 /**
528 * Only available if ValueTypeContainer is a std::vector. Same as calling 'values_container().data()'.
529 */
530 template<class U = values_container_type, typename std::enable_if<tsl::detail_ordered_hash::is_vector<U>::value>::type* = nullptr>
531 const typename values_container_type::value_type* data() const noexcept { return m_ht.data(); }
532
533 /**
534 * Return the container in which the values are stored. The values are in the same order as the insertion order
535 * and are contiguous in the structure, no holes (size() == values_container().size()).
536 */
537 const values_container_type& values_container() const noexcept { return m_ht.values_container(); }
538
539 template<class U = values_container_type, typename std::enable_if<tsl::detail_ordered_hash::is_vector<U>::value>::type* = nullptr>
540 size_type capacity() const noexcept { return m_ht.capacity(); }
541
542 void shrink_to_fit() { m_ht.shrink_to_fit(); }
543
544
545
546 /**
547 * Insert the value before pos shifting all the elements on the right of pos (including pos) one position
548 * to the right.
549 *
550 * Amortized linear time-complexity in the distance between pos and end().
551 */
552 std::pair<iterator, bool> insert_at_position(const_iterator pos, const value_type& value) {
553 return m_ht.insert_at_position(pos, value);
554 }
555
556 /**
557 * @copydoc insert_at_position(const_iterator pos, const value_type& value)
558 */
559 std::pair<iterator, bool> insert_at_position(const_iterator pos, value_type&& value) {
560 return m_ht.insert_at_position(pos, std::move(value));
561 }
562
563 /**
564 * @copydoc insert_at_position(const_iterator pos, const value_type& value)
565 *
566 * Same as insert_at_position(pos, value_type(std::forward<Args>(args)...), mainly
567 * here for coherence.
568 */
569 template<class... Args>
570 std::pair<iterator, bool> emplace_at_position(const_iterator pos, Args&&... args) {
571 return m_ht.emplace_at_position(pos, std::forward<Args>(args)...);
572 }
573
574
575
576 void pop_back() { m_ht.pop_back(); }
577
578 /**
579 * Faster erase operation with an O(1) average complexity but it doesn't preserve the insertion order.
580 *
581 * If an erasure occurs, the last element of the map will take the place of the erased element.
582 */
583 iterator unordered_erase(iterator pos) { return m_ht.unordered_erase(pos); }
584
585 /**
586 * @copydoc unordered_erase(iterator pos)
587 */
588 iterator unordered_erase(const_iterator pos) { return m_ht.unordered_erase(pos); }
589
590 /**
591 * @copydoc unordered_erase(iterator pos)
592 */
593 size_type unordered_erase(const key_type& key) { return m_ht.unordered_erase(key); }
594
595 /**
596 * @copydoc unordered_erase(iterator pos)
597 *
598 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
599 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
600 */
601 size_type unordered_erase(const key_type& key, std::size_t precalculated_hash) {
602 return m_ht.unordered_erase(key, precalculated_hash);
603 }
604
605 /**
606 * @copydoc unordered_erase(iterator pos)
607 *
608 * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
609 * If so, K must be hashable and comparable to Key.
610 */
611 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
612 size_type unordered_erase(const K& key) { return m_ht.unordered_erase(key); }
613
614 /**
615 * @copydoc unordered_erase(const K& key)
616 *
617 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
618 * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
619 */
620 template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
621 size_type unordered_erase(const K& key, std::size_t precalculated_hash) {
622 return m_ht.unordered_erase(key, precalculated_hash);
623 }
624
625
626
627 friend bool operator==(const ordered_set& lhs, const ordered_set& rhs) { return lhs.m_ht == rhs.m_ht; }
628 friend bool operator!=(const ordered_set& lhs, const ordered_set& rhs) { return lhs.m_ht != rhs.m_ht; }
629 friend bool operator<(const ordered_set& lhs, const ordered_set& rhs) { return lhs.m_ht < rhs.m_ht; }
630 friend bool operator<=(const ordered_set& lhs, const ordered_set& rhs) { return lhs.m_ht <= rhs.m_ht; }
631 friend bool operator>(const ordered_set& lhs, const ordered_set& rhs) { return lhs.m_ht > rhs.m_ht; }
632 friend bool operator>=(const ordered_set& lhs, const ordered_set& rhs) { return lhs.m_ht >= rhs.m_ht; }
633
634 friend void swap(ordered_set& lhs, ordered_set& rhs) { lhs.swap(rhs); }
635
636private:
637 ht m_ht;
638};
639
640} // end namespace tsl
641
642#endif
643