diff options
Diffstat (limited to 'src/corelib/tools/qflatmap_p.h')
| -rw-r--r-- | src/corelib/tools/qflatmap_p.h | 1109 |
1 files changed, 1109 insertions, 0 deletions
diff --git a/src/corelib/tools/qflatmap_p.h b/src/corelib/tools/qflatmap_p.h new file mode 100644 index 0000000000..d2c0d45b79 --- /dev/null +++ b/src/corelib/tools/qflatmap_p.h @@ -0,0 +1,1109 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only + +#ifndef QFLATMAP_P_H +#define QFLATMAP_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of a number of Qt sources files. This header file may change from +// version to version without notice, or even be removed. +// +// We mean it. +// + +#include "qlist.h" +#include "private/qglobal_p.h" + +#include <algorithm> +#include <functional> +#include <initializer_list> +#include <iterator> +#include <numeric> +#include <type_traits> +#include <utility> +#include <vector> + +QT_BEGIN_NAMESPACE + +/* + QFlatMap provides an associative container backed by sorted sequential + containers. By default, QList is used. + + Keys and values are stored in two separate containers. This provides improved + cache locality for key iteration and makes keys() and values() fast + operations. + + One can customize the underlying container type by passing the KeyContainer + and MappedContainer template arguments: + QFlatMap<float, int, std::less<float>, std::vector<float>, std::vector<int>> +*/ + +// Qt 6.4: +// - removed QFlatMap API which was incompatible with STL semantics +// - will be released with said API disabled, to catch any out-of-tree users +// - also allows opting in to the new API using QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT +// Qt 6.5 +// - will make QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT the default: + +#ifndef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT +# if QT_VERSION >= QT_VERSION_CHECK(6, 5, 0) +# define QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT +# endif +#endif + +namespace Qt { + +struct OrderedUniqueRange_t {}; +constexpr OrderedUniqueRange_t OrderedUniqueRange = {}; + +} // namespace Qt + +template <class Key, class T, class Compare> +class QFlatMapValueCompare : protected Compare +{ +public: + QFlatMapValueCompare() = default; + QFlatMapValueCompare(const Compare &key_compare) + : Compare(key_compare) + { + } + + using value_type = std::pair<const Key, T>; + static constexpr bool is_comparator_noexcept = noexcept( + std::declval<Compare>()(std::declval<const Key &>(), std::declval<const Key &>())); + + bool operator()(const value_type &lhs, const value_type &rhs) const + noexcept(is_comparator_noexcept) + { + return Compare::operator()(lhs.first, rhs.first); + } +}; + +namespace qflatmap { +namespace detail { +template <class T> +class QFlatMapMockPointer +{ + T ref; +public: + QFlatMapMockPointer(T r) + : ref(r) + { + } + + T *operator->() + { + return &ref; + } +}; +} // namespace detail +} // namespace qflatmap + +template<class Key, class T, class Compare = std::less<Key>, class KeyContainer = QList<Key>, + class MappedContainer = QList<T>> +class QFlatMap : private QFlatMapValueCompare<Key, T, Compare> +{ + static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers."); + + template<class U> + using mock_pointer = qflatmap::detail::QFlatMapMockPointer<U>; + +public: + using key_type = Key; + using mapped_type = T; + using value_compare = QFlatMapValueCompare<Key, T, Compare>; + using value_type = typename value_compare::value_type; + using key_container_type = KeyContainer; + using mapped_container_type = MappedContainer; + using size_type = typename key_container_type::size_type; + using key_compare = Compare; + + struct containers + { + key_container_type keys; + mapped_container_type values; + }; + + class iterator + { + public: + using difference_type = ptrdiff_t; + using value_type = std::pair<const Key, T>; + using reference = std::pair<const Key &, T &>; + using pointer = mock_pointer<reference>; + using iterator_category = std::random_access_iterator_tag; + + iterator() = default; + + iterator(containers *ac, size_type ai) + : c(ac), i(ai) + { + } + + reference operator*() const + { + return { c->keys[i], c->values[i] }; + } + + pointer operator->() const + { + return { operator*() }; + } + + bool operator==(const iterator &o) const + { + return c == o.c && i == o.i; + } + + bool operator!=(const iterator &o) const + { + return !operator==(o); + } + + iterator &operator++() + { + ++i; + return *this; + } + + iterator operator++(int) + { + + iterator r = *this; + ++*this; + return r; + } + + iterator &operator--() + { + --i; + return *this; + } + + iterator operator--(int) + { + iterator r = *this; + --*this; + return r; + } + + iterator &operator+=(size_type n) + { + i += n; + return *this; + } + + friend iterator operator+(size_type n, const iterator a) + { + iterator ret = a; + return ret += n; + } + + friend iterator operator+(const iterator a, size_type n) + { + return n + a; + } + + iterator &operator-=(size_type n) + { + i -= n; + return *this; + } + + friend iterator operator-(const iterator a, size_type n) + { + iterator ret = a; + return ret -= n; + } + + friend difference_type operator-(const iterator b, const iterator a) + { + return b.i - a.i; + } + + reference operator[](size_type n) const + { + size_type k = i + n; + return { c->keys[k], c->values[k] }; + } + + bool operator<(const iterator &other) const + { + return i < other.i; + } + + bool operator>(const iterator &other) const + { + return i > other.i; + } + + bool operator<=(const iterator &other) const + { + return i <= other.i; + } + + bool operator>=(const iterator &other) const + { + return i >= other.i; + } + + const Key &key() const { return c->keys[i]; } + T &value() const { return c->values[i]; } + + private: + containers *c = nullptr; + size_type i = 0; + friend QFlatMap; + }; + + class const_iterator + { + public: + using difference_type = ptrdiff_t; + using value_type = std::pair<const Key, const T>; + using reference = std::pair<const Key &, const T &>; + using pointer = mock_pointer<reference>; + using iterator_category = std::random_access_iterator_tag; + + const_iterator() = default; + + const_iterator(const containers *ac, size_type ai) + : c(ac), i(ai) + { + } + + const_iterator(iterator o) + : c(o.c), i(o.i) + { + } + + reference operator*() const + { + return { c->keys[i], c->values[i] }; + } + + pointer operator->() const + { + return { operator*() }; + } + + bool operator==(const const_iterator &o) const + { + return c == o.c && i == o.i; + } + + bool operator!=(const const_iterator &o) const + { + return !operator==(o); + } + + const_iterator &operator++() + { + ++i; + return *this; + } + + const_iterator operator++(int) + { + + const_iterator r = *this; + ++*this; + return r; + } + + const_iterator &operator--() + { + --i; + return *this; + } + + const_iterator operator--(int) + { + const_iterator r = *this; + --*this; + return r; + } + + const_iterator &operator+=(size_type n) + { + i += n; + return *this; + } + + friend const_iterator operator+(size_type n, const const_iterator a) + { + const_iterator ret = a; + return ret += n; + } + + friend const_iterator operator+(const const_iterator a, size_type n) + { + return n + a; + } + + const_iterator &operator-=(size_type n) + { + i -= n; + return *this; + } + + friend const_iterator operator-(const const_iterator a, size_type n) + { + const_iterator ret = a; + return ret -= n; + } + + friend difference_type operator-(const const_iterator b, const const_iterator a) + { + return b.i - a.i; + } + + reference operator[](size_type n) const + { + size_type k = i + n; + return { c->keys[k], c->values[k] }; + } + + bool operator<(const const_iterator &other) const + { + return i < other.i; + } + + bool operator>(const const_iterator &other) const + { + return i > other.i; + } + + bool operator<=(const const_iterator &other) const + { + return i <= other.i; + } + + bool operator>=(const const_iterator &other) const + { + return i >= other.i; + } + + const Key &key() const { return c->keys[i]; } + const T &value() const { return c->values[i]; } + + private: + const containers *c = nullptr; + size_type i = 0; + friend QFlatMap; + }; + +private: + template <class, class = void> + struct is_marked_transparent_type : std::false_type { }; + + template <class X> + struct is_marked_transparent_type<X, std::void_t<typename X::is_transparent>> : std::true_type { }; + + template <class X> + using is_marked_transparent = typename std::enable_if< + is_marked_transparent_type<X>::value>::type *; + + template <typename It> + using is_compatible_iterator = typename std::enable_if< + std::is_same<value_type, typename std::iterator_traits<It>::value_type>::value>::type *; + +public: + QFlatMap() = default; + +#ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT + explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values) + : c{keys, values} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values) + : c{std::move(keys), values} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values) + : c{keys, std::move(values)} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values) + : c{std::move(keys), std::move(values)} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(std::initializer_list<value_type> lst) + : QFlatMap(lst.begin(), lst.end()) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(InputIt first, InputIt last) + { + initWithRange(first, last); + ensureOrderedUnique(); + } +#endif + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + const mapped_container_type &values) + : c{keys, values} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + const mapped_container_type &values) + : c{std::move(keys), values} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + mapped_container_type &&values) + : c{keys, std::move(values)} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + mapped_container_type &&values) + : c{std::move(keys), std::move(values)} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst) + : QFlatMap(Qt::OrderedUniqueRange, lst.begin(), lst.end()) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last) + { + initWithRange(first, last); + } + + explicit QFlatMap(const Compare &compare) + : value_compare(compare) + { + } + +#ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT + explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values, + const Compare &compare) + : value_compare(compare), c{keys, values} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values, + const Compare &compare) + : value_compare(compare), c{std::move(keys), values} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values, + const Compare &compare) + : value_compare(compare), c{keys, std::move(values)} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values, + const Compare &compare) + : value_compare(compare), c{std::move(keys), std::move(values)} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(std::initializer_list<value_type> lst, const Compare &compare) + : QFlatMap(lst.begin(), lst.end(), compare) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(InputIt first, InputIt last, const Compare &compare) + : value_compare(compare) + { + initWithRange(first, last); + ensureOrderedUnique(); + } +#endif + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + const mapped_container_type &values, const Compare &compare) + : value_compare(compare), c{keys, values} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + const mapped_container_type &values, const Compare &compare) + : value_compare(compare), c{std::move(keys), values} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + mapped_container_type &&values, const Compare &compare) + : value_compare(compare), c{keys, std::move(values)} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + mapped_container_type &&values, const Compare &compare) + : value_compare(compare), c{std::move(keys), std::move(values)} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst, + const Compare &compare) + : QFlatMap(Qt::OrderedUniqueRange, lst.begin(), lst.end(), compare) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last, const Compare &compare) + : value_compare(compare) + { + initWithRange(first, last); + } + + size_type count() const noexcept { return c.keys.size(); } + size_type size() const noexcept { return c.keys.size(); } + size_type capacity() const noexcept { return c.keys.capacity(); } + bool isEmpty() const noexcept { return c.keys.empty(); } + bool empty() const noexcept { return c.keys.empty(); } + containers extract() && { return std::move(c); } + const key_container_type &keys() const noexcept { return c.keys; } + const mapped_container_type &values() const noexcept { return c.values; } + + void reserve(size_type s) + { + c.keys.reserve(s); + c.values.reserve(s); + } + + void clear() + { + c.keys.clear(); + c.values.clear(); + } + + bool remove(const Key &key) + { + return do_remove(find(key)); + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + bool remove(const X &key) + { + return do_remove(find(key)); + } + + iterator erase(iterator it) + { + c.values.erase(toValuesIterator(it)); + return fromKeysIterator(c.keys.erase(toKeysIterator(it))); + } + + T take(const Key &key) + { + return do_take(find(key)); + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + T take(const X &key) + { + return do_take(find(key)); + } + + bool contains(const Key &key) const + { + return find(key) != end(); + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + bool contains(const X &key) const + { + return find(key) != end(); + } + + T value(const Key &key, const T &defaultValue) const + { + auto it = find(key); + return it == end() ? defaultValue : it.value(); + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + T value(const X &key, const T &defaultValue) const + { + auto it = find(key); + return it == end() ? defaultValue : it.value(); + } + + T value(const Key &key) const + { + auto it = find(key); + return it == end() ? T() : it.value(); + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + T value(const X &key) const + { + auto it = find(key); + return it == end() ? T() : it.value(); + } + + T &operator[](const Key &key) + { + return try_emplace(key).first.value(); + } + + T &operator[](Key &&key) + { + return try_emplace(std::move(key)).first.value(); + } + + T operator[](const Key &key) const + { + return value(key); + } + +#ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT + std::pair<iterator, bool> insert(const Key &key, const T &value) + { + return try_emplace(key, value); + } + + std::pair<iterator, bool> insert(Key &&key, const T &value) + { + return try_emplace(std::move(key), value); + } + + std::pair<iterator, bool> insert(const Key &key, T &&value) + { + return try_emplace(key, std::move(value)); + } + + std::pair<iterator, bool> insert(Key &&key, T &&value) + { + return try_emplace(std::move(key), std::move(value)); + } +#endif + + template <typename...Args> + std::pair<iterator, bool> try_emplace(const Key &key, Args&&...args) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.emplace(toValuesIterator(it), std::forward<Args>(args)...); + return { fromKeysIterator(c.keys.insert(toKeysIterator(it), key)), true }; + } else { + return {it, false}; + } + } + + template <typename...Args> + std::pair<iterator, bool> try_emplace(Key &&key, Args&&...args) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.emplace(toValuesIterator(it), std::forward<Args>(args)...); + return { fromKeysIterator(c.keys.insert(toKeysIterator(it), std::move(key))), true }; + } else { + return {it, false}; + } + } + + template <typename M> + std::pair<iterator, bool> insert_or_assign(const Key &key, M &&obj) + { + auto r = try_emplace(key, std::forward<M>(obj)); + if (!r.second) + *toValuesIterator(r.first) = std::forward<M>(obj); + return r; + } + + template <typename M> + std::pair<iterator, bool> insert_or_assign(Key &&key, M &&obj) + { + auto r = try_emplace(std::move(key), std::forward<M>(obj)); + if (!r.second) + *toValuesIterator(r.first) = std::forward<M>(obj); + return r; + } + +#ifdef QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + void insert(InputIt first, InputIt last) + { + insertRange(first, last); + } + + // ### Merge with the templated version above + // once we can use std::disjunction in is_compatible_iterator. + void insert(const value_type *first, const value_type *last) + { + insertRange(first, last); + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + void insert(Qt::OrderedUniqueRange_t, InputIt first, InputIt last) + { + insertOrderedUniqueRange(first, last); + } + + // ### Merge with the templated version above + // once we can use std::disjunction in is_compatible_iterator. + void insert(Qt::OrderedUniqueRange_t, const value_type *first, const value_type *last) + { + insertOrderedUniqueRange(first, last); + } +#endif + + iterator begin() { return { &c, 0 }; } + const_iterator begin() const { return { &c, 0 }; } + const_iterator cbegin() const { return begin(); } + const_iterator constBegin() const { return cbegin(); } + iterator end() { return { &c, c.keys.size() }; } + const_iterator end() const { return { &c, c.keys.size() }; } + const_iterator cend() const { return end(); } + const_iterator constEnd() const { return cend(); } + std::reverse_iterator<iterator> rbegin() { return std::reverse_iterator<iterator>(end()); } + std::reverse_iterator<const_iterator> rbegin() const + { + return std::reverse_iterator<const_iterator>(end()); + } + std::reverse_iterator<const_iterator> crbegin() const { return rbegin(); } + std::reverse_iterator<iterator> rend() { + return std::reverse_iterator<iterator>(begin()); + } + std::reverse_iterator<const_iterator> rend() const + { + return std::reverse_iterator<const_iterator>(begin()); + } + std::reverse_iterator<const_iterator> crend() const { return rend(); } + + iterator lower_bound(const Key &key) + { + auto cit = std::as_const(*this).lower_bound(key); + return { &c, cit.i }; + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + iterator lower_bound(const X &key) + { + auto cit = std::as_const(*this).lower_bound(key); + return { &c, cit.i }; + } + + const_iterator lower_bound(const Key &key) const + { + return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp())); + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + const_iterator lower_bound(const X &key) const + { + return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp())); + } + + iterator find(const Key &key) + { + return { &c, std::as_const(*this).find(key).i }; + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + iterator find(const X &key) + { + return { &c, std::as_const(*this).find(key).i }; + } + + const_iterator find(const Key &key) const + { + auto it = lower_bound(key); + if (it != end()) { + if (!key_compare::operator()(key, it.key())) + return it; + it = end(); + } + return it; + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + const_iterator find(const X &key) const + { + auto it = lower_bound(key); + if (it != end()) { + if (!key_compare::operator()(key, it.key())) + return it; + it = end(); + } + return it; + } + + template <typename Predicate> + size_type remove_if(Predicate pred) + { + const auto indirect_call_to_pred = [pred = std::move(pred)](iterator it) { + using Pair = decltype(*it); + using K = decltype(it.key()); + using V = decltype(it.value()); + using P = Predicate; + if constexpr (std::is_invocable_v<P, K, V>) { + return pred(it.key(), it.value()); + } else if constexpr (std::is_invocable_v<P, Pair> && !std::is_invocable_v<P, K>) { + return pred(*it); + } else if constexpr (std::is_invocable_v<P, K> && !std::is_invocable_v<P, Pair>) { + return pred(it.key()); + } else { + static_assert(QtPrivate::type_dependent_false<Predicate>(), + "Don't know how to call the predicate.\n" + "Options:\n" + "- pred(*it)\n" + "- pred(it.key(), it.value())\n" + "- pred(it.key())"); + } + }; + + auto first = begin(); + const auto last = end(); + + // find_if prefix loop + while (first != last && !indirect_call_to_pred(first)) + ++first; + + if (first == last) + return 0; // nothing to do + + // we know that we need to remove *first + + auto kdest = toKeysIterator(first); + auto vdest = toValuesIterator(first); + + ++first; + + auto k = std::next(kdest); + auto v = std::next(vdest); + + // Main Loop + // - first is used only for indirect_call_to_pred + // - operations are done on k, v + // Loop invariants: + // - first, k, v are pointing to the same element + // - [begin(), first[, [c.keys.begin(), k[, [c.values.begin(), v[: already processed + // - [first, end()[, [k, c.keys.end()[, [v, c.values.end()[: still to be processed + // - [c.keys.begin(), kdest[ and [c.values.begin(), vdest[ are keepers + // - [kdest, k[, [vdest, v[ are considered removed + // - kdest is not c.keys.end() + // - vdest is not v.values.end() + while (first != last) { + if (!indirect_call_to_pred(first)) { + // keep *first, aka {*k, *v} + *kdest = std::move(*k); + *vdest = std::move(*v); + ++kdest; + ++vdest; + } + ++k; + ++v; + ++first; + } + + const size_type r = std::distance(kdest, c.keys.end()); + c.keys.erase(kdest, c.keys.end()); + c.values.erase(vdest, c.values.end()); + return r; + } + + key_compare key_comp() const noexcept + { + return static_cast<key_compare>(*this); + } + + value_compare value_comp() const noexcept + { + return static_cast<value_compare>(*this); + } + +private: + bool do_remove(iterator it) + { + if (it != end()) { + erase(it); + return true; + } + return false; + } + + T do_take(iterator it) + { + if (it != end()) { + T result = std::move(it.value()); + erase(it); + return result; + } + return {}; + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + void initWithRange(InputIt first, InputIt last) + { + QtPrivate::reserveIfForwardIterator(this, first, last); + while (first != last) { + c.keys.push_back(first->first); + c.values.push_back(first->second); + ++first; + } + } + + iterator fromKeysIterator(typename key_container_type::iterator kit) + { + return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) }; + } + + const_iterator fromKeysIterator(typename key_container_type::const_iterator kit) const + { + return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) }; + } + + typename key_container_type::iterator toKeysIterator(iterator it) + { + return c.keys.begin() + it.i; + } + + typename mapped_container_type::iterator toValuesIterator(iterator it) + { + return c.values.begin() + it.i; + } + + template <class InputIt> + void insertRange(InputIt first, InputIt last) + { + size_type i = c.keys.size(); + c.keys.resize(i + std::distance(first, last)); + c.values.resize(c.keys.size()); + for (; first != last; ++first, ++i) { + c.keys[i] = first->first; + c.values[i] = first->second; + } + ensureOrderedUnique(); + } + + class IndexedKeyComparator + { + public: + IndexedKeyComparator(const QFlatMap *am) + : m(am) + { + } + + bool operator()(size_type i, size_type k) const + { + return m->key_comp()(m->c.keys[i], m->c.keys[k]); + } + + private: + const QFlatMap *m; + }; + + template <class InputIt> + void insertOrderedUniqueRange(InputIt first, InputIt last) + { + const size_type s = c.keys.size(); + c.keys.resize(s + std::distance(first, last)); + c.values.resize(c.keys.size()); + for (size_type i = s; first != last; ++first, ++i) { + c.keys[i] = first->first; + c.values[i] = first->second; + } + + std::vector<size_type> p(size_t(c.keys.size())); + std::iota(p.begin(), p.end(), 0); + std::inplace_merge(p.begin(), p.begin() + s, p.end(), IndexedKeyComparator(this)); + applyPermutation(p); + makeUnique(); + } + + void ensureOrderedUnique() + { + std::vector<size_type> p(size_t(c.keys.size())); + std::iota(p.begin(), p.end(), 0); + std::stable_sort(p.begin(), p.end(), IndexedKeyComparator(this)); + applyPermutation(p); + makeUnique(); + } + + void applyPermutation(const std::vector<size_type> &p) + { + const size_type s = c.keys.size(); + std::vector<bool> done(s); + for (size_type i = 0; i < s; ++i) { + if (done[i]) + continue; + done[i] = true; + size_type j = i; + size_type k = p[i]; + while (i != k) { + qSwap(c.keys[j], c.keys[k]); + qSwap(c.values[j], c.values[k]); + done[k] = true; + j = k; + k = p[j]; + } + } + } + + void makeUnique() + { + // std::unique, but over two ranges + auto equivalent = [this](const auto &lhs, const auto &rhs) { + return !key_compare::operator()(lhs, rhs) && !key_compare::operator()(rhs, lhs); + }; + const auto kb = c.keys.begin(); + const auto ke = c.keys.end(); + auto k = std::adjacent_find(kb, ke, equivalent); + if (k == ke) + return; + + // equivalent keys found, we need to do actual work: + auto v = std::next(c.values.begin(), std::distance(kb, k)); + + auto kdest = k; + auto vdest = v; + + ++k; + ++v; + + // Loop Invariants: + // + // - [keys.begin(), kdest] and [values.begin(), vdest] are unique + // - k is not keys.end(), v is not values.end() + // - [next(k), keys.end()[ and [next(v), values.end()[ still need to be checked + while ((++v, ++k) != ke) { + if (!equivalent(*kdest, *k)) { + *++kdest = std::move(*k); + *++vdest = std::move(*v); + } + } + + c.keys.erase(std::next(kdest), ke); + c.values.erase(std::next(vdest), c.values.end()); + } + + containers c; +}; + +template <class Key, class T, + qsizetype N = QVarLengthArrayDefaultPrealloc, + class Compare = std::less<Key>> +using QVarLengthFlatMap = QFlatMap<Key, T, Compare, QVarLengthArray<Key, N>, QVarLengthArray<T, N>>; + +QT_END_NAMESPACE + +#endif // QFLATMAP_P_H |