diff options
| -rw-r--r-- | src/corelib/tools/qhash.cpp | 1061 |
1 files changed, 749 insertions, 312 deletions
diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp index f048aa01de..f053341afd 100644 --- a/src/corelib/tools/qhash.cpp +++ b/src/corelib/tools/qhash.cpp @@ -761,13 +761,16 @@ uint qHash(long double key, uint seed) noexcept in the code above. Internally, QHash uses a hash table to perform lookups. This - hash table automatically grows and shrinks to + hash table automatically grows to provide fast lookups without wasting too much memory. You can still control the size of the hash table by calling reserve() if you already know approximately how many items the QHash will contain, but this isn't necessary to obtain good performance. You can also call capacity() to retrieve the hash table's size. + QHash will not shrink automatically if items are removed from the + table. To minimize the memory used by the hash, call squeeze(). + If you want to navigate through all the (key, value) pairs stored in a QHash, you can use an iterator. QHash provides both \l{Java-style iterators} (QHashIterator and QMutableHashIterator) @@ -784,12 +787,15 @@ uint qHash(long double key, uint seed) noexcept QHash is unordered, so an iterator's sequence cannot be assumed to be predictable. If ordering by key is required, use a QMap. - Normally, a QHash allows only one value per key. If you call + A QHash allows only one value per key. If you call insert() with a key that already exists in the QHash, the previous value is erased. For example: \snippet code/src_corelib_tools_qhash.cpp 9 + If you need to store multiple entries for the same key in the + hash table, use \l{QMultiHash}. + If you only need to extract the values from a hash (not the keys), you can also use \l{foreach}: @@ -901,9 +907,6 @@ uint qHash(long double key, uint seed) noexcept Constructs a hash 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> template <class InputIterator> QHash<Key, T>::QHash(InputIterator begin, InputIterator end) @@ -1015,24 +1018,45 @@ uint qHash(long double key, uint seed) noexcept \sa reserve(), squeeze() */ +/*! \fn template <class Key, class T> float QHash<Key, T>::load_factor() const noexcept + + Returns the current load factor of the QHash's internal hash table. + This is the same as capacity()/size(). The implementation used + will aim to keep the load factor between 0.25 and 0.5. This avoids + having too many hash table collisions that would degrade performance. + + Even with a low load factor, the implementation of the hash table has a + very low memory overhead. + + This method purely exists for diagnostic purposes and you should rarely + need to call it yourself. + + \sa reserve(), squeeze() +*/ + + /*! \fn template <class Key, class T> void QHash<Key, T>::reserve(int size) - Ensures that the QHash's internal hash table consists of at least - \a size buckets. + Ensures that the QHash's internal hash table has space to store at + least \a size items without having to grow the hash table. + + This implies that the hash table will contain at least 2 * \a size buckets + to ensure good performance This function is useful for code that needs to build a huge hash and wants to avoid repeated reallocation. For example: \snippet code/src_corelib_tools_qhash.cpp 14 - Ideally, \a size should be slightly more than the maximum number - of items expected in the hash. \a size doesn't have to be prime, - because QHash will use a prime number internally anyway. If \a size + Ideally, \a size should be the maximum number of items expected + in the hash. QHash will then choose the smallest possible + number of buckets that will allow storing \a size items in the table + without having to grow the internal hash table. If \a size is an underestimate, the worst that will happen is that the QHash will be a bit slower. In general, you will rarely ever need to call this function. - QHash's internal hash table automatically shrinks or grows to + QHash's internal hash table automatically grows to provide good performance without wasting too much memory. \sa squeeze(), capacity() @@ -1070,30 +1094,27 @@ uint qHash(long double key, uint seed) noexcept \sa detach() */ -/*! \fn template <class Key, class T> void QHash<Key, T>::setSharable(bool sharable) - - \internal -*/ - /*! \fn template <class Key, class T> bool QHash<Key, T>::isSharedWith(const QHash &other) const \internal + + Returns true if the internal hash table of this QHash is shared with \a other, otherwise false. */ /*! \fn template <class Key, class T> void QHash<Key, T>::clear() - Removes all items from the hash. + Removes all items from the hash and frees up all memory used by it. \sa remove() */ -/*! \fn template <class Key, class T> int QHash<Key, T>::remove(const Key &key) +/*! \fn template <class Key, class T> bool QHash<Key, T>::remove(const Key &key) - Removes all the items that have the \a key from the hash. - Returns the number of items removed which is 1 if the key exists in the hash, - and 0 otherwise. + Removes the item that has the \a key from the hash. + Returns true if the key exists in the hash and the item has been removed, + and false otherwise. - \sa clear(), take(), QMultiHash::remove() + \sa clear(), take() */ /*! \fn template <class Key, class T> T QHash<Key, T>::take(const Key &key) @@ -1102,9 +1123,7 @@ uint qHash(long double key, uint seed) noexcept the value associated with it. If the item does not exist in the hash, the function simply - returns a \l{default-constructed value}. If there are multiple - items for \a key in the hash, only the most recently inserted one - is removed. + returns a \l{default-constructed value}. If you don't use the return value, remove() is more efficient. @@ -1119,23 +1138,14 @@ uint qHash(long double key, uint seed) noexcept \sa count(), QMultiHash::contains() */ -/*! \fn template <class Key, class T> T QHash<Key, T>::value(const Key &key) const +/*! \fn template <class Key, class T> T QHash<Key, T>::value(const Key &key, const T &defaultValue = T()) const + \overload Returns the value associated with the \a key. If the hash contains no item with the \a key, the function - returns a \l{default-constructed value}. If there are multiple - items for the \a key in the hash, the value of the most recently - inserted one is returned. - - \sa key(), values(), contains(), operator[]() -*/ - -/*! \fn template <class Key, class T> T QHash<Key, T>::value(const Key &key, const T &defaultValue) const - \overload - - If the hash contains no item with the given \a key, the function returns - \a defaultValue. + returns \a defaultValue, which is a \l{default-constructed value} if the + parameter has not been specified. */ /*! \fn template <class Key, class T> T &QHash<Key, T>::operator[](const Key &key) @@ -1145,9 +1155,7 @@ uint qHash(long double key, uint seed) noexcept If the hash contains no item with the \a key, the function inserts a \l{default-constructed value} into the hash with the \a key, and - returns a reference to it. If the hash contains multiple items - with the \a key, this function returns a reference to the most - recently inserted value. + returns a reference to it. \sa insert(), value() */ @@ -1159,27 +1167,14 @@ uint qHash(long double key, uint seed) noexcept Same as value(). */ -/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::uniqueKeys() const - \since 4.2 - \obsolete Use QMultiHash for storing multiple values with the same key. - - Returns a list containing all the keys in the map. 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 QMultiHash::uniqueKeys() -*/ - /*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys() const Returns a list containing all the keys in the hash, in an - arbitrary order. Keys that occur multiple times in the hash - (because the method is operating on a QMultiHash) also occur - multiple times in the list. + arbitrary order. The order is guaranteed to be the same as that used by values(). - \sa QMultiMap::uniqueKeys(), values(), key() + \sa values(), key() */ /*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys(const T &value) const @@ -1197,43 +1192,16 @@ uint qHash(long double key, uint seed) noexcept /*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values() const Returns a list containing all the values in the hash, in an - arbitrary order. 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. + arbitrary order. The order is guaranteed to be the same as that used by keys(). \sa keys(), value() */ -/*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values(const Key &key) const - \overload - \obsolete Use QMultiHash for storing multiple values with the same key. - - Returns a list of all the values associated with the \a key, - from the most recently inserted to the least recently inserted. - - \sa count(), insertMulti() -*/ - -/*! \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value) const - - Returns the first key mapped to \a value. - - If the hash contains no item with the \a value, the function - returns a \l{default-constructed value}{default-constructed key}. - - This function can be slow (\l{linear time}), because QHash's - internal data structure is optimized for fast lookup by key, not - by value. - - \sa value(), keys() -*/ - /*! - \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value, const Key &defaultKey) const + \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value, const Key &defaultKey = Key()) const \since 4.3 - \overload Returns the first key mapped to \a value, or \a defaultKey if the hash contains no item mapped to \a value. @@ -1247,7 +1215,7 @@ uint qHash(long double key, uint seed) noexcept Returns the number of items associated with the \a key. - \sa contains(), insertMulti() + \sa contains() */ /*! \fn template <class Key, class T> int QHash<Key, T>::count() const @@ -1396,7 +1364,7 @@ uint qHash(long double key, uint seed) noexcept from the hash, and returns an iterator to the next item in the hash. - Unlike remove() and take(), this function never causes QHash to + This function never causes QHash to rehash its internal data structure. This means that it can safely be called while iterating, and won't affect the order of items in the hash. For example: @@ -1426,7 +1394,7 @@ uint qHash(long double key, uint seed) noexcept \snippet code/src_corelib_tools_qhash.cpp 16 - \sa value(), values(), QMultiHash::find() + \sa value(), values() */ /*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &key) const @@ -1443,7 +1411,7 @@ uint qHash(long double key, uint seed) noexcept If the hash contains no item with the \a key, the function returns constEnd(). - \sa find(), QMultiHash::constFind() + \sa find() */ /*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &key, const T &value) @@ -1452,9 +1420,6 @@ uint qHash(long double key, uint seed) noexcept If there is already an item with the \a key, that item's value is replaced with \a value. - - If there are multiple items with the \a key, the most - recently inserted item's value is replaced with \a value. */ /*! \fn template <class Key, class T> void QHash<Key, T>::insert(const QHash &other) @@ -1469,29 +1434,6 @@ uint qHash(long double key, uint seed) noexcept final value of the key is undefined. */ -/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &key, const T &value) - \obsolete - - Inserts a new item with the \a key and a value of \a value. - - If there is already an item with the same key in the hash, this - function will simply create a new one. (This behavior is - different from insert(), which overwrites the value of an - existing item.) - - This function is obsolete. Use QMultiHash or QMultiMap instead. - - \sa insert(), values() -*/ - -/*! \fn template <class Key, class T> QHash &QHash<Key, T>::unite(const QHash &other) - \obsolete - - Inserts all the items in the \a other hash into this hash. If a - key is common to both hashes, the resulting hash will contain the - key multiple times. -*/ - /*! \fn template <class Key, class T> bool QHash<Key, T>::empty() const This function is provided for STL compatibility. It is equivalent @@ -1499,7 +1441,7 @@ uint qHash(long double key, uint seed) noexcept returns \c false. */ -/*! \fn template <class Key, class T> QPair<iterator, iterator> QHash<Key, T>::equal_range(const Key &key) +/*! \fn template <class Key, class T> QPair<iterator, iterator> QMultiHash<Key, T>::equal_range(const Key &key) \since 5.7 Returns a pair of iterators delimiting the range of values \c{[first, second)}, that @@ -1507,7 +1449,7 @@ uint qHash(long double key, uint seed) noexcept */ /*! - \fn template <class Key, class T> QPair<const_iterator, const_iterator> QHash<Key, T>::equal_range(const Key &key) const + \fn template <class Key, class T> QPair<const_iterator, const_iterator> QMultiHash<Key, T>::equal_range(const Key &key) const \overload \since 5.7 */ @@ -1604,7 +1546,7 @@ uint qHash(long double key, uint seed) noexcept /*! \class QHash::iterator \inmodule QtCore - \brief The QHash::iterator class provides an STL-style non-const iterator for QHash and QMultiHash. + \brief The QHash::iterator class provides an STL-style non-const iterator for QHash. QHash features both \l{STL-style iterators} and \l{Java-style iterators}. The STL-style iterators are more low-level and more @@ -1612,8 +1554,8 @@ uint qHash(long double key, uint seed) noexcept and, for developers who already know STL, have the advantage of familiarity. - QHash\<Key, T\>::iterator allows you to iterate over a QHash (or - QMultiHash) and to modify the value (but not the key) associated + QHash\<Key, T\>::iterator allows you to iterate over a QHash + and to modify the value (but not the key) associated with a particular key. If you want to iterate over a const QHash, you should use QHash::const_iterator. It is generally good practice to use QHash::const_iterator on a non-const QHash as @@ -1657,14 +1599,21 @@ uint qHash(long double key, uint seed) noexcept 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 hash. However, be - aware that any modification performed directly on the QHash has - the potential of dramatically changing the order in which the - items are stored in the hash, as they might cause QHash to rehash - its internal data structure. There is one notable exception: - QHash::erase(). This function can safely be called while - iterating, and won't affect the order of items in the hash. If you - need to keep iterators over a long period of time, we recommend + Multiple iterators can be used on the same hash. However, be aware + that any modification performed directly on the QHash (inserting and + removing items) can cause the iterators to become invalid. + + Inserting items into the hash or calling methods such as QHash::reserve() + or QHash::squeeze() can invalidate all iterators pointing into the hash. + Iterators are guaranteed to stay valid only as long as the QHash doesn't have + to grow/shrink its internal hash table. + Using any iterator after a rehashing operation has occurred will lead to undefined behavior. + + You can however safely use iterators to remove entries from the hash + using the QHash::erase() method. This function can safely be called while + iterating, and won't affect the order of items in the hash. + + If you need to keep iterators over a long period of time, we recommend that you use QMap rather than QHash. \warning Iterators on implicitly shared containers do not work @@ -1686,11 +1635,6 @@ uint qHash(long double key, uint seed) noexcept \sa QHash::begin(), QHash::end() */ -/*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator(void *node) - - \internal -*/ - /*! \fn template <class Key, class T> const Key &QHash<Key, T>::iterator::key() const Returns the current item's key as a const reference. @@ -1758,8 +1702,6 @@ uint qHash(long double key, uint seed) noexcept item. Calling this function on QHash::end() leads to undefined results. - - \sa operator--() */ /*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator++(int) @@ -1771,74 +1713,9 @@ uint qHash(long double key, uint seed) noexcept current item. */ -/*! - \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator--() - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - The prefix -- operator (\c{--i}) makes the preceding item - current and returns an iterator pointing to the new current item. - - Calling this function on QHash::begin() leads to undefined - results. - - \sa operator++() -*/ - -/*! - \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator--(int) - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - \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> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator+(int j) const - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - 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> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator-(int j) const - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - 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> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator+=(int j) - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - 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> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator-=(int j) - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - Makes the iterator go back by \a j items. (If \a j is negative, - the iterator goes forward.) - - \sa operator+=(), operator-() -*/ - /*! \class QHash::const_iterator \inmodule QtCore - \brief The QHash::const_iterator class provides an STL-style const iterator for QHash and QMultiHash. + \brief The QHash::const_iterator class provides an STL-style const iterator for QHash. QHash features both \l{STL-style iterators} and \l{Java-style iterators}. The STL-style iterators are more low-level and more @@ -1847,7 +1724,7 @@ uint qHash(long double key, uint seed) noexcept familiarity. QHash\<Key, T\>::const_iterator allows you to iterate over a - QHash (or a QMultiHash). If you want to modify the QHash as you + QHash. If you want to modify the QHash as you iterate over it, you must use QHash::iterator instead. It is generally good practice to use QHash::const_iterator on a non-const QHash as well, unless you need to change the QHash @@ -1869,11 +1746,14 @@ uint qHash(long double key, uint seed) noexcept recently to the least recently inserted value. Multiple iterators can be used on the same hash. However, be aware - that any modification performed directly on the QHash has the - potential of dramatically changing the order in which the items - are stored in the hash, as they might cause QHash to rehash its - internal data structure. If you need to keep iterators over a long - period of time, we recommend that you use QMap rather than QHash. + that any modification performed directly on the QHash (inserting and + removing items) can cause the iterators to become invalid. + + Inserting items into the hash or calling methods such as QHash::reserve() + or QHash::squeeze() can invalidate all iterators pointing into the hash. + Iterators are guaranteed to stay valid only as long as the QHash doesn't have + to grow/shrink its internal hash table. + Using any iterator after a rehashing operation has occurred will lead to undefined behavior. \warning Iterators on implicitly shared containers do not work exactly like STL-iterators. You should avoid copying a container @@ -1894,11 +1774,6 @@ uint qHash(long double key, uint seed) noexcept \sa QHash::constBegin(), QHash::constEnd() */ -/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(void *node) - - \internal -*/ - /*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(const iterator &other) Constructs a copy of \a other. @@ -1971,76 +1846,10 @@ uint qHash(long double key, uint seed) noexcept current item. */ -/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator--() - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - The prefix -- operator (\c{--i}) makes the preceding item - current and returns an iterator pointing to the new current item. - - Calling this function on QHash::begin() leads to undefined - results. - - \sa operator++() -*/ - -/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator--(int) - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - \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> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator+(int j) const - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - 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> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator-(int j) const - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - 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> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator+=(int j) - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - 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> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator-=(int j) - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - 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 QHash::key_iterator \inmodule QtCore \since 5.6 - \brief The QHash::key_iterator class provides an STL-style const iterator for QHash and QMultiHash keys. + \brief The QHash::key_iterator class provides an STL-style const iterator for QHash keys. QHash::key_iterator is essentially the same as QHash::const_iterator with the difference that operator*() and operator->() return a key @@ -2121,28 +1930,6 @@ uint qHash(long double key, uint seed) noexcept item. */ -/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator &QHash<Key, T>::key_iterator::operator--() - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - The prefix -- operator (\c{--i}) makes the preceding item - current and returns an iterator pointing to the new current item. - - Calling this function on QHash::keyBegin() leads to undefined - results. - - \sa operator++() -*/ - -/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator--(int) - \obsolete This operator is deprecated in order to align with std::unordered_map functionality. - - \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 QHash<Key, T>::key_iterator::base() const Returns the underlying const_iterator this key_iterator is based on. */ @@ -2150,7 +1937,7 @@ uint qHash(long double key, uint seed) noexcept /*! \typedef QHash::const_key_value_iterator \inmodule QtCore \since 5.10 - \brief The QMap::const_key_value_iterator typedef provides an STL-style const iterator for QHash and QMultiHash. + \brief The QHash::const_key_value_iterator typedef provides an STL-style const iterator for QHash. QHash::const_key_value_iterator is essentially the same as QHash::const_iterator with the difference that operator*() returns a key/value pair instead of a @@ -2162,7 +1949,7 @@ uint qHash(long double key, uint seed) noexcept /*! \typedef QHash::key_value_iterator \inmodule QtCore \since 5.10 - \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QHash and QMultiHash. + \brief The QHash::key_value_iterator typedef provides an STL-style iterator for QHash. QHash::key_value_iterator is essentially the same as QHash::iterator with the difference that operator*() returns a key/value pair instead of a @@ -2330,6 +2117,20 @@ uint qHash(long double key, uint seed) noexcept \sa keys(), values() */ +/*! \fn template <class Key, class T> T QMultiHash<Key, T>::value(const Key &key, const T &defaultValue = T()) const + \overload + + Returns the value associated with the \a key. + + If the hash contains no item with the \a key, the function + returns \a defaultValue, which is a \l{default-constructed value} if the + parameter has not been specified. + + If there are multiple + items for the \a key in the hash, the value of the most recently + inserted one is returned. +*/ + /*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values(const Key &key) const \overload @@ -2339,6 +2140,20 @@ uint qHash(long double key, uint seed) noexcept \sa count(), insert() */ +/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::operator[](const Key &key) + + Returns the value associated with the \a key as a modifiable reference. + + If the hash contains no item with the \a key, the function inserts + a \l{default-constructed value} into the hash with the \a key, and + returns a reference to it. + + If the hash contains multiple items with the \a key, this function returns + a reference to the most recently inserted value. + + \sa insert(), value() +*/ + /*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::operator+=(const QMultiHash &other) Inserts all the items in the \a other hash into this hash @@ -2363,7 +2178,7 @@ uint qHash(long double key, uint seed) noexcept Returns \c true if the hash contains an item with the \a key and \a value; otherwise returns \c false. - \sa QHash::contains() + \sa contains() */ /*! @@ -2373,7 +2188,57 @@ uint qHash(long double key, uint seed) noexcept Removes all the items that have the \a key and the value \a value from the hash. Returns the number of items removed. - \sa QHash::remove() + \sa remove() +*/ + +/*! \fn template <class Key, class T> T QMultiHash<Key, T>::take(const Key &key) + + Removes the item with the \a key from the hash and returns + the value associated with it. + + If the item does not exist in the hash, the function simply + returns a \l{default-constructed value}. If there are multiple + items for \a key in the hash, only the most recently inserted one + is removed. + + If you don't use the return value, remove() is more efficient. + + \sa remove() +*/ + +/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::keys() const + + Returns a list containing all the keys in the hash, in an + arbitrary order. Keys that occur multiple times in the hash + also occur multiple times in the list. + + The order is guaranteed to be the same as that used by values(). + + \sa values(), key() +*/ + +/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values() const + + Returns a list containing all the values in the hash, in an + arbitrary order. 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. + + The order is guaranteed to be the same as that used by keys(). + + \sa keys(), value() +*/ + +/*! + \fn template <class Key, class T> Key QMultiHash<Key, T>::key(const T &value, const Key &defaultKey = Key()) const + \since 4.3 + + Returns the first key mapped to \a value, or \a defaultKey if the + hash contains no item mapped to \a value. + + This function can be slow (\l{linear time}), because QMultiHash's + internal data structure is optimized for fast lookup by key, not + by value. */ /*! @@ -2382,11 +2247,11 @@ uint qHash(long double key, uint seed) noexcept Returns the number of items with the \a key and \a value. - \sa QHash::count() + \sa count() */ /*! - \fn template <class Key, class T> typename QHash<Key, T>::iterator QMultiHash<Key, T>::find(const Key &key, const T &value) + \fn template <class Key, class T> typename QMultiHash<Key, T>::iterator QMultiHash<Key, T>::find(const Key &key, const T &value) \since 4.3 Returns an iterator pointing to the item with the \a key and \a value. @@ -2394,18 +2259,16 @@ uint qHash(long double key, uint seed) noexcept If the hash contains multiple items with the \a key and \a value, the iterator returned points to the most recently inserted item. - - \sa QHash::find() */ /*! - \fn template <class Key, class T> typename QHash<Key, T>::const_iterator QMultiHash<Key, T>::find(const Key &key, const T &value) const + \fn template <class Key, class T> typename QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::find(const Key &key, const T &value) const \since 4.3 \overload */ /*! - \fn template <class Key, class T> typename QHash<Key, T>::const_iterator QMultiHash<Key, T>::constFind(const Key &key, const T &value) const + \fn template <class Key, class T> typename QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constFind(const Key &key, const T &value) const \since 4.3 Returns an iterator pointing to the item with the \a key and the @@ -2413,8 +2276,582 @@ uint qHash(long double key, uint seed) noexcept If the hash contains no such item, the function returns constEnd(). +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::begin() + + Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in + the hash. - \sa QHash::constFind() + \sa constBegin(), end() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::begin() const + + \overload +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::cbegin() const + \since 5.0 + + Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item + in the hash. + + \sa begin(), cend() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constBegin() const + + Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item + in the hash. + + \sa begin(), constEnd() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::keyBegin() const + \since 5.6 + + Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key + in the hash. + + \sa keyEnd() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::end() + + Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item + after the last item in the hash. + + \sa begin(), constEnd() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::end() const + + \overload +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<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 hash. + + \sa constBegin(), end() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<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 hash. + + \sa cbegin(), end() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<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 hash. + + \sa keyBegin() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_value_iterator QMultiHash<Key, T>::keyValueBegin() + \since 5.10 + + Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry + in the hash. + + \sa keyValueEnd() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_value_iterator QMultiHash<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 hash. + + \sa keyValueBegin() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::keyValueBegin() const + \since 5.10 + + Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry + in the hash. + + \sa keyValueEnd() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::constKeyValueBegin() const + \since 5.10 + + Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry + in the hash. + + \sa keyValueBegin() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<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 hash. + + \sa keyValueBegin() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<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 hash. + + \sa constKeyValueBegin() +*/ + + +/*! \class QMultiHash::iterator + \inmodule QtCore + \brief The QMultiHash::iterator class provides an STL-style non-const iterator for QMultiHash. + + QMultiHash 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. + + QMultiHash\<Key, T\>::iterator allows you to iterate over a QMultiHash + and to modify the value (but not the key) associated + with a particular key. If you want to iterate over a const QMultiHash, + you should use QMultiHash::const_iterator. It is generally good + practice to use QMultiHash::const_iterator on a non-const QMultiHash as + well, unless you need to change the QMultiHash through the iterator. + Const iterators are slightly faster, and can improve code + readability. + + The default QMultiHash::iterator constructor creates an uninitialized + iterator. You must initialize it using a QMultiHash function like + QMultiHash::begin(), QMultiHash::end(), or QMultiHash::find() before you can + start iterating. Here's a typical loop that prints all the (key, + value) pairs stored in a hash: + + \snippet code/src_corelib_tools_qhash.cpp 17 + + Unlike QMap, which orders its items by key, QMultiHash stores its + items in an arbitrary order. + + Let's see a few examples of things we can do with a + QMultiHash::iterator that we cannot do with a QMultiHash::const_iterator. + Here's an example that increments every value stored in the QMultiHash + by 2: + + \snippet code/src_corelib_tools_qhash.cpp 18 + + 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_qhash.cpp 19 + + The call to QMultiHash::erase() removes the item pointed to by the + iterator from the hash, and returns an iterator to the next item. + Here's another way of removing an item while iterating: + + \snippet code/src_corelib_tools_qhash.cpp 20 + + It might be tempting to write code like this: + + \snippet code/src_corelib_tools_qhash.cpp 21 + + 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 hash. However, be aware + that any modification performed directly on the QHash (inserting and + removing items) can cause the iterators to become invalid. + + Inserting items into the hash or calling methods such as QHash::reserve() + or QHash::squeeze() can invalidate all iterators pointing into the hash. + Iterators are guaranteed to stay valid only as long as the QHash doesn't have + to grow/shrink its internal hash table. + Using any iterator after a rehashing operation has occurred will lead to undefined behavior. + + You can however safely use iterators to remove entries from the hash + using the QHash::erase() method. This function can safely be called while + iterating, and won't affect the order of items in the hash. + + If you need to keep iterators over a long period of time, we recommend + that you use QMultiMap rather than QHash. + + \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 QMultiHash::const_iterator, QMultiHash::key_iterator, QMutableHashIterator +*/ + +/*! \fn template <class Key, class T> QMultiHash<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 QMultiHash::begin(), QMultiHash::end() +*/ + +/*! \fn template <class Key, class T> const Key &QMultiHash<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 QMultiHash::erase() + followed by QMultiHash::insert(). + + \sa value() +*/ + +/*! \fn template <class Key, class T> T &QMultiHash<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_qhash.cpp 22 + + \sa key(), operator*() +*/ + +/*! \fn template <class Key, class T> T &QMultiHash<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 *QMultiHash<Key, T>::iterator::operator->() const + + Returns a pointer to the current item's value. + + \sa value() +*/ + +/*! + \fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator==(const iterator &other) const + \fn template <class Key, class T> bool QMultiHash<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 QMultiHash<Key, T>::iterator::operator!=(const iterator &other) const + \fn template <class Key, class T> bool QMultiHash<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> QMultiHash<Key, T>::iterator &QMultiHash<Key, T>::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 QMultiHash::end() leads to undefined results. +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::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 previously + current item. +*/ + +/*! \class QMultiHash::const_iterator + \inmodule QtCore + \brief The QMultiHash::const_iterator class provides an STL-style const iterator for QMultiHash. + + QMultiHash 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. + + QMultiHash\<Key, T\>::const_iterator allows you to iterate over a + QMultiHash. If you want to modify the QMultiHash as you + iterate over it, you must use QMultiHash::iterator instead. It is + generally good practice to use QMultiHash::const_iterator on a + non-const QMultiHash as well, unless you need to change the QMultiHash + through the iterator. Const iterators are slightly faster, and + can improve code readability. + + The default QMultiHash::const_iterator constructor creates an + uninitialized iterator. You must initialize it using a QMultiHash + function like QMultiHash::constBegin(), QMultiHash::constEnd(), or + QMultiHash::find() before you can start iterating. Here's a typical + loop that prints all the (key, value) pairs stored in a hash: + + \snippet code/src_corelib_tools_qhash.cpp 23 + + Unlike QMap, which orders its items by key, QMultiHash stores its + items in an arbitrary order. The only guarantee is that items that + share the same key (because they were inserted using + a QMultiHash) will appear consecutively, from the most + recently to the least recently inserted value. + + Multiple iterators can be used on the same hash. However, be aware + that any modification performed directly on the QHash (inserting and + removing items) can cause the iterators to become invalid. + + Inserting items into the hash or calling methods such as QHash::reserve() + or QHash::squeeze() can invalidate all iterators pointing into the hash. + Iterators are guaranteed to stay valid only as long as the QHash doesn't have + to grow/shrink it's internal hash table. + Using any iterator after a rehashing operation ahs occurred will lead to undefined behavior. + + You can however safely use iterators to remove entries from the hash + using the QHash::erase() method. This function can safely be called while + iterating, and won't affect the order of items in the hash. + + If you need to keep iterators over a long period of time, we recommend + that you use QMap rather than QHash. + + \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 QMultiHash::iterator, QMultiHashIterator +*/ + +/*! \fn template <class Key, class T> QMultiHash<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 QMultiHash::constBegin(), QMultiHash::constEnd() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator::const_iterator(const iterator &other) + + Constructs a copy of \a other. +*/ + +/*! \fn template <class Key, class T> const Key &QMultiHash<Key, T>::const_iterator::key() const + + Returns the current item's key. + + \sa value() +*/ + +/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::const_iterator::value() const + + Returns the current item's value. + + \sa key(), operator*() +*/ + +/*! \fn template <class Key, class T> const T &QMultiHash<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 *QMultiHash<Key, T>::const_iterator::operator->() const + + Returns a pointer to the current item's value. + + \sa value() +*/ + +/*! \fn template <class Key, class T> bool QMultiHash<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 QMultiHash<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> QMultiHash<Key, T>::const_iterator &QMultiHash<Key, T>::const_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 QMultiHash::end() leads to undefined results. + + \sa operator--() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::const_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 previously + current item. +*/ + +/*! \class QMultiHash::key_iterator + \inmodule QtCore + \since 5.6 + \brief The QMultiHash::key_iterator class provides an STL-style const iterator for QMultiHash keys. + + QMultiHash::key_iterator is essentially the same as QMultiHash::const_iterator + with the difference that operator*() and operator->() return a key + instead of a value. + + For most uses QMultiHash::iterator and QMultiHash::const_iterator should be used, + you can easily access the key by calling QMultiHash::iterator::key(): + + \snippet code/src_corelib_tools_qhash.cpp 27 + + However, to have interoperability between QMultiHash's keys and STL-style + algorithms we need an iterator that dereferences to a key instead + of a value. With QMultiHash::key_iterator we can apply an algorithm to a + range of keys without having to call QMultiHash::keys(), which is inefficient + as it costs one QMultiHash iteration and memory allocation to create a temporary + QList. + + \snippet code/src_corelib_tools_qhash.cpp 28 + + QMultiHash::key_iterator is const, it's not possible to modify the key. + + The default QMultiHash::key_iterator constructor creates an uninitialized + iterator. You must initialize it using a QMultiHash function like + QMultiHash::keyBegin() or QMultiHash::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 QMultiHash::const_iterator, QMultiHash::iterator +*/ + +/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::key_iterator::operator*() const + + Returns the current item's key. +*/ + +/*! \fn template <class Key, class T> const T *QMultiHash<Key, T>::key_iterator::operator->() const + + Returns a pointer to the current item's key. +*/ + +/*! \fn template <class Key, class T> bool QMultiHash<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 QMultiHash<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> QMultiHash<Key, T>::key_iterator &QMultiHash<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 QMultiHash::keyEnd() leads to undefined results. + + \sa operator--() +*/ + +/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<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> const_iterator QMultiHash<Key, T>::key_iterator::base() const + Returns the underlying const_iterator this key_iterator is based on. +*/ + +/*! \typedef QMultiHash::const_key_value_iterator + \inmodule QtCore + \since 5.10 + \brief The QMap::const_key_value_iterator typedef provides an STL-style const iterator for QMultiHash and QMultiHash. + + QMultiHash::const_key_value_iterator is essentially the same as QMultiHash::const_iterator + with the difference that operator*() returns a key/value pair instead of a + value. + + \sa QKeyValueIterator +*/ + +/*! \typedef QMultiHash::key_value_iterator + \inmodule QtCore + \since 5.10 + \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QMultiHash and QMultiHash. + + QMultiHash::key_value_iterator is essentially the same as QMultiHash::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 QMultiHash<Key, T>& hash) + \relates QMultiHash + + Writes the hash \a hash to stream \a out. + + This function requires the key and value types to implement \c + operator<<(). + + \sa {Serializing Qt Data Types} +*/ + +/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QMultiHash<Key, T> &hash) + \relates QMultiHash + + Reads a hash from stream \a in into \a hash. + + This function requires the key and value types to implement \c + operator>>(). + + \sa {Serializing Qt Data Types} */ /*! |