diff options
Diffstat (limited to 'src/corelib/tools/qmap.h')
| -rw-r--r-- | src/corelib/tools/qmap.h | 2353 |
1 files changed, 1349 insertions, 1004 deletions
diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index f169ed5e49..7ee0be1e51 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -1,495 +1,569 @@ -/**************************************************************************** -** -** Copyright (C) 2016 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$ -** -****************************************************************************/ +// Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> +// Copyright (C) 2021 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 QMAP_H #define QMAP_H +#include <QtCore/qhashfunctions.h> #include <QtCore/qiterator.h> #include <QtCore/qlist.h> #include <QtCore/qrefcount.h> #include <QtCore/qpair.h> - -#ifdef Q_MAP_DEBUG -#include <QtCore/qdebug.h> -#endif +#include <QtCore/qshareddata.h> +#include <QtCore/qshareddata_impl.h> #include <functional> #include <initializer_list> #include <map> -#include <new> +#include <algorithm> QT_BEGIN_NAMESPACE -/* - QMap uses qMapLessThanKey() to compare keys. The default - implementation uses operator<(). For pointer types, - qMapLessThanKey() uses std::less (because operator<() on - pointers can be used only between pointers in the same array). -*/ - -template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2) +// common code shared between QMap and QMultimap +template <typename AMap> +class QMapData : public QSharedData { - return key1 < key2; -} +public: + using Map = AMap; + using Key = typename Map::key_type; + using T = typename Map::mapped_type; + using value_type = typename Map::value_type; + using size_type = typename Map::size_type; + using iterator = typename Map::iterator; + using const_iterator = typename Map::const_iterator; + + static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers."); + static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers."); + + Map m; + + QMapData() = default; + explicit QMapData(const Map &other) + : m(other) + {} + + explicit QMapData(Map &&other) + : m(std::move(other)) + {} + + // used in remove(); copies from source all the values not matching key. + // returns how many were NOT copied (removed). + size_type copyIfNotEquivalentTo(const Map &source, const Key &key) + { + Q_ASSERT(m.empty()); + + size_type result = 0; + const auto &keyCompare = source.key_comp(); + const auto filter = [&result, &key, &keyCompare](const auto &v) + { + if (!keyCompare(key, v.first) && !keyCompare(v.first, key)) { + // keys are equivalent (neither a<b nor b<a) => found it + ++result; + return true; + } + return false; + }; -template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2) -{ - return std::less<const Ptr *>()(key1, key2); -} + std::remove_copy_if(source.cbegin(), source.cend(), + std::inserter(m, m.end()), + filter); + return result; + } -struct QMapDataBase; -template <class Key, class T> struct QMapData; + // used in key(T), count(Key, T), find(key, T), etc; returns a + // comparator object suitable for algorithms with std::(multi)map + // iterators. + static auto valueIsEqualTo(const T &value) + { + return [&value](const auto &v) { return v.second == value; }; + } -struct Q_CORE_EXPORT QMapNodeBase -{ - quintptr p; - QMapNodeBase *left; - QMapNodeBase *right; - - enum Color { Red = 0, Black = 1 }; - enum { Mask = 3 }; // reserve the second bit as well - - const QMapNodeBase *nextNode() const; - QMapNodeBase *nextNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->nextNode()); } - const QMapNodeBase *previousNode() const; - QMapNodeBase *previousNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->previousNode()); } - - Color color() const { return Color(p & 1); } - void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; } - QMapNodeBase *parent() const { return reinterpret_cast<QMapNodeBase *>(p & ~Mask); } - void setParent(QMapNodeBase *pp) { p = (p & Mask) | quintptr(pp); } - - template <typename T> - static typename std::enable_if<QTypeInfo<T>::isComplex>::type - callDestructorIfNecessary(T &t) noexcept { Q_UNUSED(t); t.~T(); } // Q_UNUSED: silence MSVC unused 't' warning - template <typename T> - static typename std::enable_if<!QTypeInfo<T>::isComplex>::type - callDestructorIfNecessary(T &) noexcept {} -}; + Key key(const T &value, const Key &defaultKey) const + { + auto i = std::find_if(m.cbegin(), + m.cend(), + valueIsEqualTo(value)); + if (i != m.cend()) + return i->first; -template <class Key, class T> -struct QMapNode : public QMapNodeBase -{ - Key key; - T value; + return defaultKey; + } - inline QMapNode *leftNode() const { return static_cast<QMapNode *>(left); } - inline QMapNode *rightNode() const { return static_cast<QMapNode *>(right); } + QList<Key> keys() const + { + QList<Key> result; + result.reserve(m.size()); - inline const QMapNode *nextNode() const { return reinterpret_cast<const QMapNode *>(QMapNodeBase::nextNode()); } - inline const QMapNode *previousNode() const { return static_cast<const QMapNode *>(QMapNodeBase::previousNode()); } - inline QMapNode *nextNode() { return reinterpret_cast<QMapNode *>(QMapNodeBase::nextNode()); } - inline QMapNode *previousNode() { return static_cast<QMapNode *>(QMapNodeBase::previousNode()); } + const auto extractKey = [](const auto &v) { return v.first; }; - QMapNode<Key, T> *copy(QMapData<Key, T> *d) const; + std::transform(m.cbegin(), + m.cend(), + std::back_inserter(result), + extractKey); + return result; + } - void destroySubTree() + QList<Key> keys(const T &value) const { - callDestructorIfNecessary(key); - callDestructorIfNecessary(value); - doDestroySubTree(std::integral_constant<bool, QTypeInfo<T>::isComplex || QTypeInfo<Key>::isComplex>()); + QList<Key> result; + result.reserve(m.size()); + // no std::transform_if... + for (const auto &v : m) { + if (v.second == value) + result.append(v.first); + } + result.shrink_to_fit(); + return result; } - QMapNode<Key, T> *lowerBound(const Key &key); - QMapNode<Key, T> *upperBound(const Key &key); + QList<T> values() const + { + QList<T> result; + result.reserve(m.size()); -private: - void doDestroySubTree(std::false_type) {} - void doDestroySubTree(std::true_type) + const auto extractValue = [](const auto &v) { return v.second; }; + + std::transform(m.cbegin(), + m.cend(), + std::back_inserter(result), + extractValue); + return result; + } + + size_type count(const Key &key) const { - if (left) - leftNode()->destroySubTree(); - if (right) - rightNode()->destroySubTree(); + return m.count(key); } - QMapNode() = delete; - Q_DISABLE_COPY(QMapNode) -}; + // Used in erase. Allocates a new QMapData and copies, from this->m, + // the elements not in the [first, last) range. The return contains + // the new QMapData and an iterator in its map pointing at the first + // element after the erase. + struct EraseResult { + QMapData *data; + iterator it; + }; -template <class Key, class T> -inline QMapNode<Key, T> *QMapNode<Key, T>::lowerBound(const Key &akey) -{ - QMapNode<Key, T> *n = this; - QMapNode<Key, T> *lastNode = nullptr; - while (n) { - if (!qMapLessThanKey(n->key, akey)) { - lastNode = n; - n = n->leftNode(); - } else { - n = n->rightNode(); + EraseResult erase(const_iterator first, const_iterator last) const + { + EraseResult result; + result.data = new QMapData; + result.it = result.data->m.end(); + const auto newDataEnd = result.it; + + auto i = m.begin(); + const auto e = m.end(); + + // copy over all the elements before first + while (i != first) { + result.it = result.data->m.insert(newDataEnd, *i); + ++i; } + + // skip until last + while (i != last) + ++i; + + // copy from last to the end + while (i != e) { + result.data->m.insert(newDataEnd, *i); + ++i; + } + + if (result.it != newDataEnd) + ++result.it; + + return result; } - return lastNode; -} +}; + +// +// QMap +// template <class Key, class T> -inline QMapNode<Key, T> *QMapNode<Key, T>::upperBound(const Key &akey) +class QMap { - QMapNode<Key, T> *n = this; - QMapNode<Key, T> *lastNode = nullptr; - while (n) { - if (qMapLessThanKey(akey, n->key)) { - lastNode = n; - n = n->leftNode(); - } else { - n = n->rightNode(); - } - } - return lastNode; -} + using Map = std::map<Key, T>; + using MapData = QMapData<Map>; + QtPrivate::QExplicitlySharedDataPointerV2<MapData> d; + friend class QMultiMap<Key, T>; +public: + using key_type = Key; + using mapped_type = T; + using difference_type = qptrdiff; + using size_type = qsizetype; -struct Q_CORE_EXPORT QMapDataBase -{ - QtPrivate::RefCount ref; - int size; - QMapNodeBase header; - QMapNodeBase *mostLeftNode; + QMap() = default; - void rotateLeft(QMapNodeBase *x); - void rotateRight(QMapNodeBase *x); - void rebalance(QMapNodeBase *x); - void freeNodeAndRebalance(QMapNodeBase *z); - void recalcMostLeftNode(); + // implicitly generated special member functions are OK! - QMapNodeBase *createNode(int size, int alignment, QMapNodeBase *parent, bool left); - void freeTree(QMapNodeBase *root, int alignment); + void swap(QMap<Key, T> &other) noexcept + { + d.swap(other.d); + } - static const QMapDataBase shared_null; + QMap(std::initializer_list<std::pair<Key, T>> list) + { + for (auto &p : list) + insert(p.first, p.second); + } - static QMapDataBase *createData(); - static void freeData(QMapDataBase *d); -}; + explicit QMap(const std::map<Key, T> &other) + : d(other.empty() ? nullptr : new MapData(other)) + { + } -template <class Key, class T> -struct QMapData : public QMapDataBase -{ - typedef QMapNode<Key, T> Node; - - Node *root() const { return static_cast<Node *>(header.left); } - - // using reinterpret_cast because QMapDataBase::header is not - // actually a QMapNode. - const Node *end() const { return reinterpret_cast<const Node *>(&header); } - Node *end() { return reinterpret_cast<Node *>(&header); } - const Node *begin() const { if (root()) return static_cast<const Node*>(mostLeftNode); return end(); } - Node *begin() { if (root()) return static_cast<Node*>(mostLeftNode); return end(); } - - void deleteNode(Node *z); - Node *findNode(const Key &akey) const; - void nodeRange(const Key &akey, Node **firstNode, Node **lastNode); - - Node *createNode(const Key &k, const T &v, Node *parent = nullptr, bool left = false) - { - Node *n = static_cast<Node *>(QMapDataBase::createNode(sizeof(Node), alignof(Node), - parent, left)); - QT_TRY { - new (&n->key) Key(k); - QT_TRY { - new (&n->value) T(v); - } QT_CATCH(...) { - n->key.~Key(); - QT_RETHROW; - } - } QT_CATCH(...) { - QMapDataBase::freeNodeAndRebalance(n); - QT_RETHROW; - } - return n; + explicit QMap(std::map<Key, T> &&other) + : d(other.empty() ? nullptr : new MapData(std::move(other))) + { } - static QMapData *create() { - return static_cast<QMapData *>(createData()); + std::map<Key, T> toStdMap() const & + { + if (d) + return d->m; + return {}; } - void destroy() { - if (root()) { - root()->destroySubTree(); - freeTree(header.left, alignof(Node)); + std::map<Key, T> toStdMap() && + { + if (d) { + if (d.isShared()) + return d->m; + else + return std::move(d->m); } - freeData(this); + + return {}; } -}; -template <class Key, class T> -QMapNode<Key, T> *QMapNode<Key, T>::copy(QMapData<Key, T> *d) const -{ - QMapNode<Key, T> *n = d->createNode(key, value); - n->setColor(color()); - if (left) { - n->left = leftNode()->copy(d); - n->left->setParent(n); - } else { - n->left = nullptr; - } - if (right) { - n->right = rightNode()->copy(d); - n->right->setParent(n); - } else { - n->right = nullptr; - } - return n; -} +#ifndef Q_QDOC + template <typename AKey = Key, typename AT = T> friend + QTypeTraits::compare_eq_result_container<QMap, AKey, AT> operator==(const QMap &lhs, const QMap &rhs) + { + if (lhs.d == rhs.d) + return true; + if (!lhs.d) + return rhs == lhs; + Q_ASSERT(lhs.d); + return rhs.d ? (lhs.d->m == rhs.d->m) : lhs.d->m.empty(); + } -template <class Key, class T> -void QMapData<Key, T>::deleteNode(QMapNode<Key, T> *z) -{ - QMapNodeBase::callDestructorIfNecessary(z->key); - QMapNodeBase::callDestructorIfNecessary(z->value); - freeNodeAndRebalance(z); -} + template <typename AKey = Key, typename AT = T> friend + QTypeTraits::compare_eq_result_container<QMap, AKey, AT> operator!=(const QMap &lhs, const QMap &rhs) + { + return !(lhs == rhs); + } + // TODO: add the other comparison operators; std::map has them. +#else + friend bool operator==(const QMap &lhs, const QMap &rhs); + friend bool operator!=(const QMap &lhs, const QMap &rhs); +#endif // Q_QDOC -template <class Key, class T> -QMapNode<Key, T> *QMapData<Key, T>::findNode(const Key &akey) const -{ - if (Node *r = root()) { - Node *lb = r->lowerBound(akey); - if (lb && !qMapLessThanKey(akey, lb->key)) - return lb; + size_type size() const { return d ? size_type(d->m.size()) : size_type(0); } + + bool isEmpty() const { return d ? d->m.empty() : true; } + + void detach() + { + if (d) + d.detach(); + else + d.reset(new MapData); } - return nullptr; -} + bool isDetached() const noexcept + { + return d ? !d.isShared() : false; // false makes little sense, but that's shared_null's behavior... + } -template <class Key, class T> -void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **firstNode, QMapNode<Key, T> **lastNode) -{ - Node *n = root(); - Node *l = end(); - while (n) { - if (qMapLessThanKey(akey, n->key)) { - l = n; - n = n->leftNode(); - } else if (qMapLessThanKey(n->key, akey)) { - n = n->rightNode(); - } else { - *firstNode = n->leftNode() ? n->leftNode()->lowerBound(akey) : nullptr; - if (!*firstNode) - *firstNode = n; - *lastNode = n->rightNode() ? n->rightNode()->upperBound(akey) : nullptr; - if (!*lastNode) - *lastNode = l; + bool isSharedWith(const QMap<Key, T> &other) const noexcept + { + return d == other.d; // also this makes little sense? + } + + void clear() + { + if (!d) return; - } + + if (!d.isShared()) + d->m.clear(); + else + d.reset(); } - *firstNode = *lastNode = l; -} + size_type remove(const Key &key) + { + if (!d) + return 0; + + if (!d.isShared()) + return size_type(d->m.erase(key)); -template <class Key, class T> -class QMap -{ - typedef QMapNode<Key, T> Node; + MapData *newData = new MapData; + size_type result = newData->copyIfNotEquivalentTo(d->m, key); - QMapData<Key, T> *d; + d.reset(newData); -public: - inline QMap() noexcept : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { } - inline QMap(std::initializer_list<std::pair<Key,T> > list) - : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) + return result; + } + + template <typename Predicate> + size_type removeIf(Predicate pred) { - for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) - insert(it->first, it->second); + return QtPrivate::associative_erase_if(*this, pred); } - QMap(const QMap<Key, T> &other); - inline ~QMap() { if (!d->ref.deref()) d->destroy(); } + T take(const Key &key) + { + if (!d) + return T(); + + const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach + // TODO: improve. There is no need of copying all the + // elements (the one to be removed can be skipped). + detach(); + + auto i = d->m.find(key); + if (i != d->m.end()) { + T result(std::move(i->second)); + d->m.erase(i); + return result; + } + return T(); + } - QMap<Key, T> &operator=(const QMap<Key, T> &other); - inline QMap(QMap<Key, T> &&other) noexcept - : d(other.d) + bool contains(const Key &key) const { - other.d = static_cast<QMapData<Key, T> *>( - const_cast<QMapDataBase *>(&QMapDataBase::shared_null)); + if (!d) + return false; + auto i = d->m.find(key); + return i != d->m.end(); } - inline QMap<Key, T> &operator=(QMap<Key, T> &&other) noexcept - { QMap moved(std::move(other)); swap(moved); return *this; } - inline void swap(QMap<Key, T> &other) noexcept { qSwap(d, other.d); } - explicit QMap(const typename std::map<Key, T> &other); - std::map<Key, T> toStdMap() const; + Key key(const T &value, const Key &defaultKey = Key()) const + { + if (!d) + return defaultKey; - bool operator==(const QMap<Key, T> &other) const; - inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); } + return d->key(value, defaultKey); + } - inline int size() const { return d->size; } + T value(const Key &key, const T &defaultValue = T()) const + { + if (!d) + return defaultValue; + const auto i = d->m.find(key); + if (i != d->m.cend()) + return i->second; + return defaultValue; + } - inline bool isEmpty() const { return d->size == 0; } + T &operator[](const Key &key) + { + const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach + detach(); + auto i = d->m.find(key); + if (i == d->m.end()) + i = d->m.insert({key, T()}).first; + return i->second; + } - inline void detach() { if (d->ref.isShared()) detach_helper(); } - inline bool isDetached() const { return !d->ref.isShared(); } - inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; } + // CHANGE: return T, not const T! + T operator[](const Key &key) const + { + return value(key); + } - void clear(); + QList<Key> keys() const + { + if (!d) + return {}; + return d->keys(); + } - int remove(const Key &key); - T take(const Key &key); + QList<Key> keys(const T &value) const + { + if (!d) + return {}; + return d->keys(value); + } - bool contains(const Key &key) const; - const Key key(const T &value, const Key &defaultKey = Key()) const; - const T value(const Key &key, const T &defaultValue = T()) const; - T &operator[](const Key &key); - const T operator[](const Key &key) const; + QList<T> values() const + { + if (!d) + return {}; + return d->values(); + } - QList<Key> uniqueKeys() const; - QList<Key> keys() const; - QList<Key> keys(const T &value) const; - QList<T> values() const; - QList<T> values(const Key &key) const; - int count(const Key &key) const; + size_type count(const Key &key) const + { + if (!d) + return 0; + return d->count(key); + } + + size_type count() const + { + return size(); + } inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); } - inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (constEnd() - 1).key(); } + inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (--constEnd()).key(); } inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); } inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); } - inline T &last() { Q_ASSERT(!isEmpty()); return *(end() - 1); } - inline const T &last() const { Q_ASSERT(!isEmpty()); return *(constEnd() - 1); } + inline T &last() { Q_ASSERT(!isEmpty()); return *(--end()); } + inline const T &last() const { Q_ASSERT(!isEmpty()); return *(--constEnd()); } class const_iterator; class iterator { + friend class QMap<Key, T>; friend class const_iterator; - Node *i; + typename Map::iterator i; + explicit iterator(typename Map::iterator it) : i(it) {} public: - typedef std::bidirectional_iterator_tag iterator_category; - typedef qptrdiff difference_type; - typedef T value_type; - typedef T *pointer; - typedef T &reference; - - inline iterator() : i(nullptr) { } - inline iterator(Node *node) : i(node) { } - - inline const Key &key() const { return i->key; } - inline T &value() const { return i->value; } - inline T &operator*() const { return i->value; } - inline T *operator->() const { return &i->value; } - inline bool operator==(const iterator &o) const { return i == o.i; } - inline bool operator!=(const iterator &o) const { return i != o.i; } - - inline iterator &operator++() { - i = i->nextNode(); + using iterator_category = std::bidirectional_iterator_tag; + using difference_type = qptrdiff; + using value_type = T; + using pointer = T *; + using reference = T &; + + iterator() = default; + + const Key &key() const { return i->first; } + T &value() const { return i->second; } + T &operator*() const { return i->second; } + T *operator->() const { return &i->second; } + friend bool operator==(const iterator &lhs, const iterator &rhs) { return lhs.i == rhs.i; } + friend bool operator!=(const iterator &lhs, const iterator &rhs) { return lhs.i != rhs.i; } + + iterator &operator++() + { + ++i; return *this; } - inline iterator operator++(int) { + iterator operator++(int) + { iterator r = *this; - i = i->nextNode(); + ++i; return r; } - inline iterator &operator--() { - i = i->previousNode(); + iterator &operator--() + { + --i; return *this; } - inline iterator operator--(int) { + iterator operator--(int) + { iterator r = *this; - i = i->previousNode(); + --i; return r; } - inline iterator operator+(int j) const - { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline iterator operator-(int j) const { return operator+(-j); } - inline iterator &operator+=(int j) { return *this = *this + j; } - inline iterator &operator-=(int j) { return *this = *this - j; } - friend inline iterator operator+(int j, iterator k) { return k + j; } - - inline bool operator==(const const_iterator &o) const { return i == o.i; } - inline bool operator!=(const const_iterator &o) const { return i != o.i; } - friend class QMap<Key, T>; + +#if QT_DEPRECATED_SINCE(6, 0) + QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access") + //! [qmap-op-it-plus-step] + friend iterator operator+(iterator it, difference_type j) { return std::next(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access") + //! [qmap-op-it-minus-step] + friend iterator operator-(iterator it, difference_type j) { return std::prev(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMap iterators are not random access") + iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMap iterators are not random access") + iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; } + + QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access") + //! [qmap-op-step-plus-it] + friend iterator operator+(difference_type j, iterator it) { return std::next(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access") + //! [qmap-op-step-minus-it] + friend iterator operator-(difference_type j, iterator it) { return std::prev(it, j); } +#endif }; - friend class iterator; class const_iterator { - friend class iterator; - const Node *i; + friend class QMap<Key, T>; + typename Map::const_iterator i; + explicit const_iterator(typename Map::const_iterator it) : i(it) {} public: - typedef std::bidirectional_iterator_tag iterator_category; - typedef qptrdiff difference_type; - typedef T value_type; - typedef const T *pointer; - typedef const T &reference; - - Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { } - inline const_iterator(const Node *node) : i(node) { } - inline const_iterator(const iterator &o) { i = o.i; } - - inline const Key &key() const { return i->key; } - inline const T &value() const { return i->value; } - inline const T &operator*() const { return i->value; } - inline const T *operator->() const { return &i->value; } - Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; } - Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return i != o.i; } - - inline const_iterator &operator++() { - i = i->nextNode(); + using iterator_category = std::bidirectional_iterator_tag; + using difference_type = qptrdiff; + using value_type = T; + using pointer = const T *; + using reference = const T &; + + const_iterator() = default; + Q_IMPLICIT const_iterator(const iterator &o) : i(o.i) {} + + const Key &key() const { return i->first; } + const T &value() const { return i->second; } + const T &operator*() const { return i->second; } + const T *operator->() const { return &i->second; } + friend bool operator==(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i == rhs.i; } + friend bool operator!=(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i != rhs.i; } + + const_iterator &operator++() + { + ++i; return *this; } - inline const_iterator operator++(int) { + const_iterator operator++(int) + { const_iterator r = *this; - i = i->nextNode(); + ++i; return r; } - inline const_iterator &operator--() { - i = i->previousNode(); + const_iterator &operator--() + { + --i; return *this; } - inline const_iterator operator--(int) { + const_iterator operator--(int) + { const_iterator r = *this; - i = i->previousNode(); + --i; return r; } - inline const_iterator operator+(int j) const - { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline const_iterator operator-(int j) const { return operator+(-j); } - inline const_iterator &operator+=(int j) { return *this = *this + j; } - inline const_iterator &operator-=(int j) { return *this = *this - j; } - friend inline const_iterator operator+(int j, const_iterator k) { return k + j; } - friend class QMap<Key, T>; +#if QT_DEPRECATED_SINCE(6, 0) + QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access") + //! [qmap-op-it-plus-step-const] + friend const_iterator operator+(const_iterator it, difference_type j) { return std::next(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access") + //! [qmap-op-it-minus-step-const] + friend const_iterator operator-(const_iterator it, difference_type j) { return std::prev(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMap iterators are not random access") + const_iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMap iterators are not random access") + const_iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; } + + QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access") + //! [qmap-op-step-plus-it-const] + friend const_iterator operator+(difference_type j, const_iterator it) { return std::next(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access") + //! [qmap-op-step-minus-it-const] + friend const_iterator operator-(difference_type j, const_iterator it) { return std::prev(it, j); } +#endif }; - friend class const_iterator; class key_iterator { @@ -521,740 +595,1011 @@ public: typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator; // STL style - inline iterator begin() { detach(); return iterator(d->begin()); } - inline const_iterator begin() const { return const_iterator(d->begin()); } - inline const_iterator constBegin() const { return const_iterator(d->begin()); } - inline const_iterator cbegin() const { return const_iterator(d->begin()); } - inline iterator end() { detach(); return iterator(d->end()); } - inline const_iterator end() const { return const_iterator(d->end()); } - inline const_iterator constEnd() const { return const_iterator(d->end()); } - inline const_iterator cend() const { return const_iterator(d->end()); } - inline key_iterator keyBegin() const { return key_iterator(begin()); } - inline key_iterator keyEnd() const { return key_iterator(end()); } - inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); } - inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); } - inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); } - inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); } - inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); } - inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); } - iterator erase(iterator it); + iterator begin() { detach(); return iterator(d->m.begin()); } + const_iterator begin() const { if (!d) return const_iterator(); return const_iterator(d->m.cbegin()); } + const_iterator constBegin() const { return begin(); } + const_iterator cbegin() const { return begin(); } + iterator end() { detach(); return iterator(d->m.end()); } + const_iterator end() const { if (!d) return const_iterator(); return const_iterator(d->m.end()); } + const_iterator constEnd() const { return end(); } + const_iterator cend() const { return end(); } + key_iterator keyBegin() const { return key_iterator(begin()); } + key_iterator keyEnd() const { return key_iterator(end()); } + key_value_iterator keyValueBegin() { return key_value_iterator(begin()); } + key_value_iterator keyValueEnd() { return key_value_iterator(end()); } + const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); } + const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); } + const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); } + const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); } + auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); } + auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); } + auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); } + auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); } + + iterator erase(const_iterator it) + { + return erase(it, std::next(it)); + } + + iterator erase(const_iterator afirst, const_iterator alast) + { + if (!d) + return iterator(); + + if (!d.isShared()) + return iterator(d->m.erase(afirst.i, alast.i)); + + auto result = d->erase(afirst.i, alast.i); + d.reset(result.data); + return iterator(result.it); + } // more Qt typedef iterator Iterator; typedef const_iterator ConstIterator; - inline int count() const { return d->size; } - iterator find(const Key &key); - const_iterator find(const Key &key) const; - const_iterator constFind(const Key &key) const; - iterator lowerBound(const Key &key); - const_iterator lowerBound(const Key &key) const; - iterator upperBound(const Key &key); - const_iterator upperBound(const Key &key) const; - iterator insert(const Key &key, const T &value); - iterator insert(const_iterator pos, const Key &key, const T &value); - iterator insertMulti(const Key &key, const T &value); - iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue); - QMap<Key, T> &unite(const QMap<Key, T> &other); - // STL compatibility - typedef Key key_type; - typedef T mapped_type; - typedef qptrdiff difference_type; - typedef int size_type; - inline bool empty() const { return isEmpty(); } - QPair<iterator, iterator> equal_range(const Key &akey); - QPair<const_iterator, const_iterator> equal_range(const Key &akey) const; + iterator find(const Key &key) + { + const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach + detach(); + return iterator(d->m.find(key)); + } -#ifdef Q_MAP_DEBUG - void dump() const; -#endif + const_iterator find(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.find(key)); + } -private: - void detach_helper(); - bool isValidIterator(const const_iterator &ci) const - { -#if defined(QT_DEBUG) && !defined(Q_MAP_NO_ITERATOR_DEBUG) - const QMapNodeBase *n = ci.i; - while (n->parent()) - n = n->parent(); - return n->left == d->root(); + const_iterator constFind(const Key &key) const + { + return find(key); + } + + iterator lowerBound(const Key &key) + { + const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach + detach(); + return iterator(d->m.lower_bound(key)); + } + + const_iterator lowerBound(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.lower_bound(key)); + } + + iterator upperBound(const Key &key) + { + const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach + detach(); + return iterator(d->m.upper_bound(key)); + } + + const_iterator upperBound(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.upper_bound(key)); + } + + iterator insert(const Key &key, const T &value) + { + const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach + // TODO: improve. In case of assignment, why copying first? + detach(); + return iterator(d->m.insert_or_assign(key, value).first); + } + + iterator insert(const_iterator pos, const Key &key, const T &value) + { + // TODO: improve. In case of assignment, why copying first? + typename Map::const_iterator dpos; + const auto copy = d.isShared() ? *this : QMap(); // keep `key`/`value` alive across the detach + if (!d || d.isShared()) { + auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0; + detach(); + dpos = std::next(d->m.cbegin(), posDistance); + } else { + dpos = pos.i; + } + return iterator(d->m.insert_or_assign(dpos, key, value)); + } + + void insert(const QMap<Key, T> &map) + { + // TODO: improve. In case of assignment, why copying first? + if (map.isEmpty()) + return; + + detach(); + +#ifdef __cpp_lib_node_extract + auto copy = map.d->m; + copy.merge(std::move(d->m)); + d->m = std::move(copy); #else - Q_UNUSED(ci); - return true; + // this is a std::copy, but we can't use std::inserter (need insert_or_assign...). + // copy in reverse order, trying to make effective use of insertionHint. + auto insertionHint = d->m.end(); + auto mapIt = map.d->m.crbegin(); + auto end = map.d->m.crend(); + for (; mapIt != end; ++mapIt) + insertionHint = d->m.insert_or_assign(insertionHint, mapIt->first, mapIt->second); #endif } -}; -template <class Key, class T> -inline QMap<Key, T>::QMap(const QMap<Key, T> &other) -{ - if (other.d->ref.ref()) { - d = other.d; - } else { - d = QMapData<Key, T>::create(); - if (other.d->header.left) { - d->header.left = static_cast<Node *>(other.d->header.left)->copy(d); - d->header.left->setParent(&d->header); - d->recalcMostLeftNode(); + void insert(QMap<Key, T> &&map) + { + if (!map.d || map.d->m.empty()) + return; + + if (map.d.isShared()) { + // fall back to a regular copy + insert(map); + return; } + + detach(); + +#ifdef __cpp_lib_node_extract + map.d->m.merge(std::move(d->m)); + *this = std::move(map); +#else + // same as above + auto insertionHint = d->m.end(); + auto mapIt = map.d->m.crbegin(); + auto end = map.d->m.crend(); + for (; mapIt != end; ++mapIt) + insertionHint = d->m.insert_or_assign(insertionHint, std::move(mapIt->first), std::move(mapIt->second)); +#endif } -} -template <class Key, class T> -Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other) -{ - if (d != other.d) { - QMap<Key, T> tmp(other); - tmp.swap(*this); + // STL compatibility + inline bool empty() const + { + return isEmpty(); } - return *this; -} -template <class Key, class T> -Q_INLINE_TEMPLATE void QMap<Key, T>::clear() -{ - *this = QMap<Key, T>(); -} + std::pair<iterator, iterator> equal_range(const Key &akey) + { + const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach + detach(); + auto result = d->m.equal_range(akey); + return {iterator(result.first), iterator(result.second)}; + } -QT_WARNING_PUSH -QT_WARNING_DISABLE_CLANG("-Wreturn-stack-address") + std::pair<const_iterator, const_iterator> equal_range(const Key &akey) const + { + if (!d) + return {}; + auto result = d->m.equal_range(akey); + return {const_iterator(result.first), const_iterator(result.second)}; + } -template <class Key, class T> -Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const -{ - Node *n = d->findNode(akey); - return n ? n->value : adefaultValue; -} +private: +#ifdef Q_QDOC + friend size_t qHash(const QMap &key, size_t seed = 0); +#else +# if defined(Q_CC_GHS) || defined (Q_CC_MSVC) + // GHS and MSVC tries to intantiate qHash() for the noexcept running into a + // non-SFINAE'ed hard error... Create an artificial SFINAE context as a + // work-around: + template <typename M, std::enable_if_t<std::is_same_v<M, QMap>, bool> = true> + friend QtPrivate::QHashMultiReturnType<typename M::key_type, typename M::mapped_type> +# else + using M = QMap; + friend size_t +# endif + qHash(const M &key, size_t seed = 0) + noexcept(QHashPrivate::noexceptPairHash<typename M::key_type, typename M::mapped_type>()) + { + if (!key.d) + return seed; + // don't use qHashRange to avoid its compile-time overhead: + return std::accumulate(key.d->m.begin(), key.d->m.end(), seed, + QtPrivate::QHashCombine{}); + } +#endif // !Q_QDOC +}; -QT_WARNING_POP +Q_DECLARE_ASSOCIATIVE_ITERATOR(Map) +Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map) -template <class Key, class T> -Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const +template <typename Key, typename T, typename Predicate> +qsizetype erase_if(QMap<Key, T> &map, Predicate pred) { - return value(akey); + return QtPrivate::associative_erase_if(map, pred); } -template <class Key, class T> -Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey) -{ - detach(); - Node *n = d->findNode(akey); - if (!n) - return *insert(akey, T()); - return n->value; -} -template <class Key, class T> -Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const -{ - Node *firstNode; - Node *lastNode; - d->nodeRange(akey, &firstNode, &lastNode); - - const_iterator ci_first(firstNode); - const const_iterator ci_last(lastNode); - int cnt = 0; - while (ci_first != ci_last) { - ++cnt; - ++ci_first; - } - return cnt; -} +// +// QMultiMap +// template <class Key, class T> -Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const +class QMultiMap { - return d->findNode(akey) != nullptr; -} + using Map = std::multimap<Key, T>; + using MapData = QMapData<Map>; + QtPrivate::QExplicitlySharedDataPointerV2<MapData> d; -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey, const T &avalue) -{ - detach(); - Node *n = d->root(); - Node *y = d->end(); - Node *lastNode = nullptr; - bool left = true; - while (n) { - y = n; - if (!qMapLessThanKey(n->key, akey)) { - lastNode = n; - left = true; - n = n->leftNode(); - } else { - left = false; - n = n->rightNode(); - } +public: + using key_type = Key; + using mapped_type = T; + using difference_type = qptrdiff; + using size_type = qsizetype; + + QMultiMap() = default; + + // implicitly generated special member functions are OK! + + QMultiMap(std::initializer_list<std::pair<Key,T>> list) + { + for (auto &p : list) + insert(p.first, p.second); } - if (lastNode && !qMapLessThanKey(akey, lastNode->key)) { - lastNode->value = avalue; - return iterator(lastNode); + + void swap(QMultiMap<Key, T> &other) noexcept + { + d.swap(other.d); } - Node *z = d->createNode(akey, avalue, y, left); - return iterator(z); -} -template <class Key, class T> -typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &akey, const T &avalue) -{ - if (d->ref.isShared()) - return this->insert(akey, avalue); - - Q_ASSERT_X(isValidIterator(pos), "QMap::insert", "The specified const_iterator argument 'it' is invalid"); - - if (pos == constEnd()) { - // Hint is that the Node is larger than (or equal to) the largest value. - Node *n = static_cast<Node *>(pos.i->left); - if (n) { - while (n->right) - n = static_cast<Node *>(n->right); - - if (!qMapLessThanKey(n->key, akey)) - return this->insert(akey, avalue); // ignore hint - // This can be optimized by checking equal too. - // we can overwrite if previous node key is strictly smaller - // (or there is no previous node) - - Node *z = d->createNode(akey, avalue, n, false); // insert right most - return iterator(z); + explicit QMultiMap(const QMap<Key, T> &other) + : d(other.isEmpty() ? nullptr : new MapData) + { + if (d) { + Q_ASSERT(other.d); + d->m.insert(other.d->m.begin(), + other.d->m.end()); } - return this->insert(akey, avalue); - } else { - // Hint indicates that the node should be less (or equal to) the hint given - // but larger than the previous value. - Node *next = const_cast<Node*>(pos.i); - if (qMapLessThanKey(next->key, akey)) - return this->insert(akey, avalue); // ignore hint - - if (pos == constBegin()) { - // There is no previous value - // Maybe overwrite left most value - if (!qMapLessThanKey(akey, next->key)) { - next->value = avalue; // overwrite current iterator - return iterator(next); - } - // insert left most. - Node *z = d->createNode(akey, avalue, begin().i, true); - return iterator(z); - } else { - Node *prev = const_cast<Node*>(pos.i->previousNode()); - if (!qMapLessThanKey(prev->key, akey)) { - return this->insert(akey, avalue); // ignore hint - } - // Hint is ok - if (!qMapLessThanKey(akey, next->key)) { - next->value = avalue; // overwrite current iterator - return iterator(next); - } + } - // we need to insert (not overwrite) - if (prev->right == nullptr) { - Node *z = d->createNode(akey, avalue, prev, false); - return iterator(z); - } - if (next->left == nullptr) { - Node *z = d->createNode(akey, avalue, next, true); - return iterator(z); + explicit QMultiMap(QMap<Key, T> &&other) + : d(other.isEmpty() ? nullptr : new MapData) + { + if (d) { + Q_ASSERT(other.d); + if (other.d.isShared()) { + d->m.insert(other.d->m.begin(), + other.d->m.end()); + } else { +#ifdef __cpp_lib_node_extract + d->m.merge(std::move(other.d->m)); +#else + d->m.insert(std::make_move_iterator(other.d->m.begin()), + std::make_move_iterator(other.d->m.end())); +#endif } - Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr. - return this->insert(akey, avalue); } } -} -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey, - const T &avalue) -{ - detach(); - Node* y = d->end(); - Node* x = static_cast<Node *>(d->root()); - bool left = true; - while (x != nullptr) { - left = !qMapLessThanKey(x->key, akey); - y = x; - x = left ? x->leftNode() : x->rightNode(); - } - Node *z = d->createNode(akey, avalue, y, left); - return iterator(z); -} + explicit QMultiMap(const std::multimap<Key, T> &other) + : d(other.empty() ? nullptr : new MapData(other)) + { + } -template <class Key, class T> -typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &akey, const T &avalue) -{ - if (d->ref.isShared()) - return this->insertMulti(akey, avalue); - - Q_ASSERT_X(isValidIterator(pos), "QMap::insertMulti", "The specified const_iterator argument 'pos' is invalid"); - - if (pos == constEnd()) { - // Hint is that the Node is larger than (or equal to) the largest value. - Node *n = static_cast<Node *>(pos.i->left); - if (n) { - while (n->right) - n = static_cast<Node *>(n->right); - - if (!qMapLessThanKey(n->key, akey)) - return this->insertMulti(akey, avalue); // ignore hint - Node *z = d->createNode(akey, avalue, n, false); // insert right most - return iterator(z); + explicit QMultiMap(std::multimap<Key, T> &&other) + : d(other.empty() ? nullptr : new MapData(std::move(other))) + { + } + + // CHANGE: return type + Q_DECL_DEPRECATED_X("Use toStdMultiMap instead") + std::multimap<Key, T> toStdMap() const + { + return toStdMultiMap(); + } + + std::multimap<Key, T> toStdMultiMap() const & + { + if (d) + return d->m; + return {}; + } + + std::multimap<Key, T> toStdMultiMap() && + { + if (d) { + if (d.isShared()) + return d->m; + else + return std::move(d->m); } - return this->insertMulti(akey, avalue); - } else { - // Hint indicates that the node should be less (or equal to) the hint given - // but larger than the previous value. - Node *next = const_cast<Node*>(pos.i); - if (qMapLessThanKey(next->key, akey)) - return this->insertMulti(akey, avalue); // ignore hint - - if (pos == constBegin()) { - // There is no previous value (insert left most) - Node *z = d->createNode(akey, avalue, begin().i, true); - return iterator(z); - } else { - Node *prev = const_cast<Node*>(pos.i->previousNode()); - if (!qMapLessThanKey(prev->key, akey)) - return this->insertMulti(akey, avalue); // ignore hint - - // Hint is ok - do insert - if (prev->right == nullptr) { - Node *z = d->createNode(akey, avalue, prev, false); - return iterator(z); - } - if (next->left == nullptr) { - Node *z = d->createNode(akey, avalue, next, true); - return iterator(z); + + return {}; + } + +#ifndef Q_QDOC + template <typename AKey = Key, typename AT = T> friend + QTypeTraits::compare_eq_result_container<QMultiMap, AKey, AT> operator==(const QMultiMap &lhs, const QMultiMap &rhs) + { + if (lhs.d == rhs.d) + return true; + if (!lhs.d) + return rhs == lhs; + Q_ASSERT(lhs.d); + return rhs.d ? (lhs.d->m == rhs.d->m) : lhs.d->m.empty(); + } + + template <typename AKey = Key, typename AT = T> friend + QTypeTraits::compare_eq_result_container<QMultiMap, AKey, AT> operator!=(const QMultiMap &lhs, const QMultiMap &rhs) + { + return !(lhs == rhs); + } + // TODO: add the other comparison operators; std::multimap has them. +#else + friend bool operator==(const QMultiMap &lhs, const QMultiMap &rhs); + friend bool operator!=(const QMultiMap &lhs, const QMultiMap &rhs); +#endif // Q_QDOC + + size_type size() const { return d ? size_type(d->m.size()) : size_type(0); } + + bool isEmpty() const { return d ? d->m.empty() : true; } + + void detach() + { + if (d) + d.detach(); + else + d.reset(new MapData); + } + + bool isDetached() const noexcept + { + return d ? !d.isShared() : false; // false makes little sense, but that's shared_null's behavior... + } + + bool isSharedWith(const QMultiMap<Key, T> &other) const noexcept + { + return d == other.d; // also this makes little sense? + } + + void clear() + { + if (!d) + return; + + if (!d.isShared()) + d->m.clear(); + else + d.reset(); + } + + size_type remove(const Key &key) + { + if (!d) + return 0; + + if (!d.isShared()) + return size_type(d->m.erase(key)); + + MapData *newData = new MapData; + size_type result = newData->copyIfNotEquivalentTo(d->m, key); + + d.reset(newData); + + return result; + } + + size_type remove(const Key &key, const T &value) + { + if (!d) + return 0; + + // key and value may belong to this map. As such, we need to copy + // them to ensure they stay valid throughout the iteration below + // (which may destroy them) + const Key keyCopy = key; + const T valueCopy = value; + + // TODO: improve. Copy over only the elements not to be removed. + detach(); + + size_type result = 0; + const auto &keyCompare = d->m.key_comp(); + + auto i = d->m.find(keyCopy); + const auto e = d->m.end(); + + while (i != e && !keyCompare(keyCopy, i->first)) { + if (i->second == valueCopy) { + i = d->m.erase(i); + ++result; + } else { + ++i; } - Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr. - return this->insertMulti(akey, avalue); } + + return result; } -} + template <typename Predicate> + size_type removeIf(Predicate pred) + { + return QtPrivate::associative_erase_if(*this, pred); + } -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const -{ - Node *n = d->findNode(akey); - return const_iterator(n ? n : d->end()); -} + T take(const Key &key) + { + if (!d) + return T(); -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const -{ - return constFind(akey); -} + const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key` alive across the detach -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey) -{ - detach(); - Node *n = d->findNode(akey); - return iterator(n ? n : d->end()); -} + // TODO: improve. There is no need of copying all the + // elements (the one to be removed can be skipped). + detach(); -template <class Key, class T> -Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other) -{ - QMap<Key, T> copy(other); - const_iterator it = copy.constEnd(); - const const_iterator b = copy.constBegin(); - while (it != b) { - --it; - insertMulti(it.key(), it.value()); - } - return *this; -} + auto i = d->m.find(key); + if (i != d->m.end()) { + T result(std::move(i->second)); + d->m.erase(i); + return result; + } + return T(); + } -template <class Key, class T> -QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey) -{ - detach(); - Node *firstNode, *lastNode; - d->nodeRange(akey, &firstNode, &lastNode); - return QPair<iterator, iterator>(iterator(firstNode), iterator(lastNode)); -} + bool contains(const Key &key) const + { + if (!d) + return false; + auto i = d->m.find(key); + return i != d->m.end(); + } -template <class Key, class T> -QPair<typename QMap<Key, T>::const_iterator, typename QMap<Key, T>::const_iterator> -QMap<Key, T>::equal_range(const Key &akey) const -{ - Node *firstNode, *lastNode; - d->nodeRange(akey, &firstNode, &lastNode); - return qMakePair(const_iterator(firstNode), const_iterator(lastNode)); -} + bool contains(const Key &key, const T &value) const + { + return find(key, value) != end(); + } -#ifdef Q_MAP_DEBUG -template <class Key, class T> -void QMap<Key, T>::dump() const -{ - const_iterator it = begin(); - qDebug("map dump:"); - while (it != end()) { - const QMapNodeBase *n = it.i; - int depth = 0; - while (n && n != d->root()) { - ++depth; - n = n->parent(); - } - QByteArray space(4*depth, ' '); - qDebug() << space << (it.i->color() == Node::Red ? "Red " : "Black") << it.i << it.i->left << it.i->right - << it.key() << it.value(); - ++it; + Key key(const T &value, const Key &defaultKey = Key()) const + { + if (!d) + return defaultKey; + + return d->key(value, defaultKey); } - qDebug("---------"); -} -#endif -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey) -{ - detach(); - int n = 0; - while (Node *node = d->findNode(akey)) { - d->deleteNode(node); - ++n; + T value(const Key &key, const T &defaultValue = T()) const + { + if (!d) + return defaultValue; + const auto i = d->m.find(key); + if (i != d->m.cend()) + return i->second; + return defaultValue; } - return n; -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey) -{ - detach(); + QList<Key> keys() const + { + if (!d) + return {}; + return d->keys(); + } - Node *node = d->findNode(akey); - if (node) { - T t = std::move(node->value); - d->deleteNode(node); - return t; + QList<Key> keys(const T &value) const + { + if (!d) + return {}; + return d->keys(value); } - return T(); -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it) -{ - if (it == iterator(d->end())) - return it; + QList<Key> uniqueKeys() const + { + QList<Key> result; + if (!d) + return result; + + result.reserve(size()); + + std::unique_copy(keyBegin(), keyEnd(), + std::back_inserter(result)); + + result.shrink_to_fit(); + return result; + } + + QList<T> values() const + { + if (!d) + return {}; + return d->values(); + } + + QList<T> values(const Key &key) const + { + QList<T> result; + const auto range = equal_range(key); + result.reserve(std::distance(range.first, range.second)); + std::copy(range.first, range.second, std::back_inserter(result)); + return result; + } + + size_type count(const Key &key) const + { + if (!d) + return 0; + return d->count(key); + } - Q_ASSERT_X(isValidIterator(const_iterator(it)), "QMap::erase", "The specified iterator argument 'it' is invalid"); + size_type count(const Key &key, const T &value) const + { + if (!d) + return 0; + + // TODO: improve; no need of scanning the equal_range twice. + auto range = d->m.equal_range(key); + + return size_type(std::count_if(range.first, + range.second, + MapData::valueIsEqualTo(value))); + } + + inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); } + inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return std::next(constEnd(), -1).key(); } - if (d->ref.isShared()) { - const_iterator oldBegin = constBegin(); - const_iterator old = const_iterator(it); - int backStepsWithSameKey = 0; + inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); } + inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); } + inline T &last() { Q_ASSERT(!isEmpty()); return *std::next(end(), -1); } + inline const T &last() const { Q_ASSERT(!isEmpty()); return *std::next(constEnd(), -1); } + + class const_iterator; - while (old != oldBegin) { - --old; - if (qMapLessThanKey(old.key(), it.key())) - break; - ++backStepsWithSameKey; + class iterator + { + friend class QMultiMap<Key, T>; + friend class const_iterator; + + typename Map::iterator i; + explicit iterator(typename Map::iterator it) : i(it) {} + public: + using iterator_category = std::bidirectional_iterator_tag; + using difference_type = qptrdiff; + using value_type = T; + using pointer = T *; + using reference = T &; + + iterator() = default; + + const Key &key() const { return i->first; } + T &value() const { return i->second; } + T &operator*() const { return i->second; } + T *operator->() const { return &i->second; } + friend bool operator==(const iterator &lhs, const iterator &rhs) { return lhs.i == rhs.i; } + friend bool operator!=(const iterator &lhs, const iterator &rhs) { return lhs.i != rhs.i; } + + 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; } - it = find(old.key()); // ensures detach - Q_ASSERT_X(it != iterator(d->end()), "QMap::erase", "Unable to locate same key in erase after detach."); +#if QT_DEPRECATED_SINCE(6, 0) + QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access") + //! [qmultimap-op-it-plus-step] + friend iterator operator+(iterator it, difference_type j) { return std::next(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access") + //! [qmultimap-op-it-minus-step] + friend iterator operator-(iterator it, difference_type j) { return std::prev(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMultiMap iterators are not random access") + iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMultiMap iterators are not random access") + iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; } - while (backStepsWithSameKey > 0) { - ++it; - --backStepsWithSameKey; + QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access") + //! [qmultimap-op-step-plus-it] + friend iterator operator+(difference_type j, iterator it) { return std::next(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access") + //! [qmultimap-op-step-minus-it] + friend iterator operator-(difference_type j, iterator it) { return std::prev(it, j); } +#endif + }; + + class const_iterator + { + friend class QMultiMap<Key, T>; + typename Map::const_iterator i; + explicit const_iterator(typename Map::const_iterator it) : i(it) {} + + public: + using iterator_category = std::bidirectional_iterator_tag; + using difference_type = qptrdiff; + using value_type = T; + using pointer = const T *; + using reference = const T &; + + const_iterator() = default; + Q_IMPLICIT const_iterator(const iterator &o) : i(o.i) {} + + const Key &key() const { return i->first; } + const T &value() const { return i->second; } + const T &operator*() const { return i->second; } + const T *operator->() const { return &i->second; } + friend bool operator==(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i == rhs.i; } + friend bool operator!=(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i != rhs.i; } + + 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; } + +#if QT_DEPRECATED_SINCE(6, 0) + QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access") + //! [qmultimap-op-it-plus-step-const] + friend const_iterator operator+(const_iterator it, difference_type j) { return std::next(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access") + //! [qmultimap-op-it-minus-step-const] + friend const_iterator operator-(const_iterator it, difference_type j) { return std::prev(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMultiMap iterators are not random access") + const_iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMultiMap iterators are not random access") + const_iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; } + + QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access") + //! [qmultimap-op-step-plus-it-const] + friend const_iterator operator+(difference_type j, const_iterator it) { return std::next(it, j); } + + QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access") + //! [qmultimap-op-step-minus-it-const] + friend const_iterator operator-(difference_type j, const_iterator it) { return std::prev(it, j); } +#endif + }; + + class key_iterator + { + const_iterator i; + + public: + typedef typename const_iterator::iterator_category iterator_category; + typedef typename const_iterator::difference_type difference_type; + typedef Key value_type; + typedef const Key *pointer; + typedef const Key &reference; + + key_iterator() = default; + explicit key_iterator(const_iterator o) : i(o) { } + + const Key &operator*() const { return i.key(); } + const Key *operator->() const { return &i.key(); } + bool operator==(key_iterator o) const { return i == o.i; } + bool operator!=(key_iterator o) const { return i != o.i; } + + inline key_iterator &operator++() { ++i; return *this; } + inline key_iterator operator++(int) { return key_iterator(i++);} + inline key_iterator &operator--() { --i; return *this; } + inline key_iterator operator--(int) { return key_iterator(i--); } + const_iterator base() const { return i; } + }; + + typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator; + typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator; + + // STL style + iterator begin() { detach(); return iterator(d->m.begin()); } + const_iterator begin() const { if (!d) return const_iterator(); return const_iterator(d->m.cbegin()); } + const_iterator constBegin() const { return begin(); } + const_iterator cbegin() const { return begin(); } + iterator end() { detach(); return iterator(d->m.end()); } + const_iterator end() const { if (!d) return const_iterator(); return const_iterator(d->m.end()); } + const_iterator constEnd() const { return end(); } + const_iterator cend() const { return end(); } + key_iterator keyBegin() const { return key_iterator(begin()); } + key_iterator keyEnd() const { return key_iterator(end()); } + key_value_iterator keyValueBegin() { return key_value_iterator(begin()); } + key_value_iterator keyValueEnd() { return key_value_iterator(end()); } + const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); } + const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); } + const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); } + const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); } + auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); } + auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); } + auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); } + auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); } + + iterator erase(const_iterator it) + { + return erase(it, std::next(it)); } - Node *n = it.i; - ++it; - d->deleteNode(n); - return it; -} + iterator erase(const_iterator afirst, const_iterator alast) + { + if (!d) + return iterator(); -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper() -{ - QMapData<Key, T> *x = QMapData<Key, T>::create(); - if (d->header.left) { - x->header.left = static_cast<Node *>(d->header.left)->copy(x); - x->header.left->setParent(&x->header); - } - if (!d->ref.deref()) - d->destroy(); - d = x; - d->recalcMostLeftNode(); -} + if (!d.isShared()) + return iterator(d->m.erase(afirst.i, alast.i)); -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const -{ - QList<Key> res; - res.reserve(size()); // May be too much, but assume short lifetime - const_iterator i = begin(); - if (i != end()) { - for (;;) { - const Key &aKey = i.key(); - res.append(aKey); - do { - if (++i == end()) - goto break_out_of_outer_loop; - } while (!qMapLessThanKey(aKey, i.key())); // loop while (key == i.key()) - } + auto result = d->erase(afirst.i, alast.i); + d.reset(result.data); + return iterator(result.it); } -break_out_of_outer_loop: - return res; -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const -{ - QList<Key> res; - res.reserve(size()); - const_iterator i = begin(); - while (i != end()) { - res.append(i.key()); - ++i; - } - return res; -} + // more Qt + typedef iterator Iterator; + typedef const_iterator ConstIterator; -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const -{ - QList<Key> res; - const_iterator i = begin(); - while (i != end()) { - if (i.value() == avalue) - res.append(i.key()); - ++i; - } - return res; -} + size_type count() const + { + return size(); + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const -{ - const_iterator i = begin(); - while (i != end()) { - if (i.value() == avalue) - return i.key(); - ++i; + iterator find(const Key &key) + { + const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key` alive across the detach + detach(); + return iterator(d->m.find(key)); } - return defaultKey; -} + const_iterator find(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.find(key)); + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const -{ - QList<T> res; - res.reserve(size()); - const_iterator i = begin(); - while (i != end()) { - res.append(i.value()); - ++i; - } - return res; -} + const_iterator constFind(const Key &key) const + { + return find(key); + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const -{ - QList<T> res; - Node *n = d->findNode(akey); - if (n) { - const_iterator it(n); - do { - res.append(*it); - ++it; - } while (it != constEnd() && !qMapLessThanKey<Key>(akey, it.key())); - } - return res; -} + iterator find(const Key &key, const T &value) + { + const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key`/`value` alive across the detach -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &akey) const -{ - Node *lb = d->root() ? d->root()->lowerBound(akey) : nullptr; - if (!lb) - lb = d->end(); - return const_iterator(lb); -} + detach(); -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey) -{ - detach(); - Node *lb = d->root() ? d->root()->lowerBound(akey) : nullptr; - if (!lb) - lb = d->end(); - return iterator(lb); -} + auto range = d->m.equal_range(key); + auto i = std::find_if(range.first, range.second, + MapData::valueIsEqualTo(value)); -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator -QMap<Key, T>::upperBound(const Key &akey) const -{ - Node *ub = d->root() ? d->root()->upperBound(akey) : nullptr; - if (!ub) - ub = d->end(); - return const_iterator(ub); -} + if (i != range.second) + return iterator(i); + return iterator(d->m.end()); + } -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey) -{ - detach(); - Node *ub = d->root() ? d->root()->upperBound(akey) : nullptr; - if (!ub) - ub = d->end(); - return iterator(ub); -} + const_iterator find(const Key &key, const T &value) const + { + if (!d) + return const_iterator(); -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const -{ - if (size() != other.size()) - return false; - if (d == other.d) - return true; + auto range = d->m.equal_range(key); + auto i = std::find_if(range.first, range.second, + MapData::valueIsEqualTo(value)); - const_iterator it1 = begin(); - const_iterator it2 = other.begin(); + if (i != range.second) + return const_iterator(i); + return const_iterator(d->m.end()); + } - while (it1 != end()) { - if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key())) - return false; - ++it2; - ++it1; + const_iterator constFind(const Key &key, const T &value) const + { + return find(key, value); } - return true; -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other) -{ - d = QMapData<Key, T>::create(); - typename std::map<Key,T>::const_iterator it = other.end(); - while (it != other.begin()) { - --it; - d->createNode((*it).first, (*it).second, d->begin(), true); // insert on most left node. + iterator lowerBound(const Key &key) + { + const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key` alive across the detach + detach(); + return iterator(d->m.lower_bound(key)); } -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const -{ - std::map<Key, T> map; - const_iterator it = end(); - while (it != begin()) { - --it; - map.insert(map.begin(), std::pair<Key, T>(it.key(), it.value())); + const_iterator lowerBound(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.lower_bound(key)); } - return map; -} -template <class Key, class T> -class QMultiMap : public QMap<Key, T> -{ -public: - QMultiMap() noexcept {} - inline QMultiMap(std::initializer_list<std::pair<Key,T> > list) - { - for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) - insert(it->first, it->second); - } - QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {} - QMultiMap(QMap<Key, T> &&other) noexcept : QMap<Key, T>(std::move(other)) {} - void swap(QMultiMap<Key, T> &other) noexcept { QMap<Key, T>::swap(other); } - - inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value) - { return QMap<Key, T>::insert(key, value); } - inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value) - { return QMap<Key, T>::insertMulti(key, value); } - inline typename QMap<Key, T>::iterator insert(typename QMap<Key, T>::const_iterator pos, const Key &key, const T &value) - { return QMap<Key, T>::insertMulti(pos, key, value); } - - inline QMultiMap &operator+=(const QMultiMap &other) - { this->unite(other); return *this; } - inline QMultiMap operator+(const QMultiMap &other) const - { QMultiMap result = *this; result += other; return result; } - - using QMap<Key, T>::contains; - using QMap<Key, T>::remove; - using QMap<Key, T>::count; - using QMap<Key, T>::find; - using QMap<Key, T>::constFind; - - bool contains(const Key &key, const T &value) const; - - int remove(const Key &key, const T &value); - - int count(const Key &key, const T &value) const; - - typename QMap<Key, T>::iterator find(const Key &key, const T &value) { - typename QMap<Key, T>::iterator i(find(key)); - typename QMap<Key, T>::iterator end(this->end()); - while (i != end && !qMapLessThanKey<Key>(key, i.key())) { - if (i.value() == value) - return i; - ++i; + iterator upperBound(const Key &key) + { + const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key` alive across the detach + detach(); + return iterator(d->m.upper_bound(key)); + } + + const_iterator upperBound(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.upper_bound(key)); + } + + iterator insert(const Key &key, const T &value) + { + const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key`/`value` alive across the detach + detach(); + // note that std::multimap inserts at the end of an equal_range for a key, + // QMultiMap at the beginning. + auto i = d->m.lower_bound(key); + return iterator(d->m.insert(i, {key, value})); + } + + iterator insert(const_iterator pos, const Key &key, const T &value) + { + const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key`/`value` alive across the detach + typename Map::const_iterator dpos; + if (!d || d.isShared()) { + auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0; + detach(); + dpos = std::next(d->m.cbegin(), posDistance); + } else { + dpos = pos.i; } - return end; - } - typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const { - typename QMap<Key, T>::const_iterator i(constFind(key)); - typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd()); - while (i != end && !qMapLessThanKey<Key>(key, i.key())) { - if (i.value() == value) - return i; - ++i; + return iterator(d->m.insert(dpos, {key, value})); + } + +#if QT_DEPRECATED_SINCE(6, 0) + QT_DEPRECATED_VERSION_X_6_0("Use insert() instead") + iterator insertMulti(const Key &key, const T &value) + { + return insert(key, value); + } + QT_DEPRECATED_VERSION_X_6_0("Use insert() instead") + iterator insertMulti(const_iterator pos, const Key &key, const T &value) + { + return insert(pos, key, value); + } + + QT_DEPRECATED_VERSION_X_6_0("Use unite() instead") + void insert(const QMultiMap<Key, T> &map) + { + unite(map); + } + + QT_DEPRECATED_VERSION_X_6_0("Use unite() instead") + void insert(QMultiMap<Key, T> &&map) + { + unite(std::move(map)); + } +#endif + + iterator replace(const Key &key, const T &value) + { + const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key`/`value` alive across the detach + + // TODO: improve. No need of copying and then overwriting. + detach(); + + // Similarly, improve here (e.g. lower_bound and hinted insert); + // there's no insert_or_assign on multimaps + auto i = d->m.find(key); + if (i != d->m.end()) + i->second = value; + else + i = d->m.insert({key, value}); + + return iterator(i); + } + + // STL compatibility + inline bool empty() const { return isEmpty(); } + + std::pair<iterator, iterator> equal_range(const Key &akey) + { + const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key` alive across the detach + detach(); + auto result = d->m.equal_range(akey); + return {iterator(result.first), iterator(result.second)}; + } + + std::pair<const_iterator, const_iterator> equal_range(const Key &akey) const + { + if (!d) + return {}; + auto result = d->m.equal_range(akey); + return {const_iterator(result.first), const_iterator(result.second)}; + } + + QMultiMap &unite(const QMultiMap &other) + { + if (other.isEmpty()) + return *this; + + detach(); + + auto copy = other.d->m; +#ifdef __cpp_lib_node_extract + copy.merge(std::move(d->m)); +#else + copy.insert(std::make_move_iterator(d->m.begin()), + std::make_move_iterator(d->m.end())); +#endif + d->m = std::move(copy); + return *this; + } + + QMultiMap &unite(QMultiMap<Key, T> &&other) + { + if (!other.d || other.d->m.empty()) + return *this; + + if (other.d.isShared()) { + // fall back to a regular copy + unite(other); + return *this; } - return end; + + detach(); + +#ifdef __cpp_lib_node_extract + other.d->m.merge(std::move(d->m)); +#else + other.d->m.insert(std::make_move_iterator(d->m.begin()), + std::make_move_iterator(d->m.end())); +#endif + *this = std::move(other); + return *this; } - typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const - { return find(key, value); } -private: - T &operator[](const Key &key); - const T operator[](const Key &key) const; }; -template <class Key, class T> -Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const +Q_DECLARE_ASSOCIATIVE_ITERATOR(MultiMap) +Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(MultiMap) + +template <typename Key, typename T> +QMultiMap<Key, T> operator+(const QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs) { - return constFind(key, value) != QMap<Key, T>::constEnd(); + auto result = lhs; + result += rhs; + return result; } -template <class Key, class T> -Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value) +template <typename Key, typename T> +QMultiMap<Key, T> operator+=(QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs) { - int n = 0; - typename QMap<Key, T>::iterator i(find(key)); - typename QMap<Key, T>::iterator end(QMap<Key, T>::end()); - while (i != end && !qMapLessThanKey<Key>(key, i.key())) { - if (i.value() == value) { - i = this->erase(i); - ++n; - } else { - ++i; - } - } - return n; + return lhs.unite(rhs); } -template <class Key, class T> -Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const +template <typename Key, typename T, typename Predicate> +qsizetype erase_if(QMultiMap<Key, T> &map, Predicate pred) { - int n = 0; - typename QMap<Key, T>::const_iterator i(constFind(key)); - typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd()); - while (i != end && !qMapLessThanKey<Key>(key, i.key())) { - if (i.value() == value) - ++n; - ++i; - } - return n; + return QtPrivate::associative_erase_if(map, pred); } -Q_DECLARE_ASSOCIATIVE_ITERATOR(Map) -Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map) - QT_END_NAMESPACE #endif // QMAP_H |