diff options
Diffstat (limited to 'src/corelib/tools/qmap.h')
-rw-r--r-- | src/corelib/tools/qmap.h | 67 |
1 files changed, 67 insertions, 0 deletions
diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index 280696c534..31a891b0c2 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -538,6 +538,7 @@ public: 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); QMap<Key, T> &unite(const QMap<Key, T> &other); @@ -663,6 +664,72 @@ Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key } 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); + + 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); + } + 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 == 0) { + Node *z = d->createNode(akey, avalue, prev, false); + return iterator(z); + } + if (next->left == 0) { + Node *z = d->createNode(akey, avalue, next, true); + return iterator(z); + } + Q_ASSERT(false); // We should have prev->right == 0 or next->left == 0. + 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) { |