From 4ec6748c6a30f74e6d8fbb90fc118b306d1fa690 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?M=C3=A5rten=20Nordheim?= Date: Tue, 26 Nov 2019 16:08:38 +0100 Subject: QMap: deprecate insertMulti, unite and friends insertMulti and unite will silently transform a QMap into a multi-map which is not behavior we want to keep around anymore and as such is being deprecated. QMap functions that only make sense in a multi-map scenario are also deprecated and the implementation is moved to QMultiMap where it makes sense. Use QMultiMap if multiple keys are desired and insert(const QMap &) if a non multi-map-converting unite is desired. [ChangeLog][QtCore][QMap] insertMulti(), unite(), values(Key), uniqueKeys(), count(Key) is now deprecated. Please use QMultiMap instead. Task-number: QTBUG-35544 Change-Id: I158c938ceefb5aaba0e6e7513b2c26a64d29d521 Reviewed-by: Qt CI Bot Reviewed-by: Lars Knoll --- src/corelib/tools/qmap.h | 351 +++++++++++++++++++++++++++-------------------- 1 file changed, 205 insertions(+), 146 deletions(-) (limited to 'src/corelib/tools/qmap.h') diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index fa736e8413..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 uniqueKeys() const; QList keys() const; QList keys(const T &value) const; QList values() const; - QList 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 uniqueKeys() const; + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") QList 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; + friend class QMultiMap; }; friend class iterator; @@ -514,6 +518,7 @@ public: inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); } #endif friend class QMap; + friend class QMultiMap; }; friend class const_iterator; @@ -579,9 +584,11 @@ public: iterator insert(const Key &key, const T &value); iterator insert(const_iterator pos, const Key &key, const T &value); void insert(const QMap &map); - iterator insertMulti(const Key &key, const T &value); - iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue); - QMap &unite(const QMap &other); +#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 &unite(const QMap &other); +#endif // STL compatibility typedef Key key_type; @@ -610,6 +617,8 @@ private: return true; #endif } + + friend class QMultiMap; }; template @@ -671,23 +680,6 @@ Q_INLINE_TEMPLATE T &QMap::operator[](const Key &akey) return n->value; } -template -Q_INLINE_TEMPLATE int QMap::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 Q_INLINE_TEMPLATE bool QMap::contains(const Key &akey) const { @@ -832,75 +824,6 @@ Q_INLINE_TEMPLATE void QMap::insert(const QMap &map) } } -template -Q_INLINE_TEMPLATE typename QMap::iterator QMap::insertMulti(const Key &akey, - const T &avalue) -{ - detach(); - Node* y = d->end(); - Node* x = static_cast(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); -} - -template -typename QMap::iterator QMap::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(pos.i->left); - if (n) { - while (n->right) - n = static_cast(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); - } - 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(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(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); - } - } -} - template Q_INLINE_TEMPLATE typename QMap::const_iterator QMap::constFind(const Key &akey) const @@ -923,19 +846,6 @@ Q_INLINE_TEMPLATE typename QMap::iterator QMap::find(const Key & return iterator(n ? n : d->end()); } -template -Q_INLINE_TEMPLATE QMap &QMap::unite(const QMap &other) -{ - QMap 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 QPair::iterator, typename QMap::iterator> QMap::equal_range(const Key &akey) { @@ -1051,26 +961,6 @@ Q_OUTOFLINE_TEMPLATE void QMap::detach_helper() d->recalcMostLeftNode(); } -template -Q_OUTOFLINE_TEMPLATE QList QMap::uniqueKeys() const -{ - QList 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 Q_OUTOFLINE_TEMPLATE QList QMap::keys() const { @@ -1123,21 +1013,6 @@ Q_OUTOFLINE_TEMPLATE QList QMap::values() const return res; } -template -Q_OUTOFLINE_TEMPLATE QList QMap::values(const Key &akey) const -{ - QList res; - Node *n = d->findNode(akey); - if (n) { - const_iterator it(n); - do { - res.append(*it); - ++it; - } while (it != constEnd() && !qMapLessThanKey(akey, it.key())); - } - return res; -} - template Q_INLINE_TEMPLATE typename QMap::const_iterator QMap::lowerBound(const Key &akey) const { @@ -1234,15 +1109,20 @@ public: QMultiMap(QMap &&other) noexcept : QMap(std::move(other)) {} void swap(QMultiMap &other) noexcept { QMap::swap(other); } + QList uniqueKeys() const; + QList values(const Key &key) const; + + using typename QMap::iterator; + using typename QMap::const_iterator; + inline typename QMap::iterator replace(const Key &key, const T &value) { return QMap::insert(key, value); } - inline typename QMap::iterator insert(const Key &key, const T &value) - { return QMap::insertMulti(key, value); } - inline typename QMap::iterator insert(typename QMap::const_iterator pos, const Key &key, const T &value) - { return QMap::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; } @@ -1251,11 +1131,18 @@ public: using QMap::count; using QMap::find; using QMap::constFind; + using QMap::values; + using QMap::size; + using QMap::detach; + using QMap::erase; + using QMap::isValidIterator; + using typename QMap::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::iterator find(const Key &key, const T &value) { @@ -1285,6 +1172,123 @@ private: const T operator[](const Key &key) const; }; +template +Q_OUTOFLINE_TEMPLATE QList QMultiMap::uniqueKeys() const +{ + QList 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 +Q_OUTOFLINE_TEMPLATE QList QMultiMap::values(const Key &akey) const +{ + QList res; + Node *n = this->d->findNode(akey); + if (n) { + const_iterator it(n); + do { + res.append(*it); + ++it; + } while (it != this->constEnd() && !qMapLessThanKey(akey, it.key())); + } + return res; +} + +template +Q_INLINE_TEMPLATE typename QMultiMap::iterator QMultiMap::insert(const Key &akey, + const T &avalue) +{ + detach(); + Node* y = this->d->end(); + Node* x = static_cast(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 +typename QMultiMap::iterator QMultiMap::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(pos.i->left); + if (n) { + while (n->right) + n = static_cast(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(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(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 +Q_INLINE_TEMPLATE QMultiMap &QMultiMap::unite(const QMultiMap &other) +{ + QMultiMap 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 Q_INLINE_TEMPLATE bool QMultiMap::contains(const Key &key, const T &value) const { @@ -1299,7 +1303,7 @@ Q_INLINE_TEMPLATE int QMultiMap::remove(const Key &key, const T &value) typename QMap::iterator end(QMap::end()); while (i != end && !qMapLessThanKey(key, i.key())) { if (i.value() == value) { - i = this->erase(i); + i = erase(i); ++n; } else { ++i; @@ -1308,6 +1312,23 @@ Q_INLINE_TEMPLATE int QMultiMap::remove(const Key &key, const T &value) return n; } +template +Q_INLINE_TEMPLATE int QMultiMap::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 Q_INLINE_TEMPLATE int QMultiMap::count(const Key &key, const T &value) const { @@ -1322,6 +1343,44 @@ Q_INLINE_TEMPLATE int QMultiMap::count(const Key &key, const T &value) c return n; } +#if QT_DEPRECATED_SINCE(5, 15) +template +QList QMap::uniqueKeys() const +{ + return static_cast *>(this)->uniqueKeys(); +} + +template +QList QMap::values(const Key &key) const +{ + return static_cast *>(this)->values(key); +} + +template +int QMap::count(const Key &key) const +{ + return static_cast *>(this)->count(key); +} + +template +typename QMap::iterator QMap::insertMulti(const Key &key, const T &value) +{ + return static_cast *>(this)->insert(key, value); +} + +template +typename QMap::iterator QMap::insertMulti(const_iterator pos, const Key &akey, const T &avalue) +{ + return static_cast *>(this)->insert(pos, akey, avalue); +} + +template +QMap &QMap::unite(const QMap &other) +{ + return static_cast *>(this)->unite(other); +} +#endif + Q_DECLARE_ASSOCIATIVE_ITERATOR(Map) Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map) -- cgit v1.2.3