diff options
Diffstat (limited to 'src/corelib/tools/qmap.cpp')
-rw-r--r-- | src/corelib/tools/qmap.cpp | 2140 |
1 files changed, 0 insertions, 2140 deletions
diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp deleted file mode 100644 index 279dacda0b..0000000000 --- a/src/corelib/tools/qmap.cpp +++ /dev/null @@ -1,2140 +0,0 @@ -/**************************************************************************** -** -** 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$ -** -****************************************************************************/ - -#include "qmap.h" - -#include <stdlib.h> - -#ifdef QT_QMAP_DEBUG -# include <qstring.h> -# include <qlist.h> -#endif - -QT_BEGIN_NAMESPACE - -const QMapDataBase QMapDataBase::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, { 0, nullptr, nullptr }, nullptr }; - -const QMapNodeBase *QMapNodeBase::nextNode() const -{ - const QMapNodeBase *n = this; - if (n->right) { - n = n->right; - while (n->left) - n = n->left; - } else { - const QMapNodeBase *y = n->parent(); - while (y && n == y->right) { - n = y; - y = n->parent(); - } - n = y; - } - return n; -} - -const QMapNodeBase *QMapNodeBase::previousNode() const -{ - const QMapNodeBase *n = this; - if (n->left) { - n = n->left; - while (n->right) - n = n->right; - } else { - const QMapNodeBase *y = n->parent(); - while (y && n == y->left) { - n = y; - y = n->parent(); - } - n = y; - } - return n; -} - - -void QMapDataBase::rotateLeft(QMapNodeBase *x) -{ - QMapNodeBase *&root = header.left; - QMapNodeBase *y = x->right; - x->right = y->left; - if (y->left != nullptr) - y->left->setParent(x); - y->setParent(x->parent()); - if (x == root) - root = y; - else if (x == x->parent()->left) - x->parent()->left = y; - else - x->parent()->right = y; - y->left = x; - x->setParent(y); -} - - -void QMapDataBase::rotateRight(QMapNodeBase *x) -{ - QMapNodeBase *&root = header.left; - QMapNodeBase *y = x->left; - x->left = y->right; - if (y->right != nullptr) - y->right->setParent(x); - y->setParent(x->parent()); - if (x == root) - root = y; - else if (x == x->parent()->right) - x->parent()->right = y; - else - x->parent()->left = y; - y->right = x; - x->setParent(y); -} - - -void QMapDataBase::rebalance(QMapNodeBase *x) -{ - QMapNodeBase *&root = header.left; - x->setColor(QMapNodeBase::Red); - while (x != root && x->parent()->color() == QMapNodeBase::Red) { - if (x->parent() == x->parent()->parent()->left) { - QMapNodeBase *y = x->parent()->parent()->right; - if (y && y->color() == QMapNodeBase::Red) { - x->parent()->setColor(QMapNodeBase::Black); - y->setColor(QMapNodeBase::Black); - x->parent()->parent()->setColor(QMapNodeBase::Red); - x = x->parent()->parent(); - } else { - if (x == x->parent()->right) { - x = x->parent(); - rotateLeft(x); - } - x->parent()->setColor(QMapNodeBase::Black); - x->parent()->parent()->setColor(QMapNodeBase::Red); - rotateRight (x->parent()->parent()); - } - } else { - QMapNodeBase *y = x->parent()->parent()->left; - if (y && y->color() == QMapNodeBase::Red) { - x->parent()->setColor(QMapNodeBase::Black); - y->setColor(QMapNodeBase::Black); - x->parent()->parent()->setColor(QMapNodeBase::Red); - x = x->parent()->parent(); - } else { - if (x == x->parent()->left) { - x = x->parent(); - rotateRight(x); - } - x->parent()->setColor(QMapNodeBase::Black); - x->parent()->parent()->setColor(QMapNodeBase::Red); - rotateLeft(x->parent()->parent()); - } - } - } - root->setColor(QMapNodeBase::Black); -} - -void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z) -{ - QMapNodeBase *&root = header.left; - QMapNodeBase *y = z; - QMapNodeBase *x; - QMapNodeBase *x_parent; - if (y->left == nullptr) { - x = y->right; - if (y == mostLeftNode) { - if (x) - mostLeftNode = x; // It cannot have (left) children due the red black invariant. - else - mostLeftNode = y->parent(); - } - } else { - if (y->right == nullptr) { - x = y->left; - } else { - y = y->right; - while (y->left != nullptr) - y = y->left; - x = y->right; - } - } - if (y != z) { - z->left->setParent(y); - y->left = z->left; - if (y != z->right) { - x_parent = y->parent(); - if (x) - x->setParent(y->parent()); - y->parent()->left = x; - y->right = z->right; - z->right->setParent(y); - } else { - x_parent = y; - } - if (root == z) - root = y; - else if (z->parent()->left == z) - z->parent()->left = y; - else - z->parent()->right = y; - y->setParent(z->parent()); - // Swap the colors - QMapNodeBase::Color c = y->color(); - y->setColor(z->color()); - z->setColor(c); - y = z; - } else { - x_parent = y->parent(); - if (x) - x->setParent(y->parent()); - if (root == z) - root = x; - else if (z->parent()->left == z) - z->parent()->left = x; - else - z->parent()->right = x; - } - if (y->color() != QMapNodeBase::Red) { - while (x != root && (x == nullptr || x->color() == QMapNodeBase::Black)) { - if (x == x_parent->left) { - QMapNodeBase *w = x_parent->right; - if (w->color() == QMapNodeBase::Red) { - w->setColor(QMapNodeBase::Black); - x_parent->setColor(QMapNodeBase::Red); - rotateLeft(x_parent); - w = x_parent->right; - } - if ((w->left == nullptr || w->left->color() == QMapNodeBase::Black) && - (w->right == nullptr || w->right->color() == QMapNodeBase::Black)) { - w->setColor(QMapNodeBase::Red); - x = x_parent; - x_parent = x_parent->parent(); - } else { - if (w->right == nullptr || w->right->color() == QMapNodeBase::Black) { - if (w->left) - w->left->setColor(QMapNodeBase::Black); - w->setColor(QMapNodeBase::Red); - rotateRight(w); - w = x_parent->right; - } - w->setColor(x_parent->color()); - x_parent->setColor(QMapNodeBase::Black); - if (w->right) - w->right->setColor(QMapNodeBase::Black); - rotateLeft(x_parent); - break; - } - } else { - QMapNodeBase *w = x_parent->left; - if (w->color() == QMapNodeBase::Red) { - w->setColor(QMapNodeBase::Black); - x_parent->setColor(QMapNodeBase::Red); - rotateRight(x_parent); - w = x_parent->left; - } - if ((w->right == nullptr || w->right->color() == QMapNodeBase::Black) && - (w->left == nullptr|| w->left->color() == QMapNodeBase::Black)) { - w->setColor(QMapNodeBase::Red); - x = x_parent; - x_parent = x_parent->parent(); - } else { - if (w->left == nullptr || w->left->color() == QMapNodeBase::Black) { - if (w->right) - w->right->setColor(QMapNodeBase::Black); - w->setColor(QMapNodeBase::Red); - rotateLeft(w); - w = x_parent->left; - } - w->setColor(x_parent->color()); - x_parent->setColor(QMapNodeBase::Black); - if (w->left) - w->left->setColor(QMapNodeBase::Black); - rotateRight(x_parent); - break; - } - } - } - if (x) - x->setColor(QMapNodeBase::Black); - } - free(y); - --size; -} - -void QMapDataBase::recalcMostLeftNode() -{ - mostLeftNode = &header; - while (mostLeftNode->left) - mostLeftNode = mostLeftNode->left; -} - -static inline size_t qMapAlignmentThreshold() -{ - // malloc on 32-bit platforms should return pointers that are 8-byte - // aligned or more while on 64-bit platforms they should be 16-byte aligned - // or more - return 2 * sizeof(void*); -} - -static inline void *qMapAllocate(size_t alloc, size_t alignment) -{ - return alignment > qMapAlignmentThreshold() - ? qMallocAligned(alloc, alignment) - : ::malloc(alloc); -} - -static inline void qMapDeallocate(QMapNodeBase *node, size_t alignment) -{ - if (alignment > qMapAlignmentThreshold()) - qFreeAligned(node); - else - ::free(node); -} - -QMapNodeBase *QMapDataBase::createNode(size_t alloc, size_t alignment, QMapNodeBase *parent, bool left) -{ - QMapNodeBase *node = static_cast<QMapNodeBase *>(qMapAllocate(alloc, alignment)); - Q_CHECK_PTR(node); - - memset(node, 0, alloc); - ++size; - - if (parent) { - if (left) { - parent->left = node; - if (parent == mostLeftNode) - mostLeftNode = node; - } else { - parent->right = node; - } - node->setParent(parent); - rebalance(node); - } - return node; -} - -void QMapDataBase::freeTree(QMapNodeBase *root, size_t alignment) -{ - if (root->left) - freeTree(root->left, alignment); - if (root->right) - freeTree(root->right, alignment); - qMapDeallocate(root, alignment); -} - -QMapDataBase *QMapDataBase::createData() -{ - QMapDataBase *d = new QMapDataBase; - - d->ref.initializeOwned(); - d->size = 0; - - d->header.p = 0; - d->header.left = nullptr; - d->header.right = nullptr; - d->mostLeftNode = &(d->header); - - return d; -} - -void QMapDataBase::freeData(QMapDataBase *d) -{ - delete d; -} - -/*! - \class QMap - \inmodule QtCore - \brief The QMap class is a template class that provides a red-black-tree-based dictionary. - - \ingroup tools - \ingroup shared - - \reentrant - - QMap\<Key, T\> is one of Qt's generic \l{container classes}. It - stores (key, value) pairs and provides fast lookup of the - value associated with a key. - - QMap and QHash provide very similar functionality. The - differences are: - - \list - \li QHash provides average faster lookups than QMap. (See \l{Algorithmic - Complexity} for details.) - \li When iterating over a QHash, the items are arbitrarily ordered. - With QMap, the items are always sorted by key. - \li The key type of a QHash must provide operator==() and a global - qHash(Key) function. The key type of a QMap must provide - operator<() specifying a total order. Since Qt 5.8.1 it is also safe - to use a pointer type as key, even if the underlying operator<() - does not provide a total order. - \endlist - - Here's an example QMap with QString keys and \c int values: - \snippet code/src_corelib_tools_qmap.cpp 0 - - To insert a (key, value) pair into the map, you can use operator[](): - - \snippet code/src_corelib_tools_qmap.cpp 1 - - This inserts the following three (key, value) pairs into the - QMap: ("one", 1), ("three", 3), and ("seven", 7). Another way to - insert items into the map is to use insert(): - - \snippet code/src_corelib_tools_qmap.cpp 2 - - To look up a value, use operator[]() or value(): - - \snippet code/src_corelib_tools_qmap.cpp 3 - - If there is no item with the specified key in the map, these - functions return a \l{default-constructed value}. - - If you want to check whether the map contains a certain key, use - contains(): - - \snippet code/src_corelib_tools_qmap.cpp 4 - - There is also a value() overload that uses its second argument as - a default value if there is no item with the specified key: - - \snippet code/src_corelib_tools_qmap.cpp 5 - - In general, we recommend that you use contains() and value() - rather than operator[]() for looking up a key in a map. The - reason is that operator[]() silently inserts an item into the - map if no item exists with the same key (unless the map is - const). For example, the following code snippet will create 1000 - items in memory: - - \snippet code/src_corelib_tools_qmap.cpp 6 - - To avoid this problem, replace \c map[i] with \c map.value(i) - in the code above. - - If you want to navigate through all the (key, value) pairs stored - in a QMap, you can use an iterator. QMap provides both - \l{Java-style iterators} (QMapIterator and QMutableMapIterator) - and \l{STL-style iterators} (QMap::const_iterator and - QMap::iterator). Here's how to iterate over a QMap<QString, int> - using a Java-style iterator: - - \snippet code/src_corelib_tools_qmap.cpp 7 - - Here's the same code, but using an STL-style iterator this time: - - \snippet code/src_corelib_tools_qmap.cpp 8 - - The items are traversed in ascending key order. - - Normally, a QMap allows only one value per key. If you call - insert() with a key that already exists in the QMap, the - previous value will be erased. For example: - - \snippet code/src_corelib_tools_qmap.cpp 9 - - However, you can store multiple values per key by using - using the subclass QMultiMap. If you want - to retrieve all the values for a single key, you can use - values(const Key &key), which returns a QList<T>: - - \snippet code/src_corelib_tools_qmap.cpp 10 - - The items that share the same key are available from most - recently to least recently inserted. Another approach is to call - find() to get the STL-style iterator for the first item with a - key and iterate from there: - - \snippet code/src_corelib_tools_qmap.cpp 11 - - If you only need to extract the values from a map (not the keys), - you can also use \l{foreach}: - - \snippet code/src_corelib_tools_qmap.cpp 12 - - Items can be removed from the map in several ways. One way is to - call remove(); this will remove any item with the given key. - Another way is to use QMutableMapIterator::remove(). In addition, - you can clear the entire map using clear(). - - QMap's key and value data types must be \l{assignable data - types}. This covers most data types you are likely to encounter, - but the compiler won't let you, for example, store a QWidget as a - value; instead, store a QWidget *. In addition, QMap's key type - must provide operator<(). QMap uses it to keep its items sorted, - and assumes that two keys \c x and \c y are equal if neither \c{x - < y} nor \c{y < x} is true. - - Example: - \snippet code/src_corelib_tools_qmap.cpp 13 - - In the example, we start by comparing the employees' names. If - they're equal, we compare their dates of birth to break the tie. - - \sa QMapIterator, QMutableMapIterator, QHash, QSet -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::QMap() - - Constructs an empty map. - - \sa clear() -*/ - -/*! - \fn template <class Key, class T> QMap<Key, T>::QMap(QMap<Key, T> &&other) - - Move-constructs a QMap instance, making it point at the same - object that \a other was pointing to. - - \since 5.2 -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::QMap(const QMap<Key, T> &other) - - Constructs a copy of \a other. - - This operation occurs in \l{constant time}, because QMap is - \l{implicitly shared}. This makes returning a QMap from a - function very fast. If a shared instance is modified, it will be - copied (copy-on-write), and this takes \l{linear time}. - - \sa operator=() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::QMap(const typename std::map<Key, T> & other) - - Constructs a copy of \a other. - - \sa toStdMap() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::QMap(std::initializer_list<std::pair<Key,T> > list) - \since 5.1 - - Constructs a map with a copy of each of the elements in the - initializer list \a list. - - This function is only available if the program is being - compiled in C++11 mode. -*/ - -/*! \fn template <class Key, class T> std::map<Key, T> QMap<Key, T>::toStdMap() const - - Returns an STL map equivalent to this QMap. -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::~QMap() - - Destroys the map. References to the values in the map, and all - iterators over this map, become invalid. -*/ - -/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other) - - Assigns \a other to this map and returns a reference to this map. -*/ - -/*! - \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(QMap<Key, T> &&other) - - Move-assigns \a other to this QMap instance. - - \since 5.2 -*/ - -/*! \fn template <class Key, class T> void QMap<Key, T>::swap(QMap<Key, T> &other) - \since 4.8 - - Swaps map \a other with this map. This operation is very - fast and never fails. -*/ - -/*! \fn template <class Key, class T> void QMultiMap<Key, T>::swap(QMultiMap<Key, T> &other) - \since 4.8 - - Swaps map \a other with this map. This operation is very - fast and never fails. -*/ - -/*! \fn template <class Key, class T> bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const - - Returns \c true if \a other is equal to this map; otherwise returns - false. - - Two maps are considered equal if they contain the same (key, - value) pairs. - - This function requires the value type to implement \c - operator==(). - - \sa operator!=() -*/ - -/*! \fn template <class Key, class T> bool QMap<Key, T>::operator!=(const QMap<Key, T> &other) const - - Returns \c true if \a other is not equal to this map; otherwise - returns \c false. - - Two maps are considered equal if they contain the same (key, - value) pairs. - - This function requires the value type to implement \c - operator==(). - - \sa operator==() -*/ - -/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::size() const - - Returns the number of (key, value) pairs in the map. - - \sa isEmpty(), count() -*/ - -/*! - \fn template <class Key, class T> bool QMap<Key, T>::isEmpty() const - - Returns \c true if the map contains no items; otherwise returns - false. - - \sa size() -*/ - -/*! \fn template <class Key, class T> void QMap<Key, T>::detach() - - \internal - - Detaches this map from any other maps with which it may share - data. - - \sa isDetached() -*/ - -/*! \fn template <class Key, class T> bool QMap<Key, T>::isDetached() const - - \internal - - Returns \c true if the map's internal data isn't shared with any - other map object; otherwise returns \c false. - - \sa detach() -*/ - -/*! \fn template <class Key, class T> void QMap<Key, T>::setSharable(bool sharable) - - \internal -*/ - -/*! \fn template <class Key, class T> bool QMap<Key, T>::isSharedWith(const QMap<Key, T> &other) const - - \internal -*/ - -/*! \fn template <class Key, class T> void QMap<Key, T>::clear() - - Removes all items from the map. - - \sa remove() -*/ - -/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::remove(const Key &key) - - Removes all the items that have the key \a key from the map. - Returns the number of items removed which will be 1 if the key - exists in the map, and 0 otherwise. - - \sa clear(), take(), QMultiMap::remove() -*/ - -/*! \fn template <class Key, class T> T QMap<Key, T>::take(const Key &key) - - Removes the item with the key \a key from the map and returns - the value associated with it. - - If the item does not exist in the map, the function simply - returns a \l{default-constructed value}. If there are multiple - items for \a key in the map, only the most recently inserted one - is removed and returned. - - If you don't use the return value, remove() is more efficient. - - \sa remove() -*/ - -/*! \fn template <class Key, class T> bool QMap<Key, T>::contains(const Key &key) const - - Returns \c true if the map contains an item with key \a key; - otherwise returns \c false. - - \sa count(), QMultiMap::contains() -*/ - -/*! \fn template <class Key, class T> T QMap<Key, T>::value(const Key &key, const T &defaultValue) const - - Returns the value associated with the key \a key. - - If the map contains no item with key \a key, the function returns - \a defaultValue. If no \a defaultValue is specified, the function - returns a \l{default-constructed value}. If there are multiple - items for \a key in the map, the value of the most recently - inserted one is returned. - - \sa key(), values(), contains(), operator[]() -*/ - -/*! \fn template <class Key, class T> T &QMap<Key, T>::operator[](const Key &key) - - Returns the value associated with the key \a key as a modifiable - reference. - - If the map contains no item with key \a key, the function inserts - a \l{default-constructed value} into the map with key \a key, and - returns a reference to it. If the map contains multiple items - with key \a key, this function returns a reference to the most - recently inserted value. - - \sa insert(), value() -*/ - -/*! \fn template <class Key, class T> const T QMap<Key, T>::operator[](const Key &key) const - - \overload - - Same as value(). -*/ - -/*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::uniqueKeys() const - \since 4.2 - \obsolete Use QMultiMap for storing multiple values with the same key. - - Returns a list containing all the keys in the map in ascending - order. Keys that occur multiple times in the map (because items - were inserted with insertMulti(), or unite() was used) occur only - once in the returned list. - - \sa QMultiMap::uniqueKeys() -*/ - -/*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::keys() const - - Returns a list containing all the keys in the map in ascending - order. Keys that occur multiple times in the map (because the - method is operating on a QMultiMap) also occur multiple times - in the list. - - The order is guaranteed to be the same as that used by values(). - - This function creates a new list, in \l {linear time}. The time and memory - use that entails can be avoided by iterating from \l keyBegin() to - \l keyEnd(). - - \sa QMultiMap::uniqueKeys(), values(), key() -*/ - -/*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::keys(const T &value) const - - \overload - - Returns a list containing all the keys associated with value \a - value in ascending order. - - This function can be slow (\l{linear time}), because QMap's - internal data structure is optimized for fast lookup by key, not - by value. -*/ - -/*! - \fn template <class Key, class T> Key QMap<Key, T>::key(const T &value, const Key &defaultKey) const - \since 4.3 - \overload - - Returns the first key with value \a value, or \a defaultKey if - the map contains no item with value \a value. If no \a defaultKey - is provided the function returns a - \l{default-constructed value}{default-constructed key}. - - This function can be slow (\l{linear time}), because QMap's - internal data structure is optimized for fast lookup by key, not - by value. - - \sa value(), keys() -*/ - -/*! \fn template <class Key, class T> QList<T> QMap<Key, T>::values() const - - Returns a list containing all the values in the map, in ascending - order of their keys. If a key is associated with multiple values, - all of its values will be in the list, and not just the most - recently inserted one. - - This function creates a new list, in \l {linear time}. The time and memory - use that entails can be avoided by iterating from \l keyValueBegin() to - \l keyValueEnd(). - - \sa keys(), value() -*/ - -/*! \fn template <class Key, class T> QList<T> QMap<Key, T>::values(const Key &key) const - \overload - \obsolete Use QMultiMap for maps storing multiple values with the same key. - - Returns a list containing all the values associated with key - \a key, from the most recently inserted to the least recently - inserted one. - - \sa QMultiMap::values() -*/ - -/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::count(const Key &key) const - - Returns the number of items associated with key \a key. - - \sa contains(), QMultiMap::count() -*/ - -/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::count() const - - \overload - - Same as size(). -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::begin() - - Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in - the map. - - \sa constBegin(), end() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::begin() const - - \overload -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::cbegin() const - \since 5.0 - - Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item - in the map. - - \sa begin(), cend() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::constBegin() const - - Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item - in the map. - - \sa begin(), constEnd() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::keyBegin() const - \since 5.6 - - Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key - in the map. - - \sa keyEnd(), firstKey() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::end() - - Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item - after the last item in the map. - - \sa begin(), constEnd() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::end() const - - \overload -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::cend() const - \since 5.0 - - Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary - item after the last item in the map. - - \sa cbegin(), end() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::constEnd() const - - Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary - item after the last item in the map. - - \sa constBegin(), end() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::keyEnd() const - \since 5.6 - - Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary - item after the last key in the map. - - \sa keyBegin(), lastKey() -*/ - - -/*! \fn template <class Key, class T> QMap<Key, T>::key_value_iterator QMap<Key, T>::keyValueBegin() - \since 5.10 - - Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry - in the map. - - \sa keyValueEnd() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::key_value_iterator QMap<Key, T>::keyValueEnd() - \since 5.10 - - Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary - entry after the last entry in the map. - - \sa keyValueBegin() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::keyValueBegin() const - \since 5.10 - - Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry - in the map. - - \sa keyValueEnd() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::constKeyValueBegin() const - \since 5.10 - - Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry - in the map. - - \sa keyValueBegin() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::keyValueEnd() const - \since 5.10 - - Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary - entry after the last entry in the map. - - \sa keyValueBegin() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::constKeyValueEnd() const - \since 5.10 - - Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary - entry after the last entry in the map. - - \sa constKeyValueBegin() -*/ - -/*! \fn template <class Key, class T> const Key &QMap<Key, T>::firstKey() const - \since 5.2 - - Returns a reference to the smallest key in the map. - This function assumes that the map is not empty. - - This executes in \l{constant time}. - - \sa lastKey(), first(), keyBegin(), isEmpty() -*/ - -/*! \fn template <class Key, class T> const Key &QMap<Key, T>::lastKey() const - \since 5.2 - - Returns a reference to the largest key in the map. - This function assumes that the map is not empty. - - This executes in \l{logarithmic time}. - - \sa firstKey(), last(), keyEnd(), isEmpty() -*/ - -/*! \fn template <class Key, class T> T &QMap<Key, T>::first() - \since 5.2 - - Returns a reference to the first value in the map, that is the value mapped - to the smallest key. This function assumes that the map is not empty. - - When unshared (or const version is called), this executes in \l{constant time}. - - \sa last(), firstKey(), isEmpty() -*/ - -/*! \fn template <class Key, class T> const T &QMap<Key, T>::first() const - \since 5.2 - - \overload -*/ - -/*! \fn template <class Key, class T> T &QMap<Key, T>::last() - \since 5.2 - - Returns a reference to the last value in the map, that is the value mapped - to the largest key. This function assumes that the map is not empty. - - When unshared (or const version is called), this executes in \l{logarithmic time}. - - \sa first(), lastKey(), isEmpty() -*/ - -/*! \fn template <class Key, class T> const T &QMap<Key, T>::last() const - \since 5.2 - - \overload -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::erase(iterator pos) - - Removes the (key, value) pair pointed to by the iterator \a pos - from the map, and returns an iterator to the next item in the - map. - - \sa remove() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::find(const Key &key) - - Returns an iterator pointing to the item with key \a key in the - map. - - If the map contains no item with key \a key, the function - returns end(). - - If the map contains multiple items with key \a key, this - function returns an iterator that points to the most recently - inserted value. The other values are accessible by incrementing - the iterator. For example, here's some code that iterates over all - the items with the same key: - - \snippet code/src_corelib_tools_qmap.cpp 14 - - \sa constFind(), value(), values(), lowerBound(), upperBound(), QMultiMap::find() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &key) const - - \overload -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &key) const - \since 4.1 - - Returns an const iterator pointing to the item with key \a key in the - map. - - If the map contains no item with key \a key, the function - returns constEnd(). - - \sa find(), QMultiMap::constFind() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &key) - - Returns an iterator pointing to the first item with key \a key in - the map. If the map contains no item with key \a key, the - function returns an iterator to the nearest item with a greater - key. - - Example: - \snippet code/src_corelib_tools_qmap.cpp 15 - - If the map contains multiple items with key \a key, this - function returns an iterator that points to the most recently - inserted value. The other values are accessible by incrementing - the iterator. For example, here's some code that iterates over all - the items with the same key: - - \snippet code/src_corelib_tools_qmap.cpp 16 - - \sa upperBound(), find() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &key) const - - \overload -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &key) - - Returns an iterator pointing to the item that immediately follows - the last item with key \a key in the map. If the map contains no - item with key \a key, the function returns an iterator to the - nearest item with a greater key. - - Example: - \snippet code/src_corelib_tools_qmap.cpp 17 - - \sa lowerBound(), find() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::upperBound(const Key &key) const - - \overload -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &key, const T &value) - - Inserts a new item with the key \a key and a value of \a value. - - If there is already an item with the key \a key, that item's value - is replaced with \a value. - - If there are multiple items with the key \a key, the most - recently inserted item's value is replaced with \a value. - - \sa QMultiMap::insert() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &key, const T &value) - \overload - \since 5.1 - Inserts a new item with the key \a key and value \a value and with hint \a pos - suggesting where to do the insert. - - If constBegin() is used as hint it indicates that the \a key is less than any key in the map - while constEnd() suggests that the \a key is (strictly) larger than any key in the map. - Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key(). - If the hint \a pos is wrong it is ignored and a regular insert is done. - - If there is already an item with the key \a key, that item's value - is replaced with \a value. - - If there are multiple items with the key \a key, then exactly one of them - is replaced with \a value. - - If the hint is correct and the map is unshared, the insert executes in amortized \l{constant time}. - - When creating a map from sorted data inserting the largest key first with constBegin() - is faster than inserting in sorted order with constEnd(), since constEnd() - 1 (which is needed - to check if the hint is valid) needs \l{logarithmic time}. - - \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might - crash but there is also a risk that it will silently corrupt both the map and the \a pos map. - - \sa QMultiMap::insert() -*/ - -/*! \fn template <class Key, class T> void QMap<Key, T>::insert(const QMap<Key, T> &map) - \since 5.15 - - Inserts all the items in \a map into this map. - - If a key is common to both maps, its value will be replaced with - the value stored in \a map. - - \note If \a map contains multiple entries with the same key then the - final value of the key is undefined. - - \sa QMultiMap::insert() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value) - \obsolete Use QMultiMap for storing multiple values with the same key. - - Inserts a new item with the key \a key and a value of \a value. - - If there is already an item with the same key in the map, this - function will simply create a new one. (This behavior is - different from insert(), which overwrites the value of an - existing item.) - - \sa QMultiMap::insert() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &key, const T &value) - \overload - \since 5.1 - \obsolete Use QMultiMap for storing multiple values with the same key. - Inserts a new item with the key \a key and value \a value and with hint \a pos - suggesting where to do the insert. - - If constBegin() is used as hint it indicates that the \a key is less than any key in the map - while constEnd() suggests that the \a key is larger than any key in the map. - Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key(). - If the hint \a pos is wrong it is ignored and a regular insertMulti is done. - - If there is already an item with the same key in the map, this function will simply create a new one. - - \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might - crash but there is also a risk that it will silently corrupt both the map and the \a pos map. - - \sa QMultiMap::insert() -*/ - - -/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other) - \obsolete Use QMultiMap for storing multiple values with the same key. - - Inserts all the items in the \a other map into this map. If a - key is common to both maps, the resulting map will contain the - key multiple times. - - \sa QMultiMap::unite() -*/ - -/*! \typedef QMap::Iterator - - Qt-style synonym for QMap<Key, T>::iterator. -*/ - -/*! \typedef QMap::ConstIterator - - Qt-style synonym for QMap<Key, T>::const_iterator. -*/ - -/*! \typedef QMap::difference_type - - Typedef for ptrdiff_t. Provided for STL compatibility. -*/ - -/*! \typedef QMap::key_type - - Typedef for Key. Provided for STL compatibility. -*/ - -/*! \typedef QMap::mapped_type - - Typedef for T. Provided for STL compatibility. -*/ - -/*! \typedef QMap::size_type - - Typedef for int. Provided for STL compatibility. -*/ - -/*! - \fn template <class Key, class T> bool QMap<Key, T>::empty() const - - This function is provided for STL compatibility. It is equivalent - to isEmpty(), returning true if the map is empty; otherwise - returning false. -*/ - -/*! - \fn template <class Key, class T> QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &key) - - Returns a pair of iterators delimiting the range of values \c{[first, second)}, that - are stored under \a key. -*/ - -/*! - \fn 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 &key) const - \overload - \since 5.6 -*/ - - -/*! \class QMap::iterator - \inmodule QtCore - \brief The QMap::iterator class provides an STL-style non-const iterator for QMap and QMultiMap. - - QMap features both \l{STL-style iterators} and \l{Java-style - iterators}. The STL-style iterators are more low-level and more - cumbersome to use; on the other hand, they are slightly faster - and, for developers who already know STL, have the advantage of - familiarity. - - QMap\<Key, T\>::iterator allows you to iterate over a QMap (or - QMultiMap) and to modify the value (but not the key) stored under - a particular key. If you want to iterate over a const QMap, you - should use QMap::const_iterator. It is generally good practice to - use QMap::const_iterator on a non-const QMap as well, unless you - need to change the QMap through the iterator. Const iterators are - slightly faster, and can improve code readability. - - The default QMap::iterator constructor creates an uninitialized - iterator. You must initialize it using a QMap function like - QMap::begin(), QMap::end(), or QMap::find() before you can - start iterating. Here's a typical loop that prints all the (key, - value) pairs stored in a map: - - \snippet code/src_corelib_tools_qmap.cpp 18 - - Unlike QHash, which stores its items in an arbitrary order, QMap - stores its items ordered by key. Items that share the same key - (because the map is a QMultiMap) will appear consecutively, - from the most recently to the least recently inserted value. - - Let's see a few examples of things we can do with a - QMap::iterator that we cannot do with a QMap::const_iterator. - Here's an example that increments every value stored in the QMap - by 2: - - \snippet code/src_corelib_tools_qmap.cpp 19 - - Here's an example that removes all the items whose key is a - string that starts with an underscore character: - - \snippet code/src_corelib_tools_qmap.cpp 20 - - The call to QMap::erase() removes the item pointed to by the - iterator from the map, and returns an iterator to the next item. - Here's another way of removing an item while iterating: - - \snippet code/src_corelib_tools_qmap.cpp 21 - - It might be tempting to write code like this: - - \snippet code/src_corelib_tools_qmap.cpp 22 - - However, this will potentially crash in \c{++i}, because \c i is - a dangling iterator after the call to erase(). - - Multiple iterators can be used on the same map. If you add items - to the map, existing iterators will remain valid. If you remove - items from the map, iterators that point to the removed items - will become dangling iterators. - - \warning Iterators on implicitly shared containers do not work - exactly like STL-iterators. You should avoid copying a container - while iterators are active on that container. For more information, - read \l{Implicit sharing iterator problem}. - - \sa QMap::const_iterator, QMap::key_iterator, QMutableMapIterator -*/ - -/*! \typedef QMap::iterator::difference_type - - \internal -*/ - -/*! \typedef QMap::iterator::iterator_category - - A synonym for \e {std::bidirectional_iterator_tag} indicating - this iterator is a bidirectional iterator. -*/ - -/*! \typedef QMap::iterator::pointer - - \internal -*/ - -/*! \typedef QMap::iterator::reference - - \internal -*/ - -/*! \typedef QMap::iterator::value_type - - \internal -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator::iterator() - - Constructs an uninitialized iterator. - - Functions like key(), value(), and operator++() must not be - called on an uninitialized iterator. Use operator=() to assign a - value to it before using it. - - \sa QMap::begin(), QMap::end() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator::iterator(Node *) - - \internal -*/ - -/*! \fn template <class Key, class T> const Key &QMap<Key, T>::iterator::key() const - - Returns the current item's key as a const reference. - - There is no direct way of changing an item's key through an - iterator, although it can be done by calling QMap::erase() - followed by QMap::insert() or QMap::insertMulti(). - - \sa value() -*/ - -/*! \fn template <class Key, class T> T &QMap<Key, T>::iterator::value() const - - Returns a modifiable reference to the current item's value. - - You can change the value of an item by using value() on - the left side of an assignment, for example: - - \snippet code/src_corelib_tools_qmap.cpp 23 - - \sa key(), operator*() -*/ - -/*! \fn template <class Key, class T> T &QMap<Key, T>::iterator::operator*() const - - Returns a modifiable reference to the current item's value. - - Same as value(). - - \sa key() -*/ - -/*! \fn template <class Key, class T> T *QMap<Key, T>::iterator::operator->() const - - Returns a pointer to the current item's value. - - \sa value() -*/ - -/*! - \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator==(const iterator &other) const - \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator==(const const_iterator &other) const - - Returns \c true if \a other points to the same item as this - iterator; otherwise returns \c false. - - \sa operator!=() -*/ - -/*! - \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator!=(const iterator &other) const - \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator!=(const const_iterator &other) const - - Returns \c true if \a other points to a different item than this - iterator; otherwise returns \c false. - - \sa operator==() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator++() - - The prefix ++ operator (\c{++i}) advances the iterator to the - next item in the map and returns an iterator to the new current - item. - - Calling this function on QMap::end() leads to undefined results. - - \sa operator--() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator++(int) - - \overload - - The postfix ++ operator (\c{i++}) advances the iterator to the - next item in the map and returns an iterator to the previously - current item. -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator--() - - The prefix -- operator (\c{--i}) makes the preceding item - current and returns an iterator pointing to the new current item. - - Calling this function on QMap::begin() leads to undefined - results. - - \sa operator++() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator--(int) - - \overload - - The postfix -- operator (\c{i--}) makes the preceding item - current and returns an iterator pointing to the previously - current item. -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator+(qsizetype j) const - - Returns an iterator to the item at \a j positions forward from - this iterator. (If \a j is negative, the iterator goes backward.) - - This operation can be slow for large \a j values. - - \sa operator-() - -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator-(qsizetype j) const - - Returns an iterator to the item at \a j positions backward from - this iterator. (If \a j is negative, the iterator goes forward.) - - This operation can be slow for large \a j values. - - \sa operator+() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator+=(qsizetype j) - - Advances the iterator by \a j items. (If \a j is negative, the - iterator goes backward.) - - \sa operator-=(), operator+() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator-=(qsizetype j) - - Makes the iterator go back by \a j items. (If \a j is negative, - the iterator goes forward.) - - \sa operator+=(), operator-() -*/ - -/*! \class QMap::const_iterator - \inmodule QtCore - \brief The QMap::const_iterator class provides an STL-style const iterator for QMap and QMultiMap. - - QMap features both \l{STL-style iterators} and \l{Java-style - iterators}. The STL-style iterators are more low-level and more - cumbersome to use; on the other hand, they are slightly faster - and, for developers who already know STL, have the advantage of - familiarity. - - QMap\<Key, T\>::const_iterator allows you to iterate over a QMap - (or a QMultiMap). If you want to modify the QMap as you iterate - over it, you must use QMap::iterator instead. It is generally - good practice to use QMap::const_iterator on a non-const QMap as - well, unless you need to change the QMap through the iterator. - Const iterators are slightly faster, and can improve code - readability. - - The default QMap::const_iterator constructor creates an - uninitialized iterator. You must initialize it using a QMap - function like QMap::constBegin(), QMap::constEnd(), or - QMap::find() before you can start iterating. Here's a typical - loop that prints all the (key, value) pairs stored in a map: - - \snippet code/src_corelib_tools_qmap.cpp 24 - - Unlike QHash, which stores its items in an arbitrary order, QMap - stores its items ordered by key. Items that share the same key - (because the map is a QMultiMap) will appear consecutively, - from the most recently to the least recently inserted value. - - Multiple iterators can be used on the same map. If you add items - to the map, existing iterators will remain valid. If you remove - items from the map, iterators that point to the removed items - will become dangling iterators. - - \warning Iterators on implicitly shared containers do not work - exactly like STL-iterators. You should avoid copying a container - while iterators are active on that container. For more information, - read \l{Implicit sharing iterator problem}. - - \sa QMap::iterator, QMap::key_iterator, QMapIterator -*/ - -/*! \typedef QMap::const_iterator::difference_type - - \internal -*/ - -/*! \typedef QMap::const_iterator::iterator_category - - A synonym for \e {std::bidirectional_iterator_tag} indicating - this iterator is a bidirectional iterator. -*/ - -/*! \typedef QMap::const_iterator::pointer - - \internal -*/ - -/*! \typedef QMap::const_iterator::reference - - \internal -*/ - -/*! \typedef QMap::const_iterator::value_type - - \internal -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator() - - Constructs an uninitialized iterator. - - Functions like key(), value(), and operator++() must not be - called on an uninitialized iterator. Use operator=() to assign a - value to it before using it. - - \sa QMap::constBegin(), QMap::constEnd() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator(const Node *) - - \internal -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator(const iterator &other) - - Constructs a copy of \a other. -*/ - -/*! \fn template <class Key, class T> const Key &QMap<Key, T>::const_iterator::key() const - - Returns the current item's key. - - \sa value() -*/ - -/*! \fn template <class Key, class T> const T &QMap<Key, T>::const_iterator::value() const - - Returns the current item's value. - - \sa key(), operator*() -*/ - -/*! \fn template <class Key, class T> const T &QMap<Key, T>::const_iterator::operator*() const - - Returns the current item's value. - - Same as value(). - - \sa key() -*/ - -/*! \fn template <class Key, class T> const T *QMap<Key, T>::const_iterator::operator->() const - - Returns a pointer to the current item's value. - - \sa value() -*/ - -/*! \fn template <class Key, class T> bool QMap<Key, T>::const_iterator::operator==(const const_iterator &other) const - - Returns \c true if \a other points to the same item as this - iterator; otherwise returns \c false. - - \sa operator!=() -*/ - -/*! \fn template <class Key, class T> bool QMap<Key, T>::const_iterator::operator!=(const const_iterator &other) const - - Returns \c true if \a other points to a different item than this - iterator; otherwise returns \c false. - - \sa operator==() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator++() - - The prefix ++ operator (\c{++i}) advances the iterator to the - next item in the map and returns an iterator to the new current - item. - - Calling this function on QMap::end() leads to undefined results. - - \sa operator--() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator++(int) - - \overload - - The postfix ++ operator (\c{i++}) advances the iterator to the - next item in the map and returns an iterator to the previously - current item. -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator--() - - The prefix -- operator (\c{--i}) makes the preceding item - current and returns an iterator pointing to the new current item. - - Calling this function on QMap::begin() leads to undefined - results. - - \sa operator++() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator--(int) - - \overload - - The postfix -- operator (\c{i--}) makes the preceding item - current and returns an iterator pointing to the previously - current item. -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator+(qsizetype j) const - - Returns an iterator to the item at \a j positions forward from - this iterator. (If \a j is negative, the iterator goes backward.) - - This operation can be slow for large \a j values. - - \sa operator-() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator-(qsizetype j) const - - Returns an iterator to the item at \a j positions backward from - this iterator. (If \a j is negative, the iterator goes forward.) - - This operation can be slow for large \a j values. - - \sa operator+() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator+=(qsizetype j) - - Advances the iterator by \a j items. (If \a j is negative, the - iterator goes backward.) - - This operation can be slow for large \a j values. - - \sa operator-=(), operator+() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator-=(qsizetype j) - - Makes the iterator go back by \a j items. (If \a j is negative, - the iterator goes forward.) - - This operation can be slow for large \a j values. - - \sa operator+=(), operator-() -*/ - -/*! \class QMap::key_iterator - \inmodule QtCore - \since 5.6 - \brief The QMap::key_iterator class provides an STL-style const iterator for QMap and QMultiMap keys. - - QMap::key_iterator is essentially the same as QMap::const_iterator - with the difference that operator*() and operator->() return a key - instead of a value. - - For most uses QMap::iterator and QMap::const_iterator should be used, - you can easily access the key by calling QMap::iterator::key(): - - \snippet code/src_corelib_tools_qmap.cpp keyiterator1 - - However, to have interoperability between QMap's keys and STL-style - algorithms we need an iterator that dereferences to a key instead - of a value. With QMap::key_iterator we can apply an algorithm to a - range of keys without having to call QMap::keys(), which is inefficient - as it costs one QMap iteration and memory allocation to create a temporary - QList. - - \snippet code/src_corelib_tools_qmap.cpp keyiterator2 - - QMap::key_iterator is const, it's not possible to modify the key. - - The default QMap::key_iterator constructor creates an uninitialized - iterator. You must initialize it using a QMap function like - QMap::keyBegin() or QMap::keyEnd(). - - \warning Iterators on implicitly shared containers do not work - exactly like STL-iterators. You should avoid copying a container - while iterators are active on that container. For more information, - read \l{Implicit sharing iterator problem}. - - \sa QMap::const_iterator, QMap::iterator -*/ - -/*! \typedef QMap::key_iterator::difference_type - \internal -*/ - -/*! \typedef QMap::key_iterator::iterator_category - \internal -*/ - -/*! \typedef QMap::key_iterator::pointer - \internal -*/ - -/*! \typedef QMap::key_iterator::reference - \internal -*/ - -/*! \typedef QMap::key_iterator::value_type - \internal -*/ - -/*! \fn template <class Key, class T> const T &QMap<Key, T>::key_iterator::operator*() const - - Returns the current item's key. -*/ - -/*! \fn template <class Key, class T> const T *QMap<Key, T>::key_iterator::operator->() const - - Returns a pointer to the current item's key. -*/ - -/*! \fn template <class Key, class T> bool QMap<Key, T>::key_iterator::operator==(key_iterator other) const - - Returns \c true if \a other points to the same item as this - iterator; otherwise returns \c false. - - \sa operator!=() -*/ - -/*! \fn template <class Key, class T> bool QMap<Key, T>::key_iterator::operator!=(key_iterator other) const - - Returns \c true if \a other points to a different item than this - iterator; otherwise returns \c false. - - \sa operator==() -*/ - -/*! - \fn template <class Key, class T> QMap<Key, T>::key_iterator &QMap<Key, T>::key_iterator::operator++() - - The prefix ++ operator (\c{++i}) advances the iterator to the - next item in the hash and returns an iterator to the new current - item. - - Calling this function on QMap::keyEnd() leads to undefined results. - - \sa operator--() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::key_iterator::operator++(int) - - \overload - - The postfix ++ operator (\c{i++}) advances the iterator to the - next item in the hash and returns an iterator to the previous - item. -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator &QMap<Key, T>::key_iterator::operator--() - - The prefix -- operator (\c{--i}) makes the preceding item - current and returns an iterator pointing to the new current item. - - Calling this function on QMap::keyBegin() leads to undefined - results. - - \sa operator++() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::key_iterator::operator--(int) - - \overload - - The postfix -- operator (\c{i--}) makes the preceding item - current and returns an iterator pointing to the previous - item. -*/ - -/*! \fn template <class Key, class T> const_iterator QMap<Key, T>::key_iterator::base() const - Returns the underlying const_iterator this key_iterator is based on. -*/ - -/*! \typedef QMap::const_key_value_iterator - \inmodule QtCore - \since 5.10 - \brief The QMap::const_key_value_iterator typedef provides an STL-style iterator for QMap and QMultiMap. - - QMap::const_key_value_iterator is essentially the same as QMap::const_iterator - with the difference that operator*() returns a key/value pair instead of a - value. - - \sa QKeyValueIterator -*/ - -/*! \typedef QMap::key_value_iterator - \inmodule QtCore - \since 5.10 - \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QMap and QMultiMap. - - QMap::key_value_iterator is essentially the same as QMap::iterator - with the difference that operator*() returns a key/value pair instead of a - value. - - \sa QKeyValueIterator -*/ - -/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QMap<Key, T> &map) - \relates QMap - - Writes the map \a map to stream \a out. - - This function requires the key and value types to implement \c - operator<<(). - - \sa{Serializing Qt Data Types}{Format of the QDataStream operators} -*/ - -/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QMap<Key, T> &map) - \relates QMap - - Reads a map from stream \a in into \a map. - - This function requires the key and value types to implement \c - operator>>(). - - \sa{Serializing Qt Data Types}{Format of the QDataStream operators} -*/ - -/*! \class QMultiMap - \inmodule QtCore - \brief The QMultiMap class is a convenience QMap subclass that provides multi-valued maps. - - \ingroup tools - \ingroup shared - - \reentrant - - QMultiMap\<Key, T\> is one of Qt's generic \l{container classes}. - It inherits QMap and extends it with a few functions - that make it able to store multi-valued maps. A multi-valued map - is a map that allows multiple values with the same key; QMap - doesn't allow that. - - Because QMultiMap inherits QMap, all of QMap's functionality also - applies to QMultiMap. For example, you can use isEmpty() to test - whether the map is empty, and you can traverse a QMultiMap using - QMap's iterator classes (for example, QMapIterator). But in - addition, it provides an insert() function that inserts but does - not overwrite any previous value if the key already exists, - and a replace() function that corresponds which does overwite - an existing value if they key is already in the map. - It also provides convenient operator+() and operator+=(). - - Example: - \snippet code/src_corelib_tools_qmap.cpp 25 - - Unlike QMap, QMultiMap provides no operator[]. Use value() or - replace() if you want to access the most recently inserted item - with a certain key. - - If you want to retrieve all the values for a single key, you can - use values(const Key &key), which returns a QList<T>: - - \snippet code/src_corelib_tools_qmap.cpp 26 - - The items that share the same key are available from most - recently to least recently inserted. - - If you prefer the STL-style iterators, you can call find() to get - the iterator for the first item with a key and iterate from - there: - - \snippet code/src_corelib_tools_qmap.cpp 27 - - QMultiMap's key and value data types must be \l{assignable data - types}. This covers most data types you are likely to encounter, - but the compiler won't let you, for example, store a QWidget as a - value; instead, store a QWidget *. In addition, QMultiMap's key type - must provide operator<(). See the QMap documentation for details. - - \sa QMap, QMapIterator, QMutableMapIterator, QMultiHash -*/ - -/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap() - - Constructs an empty map. -*/ - -/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(std::initializer_list<std::pair<Key,T> > list) - \since 5.1 - - Constructs a multi-map with a copy of each of the elements in the - initializer list \a list. - - This function is only available if the program is being - compiled in C++11 mode. -*/ - -/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const QMap<Key, T> &other) - - Constructs a copy of \a other (which can be a QMap or a - QMultiMap). - - \sa operator=() -*/ - -/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::replace(const Key &key, const T &value) - - Inserts a new item with the key \a key and a value of \a value. - - If there is already an item with the key \a key, that item's value - is replaced with \a value. - - If there are multiple items with the key \a key, the most - recently inserted item's value is replaced with \a value. - - \sa insert() -*/ - -/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &key, const T &value) - - Inserts a new item with the key \a key and a value of \a value. - - If there is already an item with the same key in the map, this - function will simply create a new one. (This behavior is - different from replace(), which overwrites the value of an - existing item.) - - \sa replace() -*/ - -/*! \fn [qmultimap-insert-pos] template <class Key, class T> typename QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(typename QMultiMap<Key, T>::const_iterator pos, const Key &key, const T &value) - - \since 5.1 - Inserts a new item with the key \a key and value \a value and with hint \a pos - suggesting where to do the insert. - - If constBegin() is used as hint it indicates that the \a key is less than any key in the map - while constEnd() suggests that the \a key is larger than any key in the map. - Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key(). - If the hint \a pos is wrong it is ignored and a regular insert is done. - - If there is already an item with the same key in the map, this function will simply create a new one. - - \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might - crash but there is also a risk that it will silently corrupt both the map and the \a pos map. -*/ - -/*! \fn template <class Key, class T> QMultiMap &QMultiMap<Key, T>::operator+=(const QMultiMap &other) - - Inserts all the items in the \a other map into this map and - returns a reference to this map. - - \sa insert(), operator+() -*/ - -/*! \fn template <class Key, class T> QMultiMap QMultiMap<Key, T>::operator+(const QMultiMap &other) const - - Returns a map that contains all the items in this map in - addition to all the items in \a other. If a key is common to both - maps, the resulting map will contain the key multiple times. - - \sa operator+=() -*/ - -/*! - \fn template <class Key, class T> bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const - \since 4.3 - - Returns \c true if the map contains an item with key \a key and - value \a value; otherwise returns \c false. - - \sa QMap::contains() -*/ - -/*! - \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::remove(const Key &key, const T &value) - \since 4.3 - - Removes all the items that have the key \a key and the value \a - value from the map. Returns the number of items removed. - - \sa QMap::remove() -*/ - -/*! - \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count(const Key &key, const T &value) const - \since 4.3 - - Returns the number of items with key \a key and value \a value. - - \sa QMap::count() -*/ - -/*! - \fn template <class Key, class T> typename QMap<Key, T>::iterator QMultiMap<Key, T>::find(const Key &key, const T &value) - \since 4.3 - - Returns an iterator pointing to the item with key \a key and - value \a value in the map. - - If the map contains no such item, the function returns end(). - - If the map contains multiple items with key \a key, this - function returns an iterator that points to the most recently - inserted value. - - \sa QMap::find() -*/ - -/*! - \fn template <class Key, class T> typename QMap<Key, T>::const_iterator QMultiMap<Key, T>::find(const Key &key, const T &value) const - \since 4.3 - \overload - - Returns a const iterator pointing to the item with the given \a key and - \a value in the map. - - If the map contains no such item, the function returns end(). - - If the map contains multiple items with the specified \a key, this - function returns a const iterator that points to the most recently - inserted value. - - \sa QMap::find() -*/ - -/*! - \fn template <class Key, class T> typename QMap<Key, T>::const_iterator QMultiMap<Key, T>::constFind(const Key &key, const T &value) const - \since 4.3 - - Returns an iterator pointing to the item with key \a key and the - value \a value in the map. - - If the map contains no such item, the function returns - constEnd(). - - \sa QMap::constFind() -*/ - -/*! \fn template <class Key, class T> QList<T> QMultiMap<Key, T>::values(const Key &key) const - - Returns a list containing all the values associated with key - \a key, from the most recently inserted to the least recently - inserted one. -*/ - -/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::uniqueKeys() const - \since 4.2 - - Returns a list containing all the keys in the map in ascending - order. Keys that occur multiple times in the map occur only - once in the returned list. -*/ - -/*! - \fn [qmultimap-unite] template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other) - - Inserts all the items in the \a other map into this map. If a - key is common to both maps, the resulting map will contain the - key multiple times. -*/ - -QT_END_NAMESPACE |