diff options
Diffstat (limited to 'src/corelib/tools/qmap.h')
-rw-r--r-- | src/corelib/tools/qmap.h | 375 |
1 files changed, 239 insertions, 136 deletions
diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index 18c681581f..281812b5e6 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -380,12 +380,15 @@ public: T &operator[](const Key &key); const T operator[](const Key &key) const; - 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; +#if QT_DEPRECATED_SINCE(5, 15) + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") QList<Key> uniqueKeys() const; + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") QList<T> values(const Key &key) const; + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") int count(const Key &key) const; +#endif + inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); } inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (constEnd() - 1).key(); } @@ -452,6 +455,7 @@ public: { return i != o.i; } #endif friend class QMap<Key, T>; + friend class QMultiMap<Key, T>; }; friend class iterator; @@ -514,6 +518,7 @@ public: inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); } #endif friend class QMap<Key, T>; + friend class QMultiMap<Key, T>; }; friend class const_iterator; @@ -578,9 +583,12 @@ public: 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); + void insert(const QMap<Key, T> &map); +#if QT_DEPRECATED_SINCE(5, 15) + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") iterator insertMulti(const Key &key, const T &value); + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue); + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") QMap<Key, T> &unite(const QMap<Key, T> &other); +#endif // STL compatibility typedef Key key_type; @@ -609,6 +617,8 @@ private: return true; #endif } + + friend class QMultiMap<Key, T>; }; template <class Key, class T> @@ -671,23 +681,6 @@ Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey) } 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; -} - -template <class Key, class T> Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const { return d->findNode(akey) != nullptr; @@ -789,70 +782,44 @@ typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const K } template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey, - const T &avalue) +Q_INLINE_TEMPLATE void QMap<Key, T>::insert(const QMap<Key, T> &map) { - 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); -} + if (d == map.d) + return; -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); + detach(); - 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); + Node *n = d->root(); + auto it = map.cbegin(); + const auto e = map.cend(); + while (it != e) { + // Insertion here is based on insert(Key, T) + auto parent = d->end(); + bool left = true; + Node *lastNode = nullptr; + while (n) { + parent = n; + if (!qMapLessThanKey(n->key, it.key())) { + lastNode = n; + n = n->leftNode(); + left = true; + } else { + n = n->rightNode(); + left = false; + } } - 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); + if (lastNode && !qMapLessThanKey(it.key(), lastNode->key)) { + lastNode->value = it.value(); + n = lastNode; } 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); - } - Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr. - return this->insertMulti(akey, avalue); + n = d->createNode(it.key(), it.value(), parent, left); + } + ++it; + if (it != e) { + // Move back up the tree until we find the next branch or node which is + // relevant for the next key. + while (n != d->root() && qMapLessThanKey(n->key, it.key())) + n = static_cast<Node *>(n->parent()); } } } @@ -880,19 +847,6 @@ Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key & } 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; -} - -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(); @@ -1008,26 +962,6 @@ Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper() } 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()) - } - } -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; @@ -1080,21 +1014,6 @@ Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const } 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; -} - -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; @@ -1190,15 +1109,20 @@ public: QMultiMap(QMap<Key, T> &&other) noexcept : QMap<Key, T>(std::move(other)) {} void swap(QMultiMap<Key, T> &other) noexcept { QMap<Key, T>::swap(other); } + QList<Key> uniqueKeys() const; + QList<T> values(const Key &key) const; + + using typename QMap<Key, T>::iterator; + using typename QMap<Key, T>::const_iterator; + 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); } + iterator insert(const Key &key, const T &value); + iterator insert(const_iterator pos, const Key &key, const T &value); + QMultiMap &unite(const QMultiMap &other); inline QMultiMap &operator+=(const QMultiMap &other) - { this->unite(other); return *this; } + { return unite(other); } inline QMultiMap operator+(const QMultiMap &other) const { QMultiMap result = *this; result += other; return result; } @@ -1207,11 +1131,18 @@ public: using QMap<Key, T>::count; using QMap<Key, T>::find; using QMap<Key, T>::constFind; + using QMap<Key, T>::values; + using QMap<Key, T>::size; + using QMap<Key, T>::detach; + using QMap<Key, T>::erase; + using QMap<Key, T>::isValidIterator; + using typename QMap<Key, T>::Node; bool contains(const Key &key, const T &value) const; int remove(const Key &key, const T &value); + int count(const Key &key) const; int count(const Key &key, const T &value) const; typename QMap<Key, T>::iterator find(const Key &key, const T &value) { @@ -1242,6 +1173,123 @@ private: }; template <class Key, class T> +Q_OUTOFLINE_TEMPLATE QList<Key> QMultiMap<Key, T>::uniqueKeys() const +{ + QList<Key> res; + res.reserve(size()); // May be too much, but assume short lifetime + const_iterator i = this->begin(); + if (i != this->end()) { + for (;;) { + const Key &aKey = i.key(); + res.append(aKey); + do { + if (++i == this->end()) + goto break_out_of_outer_loop; + } while (!qMapLessThanKey(aKey, i.key())); // loop while (key == i.key()) + } + } +break_out_of_outer_loop: + return res; +} + +template <class Key, class T> +Q_OUTOFLINE_TEMPLATE QList<T> QMultiMap<Key, T>::values(const Key &akey) const +{ + QList<T> res; + Node *n = this->d->findNode(akey); + if (n) { + const_iterator it(n); + do { + res.append(*it); + ++it; + } while (it != this->constEnd() && !qMapLessThanKey<Key>(akey, it.key())); + } + return res; +} + +template <class Key, class T> +Q_INLINE_TEMPLATE typename QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &akey, + const T &avalue) +{ + detach(); + Node* y = this->d->end(); + Node* x = static_cast<Node *>(this->d->root()); + bool left = true; + while (x != nullptr) { + left = !qMapLessThanKey(x->key, akey); + y = x; + x = left ? x->leftNode() : x->rightNode(); + } + Node *z = this->d->createNode(akey, avalue, y, left); + return iterator(z); +} + +template <class Key, class T> +typename QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const_iterator pos, const Key &akey, const T &avalue) +{ + if (this->d->ref.isShared()) + return insert(akey, avalue); + + Q_ASSERT_X(isValidIterator(pos), "QMap::insert", "The specified const_iterator argument 'pos' is invalid"); + + if (pos == this->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 insert(akey, avalue); // ignore hint + Node *z = this->d->createNode(akey, avalue, n, false); // insert right most + return iterator(z); + } + return 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 insert(akey, avalue); // ignore hint + + if (pos == this->constBegin()) { + // There is no previous value (insert left most) + Node *z = this->d->createNode(akey, avalue, this->begin().i, true); + return iterator(z); + } else { + Node *prev = const_cast<Node*>(pos.i->previousNode()); + if (!qMapLessThanKey(prev->key, akey)) + return insert(akey, avalue); // ignore hint + + // Hint is ok - do insert + if (prev->right == nullptr) { + Node *z = this->d->createNode(akey, avalue, prev, false); + return iterator(z); + } + if (next->left == nullptr) { + Node *z = this->d->createNode(akey, avalue, next, true); + return iterator(z); + } + Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr. + return insert(akey, avalue); + } + } +} + +template <class Key, class T> +Q_INLINE_TEMPLATE QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other) +{ + QMultiMap<Key, T> copy(other); + const_iterator it = copy.constEnd(); + const const_iterator b = copy.constBegin(); + while (it != b) { + --it; + insert(it.key(), it.value()); + } + return *this; +} + +template <class Key, class T> Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const { return constFind(key, value) != QMap<Key, T>::constEnd(); @@ -1255,7 +1303,7 @@ Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value) 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); + i = erase(i); ++n; } else { ++i; @@ -1265,6 +1313,23 @@ Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value) } template <class Key, class T> +Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &akey) const +{ + QMultiMap::Node *firstNode; + QMultiMap::Node *lastNode; + this->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; +} + +template <class Key, class T> Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const { int n = 0; @@ -1278,6 +1343,44 @@ Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) c return n; } +#if QT_DEPRECATED_SINCE(5, 15) +template<class Key, class T> +QList<Key> QMap<Key, T>::uniqueKeys() const +{ + return static_cast<const QMultiMap<Key, T> *>(this)->uniqueKeys(); +} + +template<class Key, class T> +QList<T> QMap<Key, T>::values(const Key &key) const +{ + return static_cast<const QMultiMap<Key, T> *>(this)->values(key); +} + +template<class Key, class T> +int QMap<Key, T>::count(const Key &key) const +{ + return static_cast<const QMultiMap<Key, T> *>(this)->count(key); +} + +template<class Key, class T> +typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value) +{ + return static_cast<QMultiMap<Key, T> *>(this)->insert(key, value); +} + +template<class Key, class T> +typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &akey, const T &avalue) +{ + return static_cast<QMultiMap<Key, T> *>(this)->insert(pos, akey, avalue); +} + +template<class Key, class T> +QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other) +{ + return static_cast<QMultiMap<Key, T> *>(this)->unite(other); +} +#endif + Q_DECLARE_ASSOCIATIVE_ITERATOR(Map) Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map) |