1// Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
2// Copyright (C) 2020 The Qt Company Ltd.
3// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GFDL-1.3-no-invariants-only
8 \brief The QMultiMap class is a template class that provides an associative array with multiple equivalent keys.
15 QMultiMap<Key, T> is one of Qt's generic \l{container classes}. It
16 stores (key, value) pairs and provides fast lookup by key.
18 QMultiMap and QMultiHash provide very similar functionality. The
22 \li QMultiHash provides average faster lookups than QMultiMap. (See \l{Algorithmic
23 Complexity} for details.)
24 \li When iterating over a QMultiHash, the items are arbitrarily ordered.
25 With QMultiMap, the items are always sorted by key.
26 \li The key type of a QMultiHash must provide operator==() and a global
27 qHash(Key) function. The key type of a QMultiMap must provide
28 operator<() specifying a total order. Since Qt 5.8.1 it is also safe
29 to use a pointer type as key, even if the underlying operator<()
30 does not provide a total order.
33 Here's an example QMultiMap with QString keys and \c int values:
34 \snippet code/src_corelib_tools_qmultimap.cpp 0
36 To insert a (key, value) pair into the multi map, you can use insert():
38 \snippet code/src_corelib_tools_qmultimap.cpp 2
40 This inserts the following three (key, value) pairs into the
41 QMultiMap: ("a", 1), ("b", 3), ("c", 7), and ("c", -5); note
42 that duplicate keys are allowed.
44 To look up a value, use find() or value():
46 \snippet code/src_corelib_tools_qmultimap.cpp 3
48 If there is no item with the specified key in the map, these
49 functions return a \l{default-constructed value}.
51 If you want to check whether the map contains a certain key, use
54 \snippet code/src_corelib_tools_qmultimap.cpp 4
56 There is also a value() overload that uses its second argument as
57 a default value if there is no item with the specified key:
59 \snippet code/src_corelib_tools_qmultimap.cpp 5
61 If you want to navigate through all the (key, value) pairs stored
62 in a QMultiMap, you can use an iterator. QMultiMap provides both
63 \l{Java-style iterators} (QMultiMapIterator and QMutableMultiMapIterator)
64 and \l{STL-style iterators} (QMultiMap::const_iterator and
65 QMultiMap::iterator). Here's how to iterate over a QMultiMap<QString, int>
66 using a Java-style iterator:
68 \snippet code/src_corelib_tools_qmultimap.cpp 7
70 Here's the same code, but using an STL-style iterator this time:
72 \snippet code/src_corelib_tools_qmultimap.cpp 8
74 The items are traversed in ascending key order.
76 A QMultiMap allows multiple values per key. If you call
77 insert() with a key that already exists in the map, a
78 new (key, value) pair will be inserted. For example:
80 \snippet code/src_corelib_tools_qmultimap.cpp 9
82 If you want to retrieve all the values for a single key, you can
83 use values(const Key &key), which returns a QList<T>:
85 \snippet code/src_corelib_tools_qmultimap.cpp 10
87 The items that share the same key are available from most
88 recently to least recently inserted. Another approach is to call
89 find() to get the STL-style iterator for the first item with a
90 key and iterate from there:
92 \snippet code/src_corelib_tools_qmultimap.cpp 11
94 If you only need to extract the values from a map (not the keys),
95 you can also use range-based for:
97 \snippet code/src_corelib_tools_qmultimap.cpp 12
99 Items can be removed from the multi map in several ways. One way is to
100 call remove(); this will remove any item with the given key.
101 Another way is to use QMutableMultiMapIterator::remove(). In addition,
102 you can clear the entire map using clear().
104 It is possible to merge two multi maps by calling unite(), by
105 using operator+(), and by using operator+=(). Example:
107 \snippet code/src_corelib_tools_qmultimap.cpp 25
109 QMultiMap's key and value data types must be \l{assignable data
110 types}. This covers most data types you are likely to encounter,
111 but the compiler won't let you, for example, store a QWidget as a
112 value; instead, store a QWidget *. In addition, QMultiMap's key type
113 must provide operator<(). QMap uses it to keep its items sorted,
114 and assumes that two keys \c x and \c y are equal if neither \c{x
115 < y} nor \c{y < x} is true.
118 \snippet code/src_corelib_tools_qmultimap.cpp 13
120 In the example, we start by comparing the employees' names. If
121 they're equal, we compare their dates of birth to break the tie.
123 \sa QMultiMapIterator, QMutableMultiMapIterator, QMultiHash
126/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap()
128 Constructs an empty multi map.
134 \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(QMultiMap<Key, T> &&other)
136 Move-constructs a QMultiMap instance, making it point at the same
137 object that \a other was pointing to.
142/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const QMultiMap<Key, T> &other)
144 Constructs a copy of \a other.
146 This operation occurs in \l{constant time}, because QMultiMap is
147 \l{implicitly shared}. This makes returning a QMultiMap from a
148 function very fast. If a shared instance is modified, it will be
149 copied (copy-on-write), and this takes \l{linear time}.
154/*! \fn template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::operator=(const QMultiMap<Key, T> &other)
156 Assigns \a other to this multi map and returns a reference to this multi map.
160 \fn template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::operator=(QMultiMap<Key, T> &&other)
162 Move-assigns \a other to this QMultiMap instance.
167/*! \fn template <class Key, class T> QMultiMap<Key, T>::~QMultiMap()
169 Destroys the multi map. References to the values in the multi map, and all
170 iterators over this multi map, become invalid.
173/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(std::initializer_list<std::pair<Key,T> > list)
176 Constructs a multi map with a copy of each of the elements in the
177 initializer list \a list.
180/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const QMap<Key, T> &other)
183 Constructs a multi map as a copy of \a other.
186/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(QMap<Key, T> &&other)
189 If \a other is shared, constructs a multi map as a copy of \a other.
190 Otherwise, constructs a multi map by moving the elements from \a other.
193/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const std::multimap<Key, T> &other)
195 Constructs a copy of \a other.
200/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(std::multimap<Key, T> &&other)
202 Constructs a multi map by moving from \a other.
207/*! \fn template <class Key, class T> std::multimap<Key, T> QMultiMap<Key, T>::toStdMap() const
208 \deprecated Use toStdMultiMap() instead.
210 Returns an STL multi map equivalent to this QMultiMap.
213/*! \fn template <class Key, class T> std::multimap<Key, T> QMultiMap<Key, T>::toStdMultiMap() const &
215 Returns an STL multi map equivalent to this QMultiMap.
218/*! \fn template <class Key, class T> void QMultiMap<Key, T>::swap(QMultiMap<Key, T> &other)
221 Swaps multi map \a other with this multi map. This operation is very
222 fast and never fails.
225/*! \fn template<class Key, class T> bool QMultiMap<Key, T>::operator==(const QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs)
227 Returns \c true if \a lhs is equal to \a rhs; otherwise returns
230 Two multi maps are considered equal if they contain the same (key,
231 value) pairs, in the same order (which matters for duplicate keys).
233 This function requires the key and the value types to implement \c
239/*! \fn template<class Key, class T> bool QMultiMap<Key, T>::operator!=(const QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs)
241 Returns \c true if \a lhs is not equal to \a rhs; otherwise
244 Two multi maps are considered equal if they contain the same (key,
245 value) pairs, in the same order (which matters for duplicate keys).
247 This function requires the key and the value types to implement \c
253/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::size() const
255 Returns the number of (key, value) pairs in the multi map.
257 \sa isEmpty(), count()
261 \fn template <class Key, class T> bool QMultiMap<Key, T>::isEmpty() const
263 Returns \c true if the multi map contains no items; otherwise returns
269/*! \fn template <class Key, class T> void QMultiMap<Key, T>::detach()
273 Detaches this map from any other multi maps with which it may share
279/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::isDetached() const
283 Returns \c true if the multi map's internal data isn't shared with any
284 other map object; otherwise returns \c false.
289/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::isSharedWith(const QMultiMap<Key, T> &other) const
294/*! \fn template <class Key, class T> void QMultiMap<Key, T>::clear()
296 Removes all items from the multi map.
301/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::remove(const Key &key)
303 Removes all the items that have the key \a key from the multi map.
304 Returns the number of items removed.
309/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::remove(const Key &key, const T &value)
311 Removes all the items that have the key \a key and value \a value
313 Returns the number of items removed.
318/*! \fn template <class Key, class T> template <typename Predicate> size_type QMultiMap<Key, T>::removeIf(Predicate pred)
321 Removes all elements for which the predicate \a pred returns true
324 The function supports predicates which take either an argument of
325 type \c{QMultiMap<Key, T>::iterator}, or an argument of type
326 \c{std::pair<const Key &, T &>}.
328 Returns the number of elements removed, if any.
333/*! \fn template <class Key, class T> T QMultiMap<Key, T>::take(const Key &key)
335 Removes the item with the key \a key from the multi map and returns
336 the value associated with it.
338 If the item does not exist in the multi map, the function simply
339 returns a \l{default-constructed value}. If there are multiple
340 items for \a key in the map, only the most recently inserted one
341 is removed and returned.
343 If you don't use the return value, remove() is more efficient.
348/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::contains(const Key &key) const
350 Returns \c true if the multi map contains an item with key \a key;
351 otherwise returns \c false.
356/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
359 Returns \c true if the multi map contains an item with key \a key
360 and value \a value; otherwise returns \c false.
366 \fn template <class Key, class T> Key QMultiMap<Key, T>::key(const T &value, const Key &defaultKey) const
370 Returns the first key with value \a value, or \a defaultKey if
371 the multi map contains no item with value \a value. If no \a defaultKey
372 is provided the function returns a
373 \l{default-constructed value}{default-constructed key}.
375 This function can be slow (\l{linear time}), because QMultiMap's
376 internal data structure is optimized for fast lookup by key, not
382/*! \fn template <class Key, class T> T QMultiMap<Key, T>::value(const Key &key, const T &defaultValue) const
384 Returns the value associated with the key \a key.
386 If the multi map contains no item with key \a key, the function returns
387 \a defaultValue. If no \a defaultValue is specified, the function
388 returns a \l{default-constructed value}. If there are multiple
389 items for \a key in the multi map, the value of the most recently
390 inserted one is returned.
392 \sa key(), values(), contains()
395/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::keys() const
397 Returns a list containing all the keys in the multi map in ascending
398 order. Keys that occur multiple times in the multi map
399 also occur multiple times in the list.
401 The order is guaranteed to be the same as that used by values().
403 This function creates a new list, in \l {linear time}. The time and memory
404 use that entails can be avoided by iterating from \l keyBegin() to
410/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::keys(const T &value) const
414 Returns a list containing all the keys associated with value \a
415 value in ascending order.
417 This function can be slow (\l{linear time}), because QMultiMap's
418 internal data structure is optimized for fast lookup by key, not
422/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::uniqueKeys() const
425 Returns a list containing all the keys in the map in ascending
426 order. Keys that occur multiple times in the map occur only
427 once in the returned list.
430/*! \fn template <class Key, class T> QList<T> QMultiMap<Key, T>::values() const
432 Returns a list containing all the values in the map, in ascending
433 order of their keys. If a key is associated with multiple values,
434 all of its values will be in the list, and not just the most
435 recently inserted one.
440/*! \fn template <class Key, class T> QList<T> QMultiMap<Key, T>::values(const Key &key) const
442 Returns a list containing all the values associated with key
443 \a key, from the most recently inserted to the least recently
449/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count() const
456/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count(const Key &key) const
458 Returns the number of items associated with key \a key.
460 \sa contains(), QMultiMap::count()
463/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count(const Key &key, const T &value) const
465 Returns the number of items with key \a key and value \a value.
467 \sa contains(), QMultiMap::count()
471/*! \fn template <class Key, class T> const Key &QMultiMap<Key, T>::firstKey() const
474 Returns a reference to the smallest key in the multi map.
475 This function assumes that the multi map is not empty.
477 This executes in \l{constant time}.
479 \sa lastKey(), first(), keyBegin(), isEmpty()
482/*! \fn template <class Key, class T> const Key &QMultiMap<Key, T>::lastKey() const
485 Returns a reference to the largest key in the multi map.
486 This function assumes that the multi map is not empty.
488 This executes in \l{logarithmic time}.
490 \sa firstKey(), last(), keyEnd(), isEmpty()
493/*! \fn template <class Key, class T> T &QMultiMap<Key, T>::first()
496 Returns a reference to the first value in the multi map, that is the value mapped
497 to the smallest key. This function assumes that the multi map is not empty.
499 When unshared (or const version is called), this executes in \l{constant time}.
501 \sa last(), firstKey(), isEmpty()
504/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::first() const
510/*! \fn template <class Key, class T> T &QMultiMap<Key, T>::last()
513 Returns a reference to the last value in the multi map, that is the value mapped
514 to the largest key. This function assumes that the map is not empty.
516 When unshared (or const version is called), this executes in \l{logarithmic time}.
518 \sa first(), lastKey(), isEmpty()
521/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::last() const
527/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::begin()
529 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
532 \sa constBegin(), end()
535/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::begin() const
540/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::cbegin() const
543 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
549/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::constBegin() const
551 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
554 \sa begin(), constEnd()
557/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<Key, T>::keyBegin() const
560 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
563 \sa keyEnd(), firstKey()
566/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::end()
568 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
569 after the last item in the multi map.
571 \sa begin(), constEnd()
574/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::end() const
579/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::cend() const
582 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
583 item after the last item in the multi map.
588/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::constEnd() const
590 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
591 item after the last item in the multi map.
593 \sa constBegin(), end()
596/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<Key, T>::keyEnd() const
599 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
600 item after the last key in the multi map.
602 \sa keyBegin(), lastKey()
606/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_value_iterator QMultiMap<Key, T>::keyValueBegin()
609 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
615/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_value_iterator QMultiMap<Key, T>::keyValueEnd()
618 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
619 entry after the last entry in the multi map.
624/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<Key, T>::keyValueBegin() const
627 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
633/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<Key, T>::constKeyValueBegin() const
636 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
642/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<Key, T>::keyValueEnd() const
645 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
646 entry after the last entry in the multi map.
651/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<Key, T>::constKeyValueEnd() const
654 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
655 entry after the last entry in the multi map.
657 \sa constKeyValueBegin()
660/*! \fn template <class Key, class T> auto QMultiMap<Key, T>::asKeyValueRange() &
661 \fn template <class Key, class T> auto QMultiMap<Key, T>::asKeyValueRange() const &
662 \fn template <class Key, class T> auto QMultiMap<Key, T>::asKeyValueRange() &&
663 \fn template <class Key, class T> auto QMultiMap<Key, T>::asKeyValueRange() const &&
666 Returns a range object that allows iteration over this multi map as
667 key/value pairs. For instance, this range object can be used in a
668 range-based for loop, in combination with a structured binding declaration:
670 \snippet code/src_corelib_tools_qmultimap.cpp 26
672 Note that both the key and the value obtained this way are
673 references to the ones in the multi map. Specifically, mutating the value
674 will modify the map itself.
676 \sa QKeyValueIterator
679/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::erase(const_iterator pos)
681 Removes the (key, value) pair pointed to by the iterator \a pos
682 from the multi map, and returns an iterator to the next item in the
685 \note The iterator \a pos must be valid and dereferenceable.
690/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::erase(const_iterator first, const_iterator last)
693 Removes the (key, value) pairs pointed to by the iterator range
694 [\a first, \a last) from the multi map.
695 Returns an iterator to the item in the multi map following the last
698 \note The range \c {[first, last)} \e must be a valid range in \c {*this}.
703/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::find(const Key &key)
705 Returns an iterator pointing to the item with key \a key in the
708 If the multi map contains no item with key \a key, the function
711 If the map contains multiple items with key \a key, this
712 function returns an iterator that points to the most recently
713 inserted value. The other values are accessible by incrementing
714 the iterator. For example, here's some code that iterates over all
715 the items with the same key:
717 \snippet code/src_corelib_tools_qmultimap.cpp 11
719 \sa constFind(), value(), values(), lowerBound(), upperBound()
722/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::find(const Key &key) const
727/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::constFind(const Key &key) const
730 Returns an const iterator pointing to the item with key \a key in the
733 If the multi map contains no item with key \a key, the function
736 \sa find(), QMultiMap::constFind()
740 \fn template <class Key, class T> typename QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::find(const Key &key, const T &value) const
744 Returns a const iterator pointing to the item with the given \a key and
747 If the map contains no such item, the function returns end().
749 If the map contains multiple items with the specified \a key, this
750 function returns a const iterator that points to the most recently
755 \fn template <class Key, class T> typename QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::constFind(const Key &key, const T &value) const
758 Returns an iterator pointing to the item with key \a key and the
759 value \a value in the map.
761 If the map contains no such item, the function returns
764 \sa QMap::constFind()
767/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::lowerBound(const Key &key)
769 Returns an iterator pointing to the first item with key \a key in
770 the map. If the map contains no item with key \a key, the
771 function returns an iterator to the nearest item with a greater
775 \snippet code/src_corelib_tools_qmultimap.cpp 15
777 If the map contains multiple items with key \a key, this
778 function returns an iterator that points to the most recently
779 inserted value. The other values are accessible by incrementing
780 the iterator. For example, here's some code that iterates over all
781 the items with the same key:
783 \snippet code/src_corelib_tools_qmultimap.cpp 16
785 \sa upperBound(), find()
788/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::lowerBound(const Key &key) const
793/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::upperBound(const Key &key)
795 Returns an iterator pointing to the item that immediately follows
796 the last item with key \a key in the map. If the map contains no
797 item with key \a key, the function returns an iterator to the
798 nearest item with a greater key.
801 \snippet code/src_corelib_tools_qmultimap.cpp 17
803 \sa lowerBound(), find()
806/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::upperBound(const Key &key) const
811/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &key, const T &value)
813 Inserts a new item with the key \a key and a value of \a value.
815 If there is already an item with the same key in the map, this
816 function will simply create a new one. (This behavior is
817 different from replace(), which overwrites the value of an
820 Returns an iterator pointing to the new element.
825/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const_iterator pos, const Key &key, const T &value)
828 Inserts a new item with the key \a key and value \a value and with hint \a pos
829 suggesting where to do the insert.
831 If constBegin() is used as hint it indicates that the \a key is less than any key in the multi map
832 while constEnd() suggests that the \a key is (strictly) larger than any key in the multi map.
833 Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key().
834 If the hint \a pos is wrong it is ignored and a regular insert is done.
836 If the hint is correct and the multi map is unshared, the insert executes in amortized \l{constant time}.
838 If there is already an item with the same key in the map, this function will simply create a new one.
840 When creating a multi map from sorted data inserting the largest key first with constBegin()
841 is faster than inserting in sorted order with constEnd(), since constEnd() - 1 (which is needed
842 to check if the hint is valid) needs \l{logarithmic time}.
844 Returns an iterator pointing to the new element.
846 \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might
847 crash but there is also a risk that it will silently corrupt both the multi map and the \a pos multi map.
850#if QT_DEPRECATED_SINCE(6, 0)
851/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insertMulti(const Key &key, const T &value)
852 \deprecated Use insert() instead.
854 Inserts a new item with the key \a key and a value of \a value, and returns an iterator pointing to the new item.
857/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insertMulti(const_iterator pos, const Key &key, const T &value)
858 \deprecated Use insert() instead.
861 Inserts a new item with the key \a key and value \a value and with hint \a pos
862 suggesting where to do the insert.
865/*! \fn template <class Key, class T> void QMultiMap<Key, T>::insert(const QMultiMap<Key, T> &map)
867 \deprecated Use unite() instead.
869 Inserts all the items in \a map into this map.
872/*! \fn template <class Key, class T> void QMultiMap<Key, T>::insert(QMultiMap<Key, T> &&map)
874 \deprecated Use unite() instead.
877 Moves all the items from \a map into this map.
879 If \a map is shared, then the items will be copied instead.
883/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::replace(const Key &key, const T &value)
885 Inserts a new item with the key \a key and a value of \a value.
887 If there is already an item with the key \a key, that item's value
888 is replaced with \a value.
890 If there are multiple items with the key \a key, the most
891 recently inserted item's value is replaced with \a value.
893 Returns an iterator pointing to the new/updated element.
898/*! \typedef QMultiMap::Iterator
900 Qt-style synonym for QMultiMap::iterator.
903/*! \typedef QMultiMap::ConstIterator
905 Qt-style synonym for QMultiMap::const_iterator.
908/*! \typedef QMultiMap::difference_type
910 Typedef for ptrdiff_t. Provided for STL compatibility.
913/*! \typedef QMultiMap::key_type
915 Typedef for Key. Provided for STL compatibility.
918/*! \typedef QMultiMap::mapped_type
920 Typedef for T. Provided for STL compatibility.
923/*! \typedef QMultiMap::size_type
925 Typedef for int. Provided for STL compatibility.
929 \fn template <class Key, class T> bool QMultiMap<Key, T>::empty() const
931 This function is provided for STL compatibility. It is equivalent
932 to isEmpty(), returning true if the map is empty; otherwise
937 \fn template <class Key, class T> std::pair<typename QMultiMap<Key, T>::iterator, typename QMultiMap<Key, T>::iterator> QMultiMap<Key, T>::equal_range(const Key &key)
939 Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
940 are stored under \a key.
944 \fn template <class Key, class T> std::pair<typename QMultiMap<Key, T>::const_iterator, typename QMultiMap<Key, T>::const_iterator> QMultiMap<Key, T>::equal_range(const Key &key) const
950 \fn template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other)
952 Inserts all the items in the \a other map into this map. If a
953 key is common to both maps, the resulting map will contain the
958 \fn template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::unite(QMultiMap<Key, T> &&other)
960 Moves all the items from the \a other map into this map. If a
961 key is common to both maps, the resulting map will contain the
964 If \a other is shared, then the items will be copied instead.
967/*! \fn template <class Key, class T> QMultiMap<Key, T> operator+=(QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs)
970 Inserts all the items in the \a rhs map into the \a lhs map and
971 returns the resulting map.
973 \sa insert(), operator+()
976/*! \fn template <class Key, class T> QMultiMap<Key, T> operator+(const QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs)
979 Returns a map that contains all the items in the \a lhs map in
980 addition to all the items in \a rhs. If a key is common to both
981 maps, the resulting map will contain the key multiple times.
986/*! \class QMultiMap::iterator
988 \brief The QMultiMap::iterator class provides an STL-style non-const iterator for QMultiMap.
990 QMultiMap<Key, T>::iterator allows you to iterate over a QMultiMap
991 and to modify the value (but not the key) stored under
992 a particular key. If you want to iterate over a const QMultiMap, you
993 should use QMultiMap::const_iterator. It is generally good practice to
994 use QMultiMap::const_iterator on a non-const QMultiMap as well, unless you
995 need to change the QMultiMap through the iterator. Const iterators are
996 slightly faster, and can improve code readability.
998 The default QMultiMap::iterator constructor creates an uninitialized
999 iterator. You must initialize it using a QMultiMap function like
1000 QMultiMap::begin(), QMultiMap::end(), or QMultiMap::find() before you can
1001 start iterating. Here's a typical loop that prints all the (key,
1002 value) pairs stored in a map:
1004 Unlike QMultiHash, which stores its items in an arbitrary order, QMultiMap
1005 stores its items ordered by key. Items that share the same key
1006 will appear consecutively,
1007 from the most recently to the least recently inserted value.
1009 Here's an example that increments every value stored in the QMultiMap
1012 \snippet code/src_corelib_tools_qmultimap.cpp 19
1014 To remove elements from a QMultiMap you can use erase_if(QMultiMap<Key, T> &map, Predicate pred):
1016 \snippet code/src_corelib_tools_qmultimap.cpp 21
1018 Multiple iterators can be used on the same map. If you add items
1019 to the map, existing iterators will remain valid. If you remove
1020 items from the map, iterators that point to the removed items
1021 will become dangling iterators.
1023 \warning Iterators on implicitly shared containers do not work
1024 exactly like STL-iterators. You should avoid copying a container
1025 while iterators are active on that container. For more information,
1026 read \l{Implicit sharing iterator problem}.
1028 \sa QMultiMap::const_iterator, QMultiMap::key_iterator, QMultiMap::key_value_iterator
1031/*! \typedef QMultiMap::iterator::difference_type
1036/*! \typedef QMultiMap::iterator::iterator_category
1038 A synonym for \e {std::bidirectional_iterator_tag} indicating
1039 this iterator is a bidirectional iterator.
1042/*! \typedef QMultiMap::iterator::pointer
1047/*! \typedef QMultiMap::iterator::reference
1052/*! \typedef QMultiMap::iterator::value_type
1057/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator::iterator()
1059 Constructs an uninitialized iterator.
1061 Functions like key(), value(), and operator++() must not be
1062 called on an uninitialized iterator. Use operator=() to assign a
1063 value to it before using it.
1065 \sa QMultiMap::begin(), QMultiMap::end()
1068/*! \fn template <class Key, class T> const Key &QMultiMap<Key, T>::iterator::key() const
1070 Returns the current item's key as a const reference.
1072 There is no direct way of changing an item's key through an
1073 iterator, although it can be done by calling QMultiMap::erase()
1074 followed by QMultiMap::insert().
1079/*! \fn template <class Key, class T> T &QMultiMap<Key, T>::iterator::value() const
1081 Returns a modifiable reference to the current item's value.
1083 You can change the value of an item by using value() on
1084 the left side of an assignment, for example:
1086 \snippet code/src_corelib_tools_qmultimap.cpp 23
1088 \sa key(), operator*()
1091/*! \fn template <class Key, class T> T &QMultiMap<Key, T>::iterator::operator*() const
1093 Returns a modifiable reference to the current item's value.
1100/*! \fn template <class Key, class T> T *QMultiMap<Key, T>::iterator::operator->() const
1102 Returns a pointer to the current item's value.
1108 \fn template<class Key, class T> bool QMultiMap<Key, T>::iterator::operator==(const iterator &lhs, const iterator &rhs)
1109 \fn template<class Key, class T> bool QMultiMap<Key, T>::const_iterator::operator==(const const_iterator &lhs, const const_iterator &rhs)
1111 Returns \c true if \a lhs points to the same item as the \a rhs iterator;
1112 otherwise returns \c false.
1118 \fn template<class Key, class T> bool QMultiMap<Key, T>::iterator::operator!=(const iterator &lhs, const iterator &rhs)
1119 \fn template<class Key, class T> bool QMultiMap<Key, T>::const_iterator::operator!=(const const_iterator &lhs, const const_iterator &rhs)
1121 Returns \c true if \a lhs points to a different item than the \a rhs iterator;
1122 otherwise returns \c false.
1127/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator &QMultiMap<Key, T>::iterator::operator++()
1129 The prefix \c{++} operator (\c{++i}) advances the iterator to the
1130 next item in the multi map and returns an iterator to the new current
1133 Calling this function on QMultiMap::end() leads to undefined results.
1138/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator++(int)
1142 The postfix \c{++} operator (\c{i++}) advances the iterator to the
1143 next item in the multi map and returns an iterator to the previously
1147/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator &QMultiMap<Key, T>::iterator::operator--()
1149 The prefix \c{--} operator (\c{--i}) makes the preceding item
1150 current and returns an iterator pointing to the new current item.
1152 Calling this function on QMultiMap::begin() leads to undefined
1158/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator--(int)
1162 The postfix \c{--} operator (\c{i--}) makes the preceding item
1163 current and returns an iterator pointing to the previously
1169 \fn [qmultimap-op-it-plus-step] template <class Key, class T> typename QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator+(QMultiMap<Key, T>::iterator, difference_type n)
1170 \fn [qmultimap-op-step-plus-it] template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator+(difference_type n, QMultiMap<Key, T>::iterator)
1171 \fn [qmultimap-op-it-minus-step] template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator-(QMultiMap<Key, T>::iterator, difference_type n)
1172 \fn [qmultimap-op-step-minus-it] template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator-(difference_type n, QMultiMap<Key, T>::iterator)
1175 \fn template <class Key, class T> typename QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator+=(QMultiMap<Key, T>::iterator::difference_type n)
1176 \fn template <class Key, class T> typename QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator-=(QMultiMap<Key, T>::iterator::difference_type n)
1178 \deprecated [6.2] Use \c{std::next}, \c{std::prev} or \c{std::advance} instead.
1180 Move an iterator by \e{n} positions. These operations can be
1181 expensive for large values of \e{n}; QMultiMap iterators are not
1185/*! \class QMultiMap::const_iterator
1187 \brief The QMultiMap::const_iterator class provides an STL-style const iterator for QMultiMap.
1189 QMultiMap<Key, T>::const_iterator allows you to iterate over a QMultiMap.
1190 If you want to modify the QMultiMap as you iterate
1191 over it, you must use QMultiMap::iterator instead. It is generally
1192 good practice to use QMultiMap::const_iterator on a non-const QMultiMap as
1193 well, unless you need to change the QMultiMap through the iterator.
1194 Const iterators are slightly faster, and can improve code
1197 The default QMultiMap::const_iterator constructor creates an
1198 uninitialized iterator. You must initialize it using a QMultiMap
1199 function like QMultiMap::cbegin(), QMultiMap::cend(), or
1200 QMultiMap::constFind() before you can start iterating. Here's a typical
1201 loop that prints all the (key, value) pairs stored in a map:
1203 \snippet code/src_corelib_tools_qmultimap.cpp 24
1205 Here's an example that removes all the items whose value is greater than 10:
1207 \snippet code/src_corelib_tools_qmultimap.cpp 20
1209 Unlike QMultiHash, which stores its items in an arbitrary order, QMultiMap
1210 stores its items ordered by key. Items that share the same key
1211 will appear consecutively,
1212 from the most recently to the least recently inserted value.
1214 Multiple iterators can be used on the same multi map. If you add items
1215 to the map, existing iterators will remain valid. If you remove
1216 items from the map, iterators that point to the removed items
1217 will become dangling iterators.
1219 \warning Iterators on implicitly shared containers do not work
1220 exactly like STL-iterators. You should avoid copying a container
1221 while iterators are active on that container. For more information,
1222 read \l{Implicit sharing iterator problem}.
1224 \sa QMultiMap::iterator, QMultiMap::key_iterator, QMultiMap::const_key_value_iterator
1227/*! \typedef QMultiMap::const_iterator::difference_type
1232/*! \typedef QMultiMap::const_iterator::iterator_category
1234 A synonym for \e {std::bidirectional_iterator_tag} indicating
1235 this iterator is a bidirectional iterator.
1238/*! \typedef QMultiMap::const_iterator::pointer
1243/*! \typedef QMultiMap::const_iterator::reference
1248/*! \typedef QMultiMap::const_iterator::value_type
1253/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator::const_iterator()
1255 Constructs an uninitialized iterator.
1257 Functions like key(), value(), and operator++() must not be
1258 called on an uninitialized iterator. Use operator=() to assign a
1259 value to it before using it.
1261 \sa QMultiMap::constBegin(), QMultiMap::constEnd()
1264/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator::const_iterator(const iterator &other)
1266 Constructs a copy of \a other.
1269/*! \fn template <class Key, class T> const Key &QMultiMap<Key, T>::const_iterator::key() const
1271 Returns the current item's key.
1276/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::const_iterator::value() const
1278 Returns the current item's value.
1280 \sa key(), operator*()
1283/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::const_iterator::operator*() const
1285 Returns the current item's value.
1292/*! \fn template <class Key, class T> const T *QMultiMap<Key, T>::const_iterator::operator->() const
1294 Returns a pointer to the current item's value.
1299/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator &QMultiMap<Key, T>::const_iterator::operator++()
1301 The prefix \c{++} operator (\c{++i}) advances the iterator to the
1302 next item in the map and returns an iterator to the new current
1305 Calling this function on QMultiMap::end() leads to undefined results.
1310/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator++(int)
1314 The postfix \c{++} operator (\c{i++}) advances the iterator to the
1315 next item in the map and returns an iterator to the previously
1319/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator &QMultiMap<Key, T>::const_iterator::operator--()
1321 The prefix \c{--} operator (\c{--i}) makes the preceding item
1322 current and returns an iterator pointing to the new current item.
1324 Calling this function on QMultiMap::begin() leads to undefined
1330/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator--(int)
1334 The postfix \c{--} operator (\c{i--}) makes the preceding item
1335 current and returns an iterator pointing to the previously
1341 \fn [qmultimap-op-it-plus-step-const] template <class Key, class T> typename QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator+(QMultiMap<Key, T>::const_iterator, difference_type n)
1342 \fn [qmultimap-op-step-plus-it-const] template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator+(difference_type n, QMultiMap<Key, T>::const_iterator)
1343 \fn [qmultimap-op-it-minus-step-const] template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator-(QMultiMap<Key, T>::const_iterator, difference_type n)
1344 \fn [qmultimap-op-step-minus-it-const] template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator-(difference_type n, QMultiMap<Key, T>::const_iterator)
1347 \fn template <class Key, class T> typename QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator+=(QMultiMap<Key, T>::const_iterator::difference_type n)
1348 \fn template <class Key, class T> typename QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator-=(QMultiMap<Key, T>::const_iterator::difference_type n)
1350 \deprecated [6.2] Use \c{std::next}, \c{std::prev} or \c{std::advance} instead.
1352 Move an iterator by \e{n} positions. These operations can be
1353 expensive for large values of \e{n}. QMultiMap iterators are not
1357/*! \class QMultiMap::key_iterator
1360 \brief The QMultiMap::key_iterator class provides an STL-style const iterator for QMultiMap keys.
1362 QMultiMap::key_iterator is essentially the same as QMultiMap::const_iterator
1363 with the difference that operator*() and operator->() return a key
1366 For most uses QMultiMap::iterator and QMultiMap::const_iterator should be used,
1367 you can easily access the key by calling QMultiMap::iterator::key():
1369 \snippet code/src_corelib_tools_qmultimap.cpp keyiterator1
1371 However, to have interoperability between QMultiMap's keys and STL-style
1372 algorithms we need an iterator that dereferences to a key instead
1373 of a value. With QMultiMap::key_iterator we can apply an algorithm to a
1374 range of keys without having to call QMultiMap::keys(), which is inefficient
1375 as it costs one QMultiMap iteration and memory allocation to create a temporary
1378 \snippet code/src_corelib_tools_qmultimap.cpp keyiterator2
1380 QMultiMap::key_iterator is const, it's not possible to modify the key.
1382 The default QMultiMap::key_iterator constructor creates an uninitialized
1383 iterator. You must initialize it using a QMultiMap function like
1384 QMultiMap::keyBegin() or QMultiMap::keyEnd().
1386 \warning Iterators on implicitly shared containers do not work
1387 exactly like STL-iterators. You should avoid copying a container
1388 while iterators are active on that container. For more information,
1389 read \l{Implicit sharing iterator problem}.
1391 \sa QMultiMap::const_iterator, QMultiMap::iterator
1394/*! \typedef QMultiMap::key_iterator::difference_type
1398/*! \typedef QMultiMap::key_iterator::iterator_category
1402/*! \typedef QMultiMap::key_iterator::pointer
1406/*! \typedef QMultiMap::key_iterator::reference
1410/*! \typedef QMultiMap::key_iterator::value_type
1414/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::key_iterator::operator*() const
1416 Returns the current item's key.
1419/*! \fn template <class Key, class T> const T *QMultiMap<Key, T>::key_iterator::operator->() const
1421 Returns a pointer to the current item's key.
1424/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::key_iterator::operator==(key_iterator other) const
1426 Returns \c true if \a other points to the same item as this
1427 iterator; otherwise returns \c false.
1432/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::key_iterator::operator!=(key_iterator other) const
1434 Returns \c true if \a other points to a different item than this
1435 iterator; otherwise returns \c false.
1441 \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator &QMultiMap<Key, T>::key_iterator::operator++()
1443 The prefix \c{++} operator (\c{++i}) advances the iterator to the
1444 next item in the hash and returns an iterator to the new current
1447 Calling this function on QMultiMap::keyEnd() leads to undefined results.
1452/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<Key, T>::key_iterator::operator++(int)
1456 The postfix \c{++} operator (\c{i++}) advances the iterator to the
1457 next item in the hash and returns an iterator to the previous
1461/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator &QMultiMap<Key, T>::key_iterator::operator--()
1463 The prefix \c{--} operator (\c{--i}) makes the preceding item
1464 current and returns an iterator pointing to the new current item.
1466 Calling this function on QMultiMap::keyBegin() leads to undefined
1472/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<Key, T>::key_iterator::operator--(int)
1476 The postfix \c{--} operator (\c{i--}) makes the preceding item
1477 current and returns an iterator pointing to the previous
1481/*! \fn template <class Key, class T> const_iterator QMultiMap<Key, T>::key_iterator::base() const
1482 Returns the underlying const_iterator this key_iterator is based on.
1485/*! \typedef QMultiMap::const_key_value_iterator
1488 \brief The QMultiMap::const_key_value_iterator typedef provides an STL-style iterator for QMultiMap.
1490 QMultiMap::const_key_value_iterator is essentially the same as QMultiMap::const_iterator
1491 with the difference that operator*() returns a key/value pair instead of a
1494 \sa QKeyValueIterator
1497/*! \typedef QMultiMap::key_value_iterator
1500 \brief The QMultiMap::key_value_iterator typedef provides an STL-style iterator for QMultiMap.
1502 QMultiMap::key_value_iterator is essentially the same as QMultiMap::iterator
1503 with the difference that operator*() returns a key/value pair instead of a
1506 \sa QKeyValueIterator
1509/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QMultiMap<Key, T> &map)
1512 Writes the multi map \a map to stream \a out.
1514 This function requires the key and value types to implement \c
1517 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
1520/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QMultiMap<Key, T> &map)
1523 Reads a map from stream \a in into \a map.
1525 This function requires the key and value types to implement \c
1528 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
1531/*! \fn template <typename Key, typename T, typename Predicate> qsizetype erase_if(QMultiMap<Key, T> &map, Predicate pred)
1535 Removes all elements for which the predicate \a pred returns true
1536 from the multi map \a map.
1538 The function supports predicates which take either an argument of
1539 type \c{QMultiMap<Key, T>::iterator}, or an argument of type
1540 \c{std::pair<const Key &, T &>}.
1542 Returns the number of elements removed, if any.