summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qmap.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib/tools/qmap.h')
-rw-r--r--src/corelib/tools/qmap.h142
1 files changed, 139 insertions, 3 deletions
diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h
index b0ec6fb3c6..449fcbca0a 100644
--- a/src/corelib/tools/qmap.h
+++ b/src/corelib/tools/qmap.h
@@ -54,7 +54,9 @@
#include <map>
#include <new>
-QT_BEGIN_HEADER
+#ifdef Q_COMPILER_INITIALIZER_LISTS
+#include <initializer_list>
+#endif
QT_BEGIN_NAMESPACE
@@ -327,6 +329,14 @@ class QMap
public:
inline QMap() : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { }
+#ifdef Q_COMPILER_INITIALIZER_LISTS
+ inline QMap(std::initializer_list<std::pair<Key,T> > list)
+ : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null)))
+ {
+ for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
+ insert(it->first, it->second);
+ }
+#endif
QMap(const QMap<Key, T> &other);
inline ~QMap() { if (!d->ref.deref()) d->destroy(); }
@@ -528,7 +538,9 @@ 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);
+ iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue);
QMap<Key, T> &unite(const QMap<Key, T> &other);
// STL compatibility
@@ -653,6 +665,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)
{
@@ -670,6 +748,57 @@ Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(cons
}
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);
+
+ 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);
+ }
+ 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 == 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->insertMulti(akey, avalue);
+ }
+ }
+}
+
+
+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);
@@ -960,6 +1089,13 @@ class QMultiMap : public QMap<Key, T>
{
public:
QMultiMap() {}
+#ifdef Q_COMPILER_INITIALIZER_LISTS
+ 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);
+ }
+#endif
QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
inline void swap(QMultiMap<Key, T> &other) { QMap<Key, T>::swap(other); }
@@ -967,6 +1103,8 @@ public:
{ 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; }
@@ -1072,6 +1210,4 @@ Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
QT_END_NAMESPACE
-QT_END_HEADER
-
#endif // QMAP_H
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-02 23:33:56 +0000