diff options
author | Joerg Bornemann <joerg.bornemann@qt.io> | 2019-06-12 13:42:39 +0200 |
---|---|---|
committer | Joerg Bornemann <joerg.bornemann@qt.io> | 2020-01-02 15:28:20 +0100 |
commit | deddafe0a6a32aa438cc36c7dcfae8c323274487 (patch) | |
tree | 78a1d7a7a933b86cdb2990322bddfadd6591673d /src/corelib/tools | |
parent | a0eb51c3870d90c06966dbfbe26b114f39103b60 (diff) |
Long live QFlatMap!
Add a light-weight associative container, API-wise very similar to QMap,
that's based on two sorted continuous containers (QVector by default).
The class is internal for now.
Change-Id: Ife12576c4abb39a3ea2acb0a1ba0faca91b3a4c5
Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
Diffstat (limited to 'src/corelib/tools')
-rw-r--r-- | src/corelib/tools/qflatmap_p.h | 982 | ||||
-rw-r--r-- | src/corelib/tools/tools.pri | 1 |
2 files changed, 983 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..590b0d942f --- /dev/null +++ b/src/corelib/tools/qflatmap_p.h @@ -0,0 +1,982 @@ +/**************************************************************************** +** +** Copyright (C) 2020 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#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 "qvector.h" + +#include <algorithm> +#include <functional> +#include <initializer_list> +#include <iterator> +#include <numeric> +#include <type_traits> +#include <utility> + +QT_BEGIN_NAMESPACE + +/* + QFlatMap provides an associative container backed by sorted sequential + containers. By default, QVector 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>> +*/ + +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<Key>(), std::declval<Key>())); + + bool operator()(const value_type &lhs, const value_type &rhs) const + noexcept(is_comparator_noexcept) + { + return Compare::operator()(lhs.first, rhs.first); + } +}; + +template <class Key, class T, + class Compare = std::less<Key>, + class KeyContainer = QVector<Key>, + class MappedContainer = QVector<T>> +class QFlatMap : private QFlatMapValueCompare<Key, T, Compare> +{ + using full_map_t = QFlatMap<Key, T, Compare, KeyContainer, MappedContainer>; + + template <class U> + class mock_pointer + { + U ref; + public: + mock_pointer(U r) + : ref(r) + { + } + + U *operator->() + { + return &ref; + } + }; + +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*() + { + return { c->keys[i], c->values[i] }; + } + + pointer operator->() + { + 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; + i++; + return r; + } + + iterator &operator--() + { + --i; + return *this; + } + + iterator operator--(int) + { + iterator r = *this; + i--; + 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) + { + 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() { return c->values[i]; } + + private: + containers *c = nullptr; + size_type i = 0; + friend full_map_t; + }; + + 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*() + { + return { c->keys[i], c->values[i] }; + } + + pointer operator->() + { + 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; + i++; + return r; + } + + const_iterator &operator--() + { + --i; + return *this; + } + + const_iterator operator--(int) + { + const_iterator r = *this; + i--; + 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) + { + 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() { return c->values[i]; } + + private: + const containers *c = nullptr; + size_type i = 0; + friend full_map_t; + }; + +private: + template <class, class = void> + struct is_marked_transparent_type : std::false_type { }; + + template <class X> + struct is_marked_transparent_type<X, 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; + + 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.keys = std::move(keys); + c.values = values; + ensureOrderedUnique(); + } + + explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values) + { + c.keys = keys; + c.values = std::move(values); + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values) + { + c.keys = std::move(keys); + c.values = 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(); + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + const mapped_container_type &values) + { + c.keys = keys; + c.values = values; + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + const mapped_container_type &values) + { + c.keys = std::move(keys); + c.values = values; + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + mapped_container_type &&values) + { + c.keys = keys; + c.values = std::move(values); + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + mapped_container_type &&values) + { + c.keys = std::move(keys); + c.values = std::move(values); + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst) + : QFlatMap(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) + { + } + + 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(); + } + + 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) + { + auto it = binary_find(key); + if (it != end()) { + c.keys.erase(toKeysIterator(it)); + c.values.erase(toValuesIterator(it)); + return true; + } + return false; + } + + iterator erase(iterator it) + { + c.values.erase(toValuesIterator(it)); + return fromKeysIterator(c.keys.erase(toKeysIterator(it))); + } + + T take(const Key &key) + { + auto it = binary_find(key); + if (it != end()) { + T result = std::move(it.value()); + erase(it); + return result; + } + return {}; + } + + bool contains(const Key &key) const + { + return binary_find(key) != end(); + } + + T value(const Key &key, const T &defaultValue) const + { + auto it = binary_find(key); + return it == end() ? defaultValue : it.value(); + } + + T value(const Key &key) const + { + auto it = binary_find(key); + return it == end() ? T() : it.value(); + } + + T &operator[](const Key &key) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.keys.insert(toKeysIterator(it), key); + return *c.values.insert(toValuesIterator(it), T()); + } + return it.value(); + } + + T &operator[](Key &&key) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.keys.insert(toKeysIterator(it), key); + return *c.values.insert(toValuesIterator(it), T()); + } + return it.value(); + } + + T operator[](const Key &key) const + { + return value(key); + } + + std::pair<iterator, bool> insert(const Key &key, const T &value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), value); + auto k = c.keys.insert(toKeysIterator(it), key); + return { fromKeysIterator(k), true }; + } else { + it.value() = value; + return {it, false}; + } + } + + std::pair<iterator, bool> insert(Key &&key, const T &value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), value); + return { c.keys.insert(it, std::move(key)), true }; + } else { + *toValuesIterator(it) = value; + return {it, false}; + } + } + + std::pair<iterator, bool> insert(const Key &key, T &&value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), std::move(value)); + return { c.keys.insert(it, key), true }; + } else { + *toValuesIterator(it) = std::move(value); + return {it, false}; + } + } + + std::pair<iterator, bool> insert(Key &&key, T &&value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), std::move(value)); + return { fromKeysIterator(c.keys.insert(toKeysIterator(it), std::move(key))), true }; + } else { + *toValuesIterator(it) = std::move(value); + return {it, false}; + } + } + + 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); + } + + 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 = const_cast<const full_map_t *>(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 = const_cast<const full_map_t *>(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_type &k) + { + return binary_find(k); + } + + const_iterator find(const key_type &k) const + { + return binary_find(k); + } + + 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: + 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 full_map_t *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 full_map_t *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(); + } + + iterator binary_find(const Key &key) + { + return { &c, const_cast<const full_map_t *>(this)->binary_find(key).i }; + } + + const_iterator binary_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; + } + + 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() + { + if (c.keys.size() < 2) + return; + auto k = std::end(c.keys) - 1; + auto i = k - 1; + for (;;) { + if (key_compare::operator()(*i, *k) || key_compare::operator()(*k, *i)) { + if (i == std::begin(c.keys)) + break; + --i; + --k; + } else { + c.values.erase(std::begin(c.values) + std::distance(std::begin(c.keys), i)); + i = c.keys.erase(i); + if (i == std::begin(c.keys)) + break; + k = i + 1; + } + } + c.keys.shrink_to_fit(); + c.values.shrink_to_fit(); + } + + containers c; +}; + +QT_END_NAMESPACE + +#endif // QFLATMAP_P_H diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri index a1b243dd5f..230456bef9 100644 --- a/src/corelib/tools/tools.pri +++ b/src/corelib/tools/tools.pri @@ -12,6 +12,7 @@ HEADERS += \ tools/qcontainerfwd.h \ tools/qcontainertools_impl.h \ tools/qcryptographichash.h \ + tools/qflatmap_p.h \ tools/qfreelist_p.h \ tools/qhash.h \ tools/qhashfunctions.h \ |