1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtCore module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "qmap.h"

    43 

    44 #include <stdlib.h>

    45 

    46 #ifdef QT_QMAP_DEBUG

    47 # include <qstring.h>

    48 # include <qvector.h>

    49 #endif

    50 

    51 QT_BEGIN_NAMESPACE

    52 

    53 QMapData QMapData::shared_null = {

    54     &shared_null,

    55     { &shared_null, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

    56     Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, 0, false, true

    57 };

    58 

    59 QMapData *QMapData::createData()

    60 {

    61     QMapData *d = new QMapData;

    62     Q_CHECK_PTR(d);

    63     Node *e = reinterpret_cast<Node *>(d);

    64     e->backward = e;

    65     e->forward[0] = e;

    66     d->ref = 1;

    67     d->topLevel = 0;

    68     d->size = 0;

    69     d->randomBits = 0;

    70     d->insertInOrder = false;

    71     d->sharable = true;

    72     return d;

    73 }

    74 

    75 void QMapData::continueFreeData(int offset)

    76 {

    77     Node *e = reinterpret_cast<Node *>(this);

    78     Node *cur = e->forward[0];

    79     Node *prev;

    80     while (cur != e) {

    81         prev = cur;

    82         cur = cur->forward[0];

    83         qFree(reinterpret_cast<char *>(prev) - offset);

    84     }

    85     delete this;

    86 }

    87 

    88 /*!

    89     Creates a new node inside the data structure.

    90 

    91     \a update is an array with pointers to the node after which the new node

    92     should be inserted. Because of the strange skip list data structure there

    93     could be several pointers to this node on different levels.

    94     \a offset is an amount of bytes that needs to reserved just before the

    95     QMapData::Node structure.

    96 

    97     \internal

    98     \since 4.6

    99 */

   100 QMapData::Node *QMapData::node_create(Node *update[], int offset)

   101 {

   102     int level = 0;

   103     uint mask = (1 << Sparseness) - 1;

   104 

   105     while ((randomBits & mask) == mask && level < LastLevel) {

   106         ++level;

   107         mask <<= Sparseness;

   108     }

   109 

   110     if (level > topLevel) {

   111         Node *e = reinterpret_cast<Node *>(this);

   112         level = ++topLevel;

   113         e->forward[level] = e;

   114         update[level] = e;

   115     }

   116 

   117     ++randomBits;

   118     if (level == 3 && !insertInOrder)

   119         randomBits = qrand();

   120 

   121     void *concreteNode = qMalloc(offset + sizeof(Node) + level * sizeof(Node *));

   122     Q_CHECK_PTR(concreteNode);

   123 

   124     Node *abstractNode = reinterpret_cast<Node *>(reinterpret_cast<char *>(concreteNode) + offset);

   125 

   126     abstractNode->backward = update[0];

   127     update[0]->forward[0]->backward = abstractNode;

   128 

   129     for (int i = level; i >= 0; i--) {

   130         abstractNode->forward[i] = update[i]->forward[i];

   131         update[i]->forward[i] = abstractNode;

   132         update[i] = abstractNode;

   133     }

   134     ++size;

   135     return abstractNode;

   136 }

   137 

   138 void QMapData::node_delete(Node *update[], int offset, Node *node)

   139 {

   140     node->forward[0]->backward = node->backward;

   141 

   142     for (int i = 0; i <= topLevel; ++i) {

   143         if (update[i]->forward[i] != node)

   144             break;

   145         update[i]->forward[i] = node->forward[i];

   146     }

   147     --size;

   148     qFree(reinterpret_cast<char *>(node) - offset);

   149 }

   150 

   151 #ifdef QT_QMAP_DEBUG

   152 

   153 uint QMapData::adjust_ptr(Node *node)

   154 {

   155     if (node == reinterpret_cast<Node *>(this)) {

   156        return (uint)0xDEADBEEF;

   157     } else {

   158         return (uint)node;

   159     }

   160 }

   161 

   162 void QMapData::dump()

   163 {

   164     qDebug("Map data (ref = %d, size = %d, randomBits = %#.8x)", int(ref), size, randomBits);

   165 

   166     QString preOutput;

   167     QVector<QString> output(topLevel + 1);

   168     Node *e = reinterpret_cast<Node *>(this);

   169 

   170     QString str;

   171     str.sprintf("    %.8x", adjust_ptr(reinterpret_cast<Node *>(this)));

   172     preOutput += str;

   173 

   174     Node *update[LastLevel + 1];

   175     for (int i = 0; i <= topLevel; ++i) {

   176         str.sprintf("%d: [%.8x] -", i, adjust_ptr(reinterpret_cast<Node *>(forward[i])));

   177         output[i] += str;

   178         update[i] = reinterpret_cast<Node *>(forward[i]);

   179     }

   180 

   181     Node *node = reinterpret_cast<Node *>(forward[0]);

   182     while (node != e) {

   183         int level = 0;

   184         while (level < topLevel && update[level + 1] == node)

   185             ++level;

   186 

   187         str.sprintf("       %.8x", adjust_ptr(node));

   188         preOutput += str;

   189 

   190         for (int i = 0; i <= level; ++i) {

   191             str.sprintf("-> [%.8x] -", adjust_ptr(node->forward[i]));

   192             output[i] += str;

   193             update[i] = node->forward[i];

   194         }

   195         for (int j = level + 1; j <= topLevel; ++j)

   196             output[j] += QLatin1String("---------------");

   197         node = node->forward[0];

   198     }

   199 

   200     qDebug("%s", preOutput.ascii());

   201     for (int i = 0; i <= topLevel; ++i)

   202         qDebug("%s", output[i].ascii());

   203 }

   204 #endif

   205 

   206 /*!

   207     \class QMap

   208     \brief The QMap class is a template class that provides a skip-list-based dictionary.

   209 

   210     \ingroup tools

   211     \ingroup shared

   212 

   213     \reentrant

   214 

   215     QMap\<Key, T\> is one of Qt's generic \l{container classes}. It

   216     stores (key, value) pairs and provides fast lookup of the

   217     value associated with a key.

   218 

   219     QMap and QHash provide very similar functionality. The

   220     differences are:

   221 

   222     \list

   223     \i QHash provides faster lookups than QMap. (See \l{Algorithmic

   224        Complexity} for details.)

   225     \i When iterating over a QHash, the items are arbitrarily ordered.

   226        With QMap, the items are always sorted by key.

   227     \i The key type of a QHash must provide operator==() and a global

   228        qHash(Key) function. The key type of a QMap must provide

   229        operator<() specifying a total order.

   230     \endlist

   231 

   232     Here's an example QMap with QString keys and \c int values:

   233     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 0

   234 

   235     To insert a (key, value) pair into the map, you can use operator[]():

   236 

   237     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 1

   238 

   239     This inserts the following three (key, value) pairs into the

   240     QMap: ("one", 1), ("three", 3), and ("seven", 7). Another way to

   241     insert items into the map is to use insert():

   242 

   243     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 2

   244 

   245     To look up a value, use operator[]() or value():

   246 

   247     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 3

   248 

   249     If there is no item with the specified key in the map, these

   250     functions return a \l{default-constructed value}.

   251 

   252     If you want to check whether the map contains a certain key, use

   253     contains():

   254 

   255     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 4

   256 

   257     There is also a value() overload that uses its second argument as

   258     a default value if there is no item with the specified key:

   259 

   260     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 5

   261 

   262     In general, we recommend that you use contains() and value()

   263     rather than operator[]() for looking up a key in a map. The

   264     reason is that operator[]() silently inserts an item into the

   265     map if no item exists with the same key (unless the map is

   266     const). For example, the following code snippet will create 1000

   267     items in memory:

   268 

   269     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 6

   270 

   271     To avoid this problem, replace \c map[i] with \c map.value(i)

   272     in the code above.

   273 

   274     If you want to navigate through all the (key, value) pairs stored

   275     in a QMap, you can use an iterator. QMap provides both

   276     \l{Java-style iterators} (QMapIterator and QMutableMapIterator)

   277     and \l{STL-style iterators} (QMap::const_iterator and

   278     QMap::iterator). Here's how to iterate over a QMap<QString, int>

   279     using a Java-style iterator:

   280 

   281     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 7

   282 

   283     Here's the same code, but using an STL-style iterator this time:

   284 

   285     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 8

   286 

   287     The items are traversed in ascending key order.

   288 

   289     Normally, a QMap allows only one value per key. If you call

   290     insert() with a key that already exists in the QMap, the

   291     previous value will be erased. For example:

   292 

   293     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 9

   294 

   295     However, you can store multiple values per key by using

   296     insertMulti() instead of insert() (or using the convenience

   297     subclass QMultiMap). If you want to retrieve all the values for a

   298     single key, you can use values(const Key &key), which returns a

   299     QList<T>:

   300 

   301     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 10

   302 

   303     The items that share the same key are available from most

   304     recently to least recently inserted. Another approach is to call

   305     find() to get the STL-style iterator for the first item with a

   306     key and iterate from there:

   307 

   308     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 11

   309 

   310     If you only need to extract the values from a map (not the keys),

   311     you can also use \l{foreach}:

   312 

   313     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 12

   314 

   315     Items can be removed from the map in several ways. One way is to

   316     call remove(); this will remove any item with the given key.

   317     Another way is to use QMutableMapIterator::remove(). In addition,

   318     you can clear the entire map using clear().

   319 

   320     QMap's key and value data types must be \l{assignable data

   321     types}. This covers most data types you are likely to encounter,

   322     but the compiler won't let you, for example, store a QWidget as a

   323     value; instead, store a QWidget *. In addition, QMap's key type

   324     must provide operator<(). QMap uses it to keep its items sorted,

   325     and assumes that two keys \c x and \c y are equal if neither \c{x

   326     < y} nor \c{y < x} is true.

   327 

   328     Example:

   329     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 13

   330 

   331     In the example, we start by comparing the employees' names. If

   332     they're equal, we compare their dates of birth to break the tie.

   333 

   334     \sa QMapIterator, QMutableMapIterator, QHash, QSet

   335 */

   336 

   337 /*! \fn QMap::QMap()

   338 

   339     Constructs an empty map.

   340 

   341     \sa clear()

   342 */

   343 

   344 /*! \fn QMap::QMap(const QMap<Key, T> &other)

   345 

   346     Constructs a copy of \a other.

   347 

   348     This operation occurs in \l{constant time}, because QMap is

   349     \l{implicitly shared}. This makes returning a QMap from a

   350     function very fast. If a shared instance is modified, it will be

   351     copied (copy-on-write), and this takes \l{linear time}.

   352 

   353     \sa operator=()

   354 */

   355 

   356 /*! \fn QMap::QMap(const std::map<Key, T> & other)

   357 

   358     Constructs a copy of \a other.

   359 

   360     This function is only available if Qt is configured with STL

   361     compatibility enabled.

   362 

   363     \sa toStdMap()

   364 */

   365 

   366 /*! \fn std::map<Key, T> QMap::toStdMap() const

   367 

   368     Returns an STL map equivalent to this QMap.

   369 

   370     This function is only available if Qt is configured with STL

   371     compatibility enabled.

   372 */

   373 

   374 /*! \fn QMap::~QMap()

   375 

   376     Destroys the map. References to the values in the map, and all

   377     iterators over this map, become invalid.

   378 */

   379 

   380 /*! \fn QMap<Key, T> &QMap::operator=(const QMap<Key, T> &other)

   381 

   382     Assigns \a other to this map and returns a reference to this map.

   383 */

   384 

   385 /*! \fn bool QMap::operator==(const QMap<Key, T> &other) const

   386 

   387     Returns true if \a other is equal to this map; otherwise returns

   388     false.

   389 

   390     Two maps are considered equal if they contain the same (key,

   391     value) pairs.

   392 

   393     This function requires the value type to implement \c

   394     operator==().

   395 

   396     \sa operator!=()

   397 */

   398 

   399 /*! \fn bool QMap::operator!=(const QMap<Key, T> &other) const

   400 

   401     Returns true if \a other is not equal to this map; otherwise

   402     returns false.

   403 

   404     Two maps are considered equal if they contain the same (key,

   405     value) pairs.

   406 

   407     This function requires the value type to implement \c

   408     operator==().

   409 

   410     \sa operator==()

   411 */

   412 

   413 /*! \fn int QMap::size() const

   414 

   415     Returns the number of (key, value) pairs in the map.

   416 

   417     \sa isEmpty(), count()

   418 */

   419 

   420 /*!

   421     \fn bool QMap::isEmpty() const

   422 

   423     Returns true if the map contains no items; otherwise returns

   424     false.

   425 

   426     \sa size()

   427 */

   428 

   429 /*! \fn void QMap::detach()

   430 

   431     \internal

   432 

   433     Detaches this map from any other maps with which it may share

   434     data.

   435 

   436     \sa isDetached()

   437 */

   438 

   439 /*! \fn bool QMap::isDetached() const

   440 

   441     \internal

   442 

   443     Returns true if the map's internal data isn't shared with any

   444     other map object; otherwise returns false.

   445 

   446     \sa detach()

   447 */

   448 

   449 /*! \fn void QMap::setSharable(bool sharable)

   450 

   451     \internal

   452 */

   453 

   454 /*! \fn void QMap::setInsertInOrder(bool sharable)

   455 

   456     \internal

   457 */

   458 

   459 /*! \fn void QMap::clear()

   460 

   461     Removes all items from the map.

   462 

   463     \sa remove()

   464 */

   465 

   466 /*! \fn int QMap::remove(const Key &key)

   467 

   468     Removes all the items that have the key \a key from the map.

   469     Returns the number of items removed which is usually 1 but will be

   470     0 if the key isn't in the map, or \> 1 if insertMulti() has been

   471     used with the \a key.

   472 

   473     \sa clear(), take(), QMultiMap::remove()

   474 */

   475 

   476 /*! \fn T QMap::take(const Key &key)

   477 

   478     Removes the item with the key \a key from the map and returns

   479     the value associated with it.

   480 

   481     If the item does not exist in the map, the function simply

   482     returns a \l{default-constructed value}. If there are multiple

   483     items for \a key in the map, only the most recently inserted one

   484     is removed and returned.

   485 

   486     If you don't use the return value, remove() is more efficient.

   487 

   488     \sa remove()

   489 */

   490 

   491 /*! \fn bool QMap::contains(const Key &key) const

   492 

   493     Returns true if the map contains an item with key \a key;

   494     otherwise returns false.

   495 

   496     \sa count(), QMultiMap::contains()

   497 */

   498 

   499 /*! \fn const T QMap::value(const Key &key) const

   500 

   501     Returns the value associated with the key \a key.

   502 

   503     If the map contains no item with key \a key, the function

   504     returns a \l{default-constructed value}. If there are multiple

   505     items for \a key in the map, the value of the most recently

   506     inserted one is returned.

   507 

   508     \sa key(), values(), contains(), operator[]()

   509 */

   510 

   511 /*! \fn const T QMap::value(const Key &key, const T &defaultValue) const

   512 

   513     \overload

   514 

   515     If the map contains no item with key \a key, the function returns

   516     \a defaultValue.

   517 */

   518 

   519 /*! \fn T &QMap::operator[](const Key &key)

   520 

   521     Returns the value associated with the key \a key as a modifiable

   522     reference.

   523 

   524     If the map contains no item with key \a key, the function inserts

   525     a \l{default-constructed value} into the map with key \a key, and

   526     returns a reference to it. If the map contains multiple items

   527     with key \a key, this function returns a reference to the most

   528     recently inserted value.

   529 

   530     \sa insert(), value()

   531 */

   532 

   533 /*! \fn const T QMap::operator[](const Key &key) const

   534 

   535     \overload

   536 

   537     Same as value().

   538 */

   539 

   540 /*! \fn QList<Key> QMap::uniqueKeys() const

   541     \since 4.2

   542 

   543     Returns a list containing all the keys in the map in ascending

   544     order. Keys that occur multiple times in the map (because items

   545     were inserted with insertMulti(), or unite() was used) occur only

   546     once in the returned list.

   547 

   548     \sa keys(), values()

   549 */

   550 

   551 /*! \fn QList<Key> QMap::keys() const

   552 

   553     Returns a list containing all the keys in the map in ascending

   554     order. Keys that occur multiple times in the map (because items

   555     were inserted with insertMulti(), or unite() was used) also

   556     occur multiple times in the list.

   557 

   558     To obtain a list of unique keys, where each key from the map only

   559     occurs once, use uniqueKeys().

   560 

   561     The order is guaranteed to be the same as that used by values().

   562 

   563     \sa uniqueKeys(), values(), key()

   564 */

   565 

   566 /*! \fn QList<Key> QMap::keys(const T &value) const

   567 

   568     \overload

   569 

   570     Returns a list containing all the keys associated with value \a

   571     value in ascending order.

   572 

   573     This function can be slow (\l{linear time}), because QMap's

   574     internal data structure is optimized for fast lookup by key, not

   575     by value.

   576 */

   577 

   578 /*! \fn Key QMap::key(const T &value) const

   579 

   580     Returns the first key with value \a value.

   581 

   582     If the map contains no item with value \a value, the function

   583     returns a \link {default-constructed value} default-constructed

   584     key \endlink.

   585 

   586     This function can be slow (\l{linear time}), because QMap's

   587     internal data structure is optimized for fast lookup by key, not

   588     by value.

   589 

   590     \sa value(), keys()

   591 */

   592 

   593 /*!

   594     \fn Key QMap::key(const T &value, const Key &defaultKey) const

   595     \since 4.3

   596     \overload

   597 

   598     Returns the first key with value \a value, or \a defaultKey if

   599     the map contains no item with value \a value.

   600 

   601     This function can be slow (\l{linear time}), because QMap's

   602     internal data structure is optimized for fast lookup by key, not

   603     by value.

   604 */

   605 

   606 /*! \fn QList<T> QMap::values() const

   607 

   608     Returns a list containing all the values in the map, in ascending

   609     order of their keys. If a key is associated with multiple values,

   610     all of its values will be in the list, and not just the most

   611     recently inserted one.

   612 

   613     \sa keys(), value()

   614 */

   615 

   616 /*! \fn QList<T> QMap::values(const Key &key) const

   617 

   618     \overload

   619 

   620     Returns a list containing all the values associated with key

   621     \a key, from the most recently inserted to the least recently

   622     inserted one.

   623 

   624     \sa count(), insertMulti()

   625 */

   626 

   627 /*! \fn int QMap::count(const Key &key) const

   628 

   629     Returns the number of items associated with key \a key.

   630 

   631     \sa contains(), insertMulti(), QMultiMap::count()

   632 */

   633 

   634 /*! \fn int QMap::count() const

   635 

   636     \overload

   637 

   638     Same as size().

   639 */

   640 

   641 /*! \fn QMap::iterator QMap::begin()

   642 

   643     Returns an \l{STL-style iterator} pointing to the first item in

   644     the map.

   645 

   646     \sa constBegin(), end()

   647 */

   648 

   649 /*! \fn QMap::const_iterator QMap::begin() const

   650 

   651     \overload

   652 */

   653 

   654 /*! \fn QMap::const_iterator QMap::constBegin() const

   655 

   656     Returns a const \l{STL-style iterator} pointing to the first item

   657     in the map.

   658 

   659     \sa begin(), constEnd()

   660 */

   661 

   662 /*! \fn QMap::iterator QMap::end()

   663 

   664     Returns an \l{STL-style iterator} pointing to the imaginary item

   665     after the last item in the map.

   666 

   667     \sa begin(), constEnd()

   668 */

   669 

   670 /*! \fn QMap::const_iterator QMap::end() const

   671 

   672     \overload

   673 */

   674 

   675 /*! \fn QMap::const_iterator QMap::constEnd() const

   676 

   677     Returns a const \l{STL-style iterator} pointing to the imaginary

   678     item after the last item in the map.

   679 

   680     \sa constBegin(), end()

   681 */

   682 

   683 /*! \fn QMap::iterator QMap::erase(iterator pos)

   684 

   685     Removes the (key, value) pair pointed to by the iterator \a pos

   686     from the map, and returns an iterator to the next item in the

   687     map.

   688 

   689     \sa remove()

   690 */

   691 

   692 /*! \fn QMap::iterator QMap::find(const Key &key)

   693 

   694     Returns an iterator pointing to the item with key \a key in the

   695     map.

   696 

   697     If the map contains no item with key \a key, the function

   698     returns end().

   699 

   700     If the map contains multiple items with key \a key, this

   701     function returns an iterator that points to the most recently

   702     inserted value. The other values are accessible by incrementing

   703     the iterator. For example, here's some code that iterates over all

   704     the items with the same key:

   705 

   706     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 14

   707 

   708     \sa constFind(), value(), values(), lowerBound(), upperBound(), QMultiMap::find()

   709 */

   710 

   711 /*! \fn QMap::const_iterator QMap::find(const Key &key) const

   712 

   713     \overload

   714 */

   715 

   716 /*! \fn QMap::iterator QMap::constFind(const Key &key) const

   717     \since 4.1

   718 

   719     Returns an const iterator pointing to the item with key \a key in the

   720     map.

   721 

   722     If the map contains no item with key \a key, the function

   723     returns constEnd().

   724 

   725     \sa find(), QMultiMap::constFind()

   726 */

   727 

   728 /*! \fn QMap::iterator QMap::lowerBound(const Key &key)

   729 

   730     Returns an iterator pointing to the first item with key \a key in

   731     the map. If the map contains no item with key \a key, the

   732     function returns an iterator to the nearest item with a greater

   733     key.

   734 

   735     Example:

   736     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 15

   737 

   738     If the map contains multiple items with key \a key, this

   739     function returns an iterator that points to the most recently

   740     inserted value. The other values are accessible by incrementing

   741     the iterator. For example, here's some code that iterates over all

   742     the items with the same key:

   743 

   744     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 16

   745 

   746     \sa qLowerBound(), upperBound(), find()

   747 */

   748 

   749 /*! \fn QMap::const_iterator QMap::lowerBound(const Key &key) const

   750 

   751     \overload

   752 */

   753 

   754 /*! \fn QMap::iterator QMap::upperBound(const Key &key)

   755 

   756     Returns an iterator pointing to the item that immediately follows

   757     the last item with key \a key in the map. If the map contains no

   758     item with key \a key, the function returns an iterator to the

   759     nearest item with a greater key.

   760 

   761     Example:

   762     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 17

   763 

   764     \sa qUpperBound(), lowerBound(), find()

   765 */

   766 

   767 /*! \fn QMap::const_iterator QMap::upperBound(const Key &key) const

   768 

   769     \overload

   770 */

   771 

   772 /*! \fn QMap::iterator QMap::insert(const Key &key, const T &value)

   773 

   774     Inserts a new item with the key \a key and a value of \a value.

   775 

   776     If there is already an item with the key \a key, that item's value

   777     is replaced with \a value.

   778 

   779     If there are multiple items with the key \a key, the most

   780     recently inserted item's value is replaced with \a value.

   781 

   782     \sa insertMulti()

   783 */

   784 

   785 /*! \fn QMap::iterator QMap::insertMulti(const Key &key, const T &value)

   786 

   787     Inserts a new item with the key \a key and a value of \a value.

   788 

   789     If there is already an item with the same key in the map, this

   790     function will simply create a new one. (This behavior is

   791     different from insert(), which overwrites the value of an

   792     existing item.)

   793 

   794     \sa insert(), values()

   795 */

   796 

   797 /*! \fn QMap<Key, T> &QMap::unite(const QMap<Key, T> &other)

   798 

   799     Inserts all the items in the \a other map into this map. If a

   800     key is common to both maps, the resulting map will contain the

   801     key multiple times.

   802 

   803     \sa insertMulti()

   804 */

   805 

   806 /*! \typedef QMap::Iterator

   807 

   808     Qt-style synonym for QMap::iterator.

   809 */

   810 

   811 /*! \typedef QMap::ConstIterator

   812 

   813     Qt-style synonym for QMap::const_iterator.

   814 */

   815 

   816 /*! \typedef QMap::difference_type

   817 

   818     Typedef for ptrdiff_t. Provided for STL compatibility.

   819 */

   820 

   821 /*! \typedef QMap::key_type

   822 

   823     Typedef for Key. Provided for STL compatibility.

   824 */

   825 

   826 /*! \typedef QMap::mapped_type

   827 

   828     Typedef for T. Provided for STL compatibility.

   829 */

   830 

   831 /*! \typedef QMap::size_type

   832 

   833     Typedef for int. Provided for STL compatibility.

   834 */

   835 

   836 /*!

   837     \fn bool QMap::empty() const

   838 

   839     This function is provided for STL compatibility. It is equivalent

   840     to isEmpty(), returning true if the map is empty; otherwise

   841     returning false.

   842 */

   843 

   844 /*! \class QMap::iterator

   845     \brief The QMap::iterator class provides an STL-style non-const iterator for QMap and QMultiMap.

   846 

   847     QMap features both \l{STL-style iterators} and \l{Java-style

   848     iterators}. The STL-style iterators are more low-level and more

   849     cumbersome to use; on the other hand, they are slightly faster

   850     and, for developers who already know STL, have the advantage of

   851     familiarity.

   852 

   853     QMap\<Key, T\>::iterator allows you to iterate over a QMap (or

   854     QMultiMap) and to modify the value (but not the key) stored under

   855     a particular key. If you want to iterate over a const QMap, you

   856     should use QMap::const_iterator. It is generally good practice to

   857     use QMap::const_iterator on a non-const QMap as well, unless you

   858     need to change the QMap through the iterator. Const iterators are

   859     slightly faster, and can improve code readability.

   860 

   861     The default QMap::iterator constructor creates an uninitialized

   862     iterator. You must initialize it using a QMap function like

   863     QMap::begin(), QMap::end(), or QMap::find() before you can

   864     start iterating. Here's a typical loop that prints all the (key,

   865     value) pairs stored in a map:

   866 

   867     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 18

   868 

   869     Unlike QHash, which stores its items in an arbitrary order, QMap

   870     stores its items ordered by key. Items that share the same key

   871     (because they were inserted using QMap::insertMulti(), or due to a

   872     unite()) will appear consecutively, from the most recently to the

   873     least recently inserted value.

   874 

   875     Let's see a few examples of things we can do with a

   876     QMap::iterator that we cannot do with a QMap::const_iterator.

   877     Here's an example that increments every value stored in the QMap

   878     by 2:

   879 

   880     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 19

   881 

   882     Here's an example that removes all the items whose key is a

   883     string that starts with an underscore character:

   884 

   885     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 20

   886 

   887     The call to QMap::erase() removes the item pointed to by the

   888     iterator from the map, and returns an iterator to the next item.

   889     Here's another way of removing an item while iterating:

   890 

   891     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 21

   892 

   893     It might be tempting to write code like this:

   894 

   895     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 22

   896 

   897     However, this will potentially crash in \c{++i}, because \c i is

   898     a dangling iterator after the call to erase().

   899 

   900     Multiple iterators can be used on the same map. If you add items

   901     to the map, existing iterators will remain valid. If you remove

   902     items from the map, iterators that point to the removed items

   903     will become dangling iterators.

   904 

   905     \sa QMap::const_iterator, QMutableMapIterator

   906 */

   907 

   908 /*! \fn QMap::iterator::operator QMapData::Node *() const

   909 

   910     \internal

   911 */

   912 

   913 /*! \typedef QMap::iterator::difference_type

   914 

   915     \internal

   916 */

   917 

   918 /*! \typedef QMap::iterator::iterator_category

   919 

   920   A synonym for \e {std::bidirectional_iterator_tag} indicating

   921   this iterator is a bidirectional iterator.

   922 */

   923 

   924 /*! \typedef QMap::iterator::pointer

   925 

   926     \internal

   927 */

   928 

   929 /*! \typedef QMap::iterator::reference

   930 

   931     \internal

   932 */

   933 

   934 /*! \typedef QMap::iterator::value_type

   935 

   936     \internal

   937 */

   938 

   939 /*! \fn QMap::iterator::iterator()

   940 

   941     Constructs an uninitialized iterator.

   942 

   943     Functions like key(), value(), and operator++() must not be

   944     called on an uninitialized iterator. Use operator=() to assign a

   945     value to it before using it.

   946 

   947     \sa QMap::begin() QMap::end()

   948 */

   949 

   950 /*! \fn QMap::iterator::iterator(QMapData::Node *node)

   951 

   952     \internal

   953 */

   954 

   955 /*! \fn const Key &QMap::iterator::key() const

   956 

   957     Returns the current item's key as a const reference.

   958 

   959     There is no direct way of changing an item's key through an

   960     iterator, although it can be done by calling QMap::erase()

   961     followed by QMap::insert() or QMap::insertMulti().

   962 

   963     \sa value()

   964 */

   965 

   966 /*! \fn T &QMap::iterator::value() const

   967 

   968     Returns a modifiable reference to the current item's value.

   969 

   970     You can change the value of an item by using value() on

   971     the left side of an assignment, for example:

   972 

   973     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 23

   974 

   975     \sa key(), operator*()

   976 */

   977 

   978 /*! \fn T &QMap::iterator::operator*() const

   979 

   980     Returns a modifiable reference to the current item's value.

   981 

   982     Same as value().

   983 

   984     \sa key()

   985 */

   986 

   987 /*! \fn T *QMap::iterator::operator->() const

   988 

   989     Returns a pointer to the current item's value.

   990 

   991     \sa value()

   992 */

   993 

   994 /*!

   995     \fn bool QMap::iterator::operator==(const iterator &other) const

   996     \fn bool QMap::iterator::operator==(const const_iterator &other) const

   997 

   998     Returns true if \a other points to the same item as this

   999     iterator; otherwise returns false.

  1000 

  1001     \sa operator!=()

  1002 */

  1003 

  1004 /*!

  1005     \fn bool QMap::iterator::operator!=(const iterator &other) const

  1006     \fn bool QMap::iterator::operator!=(const const_iterator &other) const

  1007 

  1008     Returns true if \a other points to a different item than this

  1009     iterator; otherwise returns false.

  1010 

  1011     \sa operator==()

  1012 */

  1013 

  1014 /*! \fn QMap::iterator QMap::iterator::operator++()

  1015 

  1016     The prefix ++ operator (\c{++i}) advances the iterator to the

  1017     next item in the map and returns an iterator to the new current

  1018     item.

  1019 

  1020     Calling this function on QMap::end() leads to undefined results.

  1021 

  1022     \sa operator--()

  1023 */

  1024 

  1025 /*! \fn QMap::iterator QMap::iterator::operator++(int)

  1026 

  1027     \overload

  1028 

  1029     The postfix ++ operator (\c{i++}) advances the iterator to the

  1030     next item in the map and returns an iterator to the previously

  1031     current item.

  1032 */

  1033 

  1034 /*! \fn QMap::iterator QMap::iterator::operator--()

  1035 

  1036     The prefix -- operator (\c{--i}) makes the preceding item

  1037     current and returns an iterator pointing to the new current item.

  1038 

  1039     Calling this function on QMap::begin() leads to undefined

  1040     results.

  1041 

  1042     \sa operator++()

  1043 */

  1044 

  1045 /*! \fn QMap::iterator QMap::iterator::operator--(int)

  1046 

  1047     \overload

  1048 

  1049     The prefix -- operator (\c{--i}) makes the preceding item

  1050     current and returns an iterator pointing to the previously

  1051     current item.

  1052 */

  1053 

  1054 /*! \fn QMap::iterator QMap::iterator::operator+(int j) const

  1055 

  1056     Returns an iterator to the item at \a j positions forward from

  1057     this iterator. (If \a j is negative, the iterator goes backward.)

  1058 

  1059     This operation can be slow for large \a j values.

  1060 

  1061     \sa operator-()

  1062 

  1063 */

  1064 

  1065 /*! \fn QMap::iterator QMap::iterator::operator-(int j) const

  1066 

  1067     Returns an iterator to the item at \a j positions backward from

  1068     this iterator. (If \a j is negative, the iterator goes forward.)

  1069 

  1070     This operation can be slow for large \a j values.

  1071 

  1072     \sa operator+()

  1073 */

  1074 

  1075 /*! \fn QMap::iterator &QMap::iterator::operator+=(int j)

  1076 

  1077     Advances the iterator by \a j items. (If \a j is negative, the

  1078     iterator goes backward.)

  1079 

  1080     \sa operator-=(), operator+()

  1081 */

  1082 

  1083 /*! \fn QMap::iterator &QMap::iterator::operator-=(int j)

  1084 

  1085     Makes the iterator go back by \a j items. (If \a j is negative,

  1086     the iterator goes forward.)

  1087 

  1088     \sa operator+=(), operator-()

  1089 */

  1090 

  1091 /*! \class QMap::const_iterator

  1092     \brief The QMap::const_iterator class provides an STL-style const iterator for QMap and QMultiMap.

  1093 

  1094     QMap features both \l{STL-style iterators} and \l{Java-style

  1095     iterators}. The STL-style iterators are more low-level and more

  1096     cumbersome to use; on the other hand, they are slightly faster

  1097     and, for developers who already know STL, have the advantage of

  1098     familiarity.

  1099 

  1100     QMap\<Key, T\>::const_iterator allows you to iterate over a QMap

  1101     (or a QMultiMap). If you want to modify the QMap as you iterate

  1102     over it, you must use QMap::iterator instead. It is generally

  1103     good practice to use QMap::const_iterator on a non-const QMap as

  1104     well, unless you need to change the QMap through the iterator.

  1105     Const iterators are slightly faster, and can improve code

  1106     readability.

  1107 

  1108     The default QMap::const_iterator constructor creates an

  1109     uninitialized iterator. You must initialize it using a QMap

  1110     function like QMap::constBegin(), QMap::constEnd(), or

  1111     QMap::find() before you can start iterating. Here's a typical

  1112     loop that prints all the (key, value) pairs stored in a map:

  1113 

  1114     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 24

  1115 

  1116     Unlike QHash, which stores its items in an arbitrary order, QMap

  1117     stores its items ordered by key. Items that share the same key

  1118     (because they were inserted using QMap::insertMulti()) will

  1119     appear consecutively, from the most recently to the least

  1120     recently inserted value.

  1121 

  1122     Multiple iterators can be used on the same map. If you add items

  1123     to the map, existing iterators will remain valid. If you remove

  1124     items from the map, iterators that point to the removed items

  1125     will become dangling iterators.

  1126 

  1127     \sa QMap::iterator, QMapIterator

  1128 */

  1129 

  1130 /*! \fn QMap::const_iterator::operator QMapData::Node *() const

  1131 

  1132     \internal

  1133 */

  1134