1 | // Copyright (C) 2022 The Qt Company Ltd. |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | |
4 | #ifndef QFLATMAP_P_H |
5 | #define QFLATMAP_P_H |
6 | |
7 | // |
8 | // W A R N I N G |
9 | // ------------- |
10 | // |
11 | // This file is not part of the Qt API. It exists for the convenience |
12 | // of a number of Qt sources files. This header file may change from |
13 | // version to version without notice, or even be removed. |
14 | // |
15 | // We mean it. |
16 | // |
17 | |
18 | #include "qlist.h" |
19 | #include "private/qglobal_p.h" |
20 | |
21 | #include <algorithm> |
22 | #include <functional> |
23 | #include <initializer_list> |
24 | #include <iterator> |
25 | #include <numeric> |
26 | #include <type_traits> |
27 | #include <utility> |
28 | #include <vector> |
29 | |
30 | QT_BEGIN_NAMESPACE |
31 | |
32 | /* |
33 | QFlatMap provides an associative container backed by sorted sequential |
34 | containers. By default, QList is used. |
35 | |
36 | Keys and values are stored in two separate containers. This provides improved |
37 | cache locality for key iteration and makes keys() and values() fast |
38 | operations. |
39 | |
40 | One can customize the underlying container type by passing the KeyContainer |
41 | and MappedContainer template arguments: |
42 | QFlatMap<float, int, std::less<float>, std::vector<float>, std::vector<int>> |
43 | */ |
44 | |
45 | // Qt 6.4: |
46 | // - removed QFlatMap API which was incompatible with STL semantics |
47 | // - will be released with said API disabled, to catch any out-of-tree users |
48 | // - also allows opting in to the new API using QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT |
49 | // Qt 6.5 |
50 | // - will make QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT the default: |
51 | |
52 | #ifndef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT |
53 | # if QT_VERSION >= QT_VERSION_CHECK(6, 5, 0) |
54 | # define QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT |
55 | # endif |
56 | #endif |
57 | |
58 | namespace Qt { |
59 | |
60 | struct OrderedUniqueRange_t {}; |
61 | constexpr OrderedUniqueRange_t OrderedUniqueRange = {}; |
62 | |
63 | } // namespace Qt |
64 | |
65 | template <class Key, class T, class Compare> |
66 | class QFlatMapValueCompare : protected Compare |
67 | { |
68 | public: |
69 | QFlatMapValueCompare() = default; |
70 | QFlatMapValueCompare(const Compare &key_compare) |
71 | : Compare(key_compare) |
72 | { |
73 | } |
74 | |
75 | using value_type = std::pair<const Key, T>; |
76 | static constexpr bool is_comparator_noexcept = noexcept( |
77 | std::declval<Compare>()(std::declval<const Key &>(), std::declval<const Key &>())); |
78 | |
79 | bool operator()(const value_type &lhs, const value_type &rhs) const |
80 | noexcept(is_comparator_noexcept) |
81 | { |
82 | return Compare::operator()(lhs.first, rhs.first); |
83 | } |
84 | }; |
85 | |
86 | namespace qflatmap { |
87 | namespace detail { |
88 | template <class T> |
89 | class QFlatMapMockPointer |
90 | { |
91 | T ref; |
92 | public: |
93 | QFlatMapMockPointer(T r) |
94 | : ref(r) |
95 | { |
96 | } |
97 | |
98 | T *operator->() |
99 | { |
100 | return &ref; |
101 | } |
102 | }; |
103 | } // namespace detail |
104 | } // namespace qflatmap |
105 | |
106 | template<class Key, class T, class Compare = std::less<Key>, class KeyContainer = QList<Key>, |
107 | class MappedContainer = QList<T>> |
108 | class QFlatMap : private QFlatMapValueCompare<Key, T, Compare> |
109 | { |
110 | static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers." ); |
111 | |
112 | template<class U> |
113 | using mock_pointer = qflatmap::detail::QFlatMapMockPointer<U>; |
114 | |
115 | public: |
116 | using key_type = Key; |
117 | using mapped_type = T; |
118 | using value_compare = QFlatMapValueCompare<Key, T, Compare>; |
119 | using value_type = typename value_compare::value_type; |
120 | using key_container_type = KeyContainer; |
121 | using mapped_container_type = MappedContainer; |
122 | using size_type = typename key_container_type::size_type; |
123 | using key_compare = Compare; |
124 | |
125 | struct containers |
126 | { |
127 | key_container_type keys; |
128 | mapped_container_type values; |
129 | }; |
130 | |
131 | class iterator |
132 | { |
133 | public: |
134 | using difference_type = ptrdiff_t; |
135 | using value_type = std::pair<const Key, T>; |
136 | using reference = std::pair<const Key &, T &>; |
137 | using pointer = mock_pointer<reference>; |
138 | using iterator_category = std::random_access_iterator_tag; |
139 | |
140 | iterator() = default; |
141 | |
142 | iterator(containers *ac, size_type ai) |
143 | : c(ac), i(ai) |
144 | { |
145 | } |
146 | |
147 | reference operator*() const |
148 | { |
149 | return { c->keys[i], c->values[i] }; |
150 | } |
151 | |
152 | pointer operator->() const |
153 | { |
154 | return { operator*() }; |
155 | } |
156 | |
157 | bool operator==(const iterator &o) const |
158 | { |
159 | return c == o.c && i == o.i; |
160 | } |
161 | |
162 | bool operator!=(const iterator &o) const |
163 | { |
164 | return !operator==(o); |
165 | } |
166 | |
167 | iterator &operator++() |
168 | { |
169 | ++i; |
170 | return *this; |
171 | } |
172 | |
173 | iterator operator++(int) |
174 | { |
175 | |
176 | iterator r = *this; |
177 | ++*this; |
178 | return r; |
179 | } |
180 | |
181 | iterator &operator--() |
182 | { |
183 | --i; |
184 | return *this; |
185 | } |
186 | |
187 | iterator operator--(int) |
188 | { |
189 | iterator r = *this; |
190 | --*this; |
191 | return r; |
192 | } |
193 | |
194 | iterator &operator+=(size_type n) |
195 | { |
196 | i += n; |
197 | return *this; |
198 | } |
199 | |
200 | friend iterator operator+(size_type n, const iterator a) |
201 | { |
202 | iterator ret = a; |
203 | return ret += n; |
204 | } |
205 | |
206 | friend iterator operator+(const iterator a, size_type n) |
207 | { |
208 | return n + a; |
209 | } |
210 | |
211 | iterator &operator-=(size_type n) |
212 | { |
213 | i -= n; |
214 | return *this; |
215 | } |
216 | |
217 | friend iterator operator-(const iterator a, size_type n) |
218 | { |
219 | iterator ret = a; |
220 | return ret -= n; |
221 | } |
222 | |
223 | friend difference_type operator-(const iterator b, const iterator a) |
224 | { |
225 | return b.i - a.i; |
226 | } |
227 | |
228 | reference operator[](size_type n) const |
229 | { |
230 | size_type k = i + n; |
231 | return { c->keys[k], c->values[k] }; |
232 | } |
233 | |
234 | bool operator<(const iterator &other) const |
235 | { |
236 | return i < other.i; |
237 | } |
238 | |
239 | bool operator>(const iterator &other) const |
240 | { |
241 | return i > other.i; |
242 | } |
243 | |
244 | bool operator<=(const iterator &other) const |
245 | { |
246 | return i <= other.i; |
247 | } |
248 | |
249 | bool operator>=(const iterator &other) const |
250 | { |
251 | return i >= other.i; |
252 | } |
253 | |
254 | const Key &key() const { return c->keys[i]; } |
255 | T &value() const { return c->values[i]; } |
256 | |
257 | private: |
258 | containers *c = nullptr; |
259 | size_type i = 0; |
260 | friend QFlatMap; |
261 | }; |
262 | |
263 | class const_iterator |
264 | { |
265 | public: |
266 | using difference_type = ptrdiff_t; |
267 | using value_type = std::pair<const Key, const T>; |
268 | using reference = std::pair<const Key &, const T &>; |
269 | using pointer = mock_pointer<reference>; |
270 | using iterator_category = std::random_access_iterator_tag; |
271 | |
272 | const_iterator() = default; |
273 | |
274 | const_iterator(const containers *ac, size_type ai) |
275 | : c(ac), i(ai) |
276 | { |
277 | } |
278 | |
279 | const_iterator(iterator o) |
280 | : c(o.c), i(o.i) |
281 | { |
282 | } |
283 | |
284 | reference operator*() const |
285 | { |
286 | return { c->keys[i], c->values[i] }; |
287 | } |
288 | |
289 | pointer operator->() const |
290 | { |
291 | return { operator*() }; |
292 | } |
293 | |
294 | bool operator==(const const_iterator &o) const |
295 | { |
296 | return c == o.c && i == o.i; |
297 | } |
298 | |
299 | bool operator!=(const const_iterator &o) const |
300 | { |
301 | return !operator==(o); |
302 | } |
303 | |
304 | const_iterator &operator++() |
305 | { |
306 | ++i; |
307 | return *this; |
308 | } |
309 | |
310 | const_iterator operator++(int) |
311 | { |
312 | |
313 | const_iterator r = *this; |
314 | ++*this; |
315 | return r; |
316 | } |
317 | |
318 | const_iterator &operator--() |
319 | { |
320 | --i; |
321 | return *this; |
322 | } |
323 | |
324 | const_iterator operator--(int) |
325 | { |
326 | const_iterator r = *this; |
327 | --*this; |
328 | return r; |
329 | } |
330 | |
331 | const_iterator &operator+=(size_type n) |
332 | { |
333 | i += n; |
334 | return *this; |
335 | } |
336 | |
337 | friend const_iterator operator+(size_type n, const const_iterator a) |
338 | { |
339 | const_iterator ret = a; |
340 | return ret += n; |
341 | } |
342 | |
343 | friend const_iterator operator+(const const_iterator a, size_type n) |
344 | { |
345 | return n + a; |
346 | } |
347 | |
348 | const_iterator &operator-=(size_type n) |
349 | { |
350 | i -= n; |
351 | return *this; |
352 | } |
353 | |
354 | friend const_iterator operator-(const const_iterator a, size_type n) |
355 | { |
356 | const_iterator ret = a; |
357 | return ret -= n; |
358 | } |
359 | |
360 | friend difference_type operator-(const const_iterator b, const const_iterator a) |
361 | { |
362 | return b.i - a.i; |
363 | } |
364 | |
365 | reference operator[](size_type n) const |
366 | { |
367 | size_type k = i + n; |
368 | return { c->keys[k], c->values[k] }; |
369 | } |
370 | |
371 | bool operator<(const const_iterator &other) const |
372 | { |
373 | return i < other.i; |
374 | } |
375 | |
376 | bool operator>(const const_iterator &other) const |
377 | { |
378 | return i > other.i; |
379 | } |
380 | |
381 | bool operator<=(const const_iterator &other) const |
382 | { |
383 | return i <= other.i; |
384 | } |
385 | |
386 | bool operator>=(const const_iterator &other) const |
387 | { |
388 | return i >= other.i; |
389 | } |
390 | |
391 | const Key &key() const { return c->keys[i]; } |
392 | const T &value() const { return c->values[i]; } |
393 | |
394 | private: |
395 | const containers *c = nullptr; |
396 | size_type i = 0; |
397 | friend QFlatMap; |
398 | }; |
399 | |
400 | private: |
401 | template <class, class = void> |
402 | struct is_marked_transparent_type : std::false_type { }; |
403 | |
404 | template <class X> |
405 | struct is_marked_transparent_type<X, std::void_t<typename X::is_transparent>> : std::true_type { }; |
406 | |
407 | template <class X> |
408 | using is_marked_transparent = typename std::enable_if< |
409 | is_marked_transparent_type<X>::value>::type *; |
410 | |
411 | template <typename It> |
412 | using is_compatible_iterator = typename std::enable_if< |
413 | std::is_same<value_type, typename std::iterator_traits<It>::value_type>::value>::type *; |
414 | |
415 | public: |
416 | QFlatMap() = default; |
417 | |
418 | #ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT |
419 | explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values) |
420 | : c{keys, values} |
421 | { |
422 | ensureOrderedUnique(); |
423 | } |
424 | |
425 | explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values) |
426 | : c{std::move(keys), values} |
427 | { |
428 | ensureOrderedUnique(); |
429 | } |
430 | |
431 | explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values) |
432 | : c{keys, std::move(values)} |
433 | { |
434 | ensureOrderedUnique(); |
435 | } |
436 | |
437 | explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values) |
438 | : c{std::move(keys), std::move(values)} |
439 | { |
440 | ensureOrderedUnique(); |
441 | } |
442 | |
443 | explicit QFlatMap(std::initializer_list<value_type> lst) |
444 | : QFlatMap(lst.begin(), lst.end()) |
445 | { |
446 | } |
447 | |
448 | template <class InputIt, is_compatible_iterator<InputIt> = nullptr> |
449 | explicit QFlatMap(InputIt first, InputIt last) |
450 | { |
451 | initWithRange(first, last); |
452 | ensureOrderedUnique(); |
453 | } |
454 | #endif |
455 | |
456 | explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, |
457 | const mapped_container_type &values) |
458 | : c{keys, values} |
459 | { |
460 | } |
461 | |
462 | explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, |
463 | const mapped_container_type &values) |
464 | : c{std::move(keys), values} |
465 | { |
466 | } |
467 | |
468 | explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, |
469 | mapped_container_type &&values) |
470 | : c{keys, std::move(values)} |
471 | { |
472 | } |
473 | |
474 | explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, |
475 | mapped_container_type &&values) |
476 | : c{std::move(keys), std::move(values)} |
477 | { |
478 | } |
479 | |
480 | explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst) |
481 | : QFlatMap(Qt::OrderedUniqueRange, lst.begin(), lst.end()) |
482 | { |
483 | } |
484 | |
485 | template <class InputIt, is_compatible_iterator<InputIt> = nullptr> |
486 | explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last) |
487 | { |
488 | initWithRange(first, last); |
489 | } |
490 | |
491 | explicit QFlatMap(const Compare &compare) |
492 | : value_compare(compare) |
493 | { |
494 | } |
495 | |
496 | #ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT |
497 | explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values, |
498 | const Compare &compare) |
499 | : value_compare(compare), c{keys, values} |
500 | { |
501 | ensureOrderedUnique(); |
502 | } |
503 | |
504 | explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values, |
505 | const Compare &compare) |
506 | : value_compare(compare), c{std::move(keys), values} |
507 | { |
508 | ensureOrderedUnique(); |
509 | } |
510 | |
511 | explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values, |
512 | const Compare &compare) |
513 | : value_compare(compare), c{keys, std::move(values)} |
514 | { |
515 | ensureOrderedUnique(); |
516 | } |
517 | |
518 | explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values, |
519 | const Compare &compare) |
520 | : value_compare(compare), c{std::move(keys), std::move(values)} |
521 | { |
522 | ensureOrderedUnique(); |
523 | } |
524 | |
525 | explicit QFlatMap(std::initializer_list<value_type> lst, const Compare &compare) |
526 | : QFlatMap(lst.begin(), lst.end(), compare) |
527 | { |
528 | } |
529 | |
530 | template <class InputIt, is_compatible_iterator<InputIt> = nullptr> |
531 | explicit QFlatMap(InputIt first, InputIt last, const Compare &compare) |
532 | : value_compare(compare) |
533 | { |
534 | initWithRange(first, last); |
535 | ensureOrderedUnique(); |
536 | } |
537 | #endif |
538 | |
539 | explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, |
540 | const mapped_container_type &values, const Compare &compare) |
541 | : value_compare(compare), c{keys, values} |
542 | { |
543 | } |
544 | |
545 | explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, |
546 | const mapped_container_type &values, const Compare &compare) |
547 | : value_compare(compare), c{std::move(keys), values} |
548 | { |
549 | } |
550 | |
551 | explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, |
552 | mapped_container_type &&values, const Compare &compare) |
553 | : value_compare(compare), c{keys, std::move(values)} |
554 | { |
555 | } |
556 | |
557 | explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, |
558 | mapped_container_type &&values, const Compare &compare) |
559 | : value_compare(compare), c{std::move(keys), std::move(values)} |
560 | { |
561 | } |
562 | |
563 | explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst, |
564 | const Compare &compare) |
565 | : QFlatMap(Qt::OrderedUniqueRange, lst.begin(), lst.end(), compare) |
566 | { |
567 | } |
568 | |
569 | template <class InputIt, is_compatible_iterator<InputIt> = nullptr> |
570 | explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last, const Compare &compare) |
571 | : value_compare(compare) |
572 | { |
573 | initWithRange(first, last); |
574 | } |
575 | |
576 | size_type count() const noexcept { return c.keys.size(); } |
577 | size_type size() const noexcept { return c.keys.size(); } |
578 | size_type capacity() const noexcept { return c.keys.capacity(); } |
579 | bool isEmpty() const noexcept { return c.keys.empty(); } |
580 | bool empty() const noexcept { return c.keys.empty(); } |
581 | containers () && { return std::move(c); } |
582 | const key_container_type &keys() const noexcept { return c.keys; } |
583 | const mapped_container_type &values() const noexcept { return c.values; } |
584 | |
585 | void reserve(size_type s) |
586 | { |
587 | c.keys.reserve(s); |
588 | c.values.reserve(s); |
589 | } |
590 | |
591 | void clear() |
592 | { |
593 | c.keys.clear(); |
594 | c.values.clear(); |
595 | } |
596 | |
597 | bool remove(const Key &key) |
598 | { |
599 | return do_remove(it: find(key)); |
600 | } |
601 | |
602 | template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> |
603 | bool remove(const X &key) |
604 | { |
605 | return do_remove(it: find(key)); |
606 | } |
607 | |
608 | iterator erase(iterator it) |
609 | { |
610 | c.values.erase(toValuesIterator(it)); |
611 | return fromKeysIterator(c.keys.erase(toKeysIterator(it))); |
612 | } |
613 | |
614 | T take(const Key &key) |
615 | { |
616 | return do_take(it: find(key)); |
617 | } |
618 | |
619 | template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> |
620 | T take(const X &key) |
621 | { |
622 | return do_take(it: find(key)); |
623 | } |
624 | |
625 | bool contains(const Key &key) const |
626 | { |
627 | return find(key) != end(); |
628 | } |
629 | |
630 | template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> |
631 | bool contains(const X &key) const |
632 | { |
633 | return find(key) != end(); |
634 | } |
635 | |
636 | T value(const Key &key, const T &defaultValue) const |
637 | { |
638 | auto it = find(key); |
639 | return it == end() ? defaultValue : it.value(); |
640 | } |
641 | |
642 | template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> |
643 | T value(const X &key, const T &defaultValue) const |
644 | { |
645 | auto it = find(key); |
646 | return it == end() ? defaultValue : it.value(); |
647 | } |
648 | |
649 | T value(const Key &key) const |
650 | { |
651 | auto it = find(key); |
652 | return it == end() ? T() : it.value(); |
653 | } |
654 | |
655 | template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> |
656 | T value(const X &key) const |
657 | { |
658 | auto it = find(key); |
659 | return it == end() ? T() : it.value(); |
660 | } |
661 | |
662 | T &operator[](const Key &key) |
663 | { |
664 | return try_emplace(key).first.value(); |
665 | } |
666 | |
667 | T &operator[](Key &&key) |
668 | { |
669 | return try_emplace(std::move(key)).first.value(); |
670 | } |
671 | |
672 | T operator[](const Key &key) const |
673 | { |
674 | return value(key); |
675 | } |
676 | |
677 | #ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT |
678 | std::pair<iterator, bool> insert(const Key &key, const T &value) |
679 | { |
680 | return try_emplace(key, value); |
681 | } |
682 | |
683 | std::pair<iterator, bool> insert(Key &&key, const T &value) |
684 | { |
685 | return try_emplace(std::move(key), value); |
686 | } |
687 | |
688 | std::pair<iterator, bool> insert(const Key &key, T &&value) |
689 | { |
690 | return try_emplace(key, std::move(value)); |
691 | } |
692 | |
693 | std::pair<iterator, bool> insert(Key &&key, T &&value) |
694 | { |
695 | return try_emplace(std::move(key), std::move(value)); |
696 | } |
697 | #endif |
698 | |
699 | template <typename...Args> |
700 | std::pair<iterator, bool> try_emplace(const Key &key, Args&&...args) |
701 | { |
702 | auto it = lower_bound(key); |
703 | if (it == end() || key_compare::operator()(key, it.key())) { |
704 | c.values.emplace(toValuesIterator(it), std::forward<Args>(args)...); |
705 | return { fromKeysIterator(c.keys.insert(toKeysIterator(it), key)), true }; |
706 | } else { |
707 | return {it, false}; |
708 | } |
709 | } |
710 | |
711 | template <typename...Args> |
712 | std::pair<iterator, bool> try_emplace(Key &&key, Args&&...args) |
713 | { |
714 | auto it = lower_bound(key); |
715 | if (it == end() || key_compare::operator()(key, it.key())) { |
716 | c.values.emplace(toValuesIterator(it), std::forward<Args>(args)...); |
717 | return { fromKeysIterator(c.keys.insert(toKeysIterator(it), std::move(key))), true }; |
718 | } else { |
719 | return {it, false}; |
720 | } |
721 | } |
722 | |
723 | template <typename M> |
724 | std::pair<iterator, bool> insert_or_assign(const Key &key, M &&obj) |
725 | { |
726 | auto r = try_emplace(key, std::forward<M>(obj)); |
727 | if (!r.second) |
728 | *toValuesIterator(it: r.first) = std::forward<M>(obj); |
729 | return r; |
730 | } |
731 | |
732 | template <typename M> |
733 | std::pair<iterator, bool> insert_or_assign(Key &&key, M &&obj) |
734 | { |
735 | auto r = try_emplace(std::move(key), std::forward<M>(obj)); |
736 | if (!r.second) |
737 | *toValuesIterator(it: r.first) = std::forward<M>(obj); |
738 | return r; |
739 | } |
740 | |
741 | #ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT |
742 | template <class InputIt, is_compatible_iterator<InputIt> = nullptr> |
743 | void insert(InputIt first, InputIt last) |
744 | { |
745 | insertRange(first, last); |
746 | } |
747 | |
748 | // ### Merge with the templated version above |
749 | // once we can use std::disjunction in is_compatible_iterator. |
750 | void insert(const value_type *first, const value_type *last) |
751 | { |
752 | insertRange(first, last); |
753 | } |
754 | |
755 | template <class InputIt, is_compatible_iterator<InputIt> = nullptr> |
756 | void insert(Qt::OrderedUniqueRange_t, InputIt first, InputIt last) |
757 | { |
758 | insertOrderedUniqueRange(first, last); |
759 | } |
760 | |
761 | // ### Merge with the templated version above |
762 | // once we can use std::disjunction in is_compatible_iterator. |
763 | void insert(Qt::OrderedUniqueRange_t, const value_type *first, const value_type *last) |
764 | { |
765 | insertOrderedUniqueRange(first, last); |
766 | } |
767 | #endif |
768 | |
769 | iterator begin() { return { &c, 0 }; } |
770 | const_iterator begin() const { return { &c, 0 }; } |
771 | const_iterator cbegin() const { return begin(); } |
772 | const_iterator constBegin() const { return cbegin(); } |
773 | iterator end() { return { &c, c.keys.size() }; } |
774 | const_iterator end() const { return { &c, c.keys.size() }; } |
775 | const_iterator cend() const { return end(); } |
776 | const_iterator constEnd() const { return cend(); } |
777 | std::reverse_iterator<iterator> rbegin() { return std::reverse_iterator<iterator>(end()); } |
778 | std::reverse_iterator<const_iterator> rbegin() const |
779 | { |
780 | return std::reverse_iterator<const_iterator>(end()); |
781 | } |
782 | std::reverse_iterator<const_iterator> crbegin() const { return rbegin(); } |
783 | std::reverse_iterator<iterator> rend() { |
784 | return std::reverse_iterator<iterator>(begin()); |
785 | } |
786 | std::reverse_iterator<const_iterator> rend() const |
787 | { |
788 | return std::reverse_iterator<const_iterator>(begin()); |
789 | } |
790 | std::reverse_iterator<const_iterator> crend() const { return rend(); } |
791 | |
792 | iterator lower_bound(const Key &key) |
793 | { |
794 | auto cit = std::as_const(*this).lower_bound(key); |
795 | return { &c, cit.i }; |
796 | } |
797 | |
798 | template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> |
799 | iterator lower_bound(const X &key) |
800 | { |
801 | auto cit = std::as_const(*this).lower_bound(key); |
802 | return { &c, cit.i }; |
803 | } |
804 | |
805 | const_iterator lower_bound(const Key &key) const |
806 | { |
807 | return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp())); |
808 | } |
809 | |
810 | template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> |
811 | const_iterator lower_bound(const X &key) const |
812 | { |
813 | return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp())); |
814 | } |
815 | |
816 | iterator find(const Key &key) |
817 | { |
818 | return { &c, std::as_const(*this).find(key).i }; |
819 | } |
820 | |
821 | template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> |
822 | iterator find(const X &key) |
823 | { |
824 | return { &c, std::as_const(*this).find(key).i }; |
825 | } |
826 | |
827 | const_iterator find(const Key &key) const |
828 | { |
829 | auto it = lower_bound(key); |
830 | if (it != end()) { |
831 | if (!key_compare::operator()(key, it.key())) |
832 | return it; |
833 | it = end(); |
834 | } |
835 | return it; |
836 | } |
837 | |
838 | template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> |
839 | const_iterator find(const X &key) const |
840 | { |
841 | auto it = lower_bound(key); |
842 | if (it != end()) { |
843 | if (!key_compare::operator()(key, it.key())) |
844 | return it; |
845 | it = end(); |
846 | } |
847 | return it; |
848 | } |
849 | |
850 | template <typename Predicate> |
851 | size_type remove_if(Predicate pred) |
852 | { |
853 | const auto indirect_call_to_pred = [pred = std::move(pred)](iterator it) { |
854 | using Pair = decltype(*it); |
855 | using K = decltype(it.key()); |
856 | using V = decltype(it.value()); |
857 | using P = Predicate; |
858 | if constexpr (std::is_invocable_v<P, K, V>) { |
859 | return pred(it.key(), it.value()); |
860 | } else if constexpr (std::is_invocable_v<P, Pair> && !std::is_invocable_v<P, K>) { |
861 | return pred(*it); |
862 | } else if constexpr (std::is_invocable_v<P, K> && !std::is_invocable_v<P, Pair>) { |
863 | return pred(it.key()); |
864 | } else { |
865 | static_assert(QtPrivate::type_dependent_false<Predicate>(), |
866 | "Don't know how to call the predicate.\n" |
867 | "Options:\n" |
868 | "- pred(*it)\n" |
869 | "- pred(it.key(), it.value())\n" |
870 | "- pred(it.key())" ); |
871 | } |
872 | }; |
873 | |
874 | auto first = begin(); |
875 | const auto last = end(); |
876 | |
877 | // find_if prefix loop |
878 | while (first != last && !indirect_call_to_pred(first)) |
879 | ++first; |
880 | |
881 | if (first == last) |
882 | return 0; // nothing to do |
883 | |
884 | // we know that we need to remove *first |
885 | |
886 | auto kdest = toKeysIterator(it: first); |
887 | auto vdest = toValuesIterator(it: first); |
888 | |
889 | ++first; |
890 | |
891 | auto k = std::next(kdest); |
892 | auto v = std::next(vdest); |
893 | |
894 | // Main Loop |
895 | // - first is used only for indirect_call_to_pred |
896 | // - operations are done on k, v |
897 | // Loop invariants: |
898 | // - first, k, v are pointing to the same element |
899 | // - [begin(), first[, [c.keys.begin(), k[, [c.values.begin(), v[: already processed |
900 | // - [first, end()[, [k, c.keys.end()[, [v, c.values.end()[: still to be processed |
901 | // - [c.keys.begin(), kdest[ and [c.values.begin(), vdest[ are keepers |
902 | // - [kdest, k[, [vdest, v[ are considered removed |
903 | // - kdest is not c.keys.end() |
904 | // - vdest is not v.values.end() |
905 | while (first != last) { |
906 | if (!indirect_call_to_pred(first)) { |
907 | // keep *first, aka {*k, *v} |
908 | *kdest = std::move(*k); |
909 | *vdest = std::move(*v); |
910 | ++kdest; |
911 | ++vdest; |
912 | } |
913 | ++k; |
914 | ++v; |
915 | ++first; |
916 | } |
917 | |
918 | const size_type r = std::distance(kdest, c.keys.end()); |
919 | c.keys.erase(kdest, c.keys.end()); |
920 | c.values.erase(vdest, c.values.end()); |
921 | return r; |
922 | } |
923 | |
924 | key_compare key_comp() const noexcept |
925 | { |
926 | return static_cast<key_compare>(*this); |
927 | } |
928 | |
929 | value_compare value_comp() const noexcept |
930 | { |
931 | return static_cast<value_compare>(*this); |
932 | } |
933 | |
934 | private: |
935 | bool do_remove(iterator it) |
936 | { |
937 | if (it != end()) { |
938 | erase(it); |
939 | return true; |
940 | } |
941 | return false; |
942 | } |
943 | |
944 | T do_take(iterator it) |
945 | { |
946 | if (it != end()) { |
947 | T result = std::move(it.value()); |
948 | erase(it); |
949 | return result; |
950 | } |
951 | return {}; |
952 | } |
953 | |
954 | template <class InputIt, is_compatible_iterator<InputIt> = nullptr> |
955 | void initWithRange(InputIt first, InputIt last) |
956 | { |
957 | QtPrivate::reserveIfForwardIterator(this, first, last); |
958 | while (first != last) { |
959 | c.keys.push_back(first->first); |
960 | c.values.push_back(first->second); |
961 | ++first; |
962 | } |
963 | } |
964 | |
965 | iterator fromKeysIterator(typename key_container_type::iterator kit) |
966 | { |
967 | return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) }; |
968 | } |
969 | |
970 | const_iterator fromKeysIterator(typename key_container_type::const_iterator kit) const |
971 | { |
972 | return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) }; |
973 | } |
974 | |
975 | typename key_container_type::iterator toKeysIterator(iterator it) |
976 | { |
977 | return c.keys.begin() + it.i; |
978 | } |
979 | |
980 | typename mapped_container_type::iterator toValuesIterator(iterator it) |
981 | { |
982 | return c.values.begin() + it.i; |
983 | } |
984 | |
985 | template <class InputIt> |
986 | void insertRange(InputIt first, InputIt last) |
987 | { |
988 | size_type i = c.keys.size(); |
989 | c.keys.resize(i + std::distance(first, last)); |
990 | c.values.resize(c.keys.size()); |
991 | for (; first != last; ++first, ++i) { |
992 | c.keys[i] = first->first; |
993 | c.values[i] = first->second; |
994 | } |
995 | ensureOrderedUnique(); |
996 | } |
997 | |
998 | class IndexedKeyComparator |
999 | { |
1000 | public: |
1001 | IndexedKeyComparator(const QFlatMap *am) |
1002 | : m(am) |
1003 | { |
1004 | } |
1005 | |
1006 | bool operator()(size_type i, size_type k) const |
1007 | { |
1008 | return m->key_comp()(m->c.keys[i], m->c.keys[k]); |
1009 | } |
1010 | |
1011 | private: |
1012 | const QFlatMap *m; |
1013 | }; |
1014 | |
1015 | template <class InputIt> |
1016 | void insertOrderedUniqueRange(InputIt first, InputIt last) |
1017 | { |
1018 | const size_type s = c.keys.size(); |
1019 | c.keys.resize(s + std::distance(first, last)); |
1020 | c.values.resize(c.keys.size()); |
1021 | for (size_type i = s; first != last; ++first, ++i) { |
1022 | c.keys[i] = first->first; |
1023 | c.values[i] = first->second; |
1024 | } |
1025 | |
1026 | std::vector<size_type> p(size_t(c.keys.size())); |
1027 | std::iota(p.begin(), p.end(), 0); |
1028 | std::inplace_merge(p.begin(), p.begin() + s, p.end(), IndexedKeyComparator(this)); |
1029 | applyPermutation(p); |
1030 | makeUnique(); |
1031 | } |
1032 | |
1033 | void ensureOrderedUnique() |
1034 | { |
1035 | std::vector<size_type> p(size_t(c.keys.size())); |
1036 | std::iota(p.begin(), p.end(), 0); |
1037 | std::stable_sort(p.begin(), p.end(), IndexedKeyComparator(this)); |
1038 | applyPermutation(p); |
1039 | makeUnique(); |
1040 | } |
1041 | |
1042 | void applyPermutation(const std::vector<size_type> &p) |
1043 | { |
1044 | const size_type s = c.keys.size(); |
1045 | std::vector<bool> done(s); |
1046 | for (size_type i = 0; i < s; ++i) { |
1047 | if (done[i]) |
1048 | continue; |
1049 | done[i] = true; |
1050 | size_type j = i; |
1051 | size_type k = p[i]; |
1052 | while (i != k) { |
1053 | qSwap(c.keys[j], c.keys[k]); |
1054 | qSwap(c.values[j], c.values[k]); |
1055 | done[k] = true; |
1056 | j = k; |
1057 | k = p[j]; |
1058 | } |
1059 | } |
1060 | } |
1061 | |
1062 | void makeUnique() |
1063 | { |
1064 | // std::unique, but over two ranges |
1065 | auto equivalent = [this](const auto &lhs, const auto &rhs) { |
1066 | return !key_compare::operator()(lhs, rhs) && !key_compare::operator()(rhs, lhs); |
1067 | }; |
1068 | const auto kb = c.keys.begin(); |
1069 | const auto ke = c.keys.end(); |
1070 | auto k = std::adjacent_find(kb, ke, equivalent); |
1071 | if (k == ke) |
1072 | return; |
1073 | |
1074 | // equivalent keys found, we need to do actual work: |
1075 | auto v = std::next(c.values.begin(), std::distance(kb, k)); |
1076 | |
1077 | auto kdest = k; |
1078 | auto vdest = v; |
1079 | |
1080 | ++k; |
1081 | ++v; |
1082 | |
1083 | // Loop Invariants: |
1084 | // |
1085 | // - [keys.begin(), kdest] and [values.begin(), vdest] are unique |
1086 | // - k is not keys.end(), v is not values.end() |
1087 | // - [next(k), keys.end()[ and [next(v), values.end()[ still need to be checked |
1088 | while ((++v, ++k) != ke) { |
1089 | if (!equivalent(*kdest, *k)) { |
1090 | *++kdest = std::move(*k); |
1091 | *++vdest = std::move(*v); |
1092 | } |
1093 | } |
1094 | |
1095 | c.keys.erase(std::next(kdest), ke); |
1096 | c.values.erase(std::next(vdest), c.values.end()); |
1097 | } |
1098 | |
1099 | containers c; |
1100 | }; |
1101 | |
1102 | template<class Key, class T, qsizetype N = 256, class Compare = std::less<Key>> |
1103 | using QVarLengthFlatMap = QFlatMap<Key, T, Compare, QVarLengthArray<Key, N>, QVarLengthArray<T, N>>; |
1104 | |
1105 | QT_END_NAMESPACE |
1106 | |
1107 | #endif // QFLATMAP_P_H |
1108 | |