1 | /* |
2 | * Copyright (c) 2015-2017, Intel Corporation |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions are met: |
6 | * |
7 | * * Redistributions of source code must retain the above copyright notice, |
8 | * this list of conditions and the following disclaimer. |
9 | * * Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * * Neither the name of Intel Corporation nor the names of its contributors |
13 | * may be used to endorse or promote products derived from this software |
14 | * without specific prior written permission. |
15 | * |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
26 | * POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
28 | |
29 | #ifndef UTIL_FLAT_CONTAINERS_H |
30 | #define UTIL_FLAT_CONTAINERS_H |
31 | |
32 | #include "ue2common.h" |
33 | #include "util/hash.h" |
34 | #include "util/operators.h" |
35 | #include "util/small_vector.h" |
36 | |
37 | #include <algorithm> |
38 | #include <iterator> |
39 | #include <type_traits> |
40 | #include <utility> |
41 | |
42 | #include <boost/iterator/iterator_facade.hpp> |
43 | |
44 | namespace ue2 { |
45 | |
46 | namespace flat_detail { |
47 | |
48 | // Iterator facade that wraps an underlying iterator, so that we get our |
49 | // own iterator types. |
50 | template <class WrappedIter, class Value> |
51 | class iter_wrapper |
52 | : public boost::iterator_facade<iter_wrapper<WrappedIter, Value>, Value, |
53 | boost::random_access_traversal_tag> { |
54 | public: |
55 | iter_wrapper() = default; |
56 | explicit iter_wrapper(WrappedIter it_in) : it(std::move(it_in)) {} |
57 | |
58 | // Templated copy-constructor to allow for interoperable iterator and |
59 | // const_iterator. |
60 | private: |
61 | template <class, class> friend class iter_wrapper; |
62 | |
63 | public: |
64 | template <class OtherIter, class OtherValue> |
65 | iter_wrapper(iter_wrapper<OtherIter, OtherValue> other, |
66 | typename std::enable_if<std::is_convertible< |
67 | OtherIter, WrappedIter>::value>::type * = nullptr) |
68 | : it(std::move(other.it)) {} |
69 | |
70 | WrappedIter get() const { return it; } |
71 | |
72 | private: |
73 | friend class boost::iterator_core_access; |
74 | |
75 | WrappedIter it; |
76 | |
77 | void increment() { ++it; } |
78 | void decrement() { --it; } |
79 | void advance(size_t n) { it += n; } |
80 | typename std::iterator_traits<WrappedIter>::difference_type |
81 | distance_to(const iter_wrapper &other) const { |
82 | return other.it - it; |
83 | } |
84 | bool equal(const iter_wrapper &other) const { return it == other.it; } |
85 | Value &dereference() const { return *it; } |
86 | }; |
87 | |
88 | template <class T, class Compare, class Allocator> |
89 | class flat_base { |
90 | protected: |
91 | // Underlying storage is a small vector with local space for one element. |
92 | using storage_type = small_vector<T, 1, Allocator>; |
93 | using storage_alloc_type = typename storage_type::allocator_type; |
94 | |
95 | // Putting our storage and comparator in a tuple allows us to make use of |
96 | // the empty base class optimization (if this STL implements it for |
97 | // std::tuple). |
98 | std::tuple<storage_type, Compare> storage; |
99 | |
100 | flat_base(const Compare &compare, const Allocator &alloc) |
101 | : storage(storage_type(storage_alloc_type(alloc)), compare) {} |
102 | |
103 | storage_type &data() { return std::get<0>(this->storage); } |
104 | const storage_type &data() const { return std::get<0>(this->storage); } |
105 | |
106 | Compare &comp() { return std::get<1>(this->storage); } |
107 | const Compare &comp() const { return std::get<1>(this->storage); } |
108 | |
109 | public: |
110 | // Common member types. |
111 | using key_compare = Compare; |
112 | |
113 | Allocator get_allocator() const { |
114 | return data().get_allocator(); |
115 | } |
116 | |
117 | key_compare key_comp() const { |
118 | return comp(); |
119 | } |
120 | |
121 | // Capacity. |
122 | |
123 | bool empty() const { return data().empty(); } |
124 | size_t size() const { return data().size(); } |
125 | size_t max_size() const { return data().max_size(); } |
126 | |
127 | // Modifiers. |
128 | |
129 | void clear() { |
130 | data().clear(); |
131 | } |
132 | |
133 | void swap(flat_base &a) { |
134 | using std::swap; |
135 | swap(comp(), a.comp()); |
136 | swap(data(), a.data()); |
137 | } |
138 | }; |
139 | |
140 | } // namespace flat_detail |
141 | |
142 | /** |
143 | * \brief Set container implemented internally as a sorted vector. Use this |
144 | * rather than std::set for small sets as it's faster, uses less memory and |
145 | * incurs less malloc time. |
146 | * |
147 | * Note: we used to use boost::flat_set, but have run into problems with all |
148 | * the extra machinery it instantiates. |
149 | */ |
150 | template <class T, class Compare = std::less<T>, |
151 | class Allocator = std::allocator<T>> |
152 | class flat_set |
153 | : public flat_detail::flat_base<T, Compare, Allocator>, |
154 | public totally_ordered<flat_set<T, Compare, Allocator>> { |
155 | using base_type = flat_detail::flat_base<T, Compare, Allocator>; |
156 | using storage_type = typename base_type::storage_type; |
157 | using storage_iterator = typename storage_type::iterator; |
158 | using storage_const_iterator = typename storage_type::const_iterator; |
159 | using base_type::data; |
160 | using base_type::comp; |
161 | |
162 | #if defined(SMALL_VECTOR_IS_STL_VECTOR) |
163 | // Construct a non-const iterator from a const iterator. Used in flat_map |
164 | // and flat_set erase() calls to work around g++-4.8 compatibility issues. |
165 | storage_iterator mutable_iterator(storage_const_iterator it) { |
166 | return data().begin() + std::distance(data().cbegin(), it); |
167 | } |
168 | #endif |
169 | |
170 | public: |
171 | // Member types. |
172 | using key_type = T; |
173 | using value_type = T; |
174 | using size_type = typename storage_type::size_type; |
175 | using difference_type = typename storage_type::difference_type; |
176 | using key_compare = typename base_type::key_compare; |
177 | using value_compare = Compare; |
178 | using allocator_type = Allocator; |
179 | using reference = value_type &; |
180 | using const_reference = const value_type &; |
181 | using allocator_traits_type = typename std::allocator_traits<Allocator>; |
182 | using pointer = typename allocator_traits_type::pointer; |
183 | using const_pointer = typename allocator_traits_type::const_pointer; |
184 | |
185 | // Iterator types. |
186 | |
187 | using iterator = flat_detail::iter_wrapper<typename storage_type::iterator, |
188 | const value_type>; |
189 | using const_iterator = |
190 | flat_detail::iter_wrapper<typename storage_type::const_iterator, |
191 | const value_type>; |
192 | |
193 | using reverse_iterator = std::reverse_iterator<iterator>; |
194 | using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
195 | |
196 | // Constructors. |
197 | |
198 | flat_set(const Compare &compare = Compare(), |
199 | const Allocator &alloc = Allocator()) |
200 | : base_type(compare, alloc) {} |
201 | |
202 | template <class InputIt> |
203 | flat_set(InputIt first, InputIt last, const Compare &compare = Compare(), |
204 | const Allocator &alloc = Allocator()) |
205 | : flat_set(compare, alloc) { |
206 | insert(first, last); |
207 | } |
208 | |
209 | flat_set(std::initializer_list<value_type> init, |
210 | const Compare &compare = Compare(), |
211 | const Allocator &alloc = Allocator()) |
212 | : flat_set(compare, alloc) { |
213 | insert(init.begin(), init.end()); |
214 | } |
215 | |
216 | flat_set(const flat_set &) = default; |
217 | flat_set(flat_set &&) = default; |
218 | flat_set &operator=(const flat_set &) = default; |
219 | flat_set &operator=(flat_set &&) = default; |
220 | |
221 | // Iterators. |
222 | |
223 | iterator begin() { return iterator(data().begin()); } |
224 | const_iterator cbegin() const { return const_iterator(data().cbegin()); } |
225 | const_iterator begin() const { return cbegin(); } |
226 | |
227 | iterator end() { return iterator(data().end()); } |
228 | const_iterator cend() const { return const_iterator(data().cend()); } |
229 | const_iterator end() const { return cend(); } |
230 | |
231 | reverse_iterator rbegin() { return reverse_iterator(end()); } |
232 | const_reverse_iterator crbegin() const { |
233 | return const_reverse_iterator(cend()); |
234 | } |
235 | const_reverse_iterator rbegin() const { return crbegin(); } |
236 | |
237 | reverse_iterator rend() { return reverse_iterator(begin()); } |
238 | const_reverse_iterator crend() const { |
239 | return const_reverse_iterator(cbegin()); |
240 | } |
241 | const_reverse_iterator rend() const { return crend(); } |
242 | |
243 | // Modifiers. |
244 | |
245 | std::pair<iterator, bool> insert(const value_type &value) { |
246 | auto it = std::lower_bound(data().begin(), data().end(), value, comp()); |
247 | if (it == data().end() || comp()(value, *it)) { |
248 | return std::make_pair(iterator(data().insert(it, value)), true); |
249 | } |
250 | return std::make_pair(iterator(it), false); |
251 | } |
252 | |
253 | iterator insert(UNUSED const_iterator hint, const value_type &value) { |
254 | return insert(value).first; |
255 | } |
256 | |
257 | std::pair<iterator, bool> insert(value_type &&value) { |
258 | auto it = std::lower_bound(data().begin(), data().end(), value, comp()); |
259 | if (it == data().end() || comp()(value, *it)) { |
260 | return std::make_pair(iterator(data().insert(it, std::move(value))), |
261 | true); |
262 | } |
263 | return std::make_pair(iterator(it), false); |
264 | } |
265 | |
266 | iterator insert(UNUSED const_iterator hint, value_type &&value) { |
267 | return insert(value).first; |
268 | } |
269 | |
270 | template <class InputIt> |
271 | void insert(InputIt first, InputIt second) { |
272 | for (; first != second; ++first) { |
273 | insert(*first); |
274 | } |
275 | } |
276 | |
277 | void insert(std::initializer_list<value_type> ilist) { |
278 | insert(ilist.begin(), ilist.end()); |
279 | } |
280 | |
281 | template<class...Args> |
282 | std::pair<iterator, bool> emplace(Args&&... args) { |
283 | return insert(value_type(std::forward<Args>(args)...)); |
284 | } |
285 | |
286 | void erase(const_iterator pos) { |
287 | #if defined(SMALL_VECTOR_IS_STL_VECTOR) |
288 | // Cope with libstdc++ 4.8's incomplete STL (it's missing C++11 |
289 | // vector::erase(const_iterator)) by explicitly using a non-const |
290 | // iterator. |
291 | auto pos_it = mutable_iterator(pos.get()); |
292 | #else |
293 | auto pos_it = pos.get(); |
294 | #endif |
295 | data().erase(pos_it); |
296 | } |
297 | |
298 | void erase(const_iterator first, const_iterator last) { |
299 | #if defined(SMALL_VECTOR_IS_STL_VECTOR) |
300 | // As above, work around libstdc++ 4.8's incomplete C++11 support. |
301 | auto first_it = mutable_iterator(first.get()); |
302 | auto last_it = mutable_iterator(last.get()); |
303 | #else |
304 | auto first_it = first.get(); |
305 | auto last_it = last.get(); |
306 | #endif |
307 | data().erase(first_it, last_it); |
308 | } |
309 | |
310 | void erase(const key_type &key) { |
311 | auto it = find(key); |
312 | if (it != end()) { |
313 | erase(it); |
314 | } |
315 | } |
316 | |
317 | // Lookup. |
318 | |
319 | size_type count(const value_type &value) const { |
320 | return find(value) != end() ? 1 : 0; |
321 | } |
322 | |
323 | iterator find(const value_type &value) { |
324 | auto it = std::lower_bound(data().begin(), data().end(), value, comp()); |
325 | if (it != data().end() && comp()(value, *it)) { |
326 | it = data().end(); |
327 | } |
328 | return iterator(it); |
329 | } |
330 | |
331 | const_iterator find(const value_type &value) const { |
332 | auto it = std::lower_bound(data().begin(), data().end(), value, comp()); |
333 | if (it != data().end() && comp()(value, *it)) { |
334 | it = data().end(); |
335 | } |
336 | return const_iterator(it); |
337 | } |
338 | |
339 | // Observers. |
340 | |
341 | value_compare value_comp() const { |
342 | return comp(); |
343 | } |
344 | |
345 | // Operators. All others provided by ue2::totally_ordered. |
346 | |
347 | bool operator==(const flat_set &a) const { |
348 | return data() == a.data(); |
349 | } |
350 | bool operator<(const flat_set &a) const { |
351 | return data() < a.data(); |
352 | } |
353 | |
354 | // Free swap function for ADL. |
355 | friend void swap(flat_set &a, flat_set &b) { |
356 | a.swap(b); |
357 | } |
358 | }; |
359 | |
360 | /** |
361 | * \brief Map container implemented internally as a sorted vector. Use this |
362 | * rather than std::map for small maps as it's faster, uses less memory and |
363 | * incurs less malloc time. |
364 | * |
365 | * Note: we used to use boost::flat_map, but have run into problems with all |
366 | * the extra machinery it instantiates. |
367 | * |
368 | * Note: ue2::flat_map does NOT provide mutable iterators, as (given the way |
369 | * the data is stored) it is difficult to provide a real mutable iterator that |
370 | * wraps std::pair<const Key, T>. Instead, all iterators are const, and you |
371 | * should use flat_map::at() or flat_map::operator[] to mutate the contents of |
372 | * the container. |
373 | */ |
374 | template <class Key, class T, class Compare = std::less<Key>, |
375 | class Allocator = std::allocator<std::pair<Key, T>>> |
376 | class flat_map |
377 | : public flat_detail::flat_base<std::pair<Key, T>, Compare, Allocator>, |
378 | public totally_ordered<flat_map<Key, T, Compare, Allocator>> { |
379 | public: |
380 | // Member types. |
381 | using key_type = Key; |
382 | using mapped_type = T; |
383 | using value_type = std::pair<const Key, T>; |
384 | |
385 | private: |
386 | using base_type = |
387 | flat_detail::flat_base<std::pair<Key, T>, Compare, Allocator>; |
388 | using keyval_storage_type = std::pair<key_type, mapped_type>; |
389 | using storage_type = typename base_type::storage_type; |
390 | using storage_iterator = typename storage_type::iterator; |
391 | using storage_const_iterator = typename storage_type::const_iterator; |
392 | using base_type::data; |
393 | using base_type::comp; |
394 | |
395 | #if defined(SMALL_VECTOR_IS_STL_VECTOR) |
396 | // Construct a non-const iterator from a const iterator. Used in flat_map |
397 | // and flat_set erase() calls to work around g++-4.8 compatibility issues. |
398 | storage_iterator mutable_iterator(storage_const_iterator it) { |
399 | return data().begin() + std::distance(data().cbegin(), it); |
400 | } |
401 | #endif |
402 | |
403 | public: |
404 | // More Member types. |
405 | using size_type = typename storage_type::size_type; |
406 | using difference_type = typename storage_type::difference_type; |
407 | using key_compare = typename base_type::key_compare; |
408 | using allocator_type = Allocator; |
409 | using reference = value_type &; |
410 | using const_reference = const value_type &; |
411 | using allocator_traits_type = typename std::allocator_traits<Allocator>; |
412 | using pointer = typename allocator_traits_type::pointer; |
413 | using const_pointer = typename allocator_traits_type::const_pointer; |
414 | |
415 | public: |
416 | using const_iterator = |
417 | flat_detail::iter_wrapper<typename storage_type::const_iterator, |
418 | const keyval_storage_type>; |
419 | |
420 | using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
421 | |
422 | // All iterators are const for flat_map. |
423 | using iterator = const_iterator; |
424 | using reverse_iterator = const_reverse_iterator; |
425 | |
426 | // Constructors. |
427 | |
428 | flat_map(const Compare &compare = Compare(), |
429 | const Allocator &alloc = Allocator()) |
430 | : base_type(compare, alloc) {} |
431 | |
432 | template <class InputIt> |
433 | flat_map(InputIt first, InputIt last, const Compare &compare = Compare(), |
434 | const Allocator &alloc = Allocator()) |
435 | : flat_map(compare, alloc) { |
436 | insert(first, last); |
437 | } |
438 | |
439 | flat_map(std::initializer_list<value_type> init, |
440 | const Compare &compare = Compare(), |
441 | const Allocator &alloc = Allocator()) |
442 | : flat_map(compare, alloc) { |
443 | insert(init.begin(), init.end()); |
444 | } |
445 | |
446 | flat_map(const flat_map &) = default; |
447 | flat_map(flat_map &&) = default; |
448 | flat_map &operator=(const flat_map &) = default; |
449 | flat_map &operator=(flat_map &&) = default; |
450 | |
451 | // Iterators. |
452 | |
453 | const_iterator cbegin() const { return const_iterator(data().cbegin()); } |
454 | const_iterator begin() const { return cbegin(); } |
455 | |
456 | const_iterator cend() const { return const_iterator(data().cend()); } |
457 | const_iterator end() const { return cend(); } |
458 | |
459 | const_reverse_iterator crbegin() const { |
460 | return const_reverse_iterator(cend()); |
461 | } |
462 | const_reverse_iterator rbegin() const { return crbegin(); } |
463 | |
464 | const_reverse_iterator crend() const { |
465 | return const_reverse_iterator(cbegin()); |
466 | } |
467 | const_reverse_iterator rend() const { return crend(); } |
468 | |
469 | private: |
470 | storage_iterator data_lower_bound(const key_type &key) { |
471 | return std::lower_bound( |
472 | data().begin(), data().end(), key, |
473 | [&](const keyval_storage_type &elem, const key_type &k) { |
474 | return comp()(elem.first, k); |
475 | }); |
476 | } |
477 | |
478 | storage_const_iterator |
479 | data_lower_bound(const key_type &key) const { |
480 | return std::lower_bound( |
481 | data().begin(), data().end(), key, |
482 | [&](const keyval_storage_type &elem, const key_type &k) { |
483 | return comp()(elem.first, k); |
484 | }); |
485 | } |
486 | |
487 | std::pair<storage_iterator, bool> data_insert(const value_type &value) { |
488 | auto it = data_lower_bound(value.first); |
489 | if (it == data().end() || comp()(value.first, it->first)) { |
490 | return std::make_pair(data().insert(it, value), true); |
491 | } |
492 | return std::make_pair(it, false); |
493 | } |
494 | |
495 | std::pair<storage_iterator, bool> data_insert(value_type &&value) { |
496 | auto it = data_lower_bound(value.first); |
497 | if (it == data().end() || comp()(value.first, it->first)) { |
498 | return std::make_pair(data().insert(it, std::move(value)), true); |
499 | } |
500 | return std::make_pair(it, false); |
501 | } |
502 | |
503 | storage_iterator data_find(const key_type &key) { |
504 | auto it = data_lower_bound(key); |
505 | if (it != data().end() && comp()(key, it->first)) { |
506 | it = data().end(); |
507 | } |
508 | return it; |
509 | } |
510 | |
511 | storage_const_iterator data_find(const key_type &key) const { |
512 | auto it = data_lower_bound(key); |
513 | if (it != data().end() && comp()(key, it->first)) { |
514 | it = data().end(); |
515 | } |
516 | return it; |
517 | } |
518 | |
519 | public: |
520 | // Modifiers. |
521 | |
522 | std::pair<iterator, bool> insert(const value_type &value) { |
523 | auto rv = data_insert(value); |
524 | return std::make_pair(iterator(rv.first), rv.second); |
525 | } |
526 | |
527 | std::pair<iterator, bool> insert(value_type &&value) { |
528 | auto rv = data_insert(std::move(value)); |
529 | return std::make_pair(iterator(rv.first), rv.second); |
530 | } |
531 | |
532 | template <class InputIt> |
533 | void insert(InputIt first, InputIt second) { |
534 | for (; first != second; ++first) { |
535 | insert(*first); |
536 | } |
537 | } |
538 | |
539 | void insert(std::initializer_list<value_type> ilist) { |
540 | insert(ilist.begin(), ilist.end()); |
541 | } |
542 | |
543 | template<class...Args> |
544 | std::pair<iterator, bool> emplace(Args&&... args) { |
545 | return insert(value_type(std::forward<Args>(args)...)); |
546 | } |
547 | |
548 | void erase(const_iterator pos) { |
549 | #if defined(SMALL_VECTOR_IS_STL_VECTOR) |
550 | // Cope with libstdc++ 4.8's incomplete STL (it's missing C++11 |
551 | // vector::erase(const_iterator)) by explicitly using a non-const |
552 | // iterator. |
553 | auto pos_it = mutable_iterator(pos.get()); |
554 | #else |
555 | auto pos_it = pos.get(); |
556 | #endif |
557 | data().erase(pos_it); |
558 | } |
559 | |
560 | void erase(const_iterator first, const_iterator last) { |
561 | #if defined(SMALL_VECTOR_IS_STL_VECTOR) |
562 | // As above, work around libstdc++ 4.8's incomplete C++11 support. |
563 | auto first_it = mutable_iterator(first.get()); |
564 | auto last_it = mutable_iterator(last.get()); |
565 | #else |
566 | auto first_it = first.get(); |
567 | auto last_it = last.get(); |
568 | #endif |
569 | data().erase(first_it, last_it); |
570 | } |
571 | |
572 | void erase(const key_type &key) { |
573 | auto it = find(key); |
574 | if (it != end()) { |
575 | erase(it); |
576 | } |
577 | } |
578 | |
579 | // Lookup. |
580 | |
581 | size_type count(const key_type &key) const { |
582 | return find(key) != end() ? 1 : 0; |
583 | } |
584 | |
585 | const_iterator find(const key_type &key) const { |
586 | return const_iterator(data_find(key)); |
587 | } |
588 | |
589 | // Element access. |
590 | |
591 | mapped_type &at(const key_type &key) { |
592 | auto it = data_find(key); |
593 | if (it == data().end()) { |
594 | throw std::out_of_range("element not found" ); |
595 | } |
596 | return it->second; |
597 | } |
598 | |
599 | const mapped_type &at(const key_type &key) const { |
600 | auto it = data_find(key); |
601 | if (it == data().end()) { |
602 | throw std::out_of_range("element not found" ); |
603 | } |
604 | return it->second; |
605 | } |
606 | |
607 | mapped_type &operator[](const key_type &key) { |
608 | auto p = data_insert(value_type(key, mapped_type())); |
609 | return p.first->second; |
610 | } |
611 | |
612 | // Observers. |
613 | |
614 | class value_compare { |
615 | friend class flat_map; |
616 | protected: |
617 | Compare c; |
618 | value_compare(Compare c_in) : c(c_in) {} |
619 | public: |
620 | bool operator()(const value_type &lhs, const value_type &rhs) { |
621 | return c(lhs.first, rhs.first); |
622 | } |
623 | }; |
624 | |
625 | value_compare value_comp() const { |
626 | return value_compare(comp()); |
627 | } |
628 | |
629 | // Operators. All others provided by ue2::totally_ordered. |
630 | |
631 | bool operator==(const flat_map &a) const { |
632 | return data() == a.data(); |
633 | } |
634 | bool operator<(const flat_map &a) const { |
635 | return data() < a.data(); |
636 | } |
637 | |
638 | // Free swap function for ADL. |
639 | friend void swap(flat_map &a, flat_map &b) { |
640 | a.swap(b); |
641 | } |
642 | }; |
643 | |
644 | } // namespace ue2 |
645 | |
646 | namespace std { |
647 | |
648 | template<typename T, typename Compare, typename Allocator> |
649 | struct hash<ue2::flat_set<T, Compare, Allocator>> { |
650 | size_t operator()(const ue2::flat_set<T, Compare, Allocator> &f) { |
651 | return ue2::ue2_hasher()(f); |
652 | } |
653 | }; |
654 | |
655 | template<typename Key, typename T, typename Compare, typename Allocator> |
656 | struct hash<ue2::flat_map<Key, T, Compare, Allocator>> { |
657 | size_t operator()(const ue2::flat_map<Key, T, Compare, Allocator> &f) { |
658 | return ue2::ue2_hasher()(f); |
659 | } |
660 | }; |
661 | |
662 | } // namespace std |
663 | |
664 | #endif // UTIL_FLAT_CONTAINERS_H |
665 | |