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
30QT_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
58namespace Qt {
59
60struct OrderedUniqueRange_t {};
61constexpr OrderedUniqueRange_t OrderedUniqueRange = {};
62
63} // namespace Qt
64
65template <class Key, class T, class Compare>
66class QFlatMapValueCompare : protected Compare
67{
68public:
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
86namespace qflatmap {
87namespace detail {
88template <class T>
89class QFlatMapMockPointer
90{
91 T ref;
92public:
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
106template<class Key, class T, class Compare = std::less<Key>, class KeyContainer = QList<Key>,
107 class MappedContainer = QList<T>>
108class 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
115public:
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
400private:
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
415public:
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 extract() && { 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
934private:
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
1102template<class Key, class T, qsizetype N = 256, class Compare = std::less<Key>>
1103using QVarLengthFlatMap = QFlatMap<Key, T, Compare, QVarLengthArray<Key, N>, QVarLengthArray<T, N>>;
1104
1105QT_END_NAMESPACE
1106
1107#endif // QFLATMAP_P_H
1108

source code of qtbase/src/corelib/tools/qflatmap_p.h