diff options
24 files changed, 3315 insertions, 2054 deletions
diff --git a/examples/widgets/painting/fontsampler/mainwindow.cpp b/examples/widgets/painting/fontsampler/mainwindow.cpp index b3304b4b6d..96258a66d0 100644 --- a/examples/widgets/painting/fontsampler/mainwindow.cpp +++ b/examples/widgets/painting/fontsampler/mainwindow.cpp @@ -296,7 +296,7 @@ void MainWindow::on_printPreviewAction_triggered() void MainWindow::printPage(int index, QPainter *painter, QPrinter *printer) { #if defined(QT_PRINTSUPPORT_LIB) && QT_CONFIG(printdialog) - const QString family = (pageMap.begin() + index).key(); + const QString family = std::next(pageMap.begin(), index).key(); const StyleItems items = pageMap.value(family); // Find the dimensions of the text on each page. diff --git a/qmake/CMakeLists.txt b/qmake/CMakeLists.txt index 2a64d49c54..9e2c7b513c 100644 --- a/qmake/CMakeLists.txt +++ b/qmake/CMakeLists.txt @@ -112,7 +112,7 @@ qt_add_tool(${target_name} ../src/corelib/tools/qlist.cpp ../src/corelib/tools/qlist.h ../src/corelib/text/qlocale.cpp ../src/corelib/text/qlocale.h ../src/corelib/text/qlocale_tools.cpp ../src/corelib/text/qlocale_tools_p.h - ../src/corelib/tools/qmap.cpp ../src/corelib/tools/qmap.h + ../src/corelib/tools/qmap.h ../src/corelib/text/qregularexpression.cpp ../src/corelib/text/qregularexpression.h ../src/corelib/tools/qringbuffer.cpp # special case ../src/corelib/text/qstring.cpp ../src/corelib/text/qstring.h diff --git a/qmake/Makefile.unix b/qmake/Makefile.unix index 75d3fe3ca7..da49bb3177 100644 --- a/qmake/Makefile.unix +++ b/qmake/Makefile.unix @@ -30,7 +30,7 @@ QOBJS = \ qarraydata.o qbitarray.o qbytearray.o qbytearraylist.o qbytearraymatcher.o \ qcalendar.o qgregoriancalendar.o qromancalendar.o \ qcryptographichash.o qdatetime.o qhash.o \ - qlocale.o qlocale_tools.o qmap.o qregularexpression.o qringbuffer.o \ + qlocale.o qlocale_tools.o qregularexpression.o qringbuffer.o \ qstringbuilder.o qstring.o qstringconverter.o qstringlist.o qversionnumber.o \ qvsnprintf.o \ pcre2_auto_possess.o pcre2_chartables.o pcre2_compile.o pcre2_config.o \ @@ -129,7 +129,6 @@ DEPEND_SRC = \ $(SOURCE_PATH)/src/corelib/tools/qbitarray.cpp \ $(SOURCE_PATH)/src/corelib/tools/qcryptographichash.cpp \ $(SOURCE_PATH)/src/corelib/tools/qhash.cpp \ - $(SOURCE_PATH)/src/corelib/tools/qmap.cpp \ $(SOURCE_PATH)/src/corelib/tools/qringbuffer.cpp \ $(SOURCE_PATH)/src/corelib/tools/qversionnumber.cpp \ $(SOURCE_PATH)/src/3rdparty/pcre2/src/pcre2_auto_possess.c \ diff --git a/qmake/Makefile.win32 b/qmake/Makefile.win32 index 05ea1fb338..1cd439556f 100644 --- a/qmake/Makefile.win32 +++ b/qmake/Makefile.win32 @@ -99,7 +99,6 @@ QTOBJS= \ qlocale_win.obj \ qversionnumber.obj \ qmalloc.obj \ - qmap.obj \ qoperatingsystemversion.obj \ qoperatingsystemversion_win.obj \ qromancalendar.obj \ diff --git a/qmake/qmake.pro b/qmake/qmake.pro index 98eb3d1f6f..2cfa7c81a8 100644 --- a/qmake/qmake.pro +++ b/qmake/qmake.pro @@ -149,7 +149,6 @@ SOURCES += \ qlocale_tools.cpp \ qlogging.cpp \ qmalloc.cpp \ - qmap.cpp \ qmetatype.cpp \ qnumeric.cpp \ qregularexpression.cpp \ diff --git a/src/corelib/CMakeLists.txt b/src/corelib/CMakeLists.txt index fda150251c..0702c32170 100644 --- a/src/corelib/CMakeLists.txt +++ b/src/corelib/CMakeLists.txt @@ -213,7 +213,7 @@ qt_add_module(Core tools/qline.cpp tools/qline.h tools/qlist.cpp tools/qlist.h tools/qmakearray_p.h - tools/qmap.cpp tools/qmap.h + tools/qmap.h tools/qmargins.cpp tools/qmargins.h tools/qmessageauthenticationcode.cpp tools/qmessageauthenticationcode.h tools/qoffsetstringarray_p.h diff --git a/src/corelib/doc/snippets/code/doc_src_qiterator.cpp b/src/corelib/doc/snippets/code/doc_src_qiterator.cpp index ed0cf9e329..2ee618d394 100644 --- a/src/corelib/doc/snippets/code/doc_src_qiterator.cpp +++ b/src/corelib/doc/snippets/code/doc_src_qiterator.cpp @@ -183,6 +183,35 @@ while (i.findNext(widget)) { } //! [28] +//! [26multi] +QMultiMap<int, QWidget *> multimap; +... +QMultiMapIterator<int, QWidget *> i(multimap); +while (i.hasNext()) { + i.next(); + qDebug() << i.key() << ": " << i.value(); +} +//! [26multi] + + +//! [27multi] +QMultiMapIterator<int, QWidget *> i(multimap); +i.toBack(); +while (i.hasPrevious()) { + i.previous(); + qDebug() << i.key() << ": " << i.value(); +} +//! [27multi] + + +//! [28multi] +QMultiMapIterator<int, QWidget *> i(multimap); +while (i.findNext(widget)) { + qDebug() << "Found widget " << widget << " under key " + << i.key(); +} +//! [28multi] + //! [29] QHash<int, QWidget *> hash; @@ -244,6 +273,46 @@ while (i.hasNext()) { //! [35] +//! [32multi] +QMultiMap<int, QWidget *> multimap; +... +QMutableMultiMapIterator<int, QWidget *> i(multimap); +while (i.hasNext()) { + i.next(); + qDebug() << i.key() << ": " << i.value(); +} +//! [32multi] + + +//! [33multi] +QMutableMultiMapIterator<int, QWidget *> i(multimap); +i.toBack(); +while (i.hasPrevious()) { + i.previous(); + qDebug() << i.key() << ": " << i.value(); +} +//! [33multi] + + +//! [34multi] +QMutableMultiMapIterator<int, QWidget *> i(multimap); +while (i.findNext(widget)) { + qDebug() << "Found widget " << widget << " under key " + << i.key(); +} +//! [34multi] + + +//! [35multi] +QMutableMultiMapIterator<QString, QString> i(multimap); +while (i.hasNext()) { + i.next(); + if (i.key() == i.value()) + i.remove(); +} +//! [35multi] + + //! [36] QHash<int, QWidget *> hash; ... diff --git a/src/corelib/doc/snippets/code/src_corelib_tools_qmultimap.cpp b/src/corelib/doc/snippets/code/src_corelib_tools_qmultimap.cpp new file mode 100644 index 0000000000..9c2a01834b --- /dev/null +++ b/src/corelib/doc/snippets/code/src_corelib_tools_qmultimap.cpp @@ -0,0 +1,324 @@ +/**************************************************************************** +** +** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the documentation of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:BSD$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** BSD License Usage +** Alternatively, you may use this file under the terms of the BSD license +** as follows: +** +** "Redistribution and use in source and binary forms, with or without +** modification, are permitted provided that the following conditions are +** met: +** * Redistributions of source code must retain the above copyright +** notice, this list of conditions and the following disclaimer. +** * Redistributions in binary form must reproduce the above copyright +** notice, this list of conditions and the following disclaimer in +** the documentation and/or other materials provided with the +** distribution. +** * Neither the name of The Qt Company Ltd nor the names of its +** contributors may be used to endorse or promote products derived +** from this software without specific prior written permission. +** +** +** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +** "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +** LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +** A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +** OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +** LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +** DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +** THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +** (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +** OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE." +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +//! [0] +QMultiMap<QString, int> multimap; +//! [0] + + +//! [2] +multimap.insert("a", 1); +multimap.insert("b", 3); +multimap.insert("c", 7); +multimap.insert("c", -5); +//! [2] + + +//! [3] +int num2 = multimap.value("a"); // 1 +int num3 = multimap.value("thirteen"); // not found; 0 +int num3 = 0; +auto it = multimap.value("b"); +if (it != multimap.end()) { + num3 = it.value(); +} +//! [3] + + +//! [4] +int timeout = 30; +if (multimap.contains("TIMEOUT")) + timeout = multimap.value("TIMEOUT"); + +// better: +auto it = multimap.find("TIMEOUT"); +if (it != multimap.end()) + timeout = it.value(); +//! [4] + + +//! [5] +int timeout = multimap.value("TIMEOUT", 30); +//! [5] + + +//! [7] +QMultiMapIterator<QString, int> i(multimap); +while (i.hasNext()) { + i.next(); + cout << i.key() << ": " << i.value() << Qt::endl; +} +//! [7] + + +//! [8] +auto i = multimap.constBegin(); +while (i != multimap.constEnd()) { + cout << i.key() << ": " << i.value() << Qt::endl; + ++i; +} +//! [8] + + +//! [9] +multimap.insert("plenty", 100); +multimap.insert("plenty", 2000); +// multimap.size() == 2 +//! [9] + + +//! [10] +QList<int> values = multimap.values("plenty"); +for (int i = 0; i < values.size(); ++i) + cout << values.at(i) << Qt::endl; +//! [10] + + +//! [11] +QMultiMap<QString, int>::iterator i = multimap.find("plenty"); +while (i != map.end() && i.key() == "plenty") { + cout << i.value() << Qt::endl; + ++i; +} + +// better: +auto [i, end] = multimap.equal_range("plenty"); +while (i != end) { + cout << i.value() << Qt::endl; + ++i; +} +//! [11] + + +//! [12] +QMap<QString, int> multimap; +... +foreach (int value, multimap) + cout << value << Qt::endl; +//! [12] + + +//! [13] +#ifndef EMPLOYEE_H +#define EMPLOYEE_H + +class Employee +{ +public: + Employee() {} + Employee(const QString &name, QDate dateOfBirth); + ... + +private: + QString myName; + QDate myDateOfBirth; +}; + +inline bool operator<(const Employee &e1, const Employee &e2) +{ + if (e1.name() != e2.name()) + return e1.name() < e2.name(); + return e1.dateOfBirth() < e2.dateOfBirth(); +} + +#endif // EMPLOYEE_H +//! [13] + + +//! [15] +QMultiMap<int, QString> multimap; +multimap.insert(1, "one"); +multimap.insert(5, "five"); +multimap.insert(5, "five (2)"); +multimap.insert(10, "ten"); + +multimap.lowerBound(0); // returns iterator to (1, "one") +multimap.lowerBound(1); // returns iterator to (1, "one") +multimap.lowerBound(2); // returns iterator to (5, "five") +multimap.lowerBound(5); // returns iterator to (5, "five") +multimap.lowerBound(6); // returns iterator to (10, "ten") +multimap.lowerBound(10); // returns iterator to (10, "ten") +multimap.lowerBound(999); // returns end() +//! [15] + + +//! [16] +QMap<QString, int> multimap; +... +QMap<QString, int>::const_iterator i = multimap.lowerBound("HDR"); +QMap<QString, int>::const_iterator upperBound = multimap.upperBound("HDR"); +while (i != upperBound) { + cout << i.value() << Qt::endl; + ++i; +} +//! [16] + + +//! [17] +QMultiMap<int, QString> multimap; +multimap.insert(1, "one"); +multimap.insert(5, "five"); +multimap.insert(5, "five (2)"); +multimap.insert(10, "ten"); + +multimap.upperBound(0); // returns iterator to (1, "one") +multimap.upperBound(1); // returns iterator to (5, "five") +multimap.upperBound(2); // returns iterator to (5, "five") +multimap.lowerBound(5); // returns iterator to (5, "five (2)") +multimap.lowerBound(6); // returns iterator to (10, "ten") +multimap.upperBound(10); // returns end() +multimap.upperBound(999); // returns end() +//! [17] + + +//! [18] +QMultiMap<QString, int> multimap; +multimap.insert("January", 1); +multimap.insert("February", 2); +... +multimap.insert("December", 12); + +QMap<QString, int>::iterator i; +for (i = multimap.begin(); i != multimap.end(); ++i) + cout << i.key() << ": " << i.value() << Qt::endl; +//! [18] + + +//! [19] +QMultiMap<QString, int>::iterator i; +for (i = multimap.begin(); i != multimap.end(); ++i) + i.value() += 2; +//! [19] + + +//! [20] +QMultiMap<QString, int>::iterator i = multimap.begin(); +while (i != multimap.end()) { + if (i.key().startsWith('_')) + i = multimap.erase(i); + else + ++i; +} +//! [20] + + +//! [21] +QMultiMap<QString, int>::iterator i = multimap.begin(); +while (i != multimap.end()) { + QMap<QString, int>::iterator prev = i; + ++i; + if (prev.key().startsWith('_')) + multimap.erase(prev); +} +//! [21] + + +//! [22] +// WRONG +while (i != multimap.end()) { + if (i.key().startsWith('_')) + multimap.erase(i); + ++i; +} +//! [22] + + +//! [23] +if (i.key() == "Hello") + i.value() = "Bonjour"; +//! [23] + + +//! [24] +QMultiMap<QString, int> multi; +multimap.insert("January", 1); +multimap.insert("February", 2); +... +multimap.insert("December", 12); + +QMultiMap<QString, int>::const_iterator i; +for (i = multimap.constBegin(); i != multimap.constEnd(); ++i) + cout << i.key() << ": " << i.value() << Qt::endl; +//! [24] + + +//! [25] +QMultiMap<QString, int> map1, map2, map3; + +map1.insert("plenty", 100); +map1.insert("plenty", 2000); +// map1.size() == 2 + +map2.insert("plenty", 5000); +// map2.size() == 1 + +map3 = map1 + map2; +// map3.size() == 3 +//! [25] + +//! [keyiterator1] +for (QMultiMap<int, QString>::const_iterator it = multimap.cbegin(), end = multimap.cend(); it != end; ++it) { + cout << "The key: " << it.key() << Qt::endl + cout << "The value: " << it.value() << Qt::endl; + cout << "Also the value: " << (*it) << Qt::endl; +} +//! [keyiterator1] + +//! [keyiterator2] +// Inefficient, keys() is expensive +QList<int> keys = multimap.keys(); +int numPrimes = std::count_if(multimap.cbegin(), multimap.cend(), isPrimeNumber); +qDeleteAll(multimap2.keys()); + +// Efficient, no memory allocation needed +int numPrimes = std::count_if(multimap.keyBegin(), multimap.keyEnd(), isPrimeNumber); +qDeleteAll(multimap2.keyBegin(), multimap2.keyEnd()); +//! [keyiterator2] diff --git a/src/corelib/kernel/qvariant.cpp b/src/corelib/kernel/qvariant.cpp index 8a34806c60..f8859ddedc 100644 --- a/src/corelib/kernel/qvariant.cpp +++ b/src/corelib/kernel/qvariant.cpp @@ -924,7 +924,7 @@ static bool convert(const QVariant::Private *d, int t, void *result, bool *ok) const QVariantHash *hash = v_cast<QVariantHash>(d); const auto end = hash->end(); for (auto it = hash->begin(); it != end; ++it) - static_cast<QMultiMap<QString, QVariant> *>(map)->insert(it.key(), it.value()); + map->insert(it.key(), it.value()); #ifndef QT_BOOTSTRAPPED } else if (d->type().id() == QMetaType::QCborValue) { if (!v_cast<QCborValue>(d)->isMap()) diff --git a/src/corelib/kernel/qvariant.h b/src/corelib/kernel/qvariant.h index 87fb16485f..e7b64c2aed 100644 --- a/src/corelib/kernel/qvariant.h +++ b/src/corelib/kernel/qvariant.h @@ -808,7 +808,7 @@ namespace QtPrivate { QAssociativeIterable iter = QVariantValueHelperInterface<QAssociativeIterable>::invoke(v); QVariantMap l; for (QAssociativeIterable::const_iterator it = iter.begin(), end = iter.end(); it != end; ++it) - static_cast<QMultiMap<QString, QVariant> &>(l).insert(it.key().toString(), it.value()); + l.insert(it.key().toString(), it.value()); return l; } return QVariantValueHelper<QVariantMap>::invoke(v); diff --git a/src/corelib/tools/qiterator.qdoc b/src/corelib/tools/qiterator.qdoc index 4b61ae7778..49ee9ef00c 100644 --- a/src/corelib/tools/qiterator.qdoc +++ b/src/corelib/tools/qiterator.qdoc @@ -709,15 +709,15 @@ \class QMapIterator \inmodule QtCore - \brief The QMapIterator class provides a Java-style const iterator for QMap and QMultiMap. + \brief The QMapIterator class provides a Java-style const iterator for QMap. QMap has both \l{Java-style iterators} and \l{STL-style iterators}. The Java-style iterators are more high-level and easier to use than the STL-style iterators; on the other hand, they are slightly less efficient. - QMapIterator\<Key, T\> allows you to iterate over a QMap (or a - QMultiMap). If you want to modify the map as you iterate over + QMapIterator\<Key, T\> allows you to iterate over a QMap. + If you want to modify the map as you iterate over it, use QMutableMapIterator instead. The QMapIterator constructor takes a QMap as argument. After @@ -758,6 +758,57 @@ */ /*! + \class QMultiMapIterator + \inmodule QtCore + + \brief The QMultiMapIterator class provides a Java-style const iterator for QMultiMap. + QMultiMap has both \l{Java-style iterators} and \l{STL-style + iterators}. The Java-style iterators are more high-level and + easier to use than the STL-style iterators; on the other hand, + they are slightly less efficient. + + QMultiMapIterator\<Key, T\> allows you to iterate over a QMultiMap. + If you want to modify the map as you iterate over + it, use QMutableMultiMapIterator instead. + + The QMultiMapIterator constructor takes a QMultiMap as argument. After + construction, the iterator is located at the very beginning of + the map (before the first item). Here's how to iterate over all + the elements sequentially: + + \snippet code/doc_src_qiterator.cpp 26multi + + The next() function returns the next item in the map and + advances the iterator. The key() and value() functions return the + key and value of the last item that was jumped over. + + Unlike STL-style iterators, Java-style iterators point \e between + items rather than directly \e at items. The first call to next() + advances the iterator to the position between the first and + second item, and returns the first item; the second call to + next() advances the iterator to the position between the second + and third item; and so on. + + \image javaiterators1.png + + Here's how to iterate over the elements in reverse order: + + \snippet code/doc_src_qiterator.cpp 27multi + + If you want to find all occurrences of a particular value, use + findNext() or findPrevious() in a loop. For example: + + \snippet code/doc_src_qiterator.cpp 28multi + + Multiple iterators can be used on the same map. If the map is + modified while a QMultiMapIterator is active, the QMultiMapIterator will + continue iterating over the original map, ignoring the modified + copy. + + \sa QMutableMultiMapIterator, QMultiMapIterator::const_iterator +*/ + +/*! \class QHashIterator \inmodule QtCore @@ -809,7 +860,7 @@ \class QMutableMapIterator \inmodule QtCore - \brief The QMutableMapIterator class provides a Java-style non-const iterator for QMap and QMultiMap. + \brief The QMutableMapIterator class provides a Java-style non-const iterator for QMap. QMap has both \l{Java-style iterators} and \l{STL-style iterators}. The Java-style iterators are more high-level and @@ -817,7 +868,7 @@ they are slightly less efficient. QMutableMapIterator\<Key, T\> allows you to iterate over a QMap - (or a QMultiMap) and modify the map. If you don't want to modify + and modify the map. If you don't want to modify the map (or have a const QMap), use the slightly faster QMapIterator instead. @@ -871,6 +922,71 @@ */ /*! + \class QMutableMultiMapIterator + \inmodule QtCore + + \brief The QMutableMultiMapIterator class provides a Java-style non-const iterator for QMultiMap. + + QMultiMap has both \l{Java-style iterators} and \l{STL-style + iterators}. The Java-style iterators are more high-level and + easier to use than the STL-style iterators; on the other hand, + they are slightly less efficient. + + QMutableMultiMapIterator\<Key, T\> allows you to iterate over a QMultiMap + and modify the map. If you don't want to modify + the map (or have a const QMultiMap), use the slightly faster + QMultiMapIterator instead. + + The QMutableMultiMapIterator constructor takes a QMultiMap as argument. + After construction, the iterator is located at the very beginning + of the map (before the first item). Here's how to iterate over + all the elements sequentially: + + \snippet code/doc_src_qiterator.cpp 32multi + + The next() function returns the next item in the map and + advances the iterator. The key() and value() functions return the + key and value of the last item that was jumped over. + + Unlike STL-style iterators, Java-style iterators point \e between + items rather than directly \e at items. The first call to next() + advances the iterator to the position between the first and + second item, and returns the first item; the second call to + next() advances the iterator to the position between the second + and third item; and so on. + + \image javaiterators1.png + + Here's how to iterate over the elements in reverse order: + + \snippet code/doc_src_qiterator.cpp 33multi + + If you want to find all occurrences of a particular value, use + findNext() or findPrevious() in a loop. For example: + + \snippet code/doc_src_qiterator.cpp 34multi + + If you want to remove items as you iterate over the map, use + remove(). If you want to modify the value of an item, use + setValue(). + + Example: + + \snippet code/doc_src_qiterator.cpp 35multi + + The example removes all (key, value) pairs where the key and the + value are the same. + + Only one mutable iterator can be active on a given map at any + time. Furthermore, no changes should be done directly to the map + while the iterator is active (as opposed to through the + iterator), since this could invalidate the iterator and lead to + undefined behavior. + + \sa QMultiMapIterator, QMultiMap::iterator +*/ + +/*! \class QMutableHashIterator \inmodule QtCore @@ -933,6 +1049,8 @@ /*! \fn template <class Key, class T> QMapIterator<Key, T>::QMapIterator(const QMap<Key, T> &map) \fn template <class Key, class T> QMutableMapIterator<Key, T>::QMutableMapIterator(QMap<Key, T> &map) + \fn template <class Key, class T> QMultiMapIterator<Key, T>::QMultiMapIterator(const QMultiMap<Key, T> &map) + \fn template <class Key, class T> QMutableMultiMapIterator<Key, T>::QMutableMultiMapIterator(QMultiMap<Key, T> &map) Constructs an iterator for traversing \a map. The iterator is set to be at the front of the map (before the first item). @@ -951,6 +1069,8 @@ /*! \fn template <class Key, class T> QMapIterator &QMapIterator<Key, T>::operator=(const QMap<Key, T> &map) \fn template <class Key, class T> QMutableMapIterator &QMutableMapIterator<Key, T>::operator=(QMap<Key, T> &map) + \fn template <class Key, class T> QMultiMapIterator &QMultiMapIterator<Key, T>::operator=(const QMultiMap<Key, T> &map) + \fn template <class Key, class T> QMutableMultiMapIterator &QMutableMultiMapIterator<Key, T>::operator=(QMultiMap<Key, T> &map) Makes the iterator operate on \a map. The iterator is set to be at the front of the map (before the first item). @@ -968,8 +1088,10 @@ */ /*! \fn template <class Key, class T> void QMapIterator<Key, T>::toFront() + \fn template <class Key, class T> void QMultiMapIterator<Key, T>::toFront() \fn template <class Key, class T> void QHashIterator<Key, T>::toFront() \fn template <class Key, class T> void QMutableMapIterator<Key, T>::toFront() + \fn template <class Key, class T> void QMutableMultiMapIterator<Key, T>::toFront() \fn template <class Key, class T> void QMutableHashIterator<Key, T>::toFront() Moves the iterator to the front of the container (before the @@ -979,7 +1101,9 @@ */ /*! \fn template <class Key, class T> void QMapIterator<Key, T>::toBack() + \fn template <class Key, class T> void QMultiMapIterator<Key, T>::toBack() \fn template <class Key, class T> void QMutableMapIterator<Key, T>::toBack() + \fn template <class Key, class T> void QMutableMultiMapIterator<Key, T>::toBack() Moves the iterator to the back of the container (after the last item). @@ -998,7 +1122,9 @@ */ /*! \fn template <class Key, class T> bool QMapIterator<Key, T>::hasNext() const + \fn template <class Key, class T> bool QMultiMapIterator<Key, T>::hasNext() const \fn template <class Key, class T> bool QMutableMapIterator<Key, T>::hasNext() const + \fn template <class Key, class T> bool QMutableMultiMapIterator<Key, T>::hasNext() const Returns \c true if there is at least one item ahead of the iterator, i.e. the iterator is \e not at the back of the container; @@ -1019,6 +1145,7 @@ */ /*! \fn template <class Key, class T> QMapIterator<Key, T>::Item QMapIterator<Key, T>::next() + \fn template <class Key, class T> QMultiMapIterator<Key, T>::Item QMultiMapIterator<Key, T>::next() Returns the next item and advances the iterator by one position. @@ -1032,6 +1159,7 @@ */ /*! \fn template <class Key, class T> QMutableMapIterator<Key, T>::Item QMutableMapIterator<Key, T>::next() + \fn template <class Key, class T> QMutableMultiMapIterator<Key, T>::Item QMutableMultiMapIterator<Key, T>::next() Returns the next item and advances the iterator by one position. @@ -1073,6 +1201,7 @@ */ /*! \fn template <class Key, class T> QMapIterator<Key, T>::Item QMapIterator<Key, T>::peekNext() const + \fn template <class Key, class T> QMutableMapIterator<Key, T>::Item QMutableMapIterator<Key, T>::peekNext() Returns the next item without moving the iterator. @@ -1086,6 +1215,7 @@ */ /*! \fn template <class Key, class T> QMutableMapIterator<Key, T>::Item QMutableMapIterator<Key, T>::peekNext() const + \fn template <class Key, class T> QMutableMultiMapIterator<Key, T>::Item QMutableMultiMapIterator<Key, T>::peekNext() Returns a reference to the next item without moving the iterator. @@ -1127,7 +1257,9 @@ */ /*! \fn template <class Key, class T> bool QMapIterator<Key, T>::hasPrevious() const + \fn template <class Key, class T> bool QMultiMapIterator<Key, T>::hasPrevious() const \fn template <class Key, class T> bool QMutableMapIterator<Key, T>::hasPrevious() const + \fn template <class Key, class T> bool QMutableMultiMapIterator<Key, T>::hasPrevious() const Returns \c true if there is at least one item behind the iterator, i.e. the iterator is \e not at the front of the container; @@ -1160,6 +1292,8 @@ /*! \fn template <class Key, class T> QMapIterator<Key, T>::Item QMapIterator<Key, T>::previous() \fn template <class Key, class T> QMutableMapIterator<Key, T>::Item QMutableMapIterator<Key, T>::previous() + \fn template <class Key, class T> QMultiMapIterator<Key, T>::Item QMultiMapIterator<Key, T>::previous() + \fn template <class Key, class T> QMutableMultiMapIterator<Key, T>::Item QMutableMultiMapIterator<Key, T>::previous() Returns the previous item and moves the iterator back by one position. @@ -1207,6 +1341,8 @@ /*! \fn template <class Key, class T> QMapIterator<Key, T>::Item QMapIterator<Key, T>::peekPrevious() const \fn template <class Key, class T> QMutableMapIterator<Key, T>::Item QMutableMapIterator<Key, T>::peekPrevious() const + \fn template <class Key, class T> QMultiMapIterator<Key, T>::Item QMultiMapIterator<Key, T>::peekPrevious() const + \fn template <class Key, class T> QMutableMultiMapIterator<Key, T>::Item QMutableMultiMapIterator<Key, T>::peekPrevious() const Returns the previous item without moving the iterator. @@ -1250,6 +1386,7 @@ */ /*! \fn template <class Key, class T> const T &QMapIterator<Key, T>::value() const + \fn template <class Key, class T> const T &QMultiMapIterator<Key, T>::value() const Returns the value of the last item that was jumped over using one of the traversal functions (next(), previous(), findNext(), @@ -1264,6 +1401,7 @@ /*! \fn template <class Key, class T> const T &QMutableMapIterator<Key, T>::value() const + \fn template <class Key, class T> const T &QMutableMultiMapIterator<Key, T>::value() const Returns the value of the last item that was jumped over using one of the traversal functions (next(), previous(), findNext(), @@ -1295,6 +1433,7 @@ /*! \fn template <class Key, class T> T &QMutableMapIterator<Key, T>::value() + \fn template <class Key, class T> T &QMutableMultiMapIterator<Key, T>::value() \fn template <class Key, class T> T &QMutableHashIterator<Key, T>::value() \overload @@ -1305,6 +1444,8 @@ /*! \fn template <class Key, class T> const Key &QMapIterator<Key, T>::key() const \fn template <class Key, class T> const Key &QMutableMapIterator<Key, T>::key() const + \fn template <class Key, class T> const Key &QMultiMapIterator<Key, T>::key() const + \fn template <class Key, class T> const Key &QMutableMultiMapIterator<Key, T>::key() const Returns the key of the last item that was jumped over using one of the traversal functions (next(), previous(), findNext(), @@ -1328,6 +1469,8 @@ /*! \fn template <class Key, class T> bool QMapIterator<Key, T>::findNext(const T &value) \fn template <class Key, class T> bool QMutableMapIterator<Key, T>::findNext(const T &value) + \fn template <class Key, class T> bool QMultiMapIterator<Key, T>::findNext(const T &value) + \fn template <class Key, class T> bool QMutableMultiMapIterator<Key, T>::findNext(const T &value) Searches for \a value starting from the current iterator position forward. Returns \c true if a (key, value) pair with value \a value @@ -1354,6 +1497,8 @@ /*! \fn template <class Key, class T> bool QMapIterator<Key, T>::findPrevious(const T &value) \fn template <class Key, class T> bool QMutableMapIterator<Key, T>::findPrevious(const T &value) + \fn template <class Key, class T> bool QMultiMapIterator<Key, T>::findPrevious(const T &value) + \fn template <class Key, class T> bool QMutableMultiMapIterator<Key, T>::findPrevious(const T &value) Searches for \a value starting from the current iterator position backward. Returns \c true if a (key, value) pair with value \a value @@ -1397,6 +1542,7 @@ */ /*! \fn template <class Key, class T> void QMutableMapIterator<Key, T>::remove() + \fn template <class Key, class T> void QMutableMultiMapIterator<Key, T>::remove() Removes the last item that was jumped over using one of the traversal functions (next(), previous(), findNext(), findPrevious()). @@ -1413,6 +1559,7 @@ */ /*! \fn template <class Key, class T> void QMutableMapIterator<Key, T>::setValue(const T &value) + \fn template <class Key, class T> void QMutableMultiMapIterator<Key, T>::setValue(const T &value) Replaces the value of the last item that was jumped over using one of the traversal functions with \a value. diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index d3e27f09ef..2a87912c4a 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -1,5 +1,6 @@ /**************************************************************************** ** +** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> ** Copyright (C) 2016 The Qt Company Ltd. ** Contact: https://www.qt.io/licensing/ ** @@ -44,376 +45,357 @@ #include <QtCore/qlist.h> #include <QtCore/qrefcount.h> #include <QtCore/qpair.h> - -#ifdef Q_MAP_DEBUG -#include <QtCore/qdebug.h> -#endif +#include <QtCore/qshareddata.h> +#include <QtCore/qshareddata_impl.h> #include <functional> #include <initializer_list> #include <map> -#include <new> +#include <algorithm> QT_BEGIN_NAMESPACE -/* - QMap uses qMapLessThanKey() to compare keys. The default - implementation uses operator<(). For pointer types, - qMapLessThanKey() uses std::less (because operator<() on - pointers can be used only between pointers in the same array). -*/ - -template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2) +// common code shared between QMap and QMultimap +template <typename AMap> +class QMapData : public QSharedData { - return key1 < key2; -} +public: + using Map = AMap; + using Key = typename Map::key_type; + using T = typename Map::mapped_type; + using value_type = typename Map::value_type; + using size_type = typename Map::size_type; + + Map m; + + QMapData() = default; + explicit QMapData(const Map &other) + : m(other) + {} + + explicit QMapData(Map &&other) + : m(std::move(other)) + {} + + // used in remove(); copies from source all the values not matching key. + // returns how many were NOT copied (removed). + size_type copyIfNotEquivalentTo(const Map &source, const Key &key) + { + Q_ASSERT(m.empty()); + + size_type result = 0; + const auto &keyCompare = source.key_comp(); + const auto filter = [&result, &key, &keyCompare](const auto &v) + { + if (!keyCompare(key, v.first) && !keyCompare(v.first, key)) { + // keys are equivalent (neither a<b nor b<a) => found it + ++result; + return true; + } + return false; + }; -template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2) -{ - return std::less<const Ptr *>()(key1, key2); -} + std::remove_copy_if(source.cbegin(), source.cend(), + std::inserter(m, m.end()), + filter); + return result; + } -struct QMapDataBase; -template <class Key, class T> struct QMapData; + // used in key(T), count(Key, T), find(key, T), etc; returns a + // comparator object suitable for algorithms with std::(multi)map + // iterators. + static auto valueIsEqualTo(const T &value) + { + return [&value](const auto &v) { return v.second == value; }; + } -struct Q_CORE_EXPORT QMapNodeBase -{ - quintptr p; - QMapNodeBase *left; - QMapNodeBase *right; - - enum Color { Red = 0, Black = 1 }; - enum { Mask = 3 }; // reserve the second bit as well - - const QMapNodeBase *nextNode() const; - QMapNodeBase *nextNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->nextNode()); } - const QMapNodeBase *previousNode() const; - QMapNodeBase *previousNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->previousNode()); } - - Color color() const { return Color(p & 1); } - void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; } - QMapNodeBase *parent() const { return reinterpret_cast<QMapNodeBase *>(p & ~Mask); } - void setParent(QMapNodeBase *pp) { p = (p & Mask) | quintptr(pp); } - - template <typename T> - static typename std::enable_if<QTypeInfo<T>::isComplex>::type - callDestructorIfNecessary(T &t) noexcept { Q_UNUSED(t); t.~T(); } // Q_UNUSED: silence MSVC unused 't' warning - template <typename T> - static typename std::enable_if<!QTypeInfo<T>::isComplex>::type - callDestructorIfNecessary(T &) noexcept {} -}; + Key key(const T &value, const Key &defaultKey) const + { + auto i = std::find_if(m.cbegin(), + m.cend(), + valueIsEqualTo(value)); + if (i != m.cend()) + return i->first; -template <class Key, class T> -struct QMapNode : public QMapNodeBase -{ - Key key; - T value; + return defaultKey; + } - inline QMapNode *leftNode() const { return static_cast<QMapNode *>(left); } - inline QMapNode *rightNode() const { return static_cast<QMapNode *>(right); } + QList<Key> keys() const + { + QList<Key> result; + result.reserve(m.size()); - inline const QMapNode *nextNode() const { return reinterpret_cast<const QMapNode *>(QMapNodeBase::nextNode()); } - inline const QMapNode *previousNode() const { return static_cast<const QMapNode *>(QMapNodeBase::previousNode()); } - inline QMapNode *nextNode() { return reinterpret_cast<QMapNode *>(QMapNodeBase::nextNode()); } - inline QMapNode *previousNode() { return static_cast<QMapNode *>(QMapNodeBase::previousNode()); } + const auto extractKey = [](const auto &v) { return v.first; }; - QMapNode<Key, T> *copy(QMapData<Key, T> *d) const; + std::transform(m.cbegin(), + m.cend(), + std::back_inserter(result), + extractKey); + return result; + } - void destroySubTree() + QList<Key> keys(const T &value) const { - callDestructorIfNecessary(key); - callDestructorIfNecessary(value); - doDestroySubTree(std::integral_constant<bool, QTypeInfo<T>::isComplex || QTypeInfo<Key>::isComplex>()); + QList<Key> result; + result.reserve(m.size()); + // no std::transform_if... + for (const auto &v : m) { + if (v.second == value) + result.append(v.first); + } + result.shrink_to_fit(); + return result; } - QMapNode<Key, T> *lowerBound(const Key &key); - QMapNode<Key, T> *upperBound(const Key &key); - -private: - void doDestroySubTree(std::false_type) {} - void doDestroySubTree(std::true_type) + QList<T> values() const { - if (left) - leftNode()->destroySubTree(); - if (right) - rightNode()->destroySubTree(); + QList<T> result; + result.reserve(m.size()); + + const auto extractValue = [](const auto &v) { return v.second; }; + + std::transform(m.cbegin(), + m.cend(), + std::back_inserter(result), + extractValue); + return result; } - QMapNode() = delete; - Q_DISABLE_COPY(QMapNode) + size_type count(const Key &key) const + { + return m.count(key); + } }; -template <class Key, class T> -inline QMapNode<Key, T> *QMapNode<Key, T>::lowerBound(const Key &akey) -{ - QMapNode<Key, T> *n = this; - QMapNode<Key, T> *lastNode = nullptr; - while (n) { - if (!qMapLessThanKey(n->key, akey)) { - lastNode = n; - n = n->leftNode(); - } else { - n = n->rightNode(); - } - } - return lastNode; -} +// +// QMap +// template <class Key, class T> -inline QMapNode<Key, T> *QMapNode<Key, T>::upperBound(const Key &akey) +class QMap { - QMapNode<Key, T> *n = this; - QMapNode<Key, T> *lastNode = nullptr; - while (n) { - if (qMapLessThanKey(akey, n->key)) { - lastNode = n; - n = n->leftNode(); - } else { - n = n->rightNode(); - } - } - return lastNode; -} + using MapData = QMapData<std::map<Key, T>>; + QtPrivate::QExplicitlySharedDataPointerV2<MapData> d; +public: + using key_type = Key; + using mapped_type = T; + using difference_type = qptrdiff; + using size_type = qsizetype; + constexpr QMap() noexcept {} -struct Q_CORE_EXPORT QMapDataBase -{ - QtPrivate::RefCount ref; - qsizetype size; - QMapNodeBase header; - QMapNodeBase *mostLeftNode; + // implicitly generated special member functions are OK! - void rotateLeft(QMapNodeBase *x); - void rotateRight(QMapNodeBase *x); - void rebalance(QMapNodeBase *x); - void freeNodeAndRebalance(QMapNodeBase *z); - void recalcMostLeftNode(); - - QMapNodeBase *createNode(size_t size, size_t alignment, QMapNodeBase *parent, bool left); - void freeTree(QMapNodeBase *root, size_t alignment); + void swap(QMap<Key, T> &other) noexcept + { + qSwap(d, other.d); + } - static const QMapDataBase shared_null; + QMap(std::initializer_list<std::pair<Key, T>> list) + { + for (auto &p : list) + insert(p.first, p.second); + } - static QMapDataBase *createData(); - static void freeData(QMapDataBase *d); -}; + explicit QMap(const std::map<Key, T> &other) + : d(other.empty() ? nullptr : new MapData(other)) + { + } -template <class Key, class T> -struct QMapData : public QMapDataBase -{ - typedef QMapNode<Key, T> Node; - - Node *root() const { return static_cast<Node *>(header.left); } - - // using reinterpret_cast because QMapDataBase::header is not - // actually a QMapNode. - const Node *end() const { return reinterpret_cast<const Node *>(&header); } - Node *end() { return reinterpret_cast<Node *>(&header); } - const Node *begin() const { if (root()) return static_cast<const Node*>(mostLeftNode); return end(); } - Node *begin() { if (root()) return static_cast<Node*>(mostLeftNode); return end(); } - - void deleteNode(Node *z); - Node *findNode(const Key &akey) const; - void nodeRange(const Key &akey, Node **firstNode, Node **lastNode); - - Node *createNode(const Key &k, const T &v, Node *parent = nullptr, bool left = false) - { - Node *n = static_cast<Node *>(QMapDataBase::createNode(sizeof(Node), alignof(Node), - parent, left)); - QT_TRY { - new (&n->key) Key(k); - QT_TRY { - new (&n->value) T(v); - } QT_CATCH(...) { - n->key.~Key(); - QT_RETHROW; - } - } QT_CATCH(...) { - QMapDataBase::freeNodeAndRebalance(n); - QT_RETHROW; - } - return n; + explicit QMap(std::map<Key, T> &&other) + : d(other.empty() ? nullptr : new MapData(std::move(other))) + { } - static QMapData *create() { - return static_cast<QMapData *>(createData()); + std::map<Key, T> toStdMap() const & + { + if (d) + return d->m; + return {}; } - void destroy() { - if (root()) { - root()->destroySubTree(); - freeTree(header.left, alignof(Node)); + std::map<Key, T> toStdMap() && + { + if (d) { + if (d.isShared()) + return d->m; + else + return std::move(d->m); } - freeData(this); + + return {}; } -}; -template <class Key, class T> -QMapNode<Key, T> *QMapNode<Key, T>::copy(QMapData<Key, T> *d) const -{ - QMapNode<Key, T> *n = d->createNode(key, value); - n->setColor(color()); - if (left) { - n->left = leftNode()->copy(d); - n->left->setParent(n); - } else { - n->left = nullptr; - } - if (right) { - n->right = rightNode()->copy(d); - n->right->setParent(n); - } else { - n->right = nullptr; - } - return n; -} + // CHANGE: non-member equality comparison + template <typename AKey, typename AT> + friend QTypeTraits::compare_eq_result<AKey, AT> operator==(const QMap<AKey, AT> &lhs, const QMap<AKey, AT> &rhs); + template <typename AKey, typename AT> + friend QTypeTraits::compare_eq_result<AKey, AT> operator!=(const QMap<AKey, AT> &lhs, const QMap<AKey, AT> &rhs); -template <class Key, class T> -void QMapData<Key, T>::deleteNode(QMapNode<Key, T> *z) -{ - QMapNodeBase::callDestructorIfNecessary(z->key); - QMapNodeBase::callDestructorIfNecessary(z->value); - freeNodeAndRebalance(z); -} + // TODO: add the other comparison operators; std::map has them. -template <class Key, class T> -QMapNode<Key, T> *QMapData<Key, T>::findNode(const Key &akey) const -{ - if (Node *r = root()) { - Node *lb = r->lowerBound(akey); - if (lb && !qMapLessThanKey(akey, lb->key)) - return lb; + size_type size() const { return d ? size_type(d->m.size()) : size_type(0); } + + bool isEmpty() const { return d ? d->m.empty() : true; } + + void detach() + { + if (d) + d.detach(); + else + d.reset(new MapData); } - return nullptr; -} + bool isDetached() const noexcept + { + return d ? !d.isShared() : false; // false makes little sense, but that's shared_null's behavior... + } -template <class Key, class T> -void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **firstNode, QMapNode<Key, T> **lastNode) -{ - Node *n = root(); - Node *l = end(); - while (n) { - if (qMapLessThanKey(akey, n->key)) { - l = n; - n = n->leftNode(); - } else if (qMapLessThanKey(n->key, akey)) { - n = n->rightNode(); - } else { - *firstNode = n->leftNode() ? n->leftNode()->lowerBound(akey) : nullptr; - if (!*firstNode) - *firstNode = n; - *lastNode = n->rightNode() ? n->rightNode()->upperBound(akey) : nullptr; - if (!*lastNode) - *lastNode = l; + bool isSharedWith(const QMap<Key, T> &other) const noexcept + { + return d == other.d; // also this makes little sense? + } + + void clear() + { + if (!d) return; - } + + if (!d.isShared()) + d->m.clear(); + else + d.reset(); } - *firstNode = *lastNode = l; -} + size_type remove(const Key &key) + { + if (!d) + return 0; + + if (!d.isShared()) + return size_type(d->m.erase(key)); -template <class Key, class T> -class QMap -{ - typedef QMapNode<Key, T> Node; + MapData *newData = new MapData; + size_type result = newData->copyIfNotEquivalentTo(d->m, key); - QMapData<Key, T> *d; + d.reset(newData); -public: - inline QMap() noexcept : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { } - inline QMap(std::initializer_list<std::pair<Key,T> > list) - : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) - { - for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) - insert(it->first, it->second); + return result; } - QMap(const QMap<Key, T> &other); - - inline ~QMap() { if (!d->ref.deref()) d->destroy(); } - QMap<Key, T> &operator=(const QMap<Key, T> &other); - inline QMap(QMap<Key, T> &&other) noexcept - : d(other.d) + T take(const Key &key) { - other.d = static_cast<QMapData<Key, T> *>( - const_cast<QMapDataBase *>(&QMapDataBase::shared_null)); + if (!d) + return T(); + + // TODO: improve. There is no need of copying all the + // elements (the one to be removed can be skipped). + detach(); + + auto i = d->m.find(key); + if (i != d->m.end()) { + T result(std::move(i->second)); + d->m.erase(i); + return result; + } + return T(); } - inline QMap<Key, T> &operator=(QMap<Key, T> &&other) noexcept - { QMap moved(std::move(other)); swap(moved); return *this; } - inline void swap(QMap<Key, T> &other) noexcept { qSwap(d, other.d); } - explicit QMap(const typename std::map<Key, T> &other); - std::map<Key, T> toStdMap() const; - - template <typename U = T> - QTypeTraits::compare_eq_result<U> operator==(const QMap<Key, T> &other) const + bool contains(const Key &key) const { - if (size() != other.size()) + if (!d) return false; - if (d == other.d) - return true; + auto i = d->m.find(key); + return i != d->m.end(); + } - const_iterator it1 = begin(); - const_iterator it2 = other.begin(); + // ### Qt 6: deprecate value->key lookup. + //Q_DECL_DEPRECATED_X("This function is inefficient; don't use it") + Key key(const T &value, const Key &defaultKey = Key()) const + { + if (!d) + return defaultKey; - while (it1 != end()) { - if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key())) - return false; - ++it2; - ++it1; - } - return true; + return d->key(value, defaultKey); } - template <typename U = T> - QTypeTraits::compare_eq_result<U> operator!=(const QMap<Key, T> &other) const - { return !(*this == other); } - inline qsizetype size() const { return d->size; } + T value(const Key &key, const T &defaultValue = T()) const + { + if (!d) + return defaultValue; + const auto i = d->m.find(key); + if (i != d->m.cend()) + return i->second; + return defaultValue; + } - inline bool isEmpty() const { return d->size == 0; } + T &operator[](const Key &key) + { + detach(); + auto i = d->m.find(key); + if (i == d->m.end()) + i = d->m.insert({key, T()}).first; + return i->second; + } - inline void detach() { if (d->ref.isShared()) detach_helper(); } - inline bool isDetached() const { return !d->ref.isShared(); } - inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; } + // CHANGE: return T, not const T! + T operator[](const Key &key) const + { + return value(key); + } - void clear(); + // ### Qt 6: this stuff should be deprecated as well + QList<Key> keys() const + { + if (!d) + return {}; + return d->keys(); + } - qsizetype remove(const Key &key); - T take(const Key &key); + QList<Key> keys(const T &value) const + { + if (!d) + return {}; + return d->keys(value); + } - bool contains(const Key &key) const; - Key key(const T &value, const Key &defaultKey = Key()) const; - T value(const Key &key, const T &defaultValue = T()) const; - T &operator[](const Key &key); - const T operator[](const Key &key) const; + QList<T> values() const + { + if (!d) + return {}; + return d->values(); + } - QList<Key> keys() const; - QList<Key> keys(const T &value) const; - QList<T> values() const; -#if QT_DEPRECATED_SINCE(5, 15) - QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") QList<Key> uniqueKeys() const; - QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") QList<T> values(const Key &key) const; -#endif - qsizetype count(const Key &key) const; + size_type count(const Key &key) const + { + if (!d) + return 0; + return d->count(key); + } + size_type count() const + { + return size(); + } inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); } - inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (constEnd() - 1).key(); } + inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (--constEnd()).key(); } inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); } inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); } - inline T &last() { Q_ASSERT(!isEmpty()); return *(end() - 1); } - inline const T &last() const { Q_ASSERT(!isEmpty()); return *(constEnd() - 1); } + inline T &last() { Q_ASSERT(!isEmpty()); return *(--end()); } + inline const T &last() const { Q_ASSERT(!isEmpty()); return *(--constEnd()); } class const_iterator; class iterator { + friend class QMap<Key, T>; friend class const_iterator; - Node *i; + typename MapData::Map::iterator i; + explicit iterator(typename MapData::Map::iterator it) : i(it) {} public: typedef std::bidirectional_iterator_tag iterator_category; typedef qptrdiff difference_type; @@ -421,52 +403,44 @@ public: typedef T *pointer; typedef T &reference; - inline iterator() : i(nullptr) { } - inline iterator(Node *node) : i(node) { } + iterator() = default; - inline const Key &key() const { return i->key; } - inline T &value() const { return i->value; } - inline T &operator*() const { return i->value; } - inline T *operator->() const { return &i->value; } - inline bool operator==(const iterator &o) const { return i == o.i; } - inline bool operator!=(const iterator &o) const { return i != o.i; } + const Key &key() const { return i->first; } + T &value() const { return i->second; } + T &operator*() const { return i->second; } + T *operator->() const { return &i->second; } + friend bool operator==(const iterator &lhs, const iterator &rhs) { return lhs.i == rhs.i; } + friend bool operator!=(const iterator &lhs, const iterator &rhs) { return lhs.i != rhs.i; } - inline iterator &operator++() { - i = i->nextNode(); + iterator &operator++() + { + ++i; return *this; } - inline iterator operator++(int) { + iterator operator++(int) + { iterator r = *this; - i = i->nextNode(); + ++i; return r; } - inline iterator &operator--() { - i = i->previousNode(); + iterator &operator--() + { + --i; return *this; } - inline iterator operator--(int) { + iterator operator--(int) + { iterator r = *this; - i = i->previousNode(); + --i; return r; } - inline iterator operator+(qsizetype j) const - { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline iterator operator-(qsizetype j) const { return operator+(-j); } - inline iterator &operator+=(qsizetype j) { return *this = *this + j; } - inline iterator &operator-=(qsizetype j) { return *this = *this - j; } - friend inline iterator operator+(qsizetype j, iterator k) { return k + j; } - - inline bool operator==(const const_iterator &o) const { return i == o.i; } - inline bool operator!=(const const_iterator &o) const { return i != o.i; } - friend class QMap<Key, T>; - friend class QMultiMap<Key, T>; }; - friend class iterator; class const_iterator { - friend class iterator; - const Node *i; + friend class QMap<Key, T>; + typename MapData::Map::const_iterator i; + explicit const_iterator(typename MapData::Map::const_iterator it) : i(it) {} public: typedef std::bidirectional_iterator_tag iterator_category; @@ -475,46 +449,39 @@ public: typedef const T *pointer; typedef const T &reference; - Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { } - inline const_iterator(const Node *node) : i(node) { } - inline const_iterator(const iterator &o) { i = o.i; } + const_iterator() = default; + /* implicit */ const_iterator(const iterator &o) { i = o.i; } - inline const Key &key() const { return i->key; } - inline const T &value() const { return i->value; } - inline const T &operator*() const { return i->value; } - inline const T *operator->() const { return &i->value; } - Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; } - Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return i != o.i; } + const Key &key() const { return i->first; } + const T &value() const { return i->second; } + const T &operator*() const { return i->second; } + const T *operator->() const { return &i->second; } + friend bool operator==(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i == rhs.i; } + friend bool operator!=(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i != rhs.i; } - inline const_iterator &operator++() { - i = i->nextNode(); + const_iterator &operator++() + { + ++i; return *this; } - inline const_iterator operator++(int) { + const_iterator operator++(int) + { const_iterator r = *this; - i = i->nextNode(); + ++i; return r; } - inline const_iterator &operator--() { - i = i->previousNode(); + const_iterator &operator--() + { + --i; return *this; } - inline const_iterator operator--(int) { + const_iterator operator--(int) + { const_iterator r = *this; - i = i->previousNode(); + --i; return r; } - inline const_iterator operator+(qsizetype j) const - { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline const_iterator operator-(qsizetype j) const { return operator+(-j); } - inline const_iterator &operator+=(qsizetype j) { return *this = *this + j; } - inline const_iterator &operator-=(qsizetype j) { return *this = *this - j; } - friend inline const_iterator operator+(qsizetype j, const_iterator k) { return k + j; } - - friend class QMap<Key, T>; - friend class QMultiMap<Key, T>; }; - friend class const_iterator; class key_iterator { @@ -546,814 +513,870 @@ public: typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator; // STL style - inline iterator begin() { detach(); return iterator(d->begin()); } - inline const_iterator begin() const { return const_iterator(d->begin()); } - inline const_iterator constBegin() const { return const_iterator(d->begin()); } - inline const_iterator cbegin() const { return const_iterator(d->begin()); } - inline iterator end() { detach(); return iterator(d->end()); } - inline const_iterator end() const { return const_iterator(d->end()); } - inline const_iterator constEnd() const { return const_iterator(d->end()); } - inline const_iterator cend() const { return const_iterator(d->end()); } - inline key_iterator keyBegin() const { return key_iterator(begin()); } - inline key_iterator keyEnd() const { return key_iterator(end()); } - inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); } - inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); } - inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); } - inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); } - inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); } - inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); } - iterator erase(iterator it); + iterator begin() { detach(); return iterator(d->m.begin()); } + const_iterator begin() const { if (!d) return const_iterator(); return const_iterator(d->m.cbegin()); } + const_iterator constBegin() const { return begin(); } + const_iterator cbegin() const { return begin(); } + iterator end() { detach(); return iterator(d->m.end()); } + const_iterator end() const { if (!d) return const_iterator(); return const_iterator(d->m.end()); } + const_iterator constEnd() const { return end(); } + const_iterator cend() const { return end(); } + key_iterator keyBegin() const { return key_iterator(begin()); } + key_iterator keyEnd() const { return key_iterator(end()); } + key_value_iterator keyValueBegin() { return key_value_iterator(begin()); } + key_value_iterator keyValueEnd() { return key_value_iterator(end()); } + const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); } + const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); } + const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); } + const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); } + + iterator erase(const_iterator it) + { + if (!d) + return iterator(); + + if (!d.isShared()) + return iterator(d->m.erase(it.i)); + + MapData *newData = new MapData; + const auto newDataEnd = newData->m.end(); + + auto i = d->m.begin(); + auto e = d->m.end(); + size_type steps = 0; + + while (i != it.i) { + newData->m.insert(newDataEnd, *i); + ++i; + ++steps; + } + + if (i != e) + ++i; + + while (i != e) + newData->m.insert(newDataEnd, *i); + + d.reset(newData); + + auto result = std::next(d->m.begin(), steps); + return iterator(result); + } // more Qt typedef iterator Iterator; typedef const_iterator ConstIterator; - inline qsizetype count() const { return d->size; } - iterator find(const Key &key); - const_iterator find(const Key &key) const; - const_iterator constFind(const Key &key) const; - iterator lowerBound(const Key &key); - const_iterator lowerBound(const Key &key) const; - iterator upperBound(const Key &key); - const_iterator upperBound(const Key &key) const; - iterator insert(const Key &key, const T &value); - iterator insert(const_iterator pos, const Key &key, const T &value); - void insert(const QMap<Key, T> &map); -#if QT_DEPRECATED_SINCE(5, 15) - QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") iterator insertMulti(const Key &key, const T &value); - QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue); - QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") QMap<Key, T> &unite(const QMap<Key, T> &other); -#endif - // STL compatibility - typedef Key key_type; - typedef T mapped_type; - typedef T value_type; - typedef qptrdiff difference_type; - typedef qsizetype size_type; - inline bool empty() const { return isEmpty(); } - QPair<iterator, iterator> equal_range(const Key &akey); - QPair<const_iterator, const_iterator> equal_range(const Key &akey) const; + iterator find(const Key &key) + { + detach(); + return iterator(d->m.find(key)); + } + + const_iterator find(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.find(key)); + } + + const_iterator constFind(const Key &key) const + { + return find(key); + } + + iterator lowerBound(const Key &key) + { + detach(); + return iterator(d->m.lower_bound(key)); + } + + const_iterator lowerBound(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.lower_bound(key)); + } + + iterator upperBound(const Key &key) + { + detach(); + return iterator(d->m.upper_bound(key)); + } -#ifdef Q_MAP_DEBUG - void dump() const; + const_iterator upperBound(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.upper_bound(key)); + } + + iterator insert(const Key &key, const T &value) + { + // TODO: improve. In case of assignment, why copying first? + detach(); + return iterator(d->m.insert_or_assign(key, value).first); + } + + iterator insert(const_iterator pos, const Key &key, const T &value) + { + // TODO: improve. In case of assignment, why copying first? + auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0; + detach(); + auto detachedPos = std::next(d->m.cbegin(), posDistance); + return iterator(d->m.insert_or_assign(detachedPos, key, value)); + } + + void insert(const QMap<Key, T> &map) + { + // TODO: improve. In case of assignment, why copying first? + if (map.isEmpty()) + return; + + detach(); + +#ifdef __cpp_lib_node_extract + auto copy = map.d->m; + copy.merge(std::move(d->m)); + d->m = std::move(copy); +#else + // this is a std::copy, but we can't use std::inserter (need insert_or_assign...). + // copy in reverse order, trying to make effective use of insertionHint. + auto insertionHint = d->m.end(); + auto mapIt = map.d->m.crbegin(); + auto end = map.d->m.crend(); + for (; mapIt != end; ++mapIt) + insertionHint = d->m.insert_or_assign(insertionHint, mapIt->first, mapIt->second); #endif + } -private: - void detach_helper(); - bool isValidIterator(const const_iterator &ci) const + void insert(QMap<Key, T> &&map) { -#if defined(QT_DEBUG) && !defined(Q_MAP_NO_ITERATOR_DEBUG) - const QMapNodeBase *n = ci.i; - while (n->parent()) - n = n->parent(); - return n->left == d->root(); + if (!map.d || map.d->m.empty()) + return; + + detach(); + +#ifdef __cpp_lib_node_extract + map.d->m.merge(std::move(d->m)); + *this = std::move(map); #else - Q_UNUSED(ci); - return true; + // same as above + auto insertionHint = d->m.end(); + auto mapIt = map.d->m.crbegin(); + auto end = map.d->m.crend(); + for (; mapIt != end; ++mapIt) + insertionHint = d->m.insert_or_assign(insertionHint, std::move(mapIt->first), std::move(mapIt->second)); #endif } - friend class QMultiMap<Key, T>; -}; + // STL compatibility + inline bool empty() const + { + return isEmpty(); + } -template <class Key, class T> -inline QMap<Key, T>::QMap(const QMap<Key, T> &other) -{ - if (other.d->ref.ref()) { - d = other.d; - } else { - d = QMapData<Key, T>::create(); - if (other.d->header.left) { - d->header.left = static_cast<Node *>(other.d->header.left)->copy(d); - d->header.left->setParent(&d->header); - d->recalcMostLeftNode(); - } + QPair<iterator, iterator> equal_range(const Key &akey) + { + detach(); + auto result = d->m.equal_range(akey); + return {iterator(result.first), iterator(result.second)}; } -} -template <class Key, class T> -Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other) -{ - if (d != other.d) { - QMap<Key, T> tmp(other); - tmp.swap(*this); + QPair<const_iterator, const_iterator> equal_range(const Key &akey) const + { + if (!d) + return {}; + auto result = d->m.equal_range(akey); + return {const_iterator(result.first), const_iterator(result.second)}; } - return *this; -} +}; -template <class Key, class T> -Q_INLINE_TEMPLATE void QMap<Key, T>::clear() +Q_DECLARE_ASSOCIATIVE_ITERATOR(Map) +Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map) + +template <typename AKey, typename AT> +QTypeTraits::compare_eq_result<AKey, AT> operator==(const QMap<AKey, AT> &lhs, const QMap<AKey, AT> &rhs) { - *this = QMap<Key, T>(); + if (lhs.d == rhs.d) + return true; + if (!lhs.d) + return rhs == lhs; + Q_ASSERT(lhs.d); + return rhs.d ? (lhs.d->m == rhs.d->m) : lhs.d->m.empty(); } -QT_WARNING_PUSH -QT_WARNING_DISABLE_CLANG("-Wreturn-stack-address") - -template <class Key, class T> -Q_INLINE_TEMPLATE T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const +template <typename AKey, typename AT> +QTypeTraits::compare_eq_result<AKey, AT> operator!=(const QMap<AKey, AT> &lhs, const QMap<AKey, AT> &rhs) { - Node *n = d->findNode(akey); - return n ? n->value : adefaultValue; + return !(lhs == rhs); } -QT_WARNING_POP -template <class Key, class T> -Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const -{ - return value(akey); -} +// +// QMultiMap +// template <class Key, class T> -Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey) +class QMultiMap { - detach(); - Node *n = d->findNode(akey); - if (!n) - return *insert(akey, T()); - return n->value; -} + using MapData = QMapData<std::multimap<Key, T>>; + QtPrivate::QExplicitlySharedDataPointerV2<MapData> d; -template <class Key, class T> -Q_INLINE_TEMPLATE qsizetype QMap<Key, T>::count(const Key &akey) const -{ - Node *firstNode; - Node *lastNode; - d->nodeRange(akey, &firstNode, &lastNode); - - const_iterator ci_first(firstNode); - const const_iterator ci_last(lastNode); - int cnt = 0; - while (ci_first != ci_last) { - ++cnt; - ++ci_first; - } - return cnt; -} +public: + using key_type = Key; + using mapped_type = T; + using difference_type = qptrdiff; + using size_type = qsizetype; -template <class Key, class T> -Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const -{ - return d->findNode(akey) != nullptr; -} + constexpr QMultiMap() noexcept {} -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey, const T &avalue) -{ - detach(); - Node *n = d->root(); - Node *y = d->end(); - Node *lastNode = nullptr; - bool left = true; - while (n) { - y = n; - if (!qMapLessThanKey(n->key, akey)) { - lastNode = n; - left = true; - n = n->leftNode(); - } else { - left = false; - n = n->rightNode(); - } + // implicitly generated special member functions are OK! + + QMultiMap(std::initializer_list<std::pair<Key,T>> list) + { + for (auto &p : list) + insert(p.first, p.second); } - if (lastNode && !qMapLessThanKey(akey, lastNode->key)) { - lastNode->value = avalue; - return iterator(lastNode); + + void swap(QMultiMap<Key, T> &other) noexcept + { + qSwap(d, other.d); } - Node *z = d->createNode(akey, avalue, y, left); - return iterator(z); -} -template <class Key, class T> -typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &akey, const T &avalue) -{ - if (d->ref.isShared()) - return this->insert(akey, avalue); - - Q_ASSERT_X(isValidIterator(pos), "QMap::insert", "The specified const_iterator argument 'it' is invalid"); - - if (pos == constEnd()) { - // Hint is that the Node is larger than (or equal to) the largest value. - Node *n = static_cast<Node *>(pos.i->left); - if (n) { - while (n->right) - n = static_cast<Node *>(n->right); - - if (!qMapLessThanKey(n->key, akey)) - return this->insert(akey, avalue); // ignore hint - // This can be optimized by checking equal too. - // we can overwrite if previous node key is strictly smaller - // (or there is no previous node) - - Node *z = d->createNode(akey, avalue, n, false); // insert right most - return iterator(z); - } - return this->insert(akey, avalue); - } else { - // Hint indicates that the node should be less (or equal to) the hint given - // but larger than the previous value. - Node *next = const_cast<Node*>(pos.i); - if (qMapLessThanKey(next->key, akey)) - return this->insert(akey, avalue); // ignore hint - - if (pos == constBegin()) { - // There is no previous value - // Maybe overwrite left most value - if (!qMapLessThanKey(akey, next->key)) { - next->value = avalue; // overwrite current iterator - return iterator(next); - } - // insert left most. - Node *z = d->createNode(akey, avalue, begin().i, true); - return iterator(z); - } else { - Node *prev = const_cast<Node*>(pos.i->previousNode()); - if (!qMapLessThanKey(prev->key, akey)) { - return this->insert(akey, avalue); // ignore hint - } - // Hint is ok - if (!qMapLessThanKey(akey, next->key)) { - next->value = avalue; // overwrite current iterator - return iterator(next); - } + explicit QMultiMap(const std::multimap<Key, T> &other) + : d(other.empty() ? nullptr : new MapData(other)) + { + } - // we need to insert (not overwrite) - if (prev->right == nullptr) { - Node *z = d->createNode(akey, avalue, prev, false); - return iterator(z); - } - if (next->left == nullptr) { - Node *z = d->createNode(akey, avalue, next, true); - return iterator(z); - } - Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr. - return this->insert(akey, avalue); - } + explicit QMultiMap(std::multimap<Key, T> &&other) + : d(other.empty() ? nullptr : new MapData(std::move(other))) + { } -} -template <class Key, class T> -Q_INLINE_TEMPLATE void QMap<Key, T>::insert(const QMap<Key, T> &map) -{ - if (d == map.d) - return; - - detach(); - - Node *n = d->root(); - auto it = map.cbegin(); - const auto e = map.cend(); - while (it != e) { - // Insertion here is based on insert(Key, T) - auto parent = d->end(); - bool left = true; - Node *lastNode = nullptr; - while (n) { - parent = n; - if (!qMapLessThanKey(n->key, it.key())) { - lastNode = n; - n = n->leftNode(); - left = true; - } else { - n = n->rightNode(); - left = false; - } - } - if (lastNode && !qMapLessThanKey(it.key(), lastNode->key)) { - lastNode->value = it.value(); - n = lastNode; - } else { - n = d->createNode(it.key(), it.value(), parent, left); - } - ++it; - if (it != e) { - // Move back up the tree until we find the next branch or node which is - // relevant for the next key. - while (n != d->root() && qMapLessThanKey(n->key, it.key())) - n = static_cast<Node *>(n->parent()); + // CHANGE: return type + Q_DECL_DEPRECATED_X("Use toStdMultiMap instead") + std::multimap<Key, T> toStdMap() const + { + return toStdMultiMap(); + } + + std::multimap<Key, T> toStdMultiMap() const & + { + if (d) + return d->m; + return {}; + } + + std::multimap<Key, T> toStdMultiMap() && + { + if (d) { + if (d.isShared()) + return d->m; + else + return std::move(d->m); } + + return {}; } -} + // CHANGE: non-member equality comparison + template <typename AKey, typename AT> + friend QTypeTraits::compare_eq_result<AKey, AT> operator==(const QMultiMap<AKey, AT> &lhs, const QMultiMap<AKey, AT> &rhs); + template <typename AKey, typename AT> + friend QTypeTraits::compare_eq_result<AKey, AT> operator!=(const QMultiMap<AKey, AT> &lhs, const QMultiMap<AKey, AT> &rhs); -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const -{ - Node *n = d->findNode(akey); - return const_iterator(n ? n : d->end()); -} + // TODO: add the other comparison operators; std::multimap has them. -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const -{ - return constFind(akey); -} + size_type size() const { return d ? size_type(d->m.size()) : size_type(0); } -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey) -{ - detach(); - Node *n = d->findNode(akey); - return iterator(n ? n : d->end()); -} + bool isEmpty() const { return d ? d->m.empty() : true; } -template <class Key, class T> -QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey) -{ - detach(); - Node *firstNode, *lastNode; - d->nodeRange(akey, &firstNode, &lastNode); - return QPair<iterator, iterator>(iterator(firstNode), iterator(lastNode)); -} + void detach() + { + if (d) + d.detach(); + else + d.reset(new MapData); + } -template <class Key, class T> -QPair<typename QMap<Key, T>::const_iterator, typename QMap<Key, T>::const_iterator> -QMap<Key, T>::equal_range(const Key &akey) const -{ - Node *firstNode, *lastNode; - d->nodeRange(akey, &firstNode, &lastNode); - return qMakePair(const_iterator(firstNode), const_iterator(lastNode)); -} + bool isDetached() const noexcept + { + return d ? !d.isShared() : false; // false makes little sense, but that's shared_null's behavior... + } -#ifdef Q_MAP_DEBUG -template <class Key, class T> -void QMap<Key, T>::dump() const -{ - const_iterator it = begin(); - qDebug("map dump:"); - while (it != end()) { - const QMapNodeBase *n = it.i; - int depth = 0; - while (n && n != d->root()) { - ++depth; - n = n->parent(); - } - QByteArray space(4*depth, ' '); - qDebug() << space << (it.i->color() == Node::Red ? "Red " : "Black") << it.i << it.i->left << it.i->right - << it.key() << it.value(); - ++it; + bool isSharedWith(const QMultiMap<Key, T> &other) const noexcept + { + return d == other.d; // also this makes little sense? } - qDebug("---------"); -} -#endif -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE qsizetype QMap<Key, T>::remove(const Key &akey) -{ - detach(); - qsizetype n = 0; - while (Node *node = d->findNode(akey)) { - d->deleteNode(node); - ++n; + void clear() + { + if (!d) + return; + + if (!d.isShared()) + d->m.clear(); + else + d.reset(); } - return n; -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey) -{ - detach(); + size_type remove(const Key &key) + { + if (!d) + return 0; - Node *node = d->findNode(akey); - if (node) { - T t = std::move(node->value); - d->deleteNode(node); - return t; + if (!d.isShared()) + return size_type(d->m.erase(key)); + + MapData *newData = new MapData; + size_type result = newData->copyIfNotEquivalentTo(d->m, key); + + d.reset(newData); + + return result; } - return T(); -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it) -{ - if (it == iterator(d->end())) - return it; + size_type remove(const Key &key, const T &value) + { + if (!d) + return 0; - Q_ASSERT_X(isValidIterator(const_iterator(it)), "QMap::erase", "The specified iterator argument 'it' is invalid"); + // TODO: improve. Copy over only the elements not to be removed. + detach(); - if (d->ref.isShared()) { - const_iterator oldBegin = constBegin(); - const_iterator old = const_iterator(it); - qsizetype backStepsWithSameKey = 0; + size_type result = 0; + const auto &keyCompare = d->m.key_comp(); - while (old != oldBegin) { - --old; - if (qMapLessThanKey(old.key(), it.key())) - break; - ++backStepsWithSameKey; + auto i = d->m.find(key); + const auto e = d->m.end(); + + while (i != e && !keyCompare(key, i->first)) { + if (i->second == value) { + i = d->m.erase(i); + ++result; + } else { + ++i; + } } - it = find(old.key()); // ensures detach - Q_ASSERT_X(it != iterator(d->end()), "QMap::erase", "Unable to locate same key in erase after detach."); + return result; + } - while (backStepsWithSameKey > 0) { - ++it; - --backStepsWithSameKey; + T take(const Key &key) + { + if (!d) + return T(); + + // TODO: improve. There is no need of copying all the + // elements (the one to be removed can be skipped). + detach(); + + auto i = d->m.find(key); + if (i != d->m.end()) { + T result(std::move(i->second)); + d->m.erase(i); + return result; } + return T(); } - Node *n = it.i; - ++it; - d->deleteNode(n); - return it; -} + bool contains(const Key &key) const + { + if (!d) + return false; + auto i = d->m.find(key); + return i != d->m.end(); + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper() -{ - QMapData<Key, T> *x = QMapData<Key, T>::create(); - if (d->header.left) { - x->header.left = static_cast<Node *>(d->header.left)->copy(x); - x->header.left->setParent(&x->header); - } - if (!d->ref.deref()) - d->destroy(); - d = x; - d->recalcMostLeftNode(); -} + bool contains(const Key &key, const T &value) const + { + return find(key, value) != end(); + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const -{ - QList<Key> res; - res.reserve(size()); - const_iterator i = begin(); - while (i != end()) { - res.append(i.key()); - ++i; - } - return res; -} + // ### Qt 6: deprecate value->key lookup. + //Q_DECL_DEPRECATED_X("This function is inefficient; don't use it") + Key key(const T &value, const Key &defaultKey = Key()) const + { + if (!d) + return defaultKey; -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const -{ - QList<Key> res; - const_iterator i = begin(); - while (i != end()) { - if (i.value() == avalue) - res.append(i.key()); - ++i; - } - return res; -} + return d->key(value, defaultKey); + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const -{ - const_iterator i = begin(); - while (i != end()) { - if (i.value() == avalue) - return i.key(); - ++i; + T value(const Key &key, const T &defaultValue = T()) const + { + if (!d) + return defaultValue; + const auto i = d->m.find(key); + if (i != d->m.cend()) + return i->second; + return defaultValue; } - return defaultKey; -} + // ### Qt 6: deprecate value->key lookup. + QList<Key> keys() const + { + if (!d) + return {}; + return d->keys(); + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const -{ - QList<T> res; - res.reserve(size()); - const_iterator i = begin(); - while (i != end()) { - res.append(i.value()); - ++i; - } - return res; -} + QList<Key> keys(const T &value) const + { + if (!d) + return {}; + return d->keys(value); + } -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &akey) const -{ - Node *lb = d->root() ? d->root()->lowerBound(akey) : nullptr; - if (!lb) - lb = d->end(); - return const_iterator(lb); -} + QList<Key> uniqueKeys() const + { + QList<Key> result; + if (!d) + return result; -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey) -{ - detach(); - Node *lb = d->root() ? d->root()->lowerBound(akey) : nullptr; - if (!lb) - lb = d->end(); - return iterator(lb); -} + result.reserve(size()); -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator -QMap<Key, T>::upperBound(const Key &akey) const -{ - Node *ub = d->root() ? d->root()->upperBound(akey) : nullptr; - if (!ub) - ub = d->end(); - return const_iterator(ub); -} + std::unique_copy(keyBegin(), keyEnd(), + std::back_inserter(result)); -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey) -{ - detach(); - Node *ub = d->root() ? d->root()->upperBound(akey) : nullptr; - if (!ub) - ub = d->end(); - return iterator(ub); -} + result.shrink_to_fit(); + return result; + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other) -{ - d = QMapData<Key, T>::create(); - typename std::map<Key,T>::const_iterator it = other.end(); - while (it != other.begin()) { - --it; - d->createNode((*it).first, (*it).second, d->begin(), true); // insert on most left node. + QList<T> values() const + { + if (!d) + return {}; + return d->values(); } -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const -{ - std::map<Key, T> map; - const_iterator it = end(); - while (it != begin()) { - --it; - map.insert(map.begin(), std::pair<Key, T>(it.key(), it.value())); + QList<T> values(const Key &key) const + { + QList<T> result; + const auto range = equal_range(key); + result.reserve(std::distance(range.first, range.second)); + std::copy(range.first, range.second, std::back_inserter(result)); + return result; } - return map; -} -template <class Key, class T> -class QMultiMap : public QMap<Key, T> -{ -public: - QMultiMap() noexcept {} - inline QMultiMap(std::initializer_list<std::pair<Key,T> > list) - { - for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) - insert(it->first, it->second); - } - QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {} - QMultiMap(QMap<Key, T> &&other) noexcept : QMap<Key, T>(std::move(other)) {} - void swap(QMultiMap<Key, T> &other) noexcept { QMap<Key, T>::swap(other); } - - QList<Key> uniqueKeys() const; - QList<T> values(const Key &key) const; - - inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value) - { return QMap<Key, T>::insert(key, value); } - typename QMap<Key, T>::iterator insert(const Key &key, const T &value); - //! [qmultimap-insert-pos] - typename QMap<Key, T>::iterator insert(typename QMap<Key, T>::const_iterator pos, - const Key &key, const T &value); - - //! [qmultimap-unite] - QMultiMap &unite(const QMultiMap &other); - inline QMultiMap &operator+=(const QMultiMap &other) - { return unite(other); } - inline QMultiMap operator+(const QMultiMap &other) const - { QMultiMap result = *this; result += other; return result; } - - using QMap<Key, T>::contains; - using QMap<Key, T>::remove; - using QMap<Key, T>::count; - using QMap<Key, T>::find; - using QMap<Key, T>::constFind; - using QMap<Key, T>::values; - using QMap<Key, T>::size; - using QMap<Key, T>::detach; - using QMap<Key, T>::erase; - using QMap<Key, T>::isValidIterator; - using typename QMap<Key, T>::Node; - - bool contains(const Key &key, const T &value) const; - - qsizetype remove(const Key &key, const T &value); - - qsizetype count(const Key &key, const T &value) const; - - typename QMap<Key, T>::iterator find(const Key &key, const T &value) { - typename QMap<Key, T>::iterator i(find(key)); - typename QMap<Key, T>::iterator end(this->end()); - while (i != end && !qMapLessThanKey<Key>(key, i.key())) { - if (i.value() == value) - return i; + size_type count(const Key &key) const + { + if (!d) + return 0; + return d->count(key); + } + + size_type count(const Key &key, const T &value) const + { + if (!d) + return 0; + + // TODO: improve; no need of scanning the equal_range twice. + auto range = d->m.equal_range(key); + + return size_type(std::count_if(range.first, + range.second, + MapData::valueIsEqualTo(value))); + } + + inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); } + inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return std::next(constEnd(), -1).key(); } + + inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); } + inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); } + inline T &last() { Q_ASSERT(!isEmpty()); return *std::next(end(), -1); } + inline const T &last() const { Q_ASSERT(!isEmpty()); return *std::next(constEnd(), -1); } + + class const_iterator; + + class iterator + { + friend class QMultiMap<Key, T>; + friend class const_iterator; + + typename MapData::Map::iterator i; + explicit iterator(typename MapData::Map::iterator it) : i(it) {} + public: + typedef std::bidirectional_iterator_tag iterator_category; + typedef qptrdiff difference_type; + typedef T value_type; + typedef T *pointer; + typedef T &reference; + + iterator() = default; + + const Key &key() const { return i->first; } + T &value() const { return i->second; } + T &operator*() const { return i->second; } + T *operator->() const { return &i->second; } + friend bool operator==(const iterator &lhs, const iterator &rhs) { return lhs.i == rhs.i; } + friend bool operator!=(const iterator &lhs, const iterator &rhs) { return lhs.i != rhs.i; } + + iterator &operator++() + { ++i; + return *this; } - return end; - } - typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const { - typename QMap<Key, T>::const_iterator i(constFind(key)); - typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd()); - while (i != end && !qMapLessThanKey<Key>(key, i.key())) { - if (i.value() == value) - return i; + iterator operator++(int) + { + iterator r = *this; ++i; + return r; } - return end; - } - typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const - { return find(key, value); } -private: - T &operator[](const Key &key); - const T operator[](const Key &key) const; -}; - -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QMultiMap<Key, T>::uniqueKeys() const -{ - QList<Key> res; - res.reserve(size()); // May be too much, but assume short lifetime - typename QMap<Key, T>::const_iterator i = this->begin(); - if (i != this->end()) { - for (;;) { - const Key &aKey = i.key(); - res.append(aKey); - do { - if (++i == this->end()) - goto break_out_of_outer_loop; - } while (!qMapLessThanKey(aKey, i.key())); // loop while (key == i.key()) + iterator &operator--() + { + --i; + return *this; } - } -break_out_of_outer_loop: - return res; -} + iterator operator--(int) + { + iterator r = *this; + --i; + return r; + } + }; -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QMultiMap<Key, T>::values(const Key &akey) const -{ - QList<T> res; - Node *n = this->d->findNode(akey); - if (n) { - typename QMap<Key, T>::const_iterator it(n); - do { - res.append(*it); - ++it; - } while (it != this->constEnd() && !qMapLessThanKey<Key>(akey, it.key())); - } - return res; -} + class const_iterator + { + friend class QMultiMap<Key, T>; + typename MapData::Map::const_iterator i; + explicit const_iterator(typename MapData::Map::const_iterator it) : i(it) {} -template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &akey, - const T &avalue) -{ - detach(); - Node* y = this->d->end(); - Node* x = static_cast<Node *>(this->d->root()); - bool left = true; - while (x != nullptr) { - left = !qMapLessThanKey(x->key, akey); - y = x; - x = left ? x->leftNode() : x->rightNode(); - } - Node *z = this->d->createNode(akey, avalue, y, left); - return typename QMap<Key, T>::iterator(z); -} + public: + typedef std::bidirectional_iterator_tag iterator_category; + typedef qptrdiff difference_type; + typedef T value_type; + typedef const T *pointer; + typedef const T &reference; -#ifndef Q_CLANG_QDOC -template <class Key, class T> -typename QMap<Key, T>::iterator QMultiMap<Key, T>::insert(typename QMap<Key, T>::const_iterator pos, - const Key &akey, const T &avalue) -{ - if (this->d->ref.isShared()) - return insert(akey, avalue); - - Q_ASSERT_X(isValidIterator(pos), "QMap::insert", "The specified const_iterator argument 'pos' is invalid"); - - if (pos == this->constEnd()) { - // Hint is that the Node is larger than (or equal to) the largest value. - Node *n = static_cast<Node *>(pos.i->left); - if (n) { - while (n->right) - n = static_cast<Node *>(n->right); - - if (!qMapLessThanKey(n->key, akey)) - return insert(akey, avalue); // ignore hint - Node *z = this->d->createNode(akey, avalue, n, false); // insert right most - return typename QMap<Key, T>::iterator(z); + const_iterator() = default; + /* implicit */ const_iterator(const iterator &o) { i = o.i; } + + const Key &key() const { return i->first; } + const T &value() const { return i->second; } + const T &operator*() const { return i->second; } + const T *operator->() const { return &i->second; } + friend bool operator==(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i == rhs.i; } + friend bool operator!=(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i != rhs.i; } + + const_iterator &operator++() + { + ++i; + return *this; } - return insert(akey, avalue); - } else { - // Hint indicates that the node should be less (or equal to) the hint given - // but larger than the previous value. - Node *next = const_cast<Node*>(pos.i); - if (qMapLessThanKey(next->key, akey)) - return insert(akey, avalue); // ignore hint - - if (pos == this->constBegin()) { - // There is no previous value (insert left most) - Node *z = this->d->createNode(akey, avalue, this->begin().i, true); - return typename QMap<Key, T>::iterator(z); - } else { - Node *prev = const_cast<Node*>(pos.i->previousNode()); - if (!qMapLessThanKey(prev->key, akey)) - return insert(akey, avalue); // ignore hint - - // Hint is ok - do insert - if (prev->right == nullptr) { - Node *z = this->d->createNode(akey, avalue, prev, false); - return typename QMap<Key, T>::iterator(z); - } - if (next->left == nullptr) { - Node *z = this->d->createNode(akey, avalue, next, true); - return typename QMap<Key, T>::iterator(z); - } - Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr. - return insert(akey, avalue); + const_iterator operator++(int) + { + const_iterator r = *this; + ++i; + return r; } - } -} + const_iterator &operator--() + { + --i; + return *this; + } + const_iterator operator--(int) + { + const_iterator r = *this; + --i; + return r; + } + }; -template <class Key, class T> -Q_INLINE_TEMPLATE QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other) -{ - QMultiMap<Key, T> copy(other); - typename QMap<Key, T>::const_iterator it = copy.constEnd(); - const typename QMap<Key, T>::const_iterator b = copy.constBegin(); - while (it != b) { - --it; - insert(it.key(), it.value()); - } - return *this; -} -#endif // Q_CLANG_QDOC + class key_iterator + { + const_iterator i; -template <class Key, class T> -Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const -{ - return constFind(key, value) != QMap<Key, T>::constEnd(); -} + public: + typedef typename const_iterator::iterator_category iterator_category; + typedef typename const_iterator::difference_type difference_type; + typedef Key value_type; + typedef const Key *pointer; + typedef const Key &reference; -template <class Key, class T> -Q_INLINE_TEMPLATE qsizetype QMultiMap<Key, T>::remove(const Key &key, const T &value) -{ - qsizetype n = 0; - typename QMap<Key, T>::iterator i(find(key)); - typename QMap<Key, T>::iterator end(QMap<Key, T>::end()); - while (i != end && !qMapLessThanKey<Key>(key, i.key())) { - if (i.value() == value) { - i = erase(i); - ++n; - } else { + key_iterator() = default; + explicit key_iterator(const_iterator o) : i(o) { } + + const Key &operator*() const { return i.key(); } + const Key *operator->() const { return &i.key(); } + bool operator==(key_iterator o) const { return i == o.i; } + bool operator!=(key_iterator o) const { return i != o.i; } + + inline key_iterator &operator++() { ++i; return *this; } + inline key_iterator operator++(int) { return key_iterator(i++);} + inline key_iterator &operator--() { --i; return *this; } + inline key_iterator operator--(int) { return key_iterator(i--); } + const_iterator base() const { return i; } + }; + + typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator; + typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator; + + // STL style + iterator begin() { detach(); return iterator(d->m.begin()); } + const_iterator begin() const { if (!d) return const_iterator(); return const_iterator(d->m.cbegin()); } + const_iterator constBegin() const { return begin(); } + const_iterator cbegin() const { return begin(); } + iterator end() { detach(); return iterator(d->m.end()); } + const_iterator end() const { if (!d) return const_iterator(); return const_iterator(d->m.end()); } + const_iterator constEnd() const { return end(); } + const_iterator cend() const { return end(); } + key_iterator keyBegin() const { return key_iterator(begin()); } + key_iterator keyEnd() const { return key_iterator(end()); } + key_value_iterator keyValueBegin() { return key_value_iterator(begin()); } + key_value_iterator keyValueEnd() { return key_value_iterator(end()); } + const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); } + const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); } + const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); } + const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); } + + iterator erase(const_iterator it) + { + if (!d) + return iterator(); + + if (!d.isShared()) + return iterator(d->m.erase(it.i)); + + auto newData = new MapData; + const auto newDataEnd = newData->m.end(); + + auto i = d->m.begin(); + auto e = d->m.end(); + size_type steps = 0; + + while (i != it.i) { + newData->m.insert(newDataEnd, *i); ++i; + ++steps; } + + if (i != e) + ++i; + + while (i != e) + newData->m.insert(newDataEnd, *i++); + + d.reset(newData); + + auto result = std::next(d->m.begin(), steps); + return iterator(result); } - return n; -} -template <class Key, class T> -Q_INLINE_TEMPLATE qsizetype QMultiMap<Key, T>::count(const Key &key, const T &value) const -{ - qsizetype n = 0; - typename QMap<Key, T>::const_iterator i(constFind(key)); - typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd()); - while (i != end && !qMapLessThanKey<Key>(key, i.key())) { - if (i.value() == value) - ++n; - ++i; - } - return n; -} + // more Qt + typedef iterator Iterator; + typedef const_iterator ConstIterator; -#if QT_DEPRECATED_SINCE(5, 15) -template<class Key, class T> -QList<Key> QMap<Key, T>::uniqueKeys() const -{ - return static_cast<const QMultiMap<Key, T> *>(this)->uniqueKeys(); -} + size_type count() const + { + return size(); + } -template<class Key, class T> -QList<T> QMap<Key, T>::values(const Key &key) const + iterator find(const Key &key) + { + detach(); + return iterator(d->m.find(key)); + } + + const_iterator find(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.find(key)); + } + + const_iterator constFind(const Key &key) const + { + return find(key); + } + + iterator find(const Key &key, const T &value) + { + if (!d) + return iterator(); + + auto range = d->m.equal_range(key); + auto i = std::find_if(range.first, range.second, + MapData::valueIsEqualTo(value)); + + return iterator(i); + } + + const_iterator find(const Key &key, const T &value) const + { + if (!d) + return const_iterator(); + // a bit evil, but effective + return const_iterator(const_cast<QMultiMap *>(this)->find(key, value)); + } + + const_iterator constFind(const Key &key, const T &value) const + { + return find(key, value); + } + + iterator lowerBound(const Key &key) + { + detach(); + return iterator(d->m.lower_bound(key)); + } + + const_iterator lowerBound(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.lower_bound(key)); + } + + iterator upperBound(const Key &key) + { + detach(); + return iterator(d->m.upper_bound(key)); + } + + const_iterator upperBound(const Key &key) const + { + if (!d) + return const_iterator(); + return const_iterator(d->m.upper_bound(key)); + } + + iterator insert(const Key &key, const T &value) + { + detach(); + // note that std::multimap inserts at the end of an equal_range for a key, + // QMultiMap at the beginning. + auto i = d->m.lower_bound(key); + return iterator(d->m.insert(i, {key, value})); + } + + iterator insert(const_iterator pos, const Key &key, const T &value) + { + auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0; + detach(); + auto detachedPos = std::next(d->m.cbegin(), posDistance); + return iterator(d->m.insert(detachedPos, {key, value})); + } + + // CHANGE: provide insertMulti for compatibility + iterator insertMulti(const Key &key, const T &value) + { + return insert(key, value); + } + + iterator insertMulti(const_iterator pos, const Key &key, const T &value) + { + return insert(pos, key, value); + } + + void insert(const QMultiMap<Key, T> &map) + { + if (map.isEmpty()) + return; + + detach(); + + auto copy = map.d->m; +#ifdef __cpp_lib_node_extract + copy.merge(std::move(d->m)); +#else + copy.insert(std::make_move_iterator(d->m.begin()), + std::make_move_iterator(d->m.end())); +#endif + d->m = std::move(copy); + } + + void insert(QMultiMap<Key, T> &&map) + { + if (!map.d || map.d->m.empty()) + return; + + detach(); + +#ifdef __cpp_lib_node_extract + map.d->m.merge(std::move(d->m)); +#else + map.d->m.insert(std::make_move_iterator(d->m.begin()), + std::make_move_iterator(d->m.end())); +#endif + *this = std::move(map); + } + + iterator replace(const Key &key, const T &value) + { + // TODO: improve. No need of copying and then overwriting. + detach(); + + // Similarly, improve here (e.g. lower_bound and hinted insert); + // there's no insert_or_assign on multimaps + auto i = d->m.find(key); + if (i != d->m.end()) + i->second = value; + else + i = d->m.insert({key, value}); + + return iterator(i); + } + + // STL compatibility + inline bool empty() const { return isEmpty(); } + + QPair<iterator, iterator> equal_range(const Key &akey) + { + detach(); + auto result = d->m.equal_range(akey); + return {iterator(result.first), iterator(result.second)}; + } + + QPair<const_iterator, const_iterator> equal_range(const Key &akey) const + { + if (!d) + return {}; + auto result = d->m.equal_range(akey); + return {const_iterator(result.first), const_iterator(result.second)}; + } + + QMultiMap &unite(const QMultiMap &other) + { + insert(other); + return *this; + } +}; + +Q_DECLARE_ASSOCIATIVE_ITERATOR(MultiMap) +Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(MultiMap) + +template <typename AKey, typename AT> +QTypeTraits::compare_eq_result<AKey, AT> operator==(const QMultiMap<AKey, AT> &lhs, const QMultiMap<AKey, AT> &rhs) { - return static_cast<const QMultiMap<Key, T> *>(this)->values(key); + if (lhs.d == rhs.d) + return true; + if (!lhs.d) + return rhs == lhs; + Q_ASSERT(lhs.d); + return rhs.d ? (lhs.d->m == rhs.d->m) : lhs.d->m.empty(); } -template<class Key, class T> -typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value) +template <typename AKey, typename AT> +QTypeTraits::compare_eq_result<AKey, AT> operator!=(const QMultiMap<AKey, AT> &lhs, const QMultiMap<AKey, AT> &rhs) { - return static_cast<QMultiMap<Key, T> *>(this)->insert(key, value); + return !(lhs == rhs); } -template<class Key, class T> -typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &akey, const T &avalue) +template <typename Key, typename T> +QMultiMap<Key, T> operator+(const QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs) { - return static_cast<QMultiMap<Key, T> *>(this)->insert(pos, akey, avalue); + auto result = lhs; + result += rhs; + return result; } -template<class Key, class T> -QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other) +template <typename Key, typename T> +QMultiMap<Key, T> operator+=(QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs) { - return static_cast<QMultiMap<Key, T> *>(this)->unite(other); + return lhs.unite(rhs); } -#endif - -Q_DECLARE_ASSOCIATIVE_ITERATOR(Map) -Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map) QT_END_NAMESPACE diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.qdoc index 279dacda0b..09798620b7 100644 --- a/src/corelib/tools/qmap.cpp +++ b/src/corelib/tools/qmap.qdoc @@ -1,5 +1,6 @@ /**************************************************************************** ** +** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> ** Copyright (C) 2016 The Qt Company Ltd. ** Contact: https://www.qt.io/licensing/ ** @@ -37,348 +38,10 @@ ** ****************************************************************************/ -#include "qmap.h" - -#include <stdlib.h> - -#ifdef QT_QMAP_DEBUG -# include <qstring.h> -# include <qlist.h> -#endif - -QT_BEGIN_NAMESPACE - -const QMapDataBase QMapDataBase::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, { 0, nullptr, nullptr }, nullptr }; - -const QMapNodeBase *QMapNodeBase::nextNode() const -{ - const QMapNodeBase *n = this; - if (n->right) { - n = n->right; - while (n->left) - n = n->left; - } else { - const QMapNodeBase *y = n->parent(); - while (y && n == y->right) { - n = y; - y = n->parent(); - } - n = y; - } - return n; -} - -const QMapNodeBase *QMapNodeBase::previousNode() const -{ - const QMapNodeBase *n = this; - if (n->left) { - n = n->left; - while (n->right) - n = n->right; - } else { - const QMapNodeBase *y = n->parent(); - while (y && n == y->left) { - n = y; - y = n->parent(); - } - n = y; - } - return n; -} - - -void QMapDataBase::rotateLeft(QMapNodeBase *x) -{ - QMapNodeBase *&root = header.left; - QMapNodeBase *y = x->right; - x->right = y->left; - if (y->left != nullptr) - y->left->setParent(x); - y->setParent(x->parent()); - if (x == root) - root = y; - else if (x == x->parent()->left) - x->parent()->left = y; - else - x->parent()->right = y; - y->left = x; - x->setParent(y); -} - - -void QMapDataBase::rotateRight(QMapNodeBase *x) -{ - QMapNodeBase *&root = header.left; - QMapNodeBase *y = x->left; - x->left = y->right; - if (y->right != nullptr) - y->right->setParent(x); - y->setParent(x->parent()); - if (x == root) - root = y; - else if (x == x->parent()->right) - x->parent()->right = y; - else - x->parent()->left = y; - y->right = x; - x->setParent(y); -} - - -void QMapDataBase::rebalance(QMapNodeBase *x) -{ - QMapNodeBase *&root = header.left; - x->setColor(QMapNodeBase::Red); - while (x != root && x->parent()->color() == QMapNodeBase::Red) { - if (x->parent() == x->parent()->parent()->left) { - QMapNodeBase *y = x->parent()->parent()->right; - if (y && y->color() == QMapNodeBase::Red) { - x->parent()->setColor(QMapNodeBase::Black); - y->setColor(QMapNodeBase::Black); - x->parent()->parent()->setColor(QMapNodeBase::Red); - x = x->parent()->parent(); - } else { - if (x == x->parent()->right) { - x = x->parent(); - rotateLeft(x); - } - x->parent()->setColor(QMapNodeBase::Black); - x->parent()->parent()->setColor(QMapNodeBase::Red); - rotateRight (x->parent()->parent()); - } - } else { - QMapNodeBase *y = x->parent()->parent()->left; - if (y && y->color() == QMapNodeBase::Red) { - x->parent()->setColor(QMapNodeBase::Black); - y->setColor(QMapNodeBase::Black); - x->parent()->parent()->setColor(QMapNodeBase::Red); - x = x->parent()->parent(); - } else { - if (x == x->parent()->left) { - x = x->parent(); - rotateRight(x); - } - x->parent()->setColor(QMapNodeBase::Black); - x->parent()->parent()->setColor(QMapNodeBase::Red); - rotateLeft(x->parent()->parent()); - } - } - } - root->setColor(QMapNodeBase::Black); -} - -void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z) -{ - QMapNodeBase *&root = header.left; - QMapNodeBase *y = z; - QMapNodeBase *x; - QMapNodeBase *x_parent; - if (y->left == nullptr) { - x = y->right; - if (y == mostLeftNode) { - if (x) - mostLeftNode = x; // It cannot have (left) children due the red black invariant. - else - mostLeftNode = y->parent(); - } - } else { - if (y->right == nullptr) { - x = y->left; - } else { - y = y->right; - while (y->left != nullptr) - y = y->left; - x = y->right; - } - } - if (y != z) { - z->left->setParent(y); - y->left = z->left; - if (y != z->right) { - x_parent = y->parent(); - if (x) - x->setParent(y->parent()); - y->parent()->left = x; - y->right = z->right; - z->right->setParent(y); - } else { - x_parent = y; - } - if (root == z) - root = y; - else if (z->parent()->left == z) - z->parent()->left = y; - else - z->parent()->right = y; - y->setParent(z->parent()); - // Swap the colors - QMapNodeBase::Color c = y->color(); - y->setColor(z->color()); - z->setColor(c); - y = z; - } else { - x_parent = y->parent(); - if (x) - x->setParent(y->parent()); - if (root == z) - root = x; - else if (z->parent()->left == z) - z->parent()->left = x; - else - z->parent()->right = x; - } - if (y->color() != QMapNodeBase::Red) { - while (x != root && (x == nullptr || x->color() == QMapNodeBase::Black)) { - if (x == x_parent->left) { - QMapNodeBase *w = x_parent->right; - if (w->color() == QMapNodeBase::Red) { - w->setColor(QMapNodeBase::Black); - x_parent->setColor(QMapNodeBase::Red); - rotateLeft(x_parent); - w = x_parent->right; - } - if ((w->left == nullptr || w->left->color() == QMapNodeBase::Black) && - (w->right == nullptr || w->right->color() == QMapNodeBase::Black)) { - w->setColor(QMapNodeBase::Red); - x = x_parent; - x_parent = x_parent->parent(); - } else { - if (w->right == nullptr || w->right->color() == QMapNodeBase::Black) { - if (w->left) - w->left->setColor(QMapNodeBase::Black); - w->setColor(QMapNodeBase::Red); - rotateRight(w); - w = x_parent->right; - } - w->setColor(x_parent->color()); - x_parent->setColor(QMapNodeBase::Black); - if (w->right) - w->right->setColor(QMapNodeBase::Black); - rotateLeft(x_parent); - break; - } - } else { - QMapNodeBase *w = x_parent->left; - if (w->color() == QMapNodeBase::Red) { - w->setColor(QMapNodeBase::Black); - x_parent->setColor(QMapNodeBase::Red); - rotateRight(x_parent); - w = x_parent->left; - } - if ((w->right == nullptr || w->right->color() == QMapNodeBase::Black) && - (w->left == nullptr|| w->left->color() == QMapNodeBase::Black)) { - w->setColor(QMapNodeBase::Red); - x = x_parent; - x_parent = x_parent->parent(); - } else { - if (w->left == nullptr || w->left->color() == QMapNodeBase::Black) { - if (w->right) - w->right->setColor(QMapNodeBase::Black); - w->setColor(QMapNodeBase::Red); - rotateLeft(w); - w = x_parent->left; - } - w->setColor(x_parent->color()); - x_parent->setColor(QMapNodeBase::Black); - if (w->left) - w->left->setColor(QMapNodeBase::Black); - rotateRight(x_parent); - break; - } - } - } - if (x) - x->setColor(QMapNodeBase::Black); - } - free(y); - --size; -} - -void QMapDataBase::recalcMostLeftNode() -{ - mostLeftNode = &header; - while (mostLeftNode->left) - mostLeftNode = mostLeftNode->left; -} - -static inline size_t qMapAlignmentThreshold() -{ - // malloc on 32-bit platforms should return pointers that are 8-byte - // aligned or more while on 64-bit platforms they should be 16-byte aligned - // or more - return 2 * sizeof(void*); -} - -static inline void *qMapAllocate(size_t alloc, size_t alignment) -{ - return alignment > qMapAlignmentThreshold() - ? qMallocAligned(alloc, alignment) - : ::malloc(alloc); -} - -static inline void qMapDeallocate(QMapNodeBase *node, size_t alignment) -{ - if (alignment > qMapAlignmentThreshold()) - qFreeAligned(node); - else - ::free(node); -} - -QMapNodeBase *QMapDataBase::createNode(size_t alloc, size_t alignment, QMapNodeBase *parent, bool left) -{ - QMapNodeBase *node = static_cast<QMapNodeBase *>(qMapAllocate(alloc, alignment)); - Q_CHECK_PTR(node); - - memset(node, 0, alloc); - ++size; - - if (parent) { - if (left) { - parent->left = node; - if (parent == mostLeftNode) - mostLeftNode = node; - } else { - parent->right = node; - } - node->setParent(parent); - rebalance(node); - } - return node; -} - -void QMapDataBase::freeTree(QMapNodeBase *root, size_t alignment) -{ - if (root->left) - freeTree(root->left, alignment); - if (root->right) - freeTree(root->right, alignment); - qMapDeallocate(root, alignment); -} - -QMapDataBase *QMapDataBase::createData() -{ - QMapDataBase *d = new QMapDataBase; - - d->ref.initializeOwned(); - d->size = 0; - - d->header.p = 0; - d->header.left = nullptr; - d->header.right = nullptr; - d->mostLeftNode = &(d->header); - - return d; -} - -void QMapDataBase::freeData(QMapDataBase *d) -{ - delete d; -} - /*! \class QMap \inmodule QtCore - \brief The QMap class is a template class that provides a red-black-tree-based dictionary. + \brief The QMap class is a template class that provides an associative array. \ingroup tools \ingroup shared @@ -468,14 +131,13 @@ void QMapDataBase::freeData(QMapDataBase *d) \snippet code/src_corelib_tools_qmap.cpp 9 However, you can store multiple values per key by using - using the subclass QMultiMap. If you want + QMultiMap. If you want to retrieve all the values for a single key, you can use values(const Key &key), which returns a QList<T>: \snippet code/src_corelib_tools_qmap.cpp 10 - The items that share the same key are available from most - recently to least recently inserted. Another approach is to call + Another approach is to call find() to get the STL-style iterator for the first item with a key and iterate from there: @@ -496,7 +158,7 @@ void QMapDataBase::freeData(QMapDataBase *d) but the compiler won't let you, for example, store a QWidget as a value; instead, store a QWidget *. In addition, QMap's key type must provide operator<(). QMap uses it to keep its items sorted, - and assumes that two keys \c x and \c y are equal if neither \c{x + and assumes that two keys \c x and \c y are equivalent if neither \c{x < y} nor \c{y < x} is true. Example: @@ -515,15 +177,6 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa clear() */ -/*! - \fn template <class Key, class T> QMap<Key, T>::QMap(QMap<Key, T> &&other) - - Move-constructs a QMap instance, making it point at the same - object that \a other was pointing to. - - \since 5.2 -*/ - /*! \fn template <class Key, class T> QMap<Key, T>::QMap(const QMap<Key, T> &other) Constructs a copy of \a other. @@ -533,29 +186,28 @@ void QMapDataBase::freeData(QMapDataBase *d) function very fast. If a shared instance is modified, it will be copied (copy-on-write), and this takes \l{linear time}. - \sa operator=() + \sa operator= */ -/*! \fn template <class Key, class T> QMap<Key, T>::QMap(const typename std::map<Key, T> & other) +/*! + \fn template <class Key, class T> QMap<Key, T>::QMap(QMap<Key, T> &&other) - Constructs a copy of \a other. + Move-constructs a QMap instance. - \sa toStdMap() + \since 5.2 */ -/*! \fn template <class Key, class T> QMap<Key, T>::QMap(std::initializer_list<std::pair<Key,T> > list) - \since 5.1 - - Constructs a map with a copy of each of the elements in the - initializer list \a list. +/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other) - This function is only available if the program is being - compiled in C++11 mode. + Assigns \a other to this map and returns a reference to this map. */ -/*! \fn template <class Key, class T> std::map<Key, T> QMap<Key, T>::toStdMap() const +/*! + \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(QMap<Key, T> &&other) - Returns an STL map equivalent to this QMap. + Move-assigns \a other to this QMap instance. + + \since 5.2 */ /*! \fn template <class Key, class T> QMap<Key, T>::~QMap() @@ -564,62 +216,70 @@ void QMapDataBase::freeData(QMapDataBase *d) iterators over this map, become invalid. */ -/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other) +/*! \fn template <class Key, class T> void QMap<Key, T>::swap(QMap<Key, T> &other) noexcept + \since 4.8 - Assigns \a other to this map and returns a reference to this map. + Swaps map \a other with this map. This operation is very + fast and never fails. */ -/*! - \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(QMap<Key, T> &&other) +/*! \fn template <class Key, class T> QMap<Key, T>::QMap(std::initializer_list<std::pair<Key,T> > list) + \since 5.1 - Move-assigns \a other to this QMap instance. + Constructs a map with a copy of each of the elements in the + initializer list \a list. +*/ - \since 5.2 +/*! \fn template <class Key, class T> QMap<Key, T>::QMap(const std::map<Key, T> & other) + + Constructs a copy of \a other. + + \sa toStdMap() */ -/*! \fn template <class Key, class T> void QMap<Key, T>::swap(QMap<Key, T> &other) - \since 4.8 +/*! \fn template <class Key, class T> QMap<Key, T>::QMap(std::map<Key, T> && other) - Swaps map \a other with this map. This operation is very - fast and never fails. + Constructs a map by moving from \a other. + + \sa toStdMap() */ -/*! \fn template <class Key, class T> void QMultiMap<Key, T>::swap(QMultiMap<Key, T> &other) - \since 4.8 +/*! \fn template <class Key, class T> std::map<Key, T> QMap<Key, T>::toStdMap() const - Swaps map \a other with this map. This operation is very - fast and never fails. + Returns an STL map equivalent to this QMap. */ -/*! \fn template <class Key, class T> bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const +/*! \fn template <class Key, class T> bool operator==(const QMap<Key, T> &lhs, const QMap<Key, T> &rhs) const + \relates QMap - Returns \c true if \a other is equal to this map; otherwise returns + Returns \c true if \a lhs is equal to \a rhs; otherwise returns false. Two maps are considered equal if they contain the same (key, value) pairs. - This function requires the value type to implement \c + This function requires the key and the value types to implement \c operator==(). \sa operator!=() */ -/*! \fn template <class Key, class T> bool QMap<Key, T>::operator!=(const QMap<Key, T> &other) const +/*! \fn template <class Key, class T> bool operator!=(const QMap<Key, T> &lhs, const QMap<Key, T> &rhs) const + \relates QMap - Returns \c true if \a other is not equal to this map; otherwise - returns \c false. + Returns \c true if \a lhs is not equal to \a rhs; otherwise returns + false. Two maps are considered equal if they contain the same (key, value) pairs. - This function requires the value type to implement \c + This function requires the key and the value types to implement \c operator==(). \sa operator==() */ -/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::size() const +/*! \fn template <class Key, class T> size_type QMap<Key, T>::size() const Returns the number of (key, value) pairs in the map. @@ -655,11 +315,6 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa detach() */ -/*! \fn template <class Key, class T> void QMap<Key, T>::setSharable(bool sharable) - - \internal -*/ - /*! \fn template <class Key, class T> bool QMap<Key, T>::isSharedWith(const QMap<Key, T> &other) const \internal @@ -672,13 +327,13 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa remove() */ -/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::remove(const Key &key) +/*! \fn template <class Key, class T> size_type QMap<Key, T>::remove(const Key &key) Removes all the items that have the key \a key from the map. Returns the number of items removed which will be 1 if the key exists in the map, and 0 otherwise. - \sa clear(), take(), QMultiMap::remove() + \sa clear(), take() */ /*! \fn template <class Key, class T> T QMap<Key, T>::take(const Key &key) @@ -701,7 +356,24 @@ void QMapDataBase::freeData(QMapDataBase *d) Returns \c true if the map contains an item with key \a key; otherwise returns \c false. - \sa count(), QMultiMap::contains() + \sa count() +*/ + +/*! + \fn template <class Key, class T> Key QMap<Key, T>::key(const T &value, const Key &defaultKey) const + \since 4.3 + \overload + + Returns the first key with value \a value, or \a defaultKey if + the map contains no item with value \a value. If no \a defaultKey + is provided the function returns a + \l{default-constructed value}{default-constructed key}. + + This function can be slow (\l{linear time}), because QMap's + internal data structure is optimized for fast lookup by key, not + by value. + + \sa value(), keys() */ /*! \fn template <class Key, class T> T QMap<Key, T>::value(const Key &key, const T &defaultValue) const @@ -710,9 +382,7 @@ void QMapDataBase::freeData(QMapDataBase *d) If the map contains no item with key \a key, the function returns \a defaultValue. If no \a defaultValue is specified, the function - returns a \l{default-constructed value}. If there are multiple - items for \a key in the map, the value of the most recently - inserted one is returned. + returns a \l{default-constructed value}. \sa key(), values(), contains(), operator[]() */ @@ -731,31 +401,17 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa insert(), value() */ -/*! \fn template <class Key, class T> const T QMap<Key, T>::operator[](const Key &key) const +/*! \fn template <class Key, class T> T QMap<Key, T>::operator[](const Key &key) const \overload Same as value(). */ -/*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::uniqueKeys() const - \since 4.2 - \obsolete Use QMultiMap for storing multiple values with the same key. - - Returns a list containing all the keys in the map in ascending - order. Keys that occur multiple times in the map (because items - were inserted with insertMulti(), or unite() was used) occur only - once in the returned list. - - \sa QMultiMap::uniqueKeys() -*/ - /*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::keys() const Returns a list containing all the keys in the map in ascending - order. Keys that occur multiple times in the map (because the - method is operating on a QMultiMap) also occur multiple times - in the list. + order. The order is guaranteed to be the same as that used by values(). @@ -778,23 +434,6 @@ void QMapDataBase::freeData(QMapDataBase *d) by value. */ -/*! - \fn template <class Key, class T> Key QMap<Key, T>::key(const T &value, const Key &defaultKey) const - \since 4.3 - \overload - - Returns the first key with value \a value, or \a defaultKey if - the map contains no item with value \a value. If no \a defaultKey - is provided the function returns a - \l{default-constructed value}{default-constructed key}. - - This function can be slow (\l{linear time}), because QMap's - internal data structure is optimized for fast lookup by key, not - by value. - - \sa value(), keys() -*/ - /*! \fn template <class Key, class T> QList<T> QMap<Key, T>::values() const Returns a list containing all the values in the map, in ascending @@ -809,29 +448,74 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa keys(), value() */ -/*! \fn template <class Key, class T> QList<T> QMap<Key, T>::values(const Key &key) const +/*! \fn template <class Key, class T> size_type QMap<Key, T>::count(const Key &key) const + + Returns the number of items associated with key \a key. + + \sa contains() +*/ + +/*! \fn template <class Key, class T> size_type QMap<Key, T>::count() const + \overload - \obsolete Use QMultiMap for maps storing multiple values with the same key. - Returns a list containing all the values associated with key - \a key, from the most recently inserted to the least recently - inserted one. + Same as size(). +*/ + +/*! \fn template <class Key, class T> const Key &QMap<Key, T>::firstKey() const + \since 5.2 + + Returns a reference to the smallest key in the map. + This function assumes that the map is not empty. - \sa QMultiMap::values() + This executes in \l{constant time}. + + \sa lastKey(), first(), keyBegin(), isEmpty() */ -/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::count(const Key &key) const +/*! \fn template <class Key, class T> const Key &QMap<Key, T>::lastKey() const + \since 5.2 - Returns the number of items associated with key \a key. + Returns a reference to the largest key in the map. + This function assumes that the map is not empty. - \sa contains(), QMultiMap::count() + This executes in \l{logarithmic time}. + + \sa firstKey(), last(), keyEnd(), isEmpty() */ -/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::count() const +/*! \fn template <class Key, class T> T &QMap<Key, T>::first() + \since 5.2 + + Returns a reference to the first value in the map, that is the value mapped + to the smallest key. This function assumes that the map is not empty. + + When unshared (or const version is called), this executes in \l{constant time}. + + \sa last(), firstKey(), isEmpty() +*/ + +/*! \fn template <class Key, class T> const T &QMap<Key, T>::first() const + \since 5.2 \overload +*/ - Same as size(). +/*! \fn template <class Key, class T> T &QMap<Key, T>::last() + \since 5.2 + + Returns a reference to the last value in the map, that is the value mapped + to the largest key. This function assumes that the map is not empty. + + When unshared (or const version is called), this executes in \l{logarithmic time}. + + \sa first(), lastKey(), isEmpty() +*/ + +/*! \fn template <class Key, class T> const T &QMap<Key, T>::last() const + \since 5.2 + + \overload */ /*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::begin() @@ -967,63 +651,7 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa constKeyValueBegin() */ -/*! \fn template <class Key, class T> const Key &QMap<Key, T>::firstKey() const - \since 5.2 - - Returns a reference to the smallest key in the map. - This function assumes that the map is not empty. - - This executes in \l{constant time}. - - \sa lastKey(), first(), keyBegin(), isEmpty() -*/ - -/*! \fn template <class Key, class T> const Key &QMap<Key, T>::lastKey() const - \since 5.2 - - Returns a reference to the largest key in the map. - This function assumes that the map is not empty. - - This executes in \l{logarithmic time}. - - \sa firstKey(), last(), keyEnd(), isEmpty() -*/ - -/*! \fn template <class Key, class T> T &QMap<Key, T>::first() - \since 5.2 - - Returns a reference to the first value in the map, that is the value mapped - to the smallest key. This function assumes that the map is not empty. - - When unshared (or const version is called), this executes in \l{constant time}. - - \sa last(), firstKey(), isEmpty() -*/ - -/*! \fn template <class Key, class T> const T &QMap<Key, T>::first() const - \since 5.2 - - \overload -*/ - -/*! \fn template <class Key, class T> T &QMap<Key, T>::last() - \since 5.2 - - Returns a reference to the last value in the map, that is the value mapped - to the largest key. This function assumes that the map is not empty. - - When unshared (or const version is called), this executes in \l{logarithmic time}. - - \sa first(), lastKey(), isEmpty() -*/ - -/*! \fn template <class Key, class T> const T &QMap<Key, T>::last() const - \since 5.2 - - \overload -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::erase(iterator pos) +/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::erase(const_iterator pos) Removes the (key, value) pair pointed to by the iterator \a pos from the map, and returns an iterator to the next item in the @@ -1040,15 +668,7 @@ void QMapDataBase::freeData(QMapDataBase *d) If the map contains no item with key \a key, the function returns end(). - If the map contains multiple items with key \a key, this - function returns an iterator that points to the most recently - inserted value. The other values are accessible by incrementing - the iterator. For example, here's some code that iterates over all - the items with the same key: - - \snippet code/src_corelib_tools_qmap.cpp 14 - - \sa constFind(), value(), values(), lowerBound(), upperBound(), QMultiMap::find() + \sa constFind(), value(), values(), lowerBound(), upperBound() */ /*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &key) const @@ -1065,7 +685,7 @@ void QMapDataBase::freeData(QMapDataBase *d) If the map contains no item with key \a key, the function returns constEnd(). - \sa find(), QMultiMap::constFind() + \sa find() */ /*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &key) @@ -1075,17 +695,6 @@ void QMapDataBase::freeData(QMapDataBase *d) function returns an iterator to the nearest item with a greater key. - Example: - \snippet code/src_corelib_tools_qmap.cpp 15 - - If the map contains multiple items with key \a key, this - function returns an iterator that points to the most recently - inserted value. The other values are accessible by incrementing - the iterator. For example, here's some code that iterates over all - the items with the same key: - - \snippet code/src_corelib_tools_qmap.cpp 16 - \sa upperBound(), find() */ @@ -1119,9 +728,6 @@ void QMapDataBase::freeData(QMapDataBase *d) If there is already an item with the key \a key, that item's value is replaced with \a value. - If there are multiple items with the key \a key, the most - recently inserted item's value is replaced with \a value. - \sa QMultiMap::insert() */ @@ -1139,9 +745,6 @@ void QMapDataBase::freeData(QMapDataBase *d) If there is already an item with the key \a key, that item's value is replaced with \a value. - If there are multiple items with the key \a key, then exactly one of them - is replaced with \a value. - If the hint is correct and the map is unshared, the insert executes in amortized \l{constant time}. When creating a map from sorted data inserting the largest key first with constBegin() @@ -1168,50 +771,6 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa QMultiMap::insert() */ -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value) - \obsolete Use QMultiMap for storing multiple values with the same key. - - Inserts a new item with the key \a key and a value of \a value. - - If there is already an item with the same key in the map, this - function will simply create a new one. (This behavior is - different from insert(), which overwrites the value of an - existing item.) - - \sa QMultiMap::insert() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &key, const T &value) - \overload - \since 5.1 - \obsolete Use QMultiMap for storing multiple values with the same key. - Inserts a new item with the key \a key and value \a value and with hint \a pos - suggesting where to do the insert. - - If constBegin() is used as hint it indicates that the \a key is less than any key in the map - while constEnd() suggests that the \a key is larger than any key in the map. - Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key(). - If the hint \a pos is wrong it is ignored and a regular insertMulti is done. - - If there is already an item with the same key in the map, this function will simply create a new one. - - \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might - crash but there is also a risk that it will silently corrupt both the map and the \a pos map. - - \sa QMultiMap::insert() -*/ - - -/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other) - \obsolete Use QMultiMap for storing multiple values with the same key. - - Inserts all the items in the \a other map into this map. If a - key is common to both maps, the resulting map will contain the - key multiple times. - - \sa QMultiMap::unite() -*/ - /*! \typedef QMap::Iterator Qt-style synonym for QMap<Key, T>::iterator. @@ -1266,7 +825,7 @@ void QMapDataBase::freeData(QMapDataBase *d) /*! \class QMap::iterator \inmodule QtCore - \brief The QMap::iterator class provides an STL-style non-const iterator for QMap and QMultiMap. + \brief The QMap::iterator class provides an STL-style non-const iterator for QMap. QMap features both \l{STL-style iterators} and \l{Java-style iterators}. The STL-style iterators are more low-level and more @@ -1274,8 +833,8 @@ void QMapDataBase::freeData(QMapDataBase *d) and, for developers who already know STL, have the advantage of familiarity. - QMap\<Key, T\>::iterator allows you to iterate over a QMap (or - QMultiMap) and to modify the value (but not the key) stored under + QMap\<Key, T\>::iterator allows you to iterate over a QMap + and to modify the value (but not the key) stored under a particular key. If you want to iterate over a const QMap, you should use QMap::const_iterator. It is generally good practice to use QMap::const_iterator on a non-const QMap as well, unless you @@ -1291,9 +850,7 @@ void QMapDataBase::freeData(QMapDataBase *d) \snippet code/src_corelib_tools_qmap.cpp 18 Unlike QHash, which stores its items in an arbitrary order, QMap - stores its items ordered by key. Items that share the same key - (because the map is a QMultiMap) will appear consecutively, - from the most recently to the least recently inserted value. + stores its items ordered by key. Let's see a few examples of things we can do with a QMap::iterator that we cannot do with a QMap::const_iterator. @@ -1370,11 +927,6 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa QMap::begin(), QMap::end() */ -/*! \fn template <class Key, class T> QMap<Key, T>::iterator::iterator(Node *) - - \internal -*/ - /*! \fn template <class Key, class T> const Key &QMap<Key, T>::iterator::key() const Returns the current item's key as a const reference. @@ -1434,7 +986,7 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa operator==() */ -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator++() +/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator++() The prefix ++ operator (\c{++i}) advances the iterator to the next item in the map and returns an iterator to the new current @@ -1454,7 +1006,7 @@ void QMapDataBase::freeData(QMapDataBase *d) current item. */ -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator--() +/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator--() The prefix -- operator (\c{--i}) makes the preceding item current and returns an iterator pointing to the new current item. @@ -1474,46 +1026,9 @@ void QMapDataBase::freeData(QMapDataBase *d) current item. */ -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator+(qsizetype j) const - - Returns an iterator to the item at \a j positions forward from - this iterator. (If \a j is negative, the iterator goes backward.) - - This operation can be slow for large \a j values. - - \sa operator-() - -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator-(qsizetype j) const - - Returns an iterator to the item at \a j positions backward from - this iterator. (If \a j is negative, the iterator goes forward.) - - This operation can be slow for large \a j values. - - \sa operator+() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator+=(qsizetype j) - - Advances the iterator by \a j items. (If \a j is negative, the - iterator goes backward.) - - \sa operator-=(), operator+() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator-=(qsizetype j) - - Makes the iterator go back by \a j items. (If \a j is negative, - the iterator goes forward.) - - \sa operator+=(), operator-() -*/ - /*! \class QMap::const_iterator \inmodule QtCore - \brief The QMap::const_iterator class provides an STL-style const iterator for QMap and QMultiMap. + \brief The QMap::const_iterator class provides an STL-style const iterator for QMap. QMap features both \l{STL-style iterators} and \l{Java-style iterators}. The STL-style iterators are more low-level and more @@ -1521,8 +1036,8 @@ void QMapDataBase::freeData(QMapDataBase *d) and, for developers who already know STL, have the advantage of familiarity. - QMap\<Key, T\>::const_iterator allows you to iterate over a QMap - (or a QMultiMap). If you want to modify the QMap as you iterate + QMap\<Key, T\>::const_iterator allows you to iterate over a QMap. + If you want to modify the QMap as you iterate over it, you must use QMap::iterator instead. It is generally good practice to use QMap::const_iterator on a non-const QMap as well, unless you need to change the QMap through the iterator. @@ -1538,9 +1053,7 @@ void QMapDataBase::freeData(QMapDataBase *d) \snippet code/src_corelib_tools_qmap.cpp 24 Unlike QHash, which stores its items in an arbitrary order, QMap - stores its items ordered by key. Items that share the same key - (because the map is a QMultiMap) will appear consecutively, - from the most recently to the least recently inserted value. + stores its items ordered by key. Multiple iterators can be used on the same map. If you add items to the map, existing iterators will remain valid. If you remove @@ -1592,11 +1105,6 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa QMap::constBegin(), QMap::constEnd() */ -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator(const Node *) - - \internal -*/ - /*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator(const iterator &other) Constructs a copy of \a other. @@ -1648,7 +1156,7 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa operator==() */ -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator++() +/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator++() The prefix ++ operator (\c{++i}) advances the iterator to the next item in the map and returns an iterator to the new current @@ -1688,50 +1196,10 @@ void QMapDataBase::freeData(QMapDataBase *d) current item. */ -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator+(qsizetype j) const - - Returns an iterator to the item at \a j positions forward from - this iterator. (If \a j is negative, the iterator goes backward.) - - This operation can be slow for large \a j values. - - \sa operator-() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator-(qsizetype j) const - - Returns an iterator to the item at \a j positions backward from - this iterator. (If \a j is negative, the iterator goes forward.) - - This operation can be slow for large \a j values. - - \sa operator+() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator+=(qsizetype j) - - Advances the iterator by \a j items. (If \a j is negative, the - iterator goes backward.) - - This operation can be slow for large \a j values. - - \sa operator-=(), operator+() -*/ - -/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator-=(qsizetype j) - - Makes the iterator go back by \a j items. (If \a j is negative, - the iterator goes forward.) - - This operation can be slow for large \a j values. - - \sa operator+=(), operator-() -*/ - /*! \class QMap::key_iterator \inmodule QtCore \since 5.6 - \brief The QMap::key_iterator class provides an STL-style const iterator for QMap and QMultiMap keys. + \brief The QMap::key_iterator class provides an STL-style const iterator for QMap keys. QMap::key_iterator is essentially the same as QMap::const_iterator with the difference that operator*() and operator->() return a key @@ -1859,7 +1327,7 @@ void QMapDataBase::freeData(QMapDataBase *d) /*! \typedef QMap::const_key_value_iterator \inmodule QtCore \since 5.10 - \brief The QMap::const_key_value_iterator typedef provides an STL-style iterator for QMap and QMultiMap. + \brief The QMap::const_key_value_iterator typedef provides an STL-style iterator for QMap. QMap::const_key_value_iterator is essentially the same as QMap::const_iterator with the difference that operator*() returns a key/value pair instead of a @@ -1871,7 +1339,7 @@ void QMapDataBase::freeData(QMapDataBase *d) /*! \typedef QMap::key_value_iterator \inmodule QtCore \since 5.10 - \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QMap and QMultiMap. + \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QMap. QMap::key_value_iterator is essentially the same as QMap::iterator with the difference that operator*() returns a key/value pair instead of a @@ -1901,240 +1369,3 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa{Serializing Qt Data Types}{Format of the QDataStream operators} */ - -/*! \class QMultiMap - \inmodule QtCore - \brief The QMultiMap class is a convenience QMap subclass that provides multi-valued maps. - - \ingroup tools - \ingroup shared - - \reentrant - - QMultiMap\<Key, T\> is one of Qt's generic \l{container classes}. - It inherits QMap and extends it with a few functions - that make it able to store multi-valued maps. A multi-valued map - is a map that allows multiple values with the same key; QMap - doesn't allow that. - - Because QMultiMap inherits QMap, all of QMap's functionality also - applies to QMultiMap. For example, you can use isEmpty() to test - whether the map is empty, and you can traverse a QMultiMap using - QMap's iterator classes (for example, QMapIterator). But in - addition, it provides an insert() function that inserts but does - not overwrite any previous value if the key already exists, - and a replace() function that corresponds which does overwite - an existing value if they key is already in the map. - It also provides convenient operator+() and operator+=(). - - Example: - \snippet code/src_corelib_tools_qmap.cpp 25 - - Unlike QMap, QMultiMap provides no operator[]. Use value() or - replace() if you want to access the most recently inserted item - with a certain key. - - If you want to retrieve all the values for a single key, you can - use values(const Key &key), which returns a QList<T>: - - \snippet code/src_corelib_tools_qmap.cpp 26 - - The items that share the same key are available from most - recently to least recently inserted. - - If you prefer the STL-style iterators, you can call find() to get - the iterator for the first item with a key and iterate from - there: - - \snippet code/src_corelib_tools_qmap.cpp 27 - - QMultiMap's key and value data types must be \l{assignable data - types}. This covers most data types you are likely to encounter, - but the compiler won't let you, for example, store a QWidget as a - value; instead, store a QWidget *. In addition, QMultiMap's key type - must provide operator<(). See the QMap documentation for details. - - \sa QMap, QMapIterator, QMutableMapIterator, QMultiHash -*/ - -/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap() - - Constructs an empty map. -*/ - -/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(std::initializer_list<std::pair<Key,T> > list) - \since 5.1 - - Constructs a multi-map with a copy of each of the elements in the - initializer list \a list. - - This function is only available if the program is being - compiled in C++11 mode. -*/ - -/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const QMap<Key, T> &other) - - Constructs a copy of \a other (which can be a QMap or a - QMultiMap). - - \sa operator=() -*/ - -/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::replace(const Key &key, const T &value) - - Inserts a new item with the key \a key and a value of \a value. - - If there is already an item with the key \a key, that item's value - is replaced with \a value. - - If there are multiple items with the key \a key, the most - recently inserted item's value is replaced with \a value. - - \sa insert() -*/ - -/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &key, const T &value) - - Inserts a new item with the key \a key and a value of \a value. - - If there is already an item with the same key in the map, this - function will simply create a new one. (This behavior is - different from replace(), which overwrites the value of an - existing item.) - - \sa replace() -*/ - -/*! \fn [qmultimap-insert-pos] template <class Key, class T> typename QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(typename QMultiMap<Key, T>::const_iterator pos, const Key &key, const T &value) - - \since 5.1 - Inserts a new item with the key \a key and value \a value and with hint \a pos - suggesting where to do the insert. - - If constBegin() is used as hint it indicates that the \a key is less than any key in the map - while constEnd() suggests that the \a key is larger than any key in the map. - Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key(). - If the hint \a pos is wrong it is ignored and a regular insert is done. - - If there is already an item with the same key in the map, this function will simply create a new one. - - \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might - crash but there is also a risk that it will silently corrupt both the map and the \a pos map. -*/ - -/*! \fn template <class Key, class T> QMultiMap &QMultiMap<Key, T>::operator+=(const QMultiMap &other) - - Inserts all the items in the \a other map into this map and - returns a reference to this map. - - \sa insert(), operator+() -*/ - -/*! \fn template <class Key, class T> QMultiMap QMultiMap<Key, T>::operator+(const QMultiMap &other) const - - Returns a map that contains all the items in this map in - addition to all the items in \a other. If a key is common to both - maps, the resulting map will contain the key multiple times. - - \sa operator+=() -*/ - -/*! - \fn template <class Key, class T> bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const - \since 4.3 - - Returns \c true if the map contains an item with key \a key and - value \a value; otherwise returns \c false. - - \sa QMap::contains() -*/ - -/*! - \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::remove(const Key &key, const T &value) - \since 4.3 - - Removes all the items that have the key \a key and the value \a - value from the map. Returns the number of items removed. - - \sa QMap::remove() -*/ - -/*! - \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count(const Key &key, const T &value) const - \since 4.3 - - Returns the number of items with key \a key and value \a value. - - \sa QMap::count() -*/ - -/*! - \fn template <class Key, class T> typename QMap<Key, T>::iterator QMultiMap<Key, T>::find(const Key &key, const T &value) - \since 4.3 - - Returns an iterator pointing to the item with key \a key and - value \a value in the map. - - If the map contains no such item, the function returns end(). - - If the map contains multiple items with key \a key, this - function returns an iterator that points to the most recently - inserted value. - - \sa QMap::find() -*/ - -/*! - \fn template <class Key, class T> typename QMap<Key, T>::const_iterator QMultiMap<Key, T>::find(const Key &key, const T &value) const - \since 4.3 - \overload - - Returns a const iterator pointing to the item with the given \a key and - \a value in the map. - - If the map contains no such item, the function returns end(). - - If the map contains multiple items with the specified \a key, this - function returns a const iterator that points to the most recently - inserted value. - - \sa QMap::find() -*/ - -/*! - \fn template <class Key, class T> typename QMap<Key, T>::const_iterator QMultiMap<Key, T>::constFind(const Key &key, const T &value) const - \since 4.3 - - Returns an iterator pointing to the item with key \a key and the - value \a value in the map. - - If the map contains no such item, the function returns - constEnd(). - - \sa QMap::constFind() -*/ - -/*! \fn template <class Key, class T> QList<T> QMultiMap<Key, T>::values(const Key &key) const - - Returns a list containing all the values associated with key - \a key, from the most recently inserted to the least recently - inserted one. -*/ - -/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::uniqueKeys() const - \since 4.2 - - Returns a list containing all the keys in the map in ascending - order. Keys that occur multiple times in the map occur only - once in the returned list. -*/ - -/*! - \fn [qmultimap-unite] template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other) - - Inserts all the items in the \a other map into this map. If a - key is common to both maps, the resulting map will contain the - key multiple times. -*/ - -QT_END_NAMESPACE diff --git a/src/corelib/tools/qmultimap.qdoc b/src/corelib/tools/qmultimap.qdoc new file mode 100644 index 0000000000..3d1081d28b --- /dev/null +++ b/src/corelib/tools/qmultimap.qdoc @@ -0,0 +1,1465 @@ +/**************************************************************************** +** +** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +/*! + \class QMultiMap + \inmodule QtCore + \brief The QMultiMap class is a template class that provides an associative array with multiple equivalent keys. + + \ingroup tools + \ingroup shared + + \reentrant + + QMultiMap\<Key, T\> is one of Qt's generic \l{container classes}. It + stores (key, value) pairs and provides fast lookup of the + value associated with a key. + + QMultiMap and QMultiHash provide very similar functionality. The + differences are: + + \list + \li QMultiHash provides average faster lookups than QMultiMap. (See \l{Algorithmic + Complexity} for details.) + \li When iterating over a QMultiHash, the items are arbitrarily ordered. + With QMultiMap, the items are always sorted by key. + \li The key type of a QMultiHash must provide operator==() and a global + qHash(Key) function. The key type of a QMultiMap must provide + operator<() specifying a total order. Since Qt 5.8.1 it is also safe + to use a pointer type as key, even if the underlying operator<() + does not provide a total order. + \endlist + + Here's an example QMultiMap with QString keys and \c int values: + \snippet code/src_corelib_tools_qmultimap.cpp 0 + + To insert a (key, value) pair into the multi map, you can use insert(): + + \snippet code/src_corelib_tools_qmultimap.cpp 2 + + This inserts the following three (key, value) pairs into the + QMultiMap: ("a", 1), ("b", 3), ("c", 7), and ("c", -5); note + that duplicate keys are allowed. + + To look up a value, use find() or value(): + + \snippet code/src_corelib_tools_qmultimap.cpp 3 + + If there is no item with the specified key in the map, these + functions return a \l{default-constructed value}. + + If you want to check whether the map contains a certain key, use + contains(): + + \snippet code/src_corelib_tools_qmultimap.cpp 4 + + There is also a value() overload that uses its second argument as + a default value if there is no item with the specified key: + + \snippet code/src_corelib_tools_qmultimap.cpp 5 + + If you want to navigate through all the (key, value) pairs stored + in a QMultiMap, you can use an iterator. QMultiMap provides both + \l{Java-style iterators} (QMultiMapIterator and QMutableMultiMapIterator) + and \l{STL-style iterators} (QMultiMap::const_iterator and + QMultiMap::iterator). Here's how to iterate over a QMultiMap<QString, int> + using a Java-style iterator: + + \snippet code/src_corelib_tools_qmultimap.cpp 7 + + Here's the same code, but using an STL-style iterator this time: + + \snippet code/src_corelib_tools_qmultimap.cpp 8 + + The items are traversed in ascending key order. + + A QMultiMap allows multiple values per key. If you call + insert() with a key that already exists in the map, a + new (key, value) pair will be inserted. For example: + + \snippet code/src_corelib_tools_qmultimap.cpp 9 + + If you want to retrieve all the values for a single key, you can + use values(const Key &key), which returns a QList<T>: + + \snippet code/src_corelib_tools_qmultimap.cpp 10 + + The items that share the same key are available from most + recently to least recently inserted. Another approach is to call + find() to get the STL-style iterator for the first item with a + key and iterate from there: + + \snippet code/src_corelib_tools_qmultimap.cpp 11 + + If you only need to extract the values from a map (not the keys), + you can also use \l{foreach}: + + \snippet code/src_corelib_tools_qmultimap.cpp 12 + + Items can be removed from the multi map in several ways. One way is to + call remove(); this will remove any item with the given key. + Another way is to use QMutableMultiMapIterator::remove(). In addition, + you can clear the entire map using clear(). + + It is possible to merge two multi maps by calling unite(), by + using operator+(), and by using operator+=(). Example: + + \snippet code/src_corelib_tools_qmultimap.cpp 25 + + QMultiMap's key and value data types must be \l{assignable data + types}. This covers most data types you are likely to encounter, + but the compiler won't let you, for example, store a QWidget as a + value; instead, store a QWidget *. In addition, QMultiMap's key type + must provide operator<(). QMap uses it to keep its items sorted, + and assumes that two keys \c x and \c y are equal if neither \c{x + < y} nor \c{y < x} is true. + + Example: + \snippet code/src_corelib_tools_qmultimap.cpp 13 + + In the example, we start by comparing the employees' names. If + they're equal, we compare their dates of birth to break the tie. + + \sa QMultiMapIterator, QMutableMultiMapIterator, QMultiHash +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap() + + Constructs an empty multi map. + + \sa clear() +*/ + +/*! + \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(QMultiMap<Key, T> &&other) + + Move-constructs a QMultiMap instance, making it point at the same + object that \a other was pointing to. + + \since 5.2 +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const QMultiMap<Key, T> &other) + + Constructs a copy of \a other. + + This operation occurs in \l{constant time}, because QMultiMap is + \l{implicitly shared}. This makes returning a QMultiMap from a + function very fast. If a shared instance is modified, it will be + copied (copy-on-write), and this takes \l{linear time}. + + \sa operator=() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::operator=(const QMultiMap<Key, T> &other) + + Assigns \a other to this multi map and returns a reference to this multi map. +*/ + +/*! + \fn template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::operator=(QMultiMap<Key, T> &&other) + + Move-assigns \a other to this QMultiMap instance. + + \since 5.2 +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::~QMultiMap() + + Destroys the multi map. References to the values in the multi map, and all + iterators over this multi map, become invalid. +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(std::initializer_list<std::pair<Key,T> > list) + \since 5.1 + + Constructs a multi map with a copy of each of the elements in the + initializer list \a list. +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const typename std::multimap<Key, T> & other) + + Constructs a copy of \a other. + + \sa toStdMultiMap() +*/ + +/*! \fn template <class Key, class T> std::multimap<Key, T> QMultiMap<Key, T>::toStdMap() const + \obsolete Use toStdMultiMap() instead. + + Returns an STL multi map equivalent to this QMultiMap. +*/ + +/*! \fn template <class Key, class T> std::multimap<Key, T> QMultiMap<Key, T>::toStdMultiMap() const + + Returns an STL multi map equivalent to this QMultiMap. +*/ + +/*! \fn template <class Key, class T> void QMultiMap<Key, T>::swap(QMultiMap<Key, T> &other) + \since 4.8 + + Swaps multi map \a other with this multi map. This operation is very + fast and never fails. +*/ + +/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::operator==(const QMultiMap<Key, T> &other) const + + Returns \c true if \a other is equal to this multi map; otherwise returns + false. + + Two multi maps are considered equal if they contain the same (key, + value) pairs, in the same order (which matters for duplicate keys). + + This function requires the key and the value types to implement \c + operator==(). + + \sa operator!=() +*/ + +/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::operator!=(const QMultiMap<Key, T> &other) const + + Returns \c true if \a other is not equal to this multi map; otherwise + returns \c false. + + Two multi maps are considered equal if they contain the same (key, + value) pairs, in the same order (which matters for duplicate keys). + + This function requires the key and the value types to implement \c + operator==(). + + \sa operator==() +*/ + +/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::size() const + + Returns the number of (key, value) pairs in the multi map. + + \sa isEmpty(), count() +*/ + +/*! + \fn template <class Key, class T> bool QMultiMap<Key, T>::isEmpty() const + + Returns \c true if the multi map contains no items; otherwise returns + false. + + \sa size() +*/ + +/*! \fn template <class Key, class T> void QMultiMap<Key, T>::detach() + + \internal + + Detaches this map from any other multi maps with which it may share + data. + + \sa isDetached() +*/ + +/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::isDetached() const + + \internal + + Returns \c true if the multi map's internal data isn't shared with any + other map object; otherwise returns \c false. + + \sa detach() +*/ + +/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::isSharedWith(const QMultiMap<Key, T> &other) const + + \internal +*/ + +/*! \fn template <class Key, class T> void QMultiMap<Key, T>::clear() + + Removes all items from the multi map. + + \sa remove() +*/ + +/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::remove(const Key &key) + + Removes all the items that have the key \a key from the multi map. + Returns the number of items removed. + + \sa clear(), take() +*/ + +/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::remove(const Key &key, const T &value) + + Removes all the items that have the key \a key and value \a value + from the multi map. + Returns the number of items removed. + + \sa clear(), take() +*/ + +/*! \fn template <class Key, class T> T QMultiMap<Key, T>::take(const Key &key) + + Removes the item with the key \a key from the multi map and returns + the value associated with it. + + If the item does not exist in the multi map, the function simply + returns a \l{default-constructed value}. If there are multiple + items for \a key in the map, only the most recently inserted one + is removed and returned. + + If you don't use the return value, remove() is more efficient. + + \sa remove() +*/ + +/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::contains(const Key &key) const + + Returns \c true if the multi map contains an item with key \a key; + otherwise returns \c false. + + \sa count() +*/ + +/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const + \since 4.3 + + Returns \c true if the multi map contains an item with key \a key + and value \a value; otherwise returns \c false. + + \sa count() +*/ + +/*! + \fn template <class Key, class T> Key QMultiMap<Key, T>::key(const T &value, const Key &defaultKey) const + \since 4.3 + \overload + + Returns the first key with value \a value, or \a defaultKey if + the multi map contains no item with value \a value. If no \a defaultKey + is provided the function returns a + \l{default-constructed value}{default-constructed key}. + + This function can be slow (\l{linear time}), because QMultiMap's + internal data structure is optimized for fast lookup by key, not + by value. + + \sa value(), keys() +*/ + +/*! \fn template <class Key, class T> T QMultiMap<Key, T>::value(const Key &key, const T &defaultValue) const + + Returns the value associated with the key \a key. + + If the multi map contains no item with key \a key, the function returns + \a defaultValue. If no \a defaultValue is specified, the function + returns a \l{default-constructed value}. If there are multiple + items for \a key in the multi map, the value of the most recently + inserted one is returned. + + \sa key(), values(), contains(), operator[]() +*/ + +/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::keys() const + + Returns a list containing all the keys in the multi map in ascending + order. Keys that occur multiple times in the multi map + 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<Key> QMultiMap<Key, T>::keys(const T &value) const + + \overload + + Returns a list containing all the keys associated with value \a + value in ascending order. + + This function can be slow (\l{linear time}), because QMultiMap's + internal data structure is optimized for fast lookup by key, not + by value. +*/ + +/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::uniqueKeys() const + \since 4.2 + + Returns a list containing all the keys in the map in ascending + order. Keys that occur multiple times in the map occur only + once in the returned list. +*/ + +/*! \fn template <class Key, class T> QList<T> QMultiMap<Key, T>::values() const + + Returns a list containing all the values in the map, in ascending + order of their keys. If a key is associated with multiple values, + all of its values will be in the list, and not just the most + recently inserted one. + + \sa keys(), value() +*/ + +/*! \fn template <class Key, class T> QList<T> QMultiMap<Key, T>::values(const Key &key) const + + Returns a list containing all the values associated with key + \a key, from the most recently inserted to the least recently + inserted one. + + \sa keys(), value() +*/ + +/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count() const + + \overload + + Same as size(). +*/ + +/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count(const Key &key) const + + Returns the number of items associated with key \a key. + + \sa contains(), QMultiMap::count() +*/ + +/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count(const Key &key, const T &value) const + + Returns the number of items with key \a key and value \a value. + + \sa contains(), QMultiMap::count() +*/ + + +/*! \fn template <class Key, class T> const Key &QMultiMap<Key, T>::firstKey() const + \since 5.2 + + Returns a reference to the smallest key in the multi map. + This function assumes that the multi map is not empty. + + This executes in \l{constant time}. + + \sa lastKey(), first(), keyBegin(), isEmpty() +*/ + +/*! \fn template <class Key, class T> const Key &QMultiMap<Key, T>::lastKey() const + \since 5.2 + + Returns a reference to the largest key in the multi map. + This function assumes that the multi map is not empty. + + This executes in \l{logarithmic time}. + + \sa firstKey(), last(), keyEnd(), isEmpty() +*/ + +/*! \fn template <class Key, class T> T &QMultiMap<Key, T>::first() + \since 5.2 + + Returns a reference to the first value in the multi map, that is the value mapped + to the smallest key. This function assumes that the multi map is not empty. + + When unshared (or const version is called), this executes in \l{constant time}. + + \sa last(), firstKey(), isEmpty() +*/ + +/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::first() const + \since 5.2 + + \overload +*/ + +/*! \fn template <class Key, class T> T &QMultiMap<Key, T>::last() + \since 5.2 + + Returns a reference to the last value in the multi map, that is the value mapped + to the largest key. This function assumes that the map is not empty. + + When unshared (or const version is called), this executes in \l{logarithmic time}. + + \sa first(), lastKey(), isEmpty() +*/ + +/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::last() const + \since 5.2 + + \overload +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::begin() + + Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in + the multi map. + + \sa constBegin(), end() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::begin() const + + \overload +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::cbegin() const + \since 5.0 + + Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item + in the multi map. + + \sa begin(), cend() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::constBegin() const + + Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item + in the multi map. + + \sa begin(), constEnd() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<Key, T>::keyBegin() const + \since 5.6 + + Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key + in the multi map. + + \sa keyEnd(), firstKey() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::end() + + Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item + after the last item in the multi map. + + \sa begin(), constEnd() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::end() const + + \overload +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<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 multi map. + + \sa cbegin(), end() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<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 multi map. + + \sa constBegin(), end() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<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 multi map. + + \sa keyBegin(), lastKey() +*/ + + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_value_iterator QMultiMap<Key, T>::keyValueBegin() + \since 5.10 + + Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry + in the multi map. + + \sa keyValueEnd() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_value_iterator QMultiMap<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 multi map. + + \sa keyValueBegin() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<Key, T>::keyValueBegin() const + \since 5.10 + + Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry + in the multi map. + + \sa keyValueEnd() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<Key, T>::constKeyValueBegin() const + \since 5.10 + + Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry + in the multi map. + + \sa keyValueBegin() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<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 multi map. + + \sa keyValueBegin() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<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 multi map. + + \sa constKeyValueBegin() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::erase(const_iterator pos) + + Removes the (key, value) pair pointed to by the iterator \a pos + from the multi map, and returns an iterator to the next item in the + map. + + \sa remove() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::find(const Key &key) + + Returns an iterator pointing to the item with key \a key in the + multi map. + + If the multi map contains no item with key \a key, the function + returns end(). + + If the map contains multiple items with key \a key, this + function returns an iterator that points to the most recently + inserted value. The other values are accessible by incrementing + the iterator. For example, here's some code that iterates over all + the items with the same key: + + \snippet code/src_corelib_tools_qmultimap.cpp 11 + + \sa constFind(), value(), values(), lowerBound(), upperBound() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::find(const Key &key) const + + \overload +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::constFind(const Key &key) const + \since 4.1 + + Returns an const iterator pointing to the item with key \a key in the + multi map. + + If the multi map contains no item with key \a key, the function + returns constEnd(). + + \sa find(), QMultiMap::constFind() +*/ + +/*! + \fn template <class Key, class T> typename QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::find(const Key &key, const T &value) const + \since 4.3 + \overload + + Returns a const iterator pointing to the item with the given \a key and + \a value in the map. + + If the map contains no such item, the function returns end(). + + If the map contains multiple items with the specified \a key, this + function returns a const iterator that points to the most recently + inserted value. +*/ + +/*! + \fn template <class Key, class T> typename QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::constFind(const Key &key, const T &value) const + \since 4.3 + + Returns an iterator pointing to the item with key \a key and the + value \a value in the map. + + If the map contains no such item, the function returns + constEnd(). + + \sa QMap::constFind() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::lowerBound(const Key &key) + + Returns an iterator pointing to the first item with key \a key in + the map. If the map contains no item with key \a key, the + function returns an iterator to the nearest item with a greater + key. + + Example: + \snippet code/src_corelib_tools_qmultimap.cpp 15 + + If the map contains multiple items with key \a key, this + function returns an iterator that points to the most recently + inserted value. The other values are accessible by incrementing + the iterator. For example, here's some code that iterates over all + the items with the same key: + + \snippet code/src_corelib_tools_qmultimap.cpp 16 + + \sa upperBound(), find() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::lowerBound(const Key &key) const + + \overload +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::upperBound(const Key &key) + + Returns an iterator pointing to the item that immediately follows + the last item with key \a key in the map. If the map contains no + item with key \a key, the function returns an iterator to the + nearest item with a greater key. + + Example: + \snippet code/src_corelib_tools_qmultimap.cpp 17 + + \sa lowerBound(), find() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::upperBound(const Key &key) const + + \overload +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &key, const T &value) + + Inserts a new item with the key \a key and a value of \a value. + + If there is already an item with the same key in the map, this + function will simply create a new one. (This behavior is + different from replace(), which overwrites the value of an + existing item.) + + \sa replace() +*/ + +/*! \fn [qmultimap-insert-pos] template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const_iterator pos, const Key &key, const T &value) + \overload + \since 5.1 + Inserts a new item with the key \a key and value \a value and with hint \a pos + suggesting where to do the insert. + + If constBegin() is used as hint it indicates that the \a key is less than any key in the multi map + while constEnd() suggests that the \a key is (strictly) larger than any key in the multi map. + Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key(). + If the hint \a pos is wrong it is ignored and a regular insert is done. + + If the hint is correct and the multi map is unshared, the insert executes in amortized \l{constant time}. + + If there is already an item with the same key in the map, this function will simply create a new one. + + When creating a multi map from sorted data inserting the largest key first with constBegin() + is faster than inserting in sorted order with constEnd(), since constEnd() - 1 (which is needed + to check if the hint is valid) needs \l{logarithmic time}. + + \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might + crash but there is also a risk that it will silently corrupt both the multi map and the \a pos multi map. +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insertMulti(const Key &key, const T &value) + + Same as insert(). +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insertMulti(const_iterator pos, const Key &key, const T &value) + \overload + + Same as insert(). +*/ + +/*! \fn template <class Key, class T> void QMultiMap<Key, T>::insert(const QMultiMap<Key, T> &map) + \since 5.15 + + Same as unite(). +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::replace(const Key &key, const T &value) + + Inserts a new item with the key \a key and a value of \a value. + + If there is already an item with the key \a key, that item's value + is replaced with \a value. + + If there are multiple items with the key \a key, the most + recently inserted item's value is replaced with \a value. + + \sa insert() +*/ + +/*! \typedef QMultiMap::Iterator + + Qt-style synonym for QMultiMap<Key, T>::iterator. +*/ + +/*! \typedef QMultiMap::ConstIterator + + Qt-style synonym for QMultiMap<Key, T>::const_iterator. +*/ + +/*! \typedef QMultiMap::difference_type + + Typedef for ptrdiff_t. Provided for STL compatibility. +*/ + +/*! \typedef QMultiMap::key_type + + Typedef for Key. Provided for STL compatibility. +*/ + +/*! \typedef QMultiMap::mapped_type + + Typedef for T. Provided for STL compatibility. +*/ + +/*! \typedef QMultiMap::size_type + + Typedef for int. Provided for STL compatibility. +*/ + +/*! + \fn template <class Key, class T> bool QMultiMap<Key, T>::empty() const + + This function is provided for STL compatibility. It is equivalent + to isEmpty(), returning true if the map is empty; otherwise + returning false. +*/ + +/*! + \fn template <class Key, class T> QPair<typename QMultiMap<Key, T>::iterator, typename QMultiMap<Key, T>::iterator> QMultiMap<Key, T>::equal_range(const Key &key) + + Returns a pair of iterators delimiting the range of values \c{[first, second)}, that + are stored under \a key. +*/ + +/*! + \fn template <class Key, class T> QPair<typename QMultiMap<Key, T>::const_iterator, typename QMultiMap<Key, T>::const_iterator> QMultiMap<Key, T>::equal_range(const Key &key) const + \overload + \since 5.6 +*/ + +/*! + \fn [qmultimap-unite] template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other) + + Inserts all the items in the \a other map into this map. If a + key is common to both maps, the resulting map will contain the + key multiple times. +*/ + +/*! \fn template <class Key, class T> QMultiMap &QMultiMap<Key, T>::operator+=(const QMultiMap &other) + + Inserts all the items in the \a other map into this map and + returns a reference to this map. + + \sa insert(), operator+() +*/ + +/*! \fn template <class Key, class T> QMultiMap QMultiMap<Key, T>::operator+(const QMultiMap &other) const + + Returns a map that contains all the items in this map in + addition to all the items in \a other. If a key is common to both + maps, the resulting map will contain the key multiple times. + + \sa operator+=() +*/ + +/*! \class QMultiMap::iterator + \inmodule QtCore + \brief The QMultiMap::iterator class provides an STL-style non-const iterator for QMultiMap. + + QMultiMap 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. + + QMultiMap\<Key, T\>::iterator allows you to iterate over a QMultiMap + and to modify the value (but not the key) stored under + a particular key. If you want to iterate over a const QMultiMap, you + should use QMultiMap::const_iterator. It is generally good practice to + use QMultiMap::const_iterator on a non-const QMultiMap as well, unless you + need to change the QMultiMap through the iterator. Const iterators are + slightly faster, and can improve code readability. + + The default QMultiMap::iterator constructor creates an uninitialized + iterator. You must initialize it using a QMultiMap function like + QMultiMap::begin(), QMultiMap::end(), or QMultiMap::find() before you can + start iterating. Here's a typical loop that prints all the (key, + value) pairs stored in a map: + + \snippet code/src_corelib_tools_qmultimap.cpp 18 + + Unlike QMultiHash, which stores its items in an arbitrary order, QMultiMap + stores its items ordered by key. Items that share the same key + will appear consecutively, + from the most recently to the least recently inserted value. + + Let's see a few examples of things we can do with a + QMultiMap::iterator that we cannot do with a QMultiMap::const_iterator. + Here's an example that increments every value stored in the QMultiMap + by 2: + + \snippet code/src_corelib_tools_qmultimap.cpp 19 + + Here's an example that removes all the items whose key is a + string that starts with an underscore character: + + \snippet code/src_corelib_tools_qmultimap.cpp 20 + + The call to QMultiMap::erase() removes the item pointed to by the + iterator from the map, and returns an iterator to the next item. + Here's another way of removing an item while iterating: + + \snippet code/src_corelib_tools_qmultimap.cpp 21 + + It might be tempting to write code like this: + + \snippet code/src_corelib_tools_qmultimap.cpp 22 + + However, this will potentially crash in \c{++i}, because \c i is + a dangling iterator after the call to erase(). + + Multiple iterators can be used on the same map. If you add items + to the map, existing iterators will remain valid. If you remove + items from the map, iterators that point to the removed items + will become dangling iterators. + + \warning Iterators on implicitly shared containers do not work + exactly like STL-iterators. You should avoid copying a container + while iterators are active on that container. For more information, + read \l{Implicit sharing iterator problem}. + + \sa QMultiMap::const_iterator, QMultiMap::key_iterator, QMutableMultiMapIterator +*/ + +/*! \typedef QMultiMap::iterator::difference_type + + \internal +*/ + +/*! \typedef QMultiMap::iterator::iterator_category + + A synonym for \e {std::bidirectional_iterator_tag} indicating + this iterator is a bidirectional iterator. +*/ + +/*! \typedef QMultiMap::iterator::pointer + + \internal +*/ + +/*! \typedef QMultiMap::iterator::reference + + \internal +*/ + +/*! \typedef QMultiMap::iterator::value_type + + \internal +*/ + +/*! \fn template <class Key, class T> QMultiMap<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 QMultiMap::begin(), QMultiMap::end() +*/ + +/*! \fn template <class Key, class T> const Key &QMultiMap<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 QMultiMap::erase() + followed by QMultiMap::insert(). + + \sa value() +*/ + +/*! \fn template <class Key, class T> T &QMultiMap<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_qmultimap.cpp 23 + + \sa key(), operator*() +*/ + +/*! \fn template <class Key, class T> T &QMultiMap<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 *QMultiMap<Key, T>::iterator::operator->() const + + Returns a pointer to the current item's value. + + \sa value() +*/ + +/*! + \fn template <class Key, class T> bool QMultiMap<Key, T>::iterator::operator==(const iterator &other) const + \fn template <class Key, class T> bool QMultiMap<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 QMultiMap<Key, T>::iterator::operator!=(const iterator &other) const + \fn template <class Key, class T> bool QMultiMap<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> QMultiMap<Key, T>::iterator &QMultiMap<Key, T>::iterator::operator++() + + The prefix ++ operator (\c{++i}) advances the iterator to the + next item in the multi map and returns an iterator to the new current + item. + + Calling this function on QMultiMap::end() leads to undefined results. + + \sa operator--() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator++(int) + + \overload + + The postfix ++ operator (\c{i++}) advances the iterator to the + next item in the multi map and returns an iterator to the previously + current item. +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator &QMultiMap<Key, T>::iterator::operator--() + + The prefix -- operator (\c{--i}) makes the preceding item + current and returns an iterator pointing to the new current item. + + Calling this function on QMultiMap::begin() leads to undefined + results. + + \sa operator++() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator--(int) + + \overload + + The postfix -- operator (\c{i--}) makes the preceding item + current and returns an iterator pointing to the previously + current item. +*/ + +/*! \class QMultiMap::const_iterator + \inmodule QtCore + \brief The QMultiMap::const_iterator class provides an STL-style const iterator for QMultiMap. + + QMultiMap 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. + + QMultiMap\<Key, T\>::const_iterator allows you to iterate over a QMultiMap. + If you want to modify the QMultiMap as you iterate + over it, you must use QMultiMap::iterator instead. It is generally + good practice to use QMultiMap::const_iterator on a non-const QMultiMap as + well, unless you need to change the QMultiMap through the iterator. + Const iterators are slightly faster, and can improve code + readability. + + The default QMultiMap::const_iterator constructor creates an + uninitialized iterator. You must initialize it using a QMultiMap + function like QMultiMap::constBegin(), QMultiMap::constEnd(), or + QMultiMap::find() before you can start iterating. Here's a typical + loop that prints all the (key, value) pairs stored in a map: + + \snippet code/src_corelib_tools_qmultimap.cpp 24 + + Unlike QMultiHash, which stores its items in an arbitrary order, QMultiMap + stores its items ordered by key. Items that share the same key + will appear consecutively, + from the most recently to the least recently inserted value. + + Multiple iterators can be used on the same multi map. If you add items + to the map, existing iterators will remain valid. If you remove + items from the map, iterators that point to the removed items + will become dangling iterators. + + \warning Iterators on implicitly shared containers do not work + exactly like STL-iterators. You should avoid copying a container + while iterators are active on that container. For more information, + read \l{Implicit sharing iterator problem}. + + \sa QMultiMap::iterator, QMultiMap::key_iterator, QMultiMapIterator +*/ + +/*! \typedef QMultiMap::const_iterator::difference_type + + \internal +*/ + +/*! \typedef QMultiMap::const_iterator::iterator_category + + A synonym for \e {std::bidirectional_iterator_tag} indicating + this iterator is a bidirectional iterator. +*/ + +/*! \typedef QMultiMap::const_iterator::pointer + + \internal +*/ + +/*! \typedef QMultiMap::const_iterator::reference + + \internal +*/ + +/*! \typedef QMultiMap::const_iterator::value_type + + \internal +*/ + +/*! \fn template <class Key, class T> QMultiMap<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 QMultiMap::constBegin(), QMultiMap::constEnd() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator::const_iterator(const iterator &other) + + Constructs a copy of \a other. +*/ + +/*! \fn template <class Key, class T> const Key &QMultiMap<Key, T>::const_iterator::key() const + + Returns the current item's key. + + \sa value() +*/ + +/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::const_iterator::value() const + + Returns the current item's value. + + \sa key(), operator*() +*/ + +/*! \fn template <class Key, class T> const T &QMultiMap<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 *QMultiMap<Key, T>::const_iterator::operator->() const + + Returns a pointer to the current item's value. + + \sa value() +*/ + +/*! \fn template <class Key, class T> bool QMultiMap<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 QMultiMap<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> QMultiMap<Key, T>::const_iterator &QMultiMap<Key, T>::const_iterator::operator++() + + The prefix ++ operator (\c{++i}) advances the iterator to the + next item in the map and returns an iterator to the new current + item. + + Calling this function on QMultiMap::end() leads to undefined results. + + \sa operator--() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator++(int) + + \overload + + The postfix ++ operator (\c{i++}) advances the iterator to the + next item in the map and returns an iterator to the previously + current item. +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator &QMultiMap<Key, T>::const_iterator::operator--() + + The prefix -- operator (\c{--i}) makes the preceding item + current and returns an iterator pointing to the new current item. + + Calling this function on QMultiMap::begin() leads to undefined + results. + + \sa operator++() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator--(int) + + \overload + + The postfix -- operator (\c{i--}) makes the preceding item + current and returns an iterator pointing to the previously + current item. +*/ + +/*! \class QMultiMap::key_iterator + \inmodule QtCore + \since 5.6 + \brief The QMultiMap::key_iterator class provides an STL-style const iterator for QMultiMap keys. + + QMultiMap::key_iterator is essentially the same as QMultiMap::const_iterator + with the difference that operator*() and operator->() return a key + instead of a value. + + For most uses QMultiMap::iterator and QMultiMap::const_iterator should be used, + you can easily access the key by calling QMultiMap::iterator::key(): + + \snippet code/src_corelib_tools_qmultimap.cpp keyiterator1 + + However, to have interoperability between QMultiMap's keys and STL-style + algorithms we need an iterator that dereferences to a key instead + of a value. With QMultiMap::key_iterator we can apply an algorithm to a + range of keys without having to call QMultiMap::keys(), which is inefficient + as it costs one QMultiMap iteration and memory allocation to create a temporary + QList. + + \snippet code/src_corelib_tools_qmultimap.cpp keyiterator2 + + QMultiMap::key_iterator is const, it's not possible to modify the key. + + The default QMultiMap::key_iterator constructor creates an uninitialized + iterator. You must initialize it using a QMultiMap function like + QMultiMap::keyBegin() or QMultiMap::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 QMultiMap::const_iterator, QMultiMap::iterator +*/ + +/*! \typedef QMultiMap::key_iterator::difference_type + \internal +*/ + +/*! \typedef QMultiMap::key_iterator::iterator_category + \internal +*/ + +/*! \typedef QMultiMap::key_iterator::pointer + \internal +*/ + +/*! \typedef QMultiMap::key_iterator::reference + \internal +*/ + +/*! \typedef QMultiMap::key_iterator::value_type + \internal +*/ + +/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::key_iterator::operator*() const + + Returns the current item's key. +*/ + +/*! \fn template <class Key, class T> const T *QMultiMap<Key, T>::key_iterator::operator->() const + + Returns a pointer to the current item's key. +*/ + +/*! \fn template <class Key, class T> bool QMultiMap<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 QMultiMap<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> QMultiMap<Key, T>::key_iterator &QMultiMap<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 QMultiMap::keyEnd() leads to undefined results. + + \sa operator--() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<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> QMultiMap<Key, T>::key_iterator &QMultiMap<Key, T>::key_iterator::operator--() + + The prefix -- operator (\c{--i}) makes the preceding item + current and returns an iterator pointing to the new current item. + + Calling this function on QMultiMap::keyBegin() leads to undefined + results. + + \sa operator++() +*/ + +/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<Key, T>::key_iterator::operator--(int) + + \overload + + The postfix -- operator (\c{i--}) makes the preceding item + current and returns an iterator pointing to the previous + item. +*/ + +/*! \fn template <class Key, class T> const_iterator QMultiMap<Key, T>::key_iterator::base() const + Returns the underlying const_iterator this key_iterator is based on. +*/ + +/*! \typedef QMultiMap::const_key_value_iterator + \inmodule QtCore + \since 5.10 + \brief The QMultiMap::const_key_value_iterator typedef provides an STL-style iterator for QMultiMap. + + QMultiMap::const_key_value_iterator is essentially the same as QMultiMap::const_iterator + with the difference that operator*() returns a key/value pair instead of a + value. + + \sa QKeyValueIterator +*/ + +/*! \typedef QMultiMap::key_value_iterator + \inmodule QtCore + \since 5.10 + \brief The QMultiMap::key_value_iterator typedef provides an STL-style iterator for QMultiMap. + + QMultiMap::key_value_iterator is essentially the same as QMultiMap::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 QMultiMap<Key, T> &map) + \relates QMultiMap + + Writes the multi map \a map to stream \a out. + + This function requires the key and value types to implement \c + operator<<(). + + \sa{Serializing Qt Data Types}{Format of the QDataStream operators} +*/ + +/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QMultiMap<Key, T> &map) + \relates QMultiMap + + Reads a map from stream \a in into \a map. + + This function requires the key and value types to implement \c + operator>>(). + + \sa{Serializing Qt Data Types}{Format of the QDataStream operators} +*/ diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri index c8ce79ce36..9380b8bd5a 100644 --- a/src/corelib/tools/tools.pri +++ b/src/corelib/tools/tools.pri @@ -58,7 +58,6 @@ SOURCES += \ tools/qline.cpp \ tools/qlist.cpp \ tools/qpoint.cpp \ - tools/qmap.cpp \ tools/qmargins.cpp \ tools/qmessageauthenticationcode.cpp \ tools/qcontiguouscache.cpp \ diff --git a/src/gui/text/qcssparser.cpp b/src/gui/text/qcssparser.cpp index 405ed94064..9b1c67c8d5 100644 --- a/src/gui/text/qcssparser.cpp +++ b/src/gui/text/qcssparser.cpp @@ -2157,7 +2157,7 @@ QList<StyleRule> StyleSelector::styleRulesForNode(NodePtr node) } rules.reserve(weightedRules.count()); - QMap<uint, StyleRule>::const_iterator it = weightedRules.constBegin(); + QMultiMap<uint, StyleRule>::const_iterator it = weightedRules.constBegin(); for ( ; it != weightedRules.constEnd() ; ++it) rules += *it; diff --git a/src/tools/bootstrap/CMakeLists.txt b/src/tools/bootstrap/CMakeLists.txt index f3889008a9..0a58f7a699 100644 --- a/src/tools/bootstrap/CMakeLists.txt +++ b/src/tools/bootstrap/CMakeLists.txt @@ -119,7 +119,6 @@ qt_extend_target(Bootstrap ../../corelib/tools/qcryptographichash.cpp ../../corelib/tools/qhash.cpp ../../corelib/tools/qline.cpp - ../../corelib/tools/qmap.cpp ../../corelib/tools/qpoint.cpp ../../corelib/tools/qrect.cpp ../../corelib/tools/qringbuffer.cpp diff --git a/src/tools/bootstrap/bootstrap.pro b/src/tools/bootstrap/bootstrap.pro index 5b7da8e687..9e7d570def 100644 --- a/src/tools/bootstrap/bootstrap.pro +++ b/src/tools/bootstrap/bootstrap.pro @@ -104,7 +104,6 @@ SOURCES += \ ../../corelib/tools/qcommandlineoption.cpp \ ../../corelib/tools/qcryptographichash.cpp \ ../../corelib/tools/qhash.cpp \ - ../../corelib/tools/qmap.cpp \ ../../corelib/tools/qringbuffer.cpp \ ../../corelib/tools/qpoint.cpp \ ../../corelib/tools/qrect.cpp \ diff --git a/src/widgets/dialogs/qwizard.cpp b/src/widgets/dialogs/qwizard.cpp index efd661e829..24d996dad4 100644 --- a/src/widgets/dialogs/qwizard.cpp +++ b/src/widgets/dialogs/qwizard.cpp @@ -2207,7 +2207,7 @@ int QWizard::addPage(QWizardPage *page) Q_D(QWizard); int theid = 0; if (!d->pageMap.isEmpty()) - theid = (d->pageMap.constEnd() - 1).key() + 1; + theid = d->pageMap.lastKey() + 1; setPage(theid, page); return theid; } diff --git a/src/widgets/kernel/qgesturemanager.cpp b/src/widgets/kernel/qgesturemanager.cpp index 134cebca09..5137b7ef07 100644 --- a/src/widgets/kernel/qgesturemanager.cpp +++ b/src/widgets/kernel/qgesturemanager.cpp @@ -274,8 +274,8 @@ bool QGestureManager::filterEventThroughContexts(const QMultiMap<QObject *, ContextIterator contextEnd = contexts.end(); for (ContextIterator context = contexts.begin(); context != contextEnd; ++context) { Qt::GestureType gestureType = context.value(); - const QMap<Qt::GestureType, QGestureRecognizer *> &const_recognizers = m_recognizers; - QMap<Qt::GestureType, QGestureRecognizer *>::const_iterator + const QMultiMap<Qt::GestureType, QGestureRecognizer *> &const_recognizers = m_recognizers; + QMultiMap<Qt::GestureType, QGestureRecognizer *>::const_iterator typeToRecognizerIterator = const_recognizers.lowerBound(gestureType), typeToRecognizerEnd = const_recognizers.upperBound(gestureType); for (; typeToRecognizerIterator != typeToRecognizerEnd; ++typeToRecognizerIterator) { diff --git a/tests/auto/corelib/kernel/qvariant/tst_qvariant.cpp b/tests/auto/corelib/kernel/qvariant/tst_qvariant.cpp index 9cc7c366db..a41af75f72 100644 --- a/tests/auto/corelib/kernel/qvariant/tst_qvariant.cpp +++ b/tests/auto/corelib/kernel/qvariant/tst_qvariant.cpp @@ -4290,10 +4290,10 @@ void tst_QVariant::iterateContainerElements() QAssociativeIterable iter = var.value<QAssociativeIterable>(); QAssociativeIterable::const_iterator it = iter.begin(); QAssociativeIterable::const_iterator end = iter.end(); - QCOMPARE(*(mapping.begin() + 1), (*(it + 1)).toString()); + QCOMPARE(*(++mapping.begin()), (*(it + 1)).toString()); int i = 0; for ( ; it != end; ++it, ++i) { - QCOMPARE(*(mapping.begin() + i), (*it).toString()); + QCOMPARE(*(std::next(mapping.begin(), i)), (*it).toString()); } QVariantList nums; diff --git a/tests/auto/corelib/tools/collections/tst_collections.cpp b/tests/auto/corelib/tools/collections/tst_collections.cpp index 2cab6312aa..e5cfb0fbad 100644 --- a/tests/auto/corelib/tools/collections/tst_collections.cpp +++ b/tests/auto/corelib/tools/collections/tst_collections.cpp @@ -2609,6 +2609,7 @@ class LessThanComparable { public: bool operator<(const LessThanComparable &) const { return true; } + bool operator==(const LessThanComparable &) const { return true; } }; class EqualsComparable @@ -2937,20 +2938,6 @@ void tst_Collections::forwardDeclared() } } -class alignas(4) Aligned4 -{ - char i; -public: - Aligned4(int i = 0) : i(i) {} - - enum { PreferredAlignment = 4 }; - - inline bool operator==(const Aligned4 &other) const { return i == other.i; } - inline bool operator<(const Aligned4 &other) const { return i < other.i; } - friend inline size_t qHash(const Aligned4 &a) { return qHash(a.i); } -}; -static_assert(alignof(Aligned4) % 4 == 0); - #if defined(Q_PROCESSOR_ARM) # if defined(Q_COMPILER_ALIGNAS) && defined(__BIGGEST_ALIGNMENT__) // On ARM __BIGGEST_ALIGNMENT__ must be multiplied by 8 to @@ -2963,18 +2950,29 @@ static_assert(alignof(Aligned4) % 4 == 0); # define BIGGEST_ALIGNMENT_TO_TEST 128 #endif -class alignas(BIGGEST_ALIGNMENT_TO_TEST) AlignedBiggest +template <size_t Alignment> +class alignas(Alignment) AlignedClass { char i; + public: - AlignedBiggest(int i = 0) : i(i) {} + AlignedClass(int i = 0) : i(i) {} - enum { PreferredAlignment = BIGGEST_ALIGNMENT_TO_TEST }; + enum { PreferredAlignment = Alignment }; - inline bool operator==(const AlignedBiggest &other) const { return i == other.i; } - inline bool operator<(const AlignedBiggest &other) const { return i < other.i; } - friend inline int qHash(const AlignedBiggest &a) { return qHash(a.i); } + inline bool operator==(const AlignedClass &other) const { return i == other.i; } + inline bool operator<(const AlignedClass &other) const { return i < other.i; } + friend inline int qHash(const AlignedClass &a) { return qHash(a.i); } }; + +using Aligned4 = AlignedClass<4>; +static_assert(alignof(Aligned4) % 4 == 0); + +using AlignedStdMax = AlignedClass<alignof(std::max_align_t)>; +static_assert(alignof(AlignedStdMax) % alignof(std::max_align_t) == 0); + +using AlignedBiggest = AlignedClass<BIGGEST_ALIGNMENT_TO_TEST>; +static_assert(BIGGEST_ALIGNMENT_TO_TEST > alignof(std::max_align_t), "Not overly aligned"); static_assert(alignof(AlignedBiggest) % BIGGEST_ALIGNMENT_TO_TEST == 0); template<typename C> @@ -3032,18 +3030,29 @@ void testAssociativeContainerAlignment() void tst_Collections::alignment() { - testVectorAlignment<QList<Aligned4>>(); - testVectorAlignment<QList<AlignedBiggest>>(); - testContiguousCacheAlignment<QContiguousCache<Aligned4>>(); - testContiguousCacheAlignment<QContiguousCache<AlignedBiggest>>(); - testAssociativeContainerAlignment<QMap<Aligned4, Aligned4>>(); - testAssociativeContainerAlignment<QMap<Aligned4, AlignedBiggest>>(); - testAssociativeContainerAlignment<QMap<AlignedBiggest, Aligned4>>(); - testAssociativeContainerAlignment<QMap<AlignedBiggest, AlignedBiggest>>(); - testAssociativeContainerAlignment<QHash<Aligned4, Aligned4>>(); - testAssociativeContainerAlignment<QHash<Aligned4, AlignedBiggest>>(); - testAssociativeContainerAlignment<QHash<AlignedBiggest, Aligned4>>(); - testAssociativeContainerAlignment<QHash<AlignedBiggest, AlignedBiggest>>(); + testVectorAlignment<QList<Aligned4> >(); + testVectorAlignment<QList<AlignedStdMax> >(); + testVectorAlignment<QList<AlignedBiggest> >(); + + testContiguousCacheAlignment<QContiguousCache<Aligned4> >(); + testContiguousCacheAlignment<QContiguousCache<AlignedStdMax> >(); + testContiguousCacheAlignment<QContiguousCache<AlignedBiggest> >(); + + // there's no guarentee that std::map supports over-aligned types + testAssociativeContainerAlignment<QMap<Aligned4, Aligned4> >(); + testAssociativeContainerAlignment<QMap<Aligned4, AlignedStdMax> >(); + testAssociativeContainerAlignment<QMap<AlignedStdMax, Aligned4> >(); + testAssociativeContainerAlignment<QMap<AlignedStdMax, AlignedStdMax> >(); + + testAssociativeContainerAlignment<QHash<Aligned4, Aligned4> >(); + testAssociativeContainerAlignment<QHash<Aligned4, AlignedStdMax> >(); + testAssociativeContainerAlignment<QHash<Aligned4, AlignedBiggest> >(); + testAssociativeContainerAlignment<QHash<AlignedStdMax, Aligned4> >(); + testAssociativeContainerAlignment<QHash<AlignedStdMax, AlignedStdMax> >(); + testAssociativeContainerAlignment<QHash<AlignedStdMax, AlignedBiggest> >(); + testAssociativeContainerAlignment<QHash<AlignedBiggest, Aligned4> >(); + testAssociativeContainerAlignment<QHash<AlignedBiggest, AlignedStdMax> >(); + testAssociativeContainerAlignment<QHash<AlignedBiggest, AlignedBiggest> >(); } #ifndef QT_NO_TEMPLATE_TEMPLATE_PARAMETERS diff --git a/tests/auto/corelib/tools/qmap/tst_qmap.cpp b/tests/auto/corelib/tools/qmap/tst_qmap.cpp index b812eb89a1..c8a228f8dd 100644 --- a/tests/auto/corelib/tools/qmap/tst_qmap.cpp +++ b/tests/auto/corelib/tools/qmap/tst_qmap.cpp @@ -36,8 +36,8 @@ class tst_QMap : public QObject { Q_OBJECT protected: - template <class KEY, class VALUE> - void sanityCheckTree(const QMap<KEY, VALUE> &m, int calledFromLine); + template <class Map> + void sanityCheckTree(const Map &m, int calledFromLine); public slots: void init(); private slots: @@ -119,15 +119,15 @@ QDebug operator << (QDebug d, const MyClass &c) { return d; } -template <class KEY, class VALUE> -void tst_QMap::sanityCheckTree(const QMap<KEY, VALUE> &m, int calledFromLine) +template <class Map> +void tst_QMap::sanityCheckTree(const Map &m, int calledFromLine) { QString possibleFrom; possibleFrom.setNum(calledFromLine); possibleFrom = "Called from line: " + possibleFrom; int count = 0; - typename QMap<KEY, VALUE>::const_iterator oldite = m.constBegin(); - for (typename QMap<KEY, VALUE>::const_iterator i = m.constBegin(); i != m.constEnd(); ++i) { + typename Map::const_iterator oldite = m.constBegin(); + for (typename Map::const_iterator i = m.constBegin(); i != m.constEnd(); ++i) { count++; bool oldIteratorIsLarger = i.key() < oldite.key(); QVERIFY2(!oldIteratorIsLarger, possibleFrom.toUtf8()); @@ -594,7 +594,7 @@ void tst_QMap::contains() void tst_QMap::find() { - QMap<int, QString> map1; + QMultiMap<int, QString> map1; QString testString="Teststring %0"; QString compareString; int i,count=0; @@ -614,7 +614,7 @@ void tst_QMap::find() QCOMPARE(map1.count(4), i - 2); } - QMap<int, QString>::const_iterator it=map1.constFind(4); + QMultiMap<int, QString>::const_iterator it=map1.constFind(4); for(i = 9; i > 2 && it != map1.constEnd() && it.key() == 4; --i) { compareString = testString.arg(i); @@ -627,7 +627,7 @@ void tst_QMap::find() void tst_QMap::constFind() { - QMap<int, QString> map1; + QMultiMap<int, QString> map1; QString testString="Teststring %0"; QString compareString; int i,count=0; @@ -648,7 +648,7 @@ void tst_QMap::constFind() map1.insertMulti(4, compareString); } - QMap<int, QString>::const_iterator it=map1.constFind(4); + QMultiMap<int, QString>::const_iterator it=map1.constFind(4); for(i = 9; i > 2 && it != map1.constEnd() && it.key() == 4; --i) { compareString = testString.arg(i); @@ -661,7 +661,7 @@ void tst_QMap::constFind() void tst_QMap::lowerUpperBound() { - QMap<int, QString> map1; + QMultiMap<int, QString> map1; map1.insert(1, "one"); map1.insert(5, "five"); @@ -712,7 +712,7 @@ void tst_QMap::lowerUpperBound() void tst_QMap::mergeCompare() { - QMap<int, QString> map1, map2, map3, map1b, map2b; + QMultiMap<int, QString> map1, map2, map3, map1b, map2b; map1.insert(1,"ett"); map1.insert(3,"tre"); @@ -770,13 +770,13 @@ void tst_QMap::iterators() QMap<int, QString>::iterator stlIt = map.begin(); QCOMPARE(stlIt.value(), QLatin1String("Teststring 1")); - stlIt+=5; + std::advance(stlIt, 5); QCOMPARE(stlIt.value(), QLatin1String("Teststring 6")); stlIt++; QCOMPARE(stlIt.value(), QLatin1String("Teststring 7")); - stlIt-=3; + std::advance(stlIt, -3); QCOMPARE(stlIt.value(), QLatin1String("Teststring 4")); stlIt--; @@ -791,13 +791,13 @@ void tst_QMap::iterators() QMap<int, QString>::const_iterator cstlIt = map.constBegin(); QCOMPARE(cstlIt.value(), QLatin1String("Teststring 1")); - cstlIt+=5; + std::advance(cstlIt, 5); QCOMPARE(cstlIt.value(), QLatin1String("Teststring 6")); cstlIt++; QCOMPARE(cstlIt.value(), QLatin1String("Teststring 7")); - cstlIt-=3; + std::advance(cstlIt, -3); QCOMPARE(cstlIt.value(), QLatin1String("Teststring 4")); cstlIt--; @@ -926,28 +926,23 @@ void tst_QMap::keyValueIterator() void tst_QMap::keys_values_uniqueKeys() { - QMap<QString, int> map; - QVERIFY(map.uniqueKeys().isEmpty()); + QMultiMap<QString, int> map; QVERIFY(map.keys().isEmpty()); QVERIFY(map.values().isEmpty()); map.insertMulti("alpha", 1); QVERIFY(map.keys() == (QList<QString>() << "alpha")); - QVERIFY(map.uniqueKeys() == map.keys()); QVERIFY(map.values() == (QList<int>() << 1)); map.insertMulti("beta", -2); QVERIFY(map.keys() == (QList<QString>() << "alpha" << "beta")); - QVERIFY(map.keys() == map.uniqueKeys()); QVERIFY(map.values() == (QList<int>() << 1 << -2)); map.insertMulti("alpha", 2); - QVERIFY(map.uniqueKeys() == (QList<QString>() << "alpha" << "beta")); QVERIFY(map.keys() == (QList<QString>() << "alpha" << "alpha" << "beta")); QVERIFY(map.values() == (QList<int>() << 2 << 1 << -2)); map.insertMulti("beta", 4); - QVERIFY(map.uniqueKeys() == (QList<QString>() << "alpha" << "beta")); QVERIFY(map.keys() == (QList<QString>() << "alpha" << "alpha" << "beta" << "beta")); QVERIFY(map.values() == (QList<int>() << 2 << 1 << 4 << -2)); } @@ -1077,14 +1072,14 @@ void tst_QMap::const_shared_null() void tst_QMap::equal_range() { - QMap<int, QString> map; - const QMap<int, QString> &cmap = map; + QMultiMap<int, QString> map; + const QMultiMap<int, QString> &cmap = map; - QPair<QMap<int, QString>::iterator, QMap<int, QString>::iterator> result = map.equal_range(0); + QPair<QMultiMap<int, QString>::iterator, QMultiMap<int, QString>::iterator> result = map.equal_range(0); QCOMPARE(result.first, map.end()); QCOMPARE(result.second, map.end()); - QPair<QMap<int, QString>::const_iterator, QMap<int, QString>::const_iterator> cresult = cmap.equal_range(0); + QPair<QMultiMap<int, QString>::const_iterator, QMultiMap<int, QString>::const_iterator> cresult = cmap.equal_range(0); QCOMPARE(cresult.first, cmap.cend()); QCOMPARE(cresult.second, cmap.cend()); @@ -1294,10 +1289,10 @@ void tst_QMap::insertMap() // make sure this isn't adding multiple entries with the // same key to the QMap. QMap<int, int> map; - QMultiMap<int, int> map2; - map2.insert(0, 0); + map.insert(0, 0); + + QMap<int, int> map2; map2.insert(0, 1); - map2.insert(0, 2); map.insert(map2); @@ -1452,11 +1447,11 @@ void tst_QMap::testInsertWithHint() void tst_QMap::testInsertMultiWithHint() { - QMap<int, int> map; + QMultiMap<int, int> map; map.insertMulti(map.end(), 64, 65); - map[128] = 129; - map[256] = 257; + map.insert(128, 129); + map.insert(256, 257); sanityCheckTree(map, __LINE__); map.insertMulti(map.end(), 512, 513); @@ -1467,11 +1462,11 @@ void tst_QMap::testInsertMultiWithHint() sanityCheckTree(map, __LINE__); QCOMPARE(map.size(), 6); - QMap<int, int>::iterator i = map.insertMulti(map.constBegin(), 256, 259); // wrong hint + QMultiMap<int, int>::iterator i = map.insertMulti(map.constBegin(), 256, 259); // wrong hint sanityCheckTree(map, __LINE__); QCOMPARE(map.size(), 7); - QMap<int, int>::iterator j = map.insertMulti(map.constBegin(), 69, 66); + QMultiMap<int, int>::iterator j = map.insertMulti(map.constBegin(), 69, 66); sanityCheckTree(map, __LINE__); QCOMPARE(map.size(), 8); @@ -1502,14 +1497,14 @@ void tst_QMap::testInsertMultiWithHint() void tst_QMap::eraseValidIteratorOnSharedMap() { - QMap<int, int> a, b; + QMultiMap<int, int> a, b; a.insert(10, 10); a.insertMulti(10, 40); a.insertMulti(10, 25); a.insertMulti(10, 30); a.insert(20, 20); - QMap<int, int>::iterator i = a.begin(); + QMultiMap<int, int>::iterator i = a.begin(); while (i.value() != 25) ++i; @@ -1529,12 +1524,12 @@ void tst_QMap::eraseValidIteratorOnSharedMap() QCOMPARE(itemsWith10, 4); // Border cases - QMap <QString, QString> ms1, ms2, ms3; + QMultiMap <QString, QString> ms1, ms2, ms3; ms1.insert("foo", "bar"); ms1.insertMulti("foo", "quux"); ms1.insertMulti("foo", "bar"); - QMap <QString, QString>::iterator si = ms1.begin(); + QMultiMap <QString, QString>::iterator si = ms1.begin(); ms2 = ms1; ms1.erase(si); si = ms1.begin(); diff --git a/tests/auto/dbus/qdbusmarshall/common.h b/tests/auto/dbus/qdbusmarshall/common.h index 44346cd6f2..7a42e8f97f 100644 --- a/tests/auto/dbus/qdbusmarshall/common.h +++ b/tests/auto/dbus/qdbusmarshall/common.h @@ -203,7 +203,11 @@ inline QDBusIntrospection::Argument arg(const char* type, const char *name = 0) template<typename T> inline QMap<QString, T>& operator<<(QMap<QString, T>& map, const T& m) -{ map.insertMulti(m.name, m); return map; } +{ map.insert(m.name, m); return map; } + +template<typename T> +inline QMultiMap<QString, T>& operator<<(QMultiMap<QString, T>& map, const T& m) +{ map.insert(m.name, m); return map; } inline const char* mapName(const MethodMap&) { return "MethodMap"; } @@ -263,11 +267,11 @@ QString printable(const QDBusIntrospection::Property& p) return result; } -template<typename T> -char* printableMap(const QMap<QString, T>& map) +template<typename Map> +char* printableMap(const Map& map) { QString contents = "\n"; - typename QMap<QString, T>::const_iterator it = map.begin(); + auto it = map.begin(); for ( ; it != map.end(); ++it) { if (it.key() != it.value().name) contents += it.value().name + ":"; |