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>

5 files changed, 1441 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 \
diff --git a/tests/auto/corelib/tools/qflatmap/qflatmap.pro b/tests/auto/corelib/tools/qflatmap/qflatmap.pro
new file mode 100644
index 0000000000..3927cee30c
--- /dev/null
+++ b/tests/auto/corelib/tools/qflatmap/qflatmap.pro
@@ -0,0 +1,4 @@
+CONFIG += testcase
+TARGET = tst_qflatmap
+QT = core-private testlib
+SOURCES = tst_qflatmap.cpp
diff --git a/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp b/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp
new file mode 100644
index 0000000000..a5ae6f5f44
--- /dev/null
+++ b/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp
@@ -0,0 +1,453 @@
+/****************************************************************************
+**
+** Copyright (C) 2020 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the test suite of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:GPL-EXCEPT$
+** 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 General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3 as published by the Free Software
+** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
+** 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-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <QtTest/QtTest>
+
+#include <private/qflatmap_p.h>
+#include <qbytearray.h>
+#include <qstring.h>
+#include <qstringview.h>
+#include <qvarlengtharray.h>
+#include <qvector.h>
+
+#include <algorithm>
+#include <list>
+#include <tuple>
+
+class tst_QFlatMap : public QObject
+{
+    Q_OBJECT
+private slots:
+    void constructing();
+    void constAccess();
+    void insertion();
+    void removal();
+    void extraction();
+    void iterators();
+    void statefulComparator();
+    void transparency();
+    void viewIterators();
+    void varLengthArray();
+};
+
+void tst_QFlatMap::constructing()
+{
+    using Map = QFlatMap<int, QByteArray>;
+    Map fmDefault;
+    QVERIFY(fmDefault.isEmpty());
+    QCOMPARE(fmDefault.size(), Map::size_type(0));
+    QCOMPARE(fmDefault.size(), fmDefault.count());
+
+    auto key_compare = fmDefault.key_comp();
+    auto selfbuilt_value_compare
+            = [&key_compare](const Map::value_type &a, const Map::value_type &b)
+              {
+                  return key_compare(a.first, b.first);
+              };
+    auto value_compare = fmDefault.value_comp();
+
+    Map::key_container_type kv = { 6, 2, 1 };
+    Map::mapped_container_type mv = { "foo", "bar", "baz" };
+    Map fmCopy{kv, mv};
+    QCOMPARE(fmCopy.size(), Map::size_type(3));
+    QVERIFY(std::is_sorted(fmCopy.begin(), fmCopy.end(), selfbuilt_value_compare));
+    QVERIFY(std::is_sorted(fmCopy.begin(), fmCopy.end(), value_compare));
+
+    Map fmMove{
+        Map::key_container_type{ 6, 2, 1 },
+        Map::mapped_container_type{ "foo", "bar", "baz" }
+    };
+    QCOMPARE(fmMove.size(), Map::size_type(3));
+    QVERIFY(std::is_sorted(fmMove.begin(), fmMove.end(), value_compare));
+
+    auto fmInitList = Map{ { 1, 2 }, { "foo", "bar" } };
+    QVERIFY(std::is_sorted(fmInitList.begin(), fmInitList.end(), value_compare));
+
+    auto fmRange = Map(fmCopy.begin(), fmCopy.end());
+    QVERIFY(std::is_sorted(fmRange.begin(), fmRange.end(), value_compare));
+
+    kv.clear();
+    mv.clear();
+    std::vector<Map::value_type> sv;
+    for (auto it = fmRange.begin(); it != fmRange.end(); ++it) {
+        kv.push_back(it->first);
+        mv.push_back(it->second);
+        sv.push_back(*it);
+    }
+    auto fmFromSortedVectorCopy = Map(Qt::OrderedUniqueRange, kv, mv);
+    auto fmFromSortedVectorMove = Map(Qt::OrderedUniqueRange, Map::key_container_type(kv),
+                                      Map::mapped_container_type(mv));
+    auto fmFromSortedInitList = Map(Qt::OrderedUniqueRange, { { 1, "foo" }, { 2, "bar" } });
+    auto fmFromSortedRange = Map(Qt::OrderedUniqueRange, sv.begin(), sv.end());
+}
+
+void tst_QFlatMap::constAccess()
+{
+    using Map = QFlatMap<QByteArray, QByteArray>;
+    const Map m{ { { "foo", "FOO" }, { "bar", "BAR" } } };
+
+    const std::vector<Map::value_type> v{ { "foo", "FOO" }, { "bar", "BAR" } };
+
+    QCOMPARE(m.value("foo").data(), "FOO");
+    QCOMPARE(m.value("bar").data(), "BAR");
+    QCOMPARE(m.value("nix"), QByteArray());
+    QCOMPARE(m.value("nix", "NIX").data(), "NIX");
+    QCOMPARE(m["foo"].data(), "FOO");
+    QCOMPARE(m["bar"].data(), "BAR");
+    QCOMPARE(m["nix"], QByteArray());
+    QVERIFY(m.contains("foo"));
+    QVERIFY(!m.contains("nix"));
+}
+
+void tst_QFlatMap::insertion()
+{
+    using Map = QFlatMap<QByteArray, QByteArray>;
+    Map m;
+    QByteArray foo = "foo";
+    m[foo] = foo.toUpper();
+    m["bar"] = "BAR";
+    m["baz"] = "BAZ";
+    QVERIFY(m.insert("oof", "eek").second);
+    QVERIFY(!m.insert("oof", "OOF").second);
+    const std::vector<Map::value_type> container = { { "bla", "BLA" }, { "blubb", "BLUBB" } };
+    m.insert(container.begin(), container.end());
+    QCOMPARE(m.value("foo").data(), "FOO");
+    QCOMPARE(m.value("bar").data(), "BAR");
+    QCOMPARE(m.value("baz").data(), "BAZ");
+    QCOMPARE(m.value("oof").data(), "OOF");
+    QCOMPARE(m.value("bla").data(), "BLA");
+    QCOMPARE(m.value("blubb").data(), "BLUBB");
+
+    Map::value_type a1[] = { { "narf", "NARF" },
+                             { "zort", "ZORT" },
+                             { "troz", "TROZ" } };
+    Map::value_type a2[] = { { "gnampf", "GNAMPF" },
+                             { "narf", "NARFFFF" },
+                             { "narf", "NARFFFFF" },
+                             { "narf", "NARFFFFFF" } };
+    m.insert(std::begin(a1), std::end(a1));
+    m.insert(Qt::OrderedUniqueRange, std::begin(a2), std::end(a2));
+    QCOMPARE(m.size(), 10);
+    QCOMPARE(m.value("narf").data(), "NARFFFFFF");
+    QCOMPARE(m.value("gnampf").data(), "GNAMPF");
+}
+
+void tst_QFlatMap::extraction()
+{
+    using Map = QFlatMap<int, QByteArray>;
+    Map::key_container_type expectedKeys = { 1, 2, 3 };
+    Map::mapped_container_type expectedValues = { "een", "twee", "dree" };
+    Map m(expectedKeys, expectedValues);
+    auto keys = m.keys();
+    auto values = m.values();
+    QCOMPARE(keys, expectedKeys);
+    QCOMPARE(values, expectedValues);
+    Map::containers c = std::move(m).extract();
+    QCOMPARE(c.keys, expectedKeys);
+    QCOMPARE(c.values, expectedValues);
+}
+
+void tst_QFlatMap::iterators()
+{
+    using Map = QFlatMap<int, QByteArray>;
+    auto m = Map{ { 1, "foo" }, { 2, "bar" }, { 3, "baz" } };
+    {
+        // forward / backward
+        Map::iterator a = m.begin();
+        QVERIFY(a != m.end());
+        QCOMPARE(a.key(), 1);
+        QCOMPARE(a.value(), "foo");
+        ++a;
+        QCOMPARE(a.key(), 2);
+        QCOMPARE(a.value(), "bar");
+        Map::iterator b = a++;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz"));
+        QCOMPARE(std::tie(b.key(), b.value()), std::make_tuple(2, "bar"));
+        QCOMPARE(++a, m.end());
+        --a;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz"));
+        a.value() = "buzz";
+        b = a--;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar"));
+        QCOMPARE(std::tie(b.key(), b.value()), std::make_tuple(3, "buzz"));
+        b.value() = "baz";
+
+        // random access
+        a = m.begin();
+        a += 2;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz"));
+        a = m.begin() + 1;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar"));
+        a = 1 + m.begin();
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar"));
+        a = m.end() - 1;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz"));
+        b = m.end();
+        b -= 1;
+        QCOMPARE(std::tie(b.key(), b.value()), std::make_tuple(3, "baz"));
+        QCOMPARE(m.end() - m.begin(), m.size());
+
+        // comparison
+        a = m.begin() + m.size() - 1;
+        b = m.end() - 1;
+        QVERIFY(a == b);
+        a = m.begin();
+        b = m.end();
+        QVERIFY(a < b);
+        QVERIFY(a <= b);
+        QVERIFY(b > a);
+        QVERIFY(b >= a);
+        a = b;
+        QVERIFY(!(a < b));
+        QVERIFY(a <= b);
+        QVERIFY(!(b > a));
+        QVERIFY(b >= a);
+
+        // de-referencing
+        a = m.begin();
+        auto ref0 = *a;
+        QCOMPARE(ref0.first, 1);
+        QCOMPARE(ref0.second, "foo");
+        auto ref1 = a[1];
+        QCOMPARE(ref1.first, 2);
+        QCOMPARE(ref1.second, "bar");
+    }
+    {
+        // forward / backward
+        Map::const_iterator a = m.cbegin();
+        QVERIFY(a != m.cend());
+        QCOMPARE(a.key(), 1);
+        QCOMPARE(a.value(), "foo");
+        ++a;
+        QCOMPARE(a.key(), 2);
+        QCOMPARE(a.value(), "bar");
+        Map::const_iterator b = a++;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz"));
+        QCOMPARE(std::tie(b.key(), b.value()), std::make_tuple(2, "bar"));
+        QCOMPARE(++a, m.cend());
+        --a;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz"));
+        b = a--;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar"));
+
+        // random access
+        a = m.cbegin();
+        a += 2;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz"));
+        a = m.cbegin() + 1;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar"));
+        a = 1 + m.cbegin();
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar"));
+        a = m.cend() - 1;
+        QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz"));
+        b = m.cend();
+        b -= 1;
+        QCOMPARE(std::tie(b.key(), b.value()), std::make_tuple(3, "baz"));
+        QCOMPARE(m.cend() - m.cbegin(), m.size());
+
+        // comparison
+        a = m.cbegin() + m.size() - 1;
+        b = m.cend() - 1;
+        QVERIFY(a == b);
+        a = m.cbegin();
+        b = m.cend();
+        QVERIFY(a < b);
+        QVERIFY(a <= b);
+        QVERIFY(b > a);
+        QVERIFY(b >= a);
+        a = b;
+        QVERIFY(!(a < b));
+        QVERIFY(a <= b);
+        QVERIFY(!(b > a));
+        QVERIFY(b >= a);
+
+        // de-referencing
+        a = m.cbegin();
+        auto ref0 = *a;
+        QCOMPARE(ref0.first, 1);
+        QCOMPARE(ref0.second, "foo");
+        auto ref1 = a[1];
+        QCOMPARE(ref1.first, 2);
+        QCOMPARE(ref1.second, "bar");
+    }
+    {
+        Map::iterator it = m.begin();
+        Map::const_iterator cit = it;
+        Q_UNUSED(it);
+        Q_UNUSED(cit);
+    }
+    {
+        std::list<Map::value_type> revlst;
+        std::copy(m.begin(), m.end(), std::front_inserter(revlst));
+        std::vector<Map::value_type> v0;
+        std::copy(revlst.begin(), revlst.end(), std::back_inserter(v0));
+        std::vector<Map::value_type> v1;
+        std::copy(m.rbegin(), m.rend(), std::back_inserter(v1));
+        const Map cm = m;
+        std::vector<Map::value_type> v2;
+        std::copy(cm.rbegin(), cm.rend(), std::back_inserter(v2));
+        std::vector<Map::value_type> v3;
+        std::copy(m.crbegin(), m.crend(), std::back_inserter(v3));
+        QCOMPARE(v0, v1);
+        QCOMPARE(v1, v2);
+        QCOMPARE(v2, v3);
+    }
+}
+
+void tst_QFlatMap::removal()
+{
+    using Map = QFlatMap<int, QByteArray>;
+    Map m({ { 2, "bar" }, { 3, "baz" }, { 1, "foo" } });
+    QCOMPARE(m.value(2).data(), "bar");
+    QCOMPARE(m.take(2).data(), "bar");
+    QVERIFY(!m.contains(2));
+    QCOMPARE(m.size(), Map::size_type(2));
+    QVERIFY(m.remove(1));
+    QVERIFY(!m.contains(1));
+    QVERIFY(!m.remove(1));
+    QCOMPARE(m.size(), Map::size_type(1));
+    m.clear();
+    QVERIFY(m.isEmpty());
+    QVERIFY(m.empty());
+
+    m[1] = "een";
+    m[2] = "twee";
+    m[3] = "dree";
+    auto it = m.lower_bound(1);
+    QCOMPARE(it.key(), 1);
+    it = m.erase(it);
+    QCOMPARE(it.key(), 2);
+    QVERIFY(!m.contains(1));
+}
+
+void tst_QFlatMap::statefulComparator()
+{
+    struct CountingCompare {
+        mutable int count = 0;
+
+        bool operator()(const QString &lhs, const QString &rhs) const
+        {
+            ++count;
+            return lhs < rhs;
+        }
+    };
+
+    using Map = QFlatMap<QString, QString, CountingCompare>;
+    auto m1 = Map{ { "en", "een"}, { "to", "twee" }, { "tre", "dree" } };
+    QVERIFY(m1.key_comp().count > 0);
+    auto m2 = Map(m1.key_comp());
+    QCOMPARE(m2.key_comp().count, m1.key_comp().count);
+    m2.insert(m1.begin(), m1.end());
+    QVERIFY(m2.key_comp().count > m1.key_comp().count);
+}
+
+void tst_QFlatMap::transparency()
+{
+    struct StringViewCompare
+    {
+        using is_transparent = void;
+        bool operator()(const QStringView &lhs, const QStringView &rhs) const
+        {
+            return lhs < rhs;
+        }
+    };
+
+    using Map = QFlatMap<QString, QString, StringViewCompare>;
+    auto m = Map{ { "one", "een" }, { "two", "twee" }, { "three", "dree" } };
+
+    const QString numbers = "one two three";
+    const QStringView sv1{numbers.constData(), 3};
+    const QStringView sv2{numbers.constData() + 4, 3};
+    const QStringView sv3{numbers.constData() + 8, 5};
+    QCOMPARE(m.lower_bound(sv1).value(), "een");
+    QCOMPARE(m.lower_bound(sv2).value(), "twee");
+    QCOMPARE(m.lower_bound(sv3).value(), "dree");
+}
+
+void tst_QFlatMap::viewIterators()
+{
+    using Map = QFlatMap<QByteArray, QByteArray>;
+    Map m({ { "yksi", "een"}, { "kaksi", "twee" }, { "kolme", "dree" } });
+    {
+        std::vector<QByteArray> keys;
+        std::transform(m.begin(), m.end(), std::back_inserter(keys),
+                       [](const Map::value_type &v)
+                       {
+                           return v.first;
+                       });
+        auto it = keys.begin();
+        QCOMPARE(*it, "kaksi");
+        QCOMPARE(it->length(), 5);
+        ++it;
+        QCOMPARE(*it, "kolme");
+        it++;
+        QCOMPARE(*it, "yksi");
+        ++it;
+        QCOMPARE(it, keys.end());
+        --it;
+        QCOMPARE(*it, "yksi");
+        it--;
+        QCOMPARE(*it, "kolme");
+    }
+    {
+        std::vector<QByteArray> values;
+        std::transform(m.begin(), m.end(), std::back_inserter(values),
+                       [](const Map::value_type &v)
+                       {
+                           return v.second;
+                       });
+        auto it = values.begin();
+        QCOMPARE(*it, "twee");
+        QCOMPARE(it->length(), 4);
+        ++it;
+        QCOMPARE(*it, "dree");
+        it++;
+        QCOMPARE(*it, "een");
+        ++it;
+        QCOMPARE(it, values.end());
+        --it;
+        QCOMPARE(*it, "een");
+        it--;
+        QCOMPARE(*it, "dree");
+    }
+}
+
+void tst_QFlatMap::varLengthArray()
+{
+    using Map = QFlatMap<int, QByteArray, std::less<int>,
+                         QVarLengthArray<int, 1024>, QVarLengthArray<QByteArray, 1024>>;
+    Map m{ { 2, "twee" } };
+    m.insert(1, "een");
+    m.remove(1);
+    QVERIFY(!m.isEmpty());
+    m.remove(2);
+    QVERIFY(m.isEmpty());
+}
+
+QTEST_APPLESS_MAIN(tst_QFlatMap)
+#include "tst_qflatmap.moc"
diff --git a/tests/auto/corelib/tools/tools.pro b/tests/auto/corelib/tools/tools.pro
index 5a7c8478f1..be195ea037 100644
--- a/tests/auto/corelib/tools/tools.pro
+++ b/tests/auto/corelib/tools/tools.pro
@@ -11,6 +11,7 @@ SUBDIRS=\
     qcryptographichash \
     qeasingcurve \
     qexplicitlyshareddatapointer \
+    qflatmap \
     qfreelist \
     qhash \
     qhashfunctions \