src/corelib/tools/qmap.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtCore module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  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 const QMapDataBase QMapDataBase::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, { 0, 0, 0 } };
  54
  55 const QMapNodeBase *QMapNodeBase::nextNode() const
  56 {
  57     const QMapNodeBase *n = this;
  58     if (n->right) {
  59         n = n->right;
  60         while (n->left)
  61             n = n->left;
  62     } else {
  63         const QMapNodeBase *y = n->parent();
  64         while (y && n == y->right) {
  65             n = y;
  66             y = n->parent();
  67         }
  68         n = y;
  69     }
  70     return n;
  71 }
  72
  73 const QMapNodeBase *QMapNodeBase::previousNode() const
  74 {
  75     const QMapNodeBase *n = this;
  76     if (n->left) {
  77         n = n->left;
  78         while (n->right)
  79             n = n->right;
  80     } else {
  81         const QMapNodeBase *y = n->parent();
  82         while (y && n == y->left) {
  83             n = y;
  84             y = n->parent();
  85         }
  86         n = y;
  87     }
  88     return n;
  89 }
  90
  91
  92 void QMapDataBase::rotateLeft(QMapNodeBase *x)
  93 {
  94     QMapNodeBase *&root = header.left;
  95     QMapNodeBase *y = x->right;
  96     x->right = y->left;
  97     if (y->left != 0)
  98         y->left->setParent(x);
  99     y->setParent(x->parent());
 100     if (x == root)
 101         root = y;
 102     else if (x == x->parent()->left)
 103         x->parent()->left = y;
 104     else
 105         x->parent()->right = y;
 106     y->left = x;
 107     x->setParent(y);
 108 }
 109
 110
 111 void QMapDataBase::rotateRight(QMapNodeBase *x)
 112 {
 113     QMapNodeBase *&root = header.left;
 114     QMapNodeBase *y = x->left;
 115     x->left = y->right;
 116     if (y->right != 0)
 117         y->right->setParent(x);
 118     y->setParent(x->parent());
 119     if (x == root)
 120         root = y;
 121     else if (x == x->parent()->right)
 122         x->parent()->right = y;
 123     else
 124         x->parent()->left = y;
 125     y->right = x;
 126     x->setParent(y);
 127 }
 128
 129
 130 void QMapDataBase::rebalance(QMapNodeBase *x)
 131 {
 132     QMapNodeBase *&root = header.left;
 133     x->setColor(QMapNodeBase::Red);
 134     while (x != root && x->parent()->color() == QMapNodeBase::Red) {
 135         if (x->parent() == x->parent()->parent()->left) {
 136             QMapNodeBase *y = x->parent()->parent()->right;
 137             if (y && y->color() == QMapNodeBase::Red) {
 138                 x->parent()->setColor(QMapNodeBase::Black);
 139                 y->setColor(QMapNodeBase::Black);
 140                 x->parent()->parent()->setColor(QMapNodeBase::Red);
 141                 x = x->parent()->parent();
 142             } else {
 143                 if (x == x->parent()->right) {
 144                     x = x->parent();
 145                     rotateLeft(x);
 146                 }
 147                 x->parent()->setColor(QMapNodeBase::Black);
 148                 x->parent()->parent()->setColor(QMapNodeBase::Red);
 149                 rotateRight (x->parent()->parent());
 150             }
 151         } else {
 152             QMapNodeBase *y = x->parent()->parent()->left;
 153             if (y && y->color() == QMapNodeBase::Red) {
 154                 x->parent()->setColor(QMapNodeBase::Black);
 155                 y->setColor(QMapNodeBase::Black);
 156                 x->parent()->parent()->setColor(QMapNodeBase::Red);
 157                 x = x->parent()->parent();
 158             } else {
 159                 if (x == x->parent()->left) {
 160                     x = x->parent();
 161                     rotateRight(x);
 162                 }
 163                 x->parent()->setColor(QMapNodeBase::Black);
 164                 x->parent()->parent()->setColor(QMapNodeBase::Red);
 165                 rotateLeft(x->parent()->parent());
 166             }
 167         }
 168     }
 169     root->setColor(QMapNodeBase::Black);
 170 }
 171
 172 void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z)
 173 {
 174     QMapNodeBase *&root = header.left;
 175     QMapNodeBase *y = z;
 176     QMapNodeBase *x;
 177     QMapNodeBase *x_parent;
 178     if (y->left == 0) {
 179         x = y->right;
 180     } else {
 181         if (y->right == 0) {
 182             x = y->left;
 183         } else {
 184             y = y->right;
 185             while (y->left != 0)
 186                 y = y->left;
 187             x = y->right;
 188         }
 189     }
 190     if (y != z) {
 191         z->left->setParent(y);
 192         y->left = z->left;
 193         if (y != z->right) {
 194             x_parent = y->parent();
 195             if (x)
 196                 x->setParent(y->parent());
 197             y->parent()->left = x;
 198             y->right = z->right;
 199             z->right->setParent(y);
 200         } else {
 201             x_parent = y;
 202         }
 203         if (root == z)
 204             root = y;
 205         else if (z->parent()->left == z)
 206             z->parent()->left = y;
 207         else
 208             z->parent()->right = y;
 209         y->setParent(z->parent());
 210         // Swap the colors
 211         QMapNodeBase::Color c = y->color();
 212         y->setColor(z->color());
 213         z->setColor(c);
 214         y = z;
 215     } else {
 216         x_parent = y->parent();
 217         if (x)
 218             x->setParent(y->parent());
 219         if (root == z)
 220             root = x;
 221         else if (z->parent()->left == z)
 222             z->parent()->left = x;
 223         else
 224             z->parent()->right = x;
 225     }
 226     if (y->color() != QMapNodeBase::Red) {
 227         while (x != root && (x == 0 || x->color() == QMapNodeBase::Black)) {
 228             if (x == x_parent->left) {
 229                 QMapNodeBase *w = x_parent->right;
 230                 if (w->color() == QMapNodeBase::Red) {
 231                     w->setColor(QMapNodeBase::Black);
 232                     x_parent->setColor(QMapNodeBase::Red);
 233                     rotateLeft(x_parent);
 234                     w = x_parent->right;
 235                 }
 236                 if ((w->left == 0 || w->left->color() == QMapNodeBase::Black) &&
 237                     (w->right == 0 || w->right->color() == QMapNodeBase::Black)) {
 238                     w->setColor(QMapNodeBase::Red);
 239                     x = x_parent;
 240                     x_parent = x_parent->parent();
 241                 } else {
 242                     if (w->right == 0 || w->right->color() == QMapNodeBase::Black) {
 243                         if (w->left)
 244                             w->left->setColor(QMapNodeBase::Black);
 245                         w->setColor(QMapNodeBase::Red);
 246                         rotateRight(w);
 247                         w = x_parent->right;
 248                     }
 249                     w->setColor(x_parent->color());
 250                     x_parent->setColor(QMapNodeBase::Black);
 251                     if (w->right)
 252                         w->right->setColor(QMapNodeBase::Black);
 253                     rotateLeft(x_parent);
 254                     break;
 255                 }
 256             } else {
 257             QMapNodeBase *w = x_parent->left;
 258             if (w->color() == QMapNodeBase::Red) {
 259                 w->setColor(QMapNodeBase::Black);
 260                 x_parent->setColor(QMapNodeBase::Red);
 261                 rotateRight(x_parent);
 262                 w = x_parent->left;
 263             }
 264             if ((w->right == 0 || w->right->color() == QMapNodeBase::Black) &&
 265                 (w->left == 0 || w->left->color() == QMapNodeBase::Black)) {
 266                 w->setColor(QMapNodeBase::Red);
 267                 x = x_parent;
 268                 x_parent = x_parent->parent();
 269             } else {
 270                 if (w->left == 0 || w->left->color() == QMapNodeBase::Black) {
 271                     if (w->right)
 272                         w->right->setColor(QMapNodeBase::Black);
 273                     w->setColor(QMapNodeBase::Red);
 274                     rotateLeft(w);
 275                     w = x_parent->left;
 276                 }
 277                 w->setColor(x_parent->color());
 278                 x_parent->setColor(QMapNodeBase::Black);
 279                 if (w->left)
 280                     w->left->setColor(QMapNodeBase::Black);
 281                 rotateRight(x_parent);
 282                 break;
 283             }
 284         }
 285     }
 286     if (x)
 287         x->setColor(QMapNodeBase::Black);
 288     }
 289     free(y);
 290     --size;
 291 }
 292
 293 static inline int qMapAlignmentThreshold()
 294 {
 295     // malloc on 32-bit platforms should return pointers that are 8-byte
 296     // aligned or more while on 64-bit platforms they should be 16-byte aligned
 297     // or more
 298     return 2 * sizeof(void*);
 299 }
 300
 301 static inline void *qMapAllocate(int alloc, int alignment)
 302 {
 303     return alignment > qMapAlignmentThreshold()
 304         ? qMallocAligned(alloc, alignment)
 305         : ::malloc(alloc);
 306 }
 307
 308 static inline void qMapDeallocate(QMapNodeBase *node, int alignment)
 309 {
 310     if (alignment > qMapAlignmentThreshold())
 311         qFreeAligned(node);
 312     else
 313         ::free(node);
 314 }
 315
 316 QMapNodeBase *QMapDataBase::createNode(int alloc, int alignment, QMapNodeBase *parent, bool left)
 317 {
 318     QMapNodeBase *node = static_cast<QMapNodeBase *>(qMapAllocate(alloc, alignment));
 319     Q_CHECK_PTR(node);
 320
 321     memset(node, 0, alloc);
 322     ++size;
 323
 324     if (parent) {
 325         if (left) {
 326             parent->left = node;
 327         } else {
 328             parent->right = node;
 329         }
 330         node->setParent(parent);
 331         rebalance(node);
 332     }
 333     return node;
 334 }
 335
 336 void QMapDataBase::freeTree(QMapNodeBase *root, int alignment)
 337 {
 338     if (root->left)
 339         freeTree(root->left, alignment);
 340     if (root->right)
 341         freeTree(root->right, alignment);
 342     qMapDeallocate(root, alignment);
 343 }
 344
 345 QMapDataBase *QMapDataBase::createData()
 346 {
 347     QMapDataBase *d = new QMapDataBase;
 348
 349     d->ref.initializeOwned();
 350     d->size = 0;
 351
 352     d->header.p = 0;
 353     d->header.left = 0;
 354     d->header.right = 0;
 355
 356     return d;
 357 }
 358
 359 void QMapDataBase::freeData(QMapDataBase *d)
 360 {
 361     delete d;
 362 }
 363
 364 /*!
 365     \class QMap
 366     \brief The QMap class is a template class that provides a skip-list-based dictionary.
 367
 368     \ingroup tools
 369     \ingroup shared
 370
 371     \reentrant
 372
 373     QMap\<Key, T\> is one of Qt's generic \l{container classes}. It
 374     stores (key, value) pairs and provides fast lookup of the
 375     value associated with a key.
 376
 377     QMap and QHash provide very similar functionality. The
 378     differences are:
 379
 380     \list
 381     \li QHash provides faster lookups than QMap. (See \l{Algorithmic
 382        Complexity} for details.)
 383     \li When iterating over a QHash, the items are arbitrarily ordered.
 384        With QMap, the items are always sorted by key.
 385     \li The key type of a QHash must provide operator==() and a global
 386        qHash(Key) function. The key type of a QMap must provide
 387        operator<() specifying a total order.
 388     \endlist
 389
 390     Here's an example QMap with QString keys and \c int values:
 391     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 0
 392
 393     To insert a (key, value) pair into the map, you can use operator[]():
 394
 395     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 1
 396
 397     This inserts the following three (key, value) pairs into the
 398     QMap: ("one", 1), ("three", 3), and ("seven", 7). Another way to
 399     insert items into the map is to use insert():
 400
 401     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 2
 402
 403     To look up a value, use operator[]() or value():
 404
 405     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 3
 406
 407     If there is no item with the specified key in the map, these
 408     functions return a \l{default-constructed value}.
 409
 410     If you want to check whether the map contains a certain key, use
 411     contains():
 412
 413     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 4
 414
 415     There is also a value() overload that uses its second argument as
 416     a default value if there is no item with the specified key:
 417
 418     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 5
 419
 420     In general, we recommend that you use contains() and value()
 421     rather than operator[]() for looking up a key in a map. The
 422     reason is that operator[]() silently inserts an item into the
 423     map if no item exists with the same key (unless the map is
 424     const). For example, the following code snippet will create 1000
 425     items in memory:
 426
 427     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 6
 428
 429     To avoid this problem, replace \c map[i] with \c map.value(i)
 430     in the code above.
 431
 432     If you want to navigate through all the (key, value) pairs stored
 433     in a QMap, you can use an iterator. QMap provides both
 434     \l{Java-style iterators} (QMapIterator and QMutableMapIterator)
 435     and \l{STL-style iterators} (QMap::const_iterator and
 436     QMap::iterator). Here's how to iterate over a QMap<QString, int>
 437     using a Java-style iterator:
 438
 439     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 7
 440
 441     Here's the same code, but using an STL-style iterator this time:
 442
 443     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 8
 444
 445     The items are traversed in ascending key order.
 446
 447     Normally, a QMap allows only one value per key. If you call
 448     insert() with a key that already exists in the QMap, the
 449     previous value will be erased. For example:
 450
 451     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 9
 452
 453     However, you can store multiple values per key by using
 454     insertMulti() instead of insert() (or using the convenience
 455     subclass QMultiMap). If you want to retrieve all the values for a
 456     single key, you can use values(const Key &key), which returns a
 457     QList<T>:
 458
 459     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 10
 460
 461     The items that share the same key are available from most
 462     recently to least recently inserted. Another approach is to call
 463     find() to get the STL-style iterator for the first item with a
 464     key and iterate from there:
 465
 466     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 11
 467
 468     If you only need to extract the values from a map (not the keys),
 469     you can also use \l{foreach}:
 470
 471     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 12
 472
 473     Items can be removed from the map in several ways. One way is to
 474     call remove(); this will remove any item with the given key.
 475     Another way is to use QMutableMapIterator::remove(). In addition,
 476     you can clear the entire map using clear().
 477
 478     QMap's key and value data types must be \l{assignable data
 479     types}. This covers most data types you are likely to encounter,
 480     but the compiler won't let you, for example, store a QWidget as a
 481     value; instead, store a QWidget *. In addition, QMap's key type
 482     must provide operator<(). QMap uses it to keep its items sorted,
 483     and assumes that two keys \c x and \c y are equal if neither \c{x
 484     < y} nor \c{y < x} is true.
 485
 486     Example:
 487     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 13
 488
 489     In the example, we start by comparing the employees' names. If
 490     they're equal, we compare their dates of birth to break the tie.
 491
 492     \sa QMapIterator, QMutableMapIterator, QHash, QSet
 493 */
 494
 495 /*! \fn QMap::QMap()
 496
 497     Constructs an empty map.
 498
 499     \sa clear()
 500 */
 501
 502 /*! \fn QMap::QMap(const QMap<Key, T> &other)
 503
 504     Constructs a copy of \a other.
 505
 506     This operation occurs in \l{constant time}, because QMap is
 507     \l{implicitly shared}. This makes returning a QMap from a
 508     function very fast. If a shared instance is modified, it will be
 509     copied (copy-on-write), and this takes \l{linear time}.
 510
 511     \sa operator=()
 512 */
 513
 514 /*! \fn QMap::QMap(const std::map<Key, T> & other)
 515
 516     Constructs a copy of \a other.
 517
 518     This function is only available if Qt is configured with STL
 519     compatibility enabled.
 520
 521     \sa toStdMap()
 522 */
 523
 524 /*! \fn std::map<Key, T> QMap::toStdMap() const
 525
 526     Returns an STL map equivalent to this QMap.
 527
 528     This function is only available if Qt is configured with STL
 529     compatibility enabled.
 530 */
 531
 532 /*! \fn QMap::~QMap()
 533
 534     Destroys the map. References to the values in the map, and all
 535     iterators over this map, become invalid.
 536 */
 537
 538 /*! \fn QMap<Key, T> &QMap::operator=(const QMap<Key, T> &other)
 539
 540     Assigns \a other to this map and returns a reference to this map.
 541 */
 542
 543 /*! \fn void QMap::swap(QMap<Key, T> &other)
 544     \since 4.8
 545
 546     Swaps map \a other with this map. This operation is very
 547     fast and never fails.
 548 */
 549
 550 /*! \fn void QMultiMap::swap(QMultiMap<Key, T> &other)
 551     \since 4.8
 552
 553     Swaps map \a other with this map. This operation is very
 554     fast and never fails.
 555 */
 556
 557 /*! \fn bool QMap::operator==(const QMap<Key, T> &other) const
 558
 559     Returns true if \a other is equal to this map; otherwise returns
 560     false.
 561
 562     Two maps are considered equal if they contain the same (key,
 563     value) pairs.
 564
 565     This function requires the value type to implement \c
 566     operator==().
 567
 568     \sa operator!=()
 569 */
 570
 571 /*! \fn bool QMap::operator!=(const QMap<Key, T> &other) const
 572
 573     Returns true if \a other is not equal to this map; otherwise
 574     returns false.
 575
 576     Two maps are considered equal if they contain the same (key,
 577     value) pairs.
 578
 579     This function requires the value type to implement \c
 580     operator==().
 581
 582     \sa operator==()
 583 */
 584
 585 /*! \fn int QMap::size() const
 586
 587     Returns the number of (key, value) pairs in the map.
 588
 589     \sa isEmpty(), count()
 590 */
 591
 592 /*!
 593     \fn bool QMap::isEmpty() const
 594
 595     Returns true if the map contains no items; otherwise returns
 596     false.
 597
 598     \sa size()
 599 */
 600
 601 /*! \fn void QMap::detach()
 602
 603     \internal
 604
 605     Detaches this map from any other maps with which it may share
 606     data.
 607
 608     \sa isDetached()
 609 */
 610
 611 /*! \fn bool QMap::isDetached() const
 612
 613     \internal
 614
 615     Returns true if the map's internal data isn't shared with any
 616     other map object; otherwise returns false.
 617
 618     \sa detach()
 619 */
 620
 621 /*! \fn void QMap::setSharable(bool sharable)
 622
 623     \internal
 624 */
 625
 626 /*! \fn bool QMap::isSharedWith(const QMap<Key, T> &other) const
 627
 628     \internal
 629 */
 630
 631 /*! \fn void QMap::clear()
 632
 633     Removes all items from the map.
 634
 635     \sa remove()
 636 */
 637
 638 /*! \fn int QMap::remove(const Key &key)
 639
 640     Removes all the items that have the key \a key from the map.
 641     Returns the number of items removed which is usually 1 but will be
 642     0 if the key isn't in the map, or \> 1 if insertMulti() has been
 643     used with the \a key.
 644
 645     \sa clear(), take(), QMultiMap::remove()
 646 */
 647
 648 /*! \fn T QMap::take(const Key &key)
 649
 650     Removes the item with the key \a key from the map and returns
 651     the value associated with it.
 652
 653     If the item does not exist in the map, the function simply
 654     returns a \l{default-constructed value}. If there are multiple
 655     items for \a key in the map, only the most recently inserted one
 656     is removed and returned.
 657
 658     If you don't use the return value, remove() is more efficient.
 659
 660     \sa remove()
 661 */
 662
 663 /*! \fn bool QMap::contains(const Key &key) const
 664
 665     Returns true if the map contains an item with key \a key;
 666     otherwise returns false.
 667
 668     \sa count(), QMultiMap::contains()
 669 */
 670
 671 /*! \fn const T QMap::value(const Key &key) const
 672
 673 */
 674
 675 /*! \fn const T QMap::value(const Key &key, const T &defaultValue) const
 676
 677     \overload
 678
 679     Returns the value associated with the key \a key.
 680
 681     If the map contains no item with key \a key, the function returns
 682     \a defaultValue. If no \a defaultValue is specified, the function
 683     returns a \l{default-constructed value}. If there are multiple
 684     items for \a key in the map, the value of the most recently
 685     inserted one is returned.
 686
 687     \sa key(), values(), contains(), operator[]()
 688 */
 689
 690 /*! \fn T &QMap::operator[](const Key &key)
 691
 692     Returns the value associated with the key \a key as a modifiable
 693     reference.
 694
 695     If the map contains no item with key \a key, the function inserts
 696     a \l{default-constructed value} into the map with key \a key, and
 697     returns a reference to it. If the map contains multiple items
 698     with key \a key, this function returns a reference to the most
 699     recently inserted value.
 700
 701     \sa insert(), value()
 702 */
 703
 704 /*! \fn const T QMap::operator[](const Key &key) const
 705
 706     \overload
 707
 708     Same as value().
 709 */
 710
 711 /*! \fn QList<Key> QMap::uniqueKeys() const
 712     \since 4.2
 713
 714     Returns a list containing all the keys in the map in ascending
 715     order. Keys that occur multiple times in the map (because items
 716     were inserted with insertMulti(), or unite() was used) occur only
 717     once in the returned list.
 718
 719     \sa keys(), values()
 720 */
 721
 722 /*! \fn QList<Key> QMap::keys() const
 723
 724     Returns a list containing all the keys in the map in ascending
 725     order. Keys that occur multiple times in the map (because items
 726     were inserted with insertMulti(), or unite() was used) also
 727     occur multiple times in the list.
 728
 729     To obtain a list of unique keys, where each key from the map only
 730     occurs once, use uniqueKeys().
 731
 732     The order is guaranteed to be the same as that used by values().
 733
 734     \sa uniqueKeys(), values(), key()
 735 */
 736
 737 /*! \fn QList<Key> QMap::keys(const T &value) const
 738
 739     \overload
 740
 741     Returns a list containing all the keys associated with value \a
 742     value in ascending order.
 743
 744     This function can be slow (\l{linear time}), because QMap's
 745     internal data structure is optimized for fast lookup by key, not
 746     by value.
 747 */
 748
 749 /*!
 750     \fn Key QMap::key(const T &value, const Key &defaultKey) const
 751     \since 4.3
 752     \overload
 753
 754     Returns the first key with value \a value, or \a defaultKey if
 755     the map contains no item with value \a value. If no \a defaultKey
 756     is provided the function returns a \link {default-constructed value}
 757     default-constructed key \endlink.
 758
 759     This function can be slow (\l{linear time}), because QMap's
 760     internal data structure is optimized for fast lookup by key, not
 761     by value.
 762
 763     \sa value(), keys()
 764 */
 765
 766 /*! \fn QList<T> QMap::values() const
 767
 768     Returns a list containing all the values in the map, in ascending
 769     order of their keys. If a key is associated with multiple values,
 770     all of its values will be in the list, and not just the most
 771     recently inserted one.
 772
 773     \sa keys(), value()
 774 */
 775
 776 /*! \fn QList<T> QMap::values(const Key &key) const
 777
 778     \overload
 779
 780     Returns a list containing all the values associated with key
 781     \a key, from the most recently inserted to the least recently
 782     inserted one.
 783
 784     \sa count(), insertMulti()
 785 */
 786
 787 /*! \fn int QMap::count(const Key &key) const
 788
 789     Returns the number of items associated with key \a key.
 790
 791     \sa contains(), insertMulti(), QMultiMap::count()
 792 */
 793
 794 /*! \fn int QMap::count() const
 795
 796     \overload
 797
 798     Same as size().
 799 */
 800
 801 /*! \fn QMap::iterator QMap::begin()
 802
 803     Returns an \l{STL-style iterator} pointing to the first item in
 804     the map.
 805
 806     \sa constBegin(), end()
 807 */
 808
 809 /*! \fn QMap::const_iterator QMap::begin() const
 810
 811     \overload
 812 */
 813
 814 /*! \fn QMap::const_iterator QMap::cbegin() const
 815     \since 5.0
 816
 817     Returns a const \l{STL-style iterator} pointing to the first item
 818     in the map.
 819
 820     \sa begin(), cend()
 821 */
 822
 823 /*! \fn QMap::const_iterator QMap::constBegin() const
 824
 825     Returns a const \l{STL-style iterator} pointing to the first item
 826     in the map.
 827
 828     \sa begin(), constEnd()
 829 */
 830
 831 /*! \fn QMap::iterator QMap::end()
 832
 833     Returns an \l{STL-style iterator} pointing to the imaginary item
 834     after the last item in the map.
 835
 836     \sa begin(), constEnd()
 837 */
 838
 839 /*! \fn QMap::const_iterator QMap::end() const
 840
 841     \overload
 842 */
 843
 844 /*! \fn QMap::const_iterator QMap::cend() const
 845     \since 5.0
 846
 847     Returns a const \l{STL-style iterator} pointing to the imaginary
 848     item after the last item in the map.
 849
 850     \sa cbegin(), end()
 851 */
 852
 853 /*! \fn QMap::const_iterator QMap::constEnd() const
 854
 855     Returns a const \l{STL-style iterator} pointing to the imaginary
 856     item after the last item in the map.
 857
 858     \sa constBegin(), end()
 859 */
 860
 861 /*! \fn QMap::iterator QMap::erase(iterator pos)
 862
 863     Removes the (key, value) pair pointed to by the iterator \a pos
 864     from the map, and returns an iterator to the next item in the
 865     map.
 866
 867     \sa remove()
 868 */
 869
 870 /*! \fn QMap::iterator QMap::find(const Key &key)
 871
 872     Returns an iterator pointing to the item with key \a key in the
 873     map.
 874
 875     If the map contains no item with key \a key, the function
 876     returns end().
 877
 878     If the map contains multiple items with key \a key, this
 879     function returns an iterator that points to the most recently
 880     inserted value. The other values are accessible by incrementing
 881     the iterator. For example, here's some code that iterates over all
 882     the items with the same key:
 883
 884     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 14
 885
 886     \sa constFind(), value(), values(), lowerBound(), upperBound(), QMultiMap::find()
 887 */
 888
 889 /*! \fn QMap::const_iterator QMap::find(const Key &key) const
 890
 891     \overload
 892 */
 893
 894 /*! \fn QMap::const_iterator QMap::constFind(const Key &key) const
 895     \since 4.1
 896
 897     Returns an const iterator pointing to the item with key \a key in the
 898     map.
 899
 900     If the map contains no item with key \a key, the function
 901     returns constEnd().
 902
 903     \sa find(), QMultiMap::constFind()
 904 */
 905
 906 /*! \fn QMap::iterator QMap::lowerBound(const Key &key)
 907
 908     Returns an iterator pointing to the first item with key \a key in
 909     the map. If the map contains no item with key \a key, the
 910     function returns an iterator to the nearest item with a greater
 911     key.
 912
 913     Example:
 914     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 15
 915
 916     If the map contains multiple items with key \a key, this
 917     function returns an iterator that points to the most recently
 918     inserted value. The other values are accessible by incrementing
 919     the iterator. For example, here's some code that iterates over all
 920     the items with the same key:
 921
 922     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 16
 923
 924     \sa qLowerBound(), upperBound(), find()
 925 */
 926
 927 /*! \fn QMap::const_iterator QMap::lowerBound(const Key &key) const
 928
 929     \overload
 930 */
 931
 932 /*! \fn QMap::iterator QMap::upperBound(const Key &key)
 933
 934     Returns an iterator pointing to the item that immediately follows
 935     the last item with key \a key in the map. If the map contains no
 936     item with key \a key, the function returns an iterator to the
 937     nearest item with a greater key.
 938
 939     Example:
 940     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 17
 941
 942     \sa qUpperBound(), lowerBound(), find()
 943 */
 944
 945 /*! \fn QMap::const_iterator QMap::upperBound(const Key &key) const
 946
 947     \overload
 948 */
 949
 950 /*! \fn QMap::iterator QMap::insert(const Key &key, const T &value)
 951
 952     Inserts a new item with the key \a key and a value of \a value.
 953
 954     If there is already an item with the key \a key, that item's value
 955     is replaced with \a value.
 956
 957     If there are multiple items with the key \a key, the most
 958     recently inserted item's value is replaced with \a value.
 959
 960     \sa insertMulti()
 961 */
 962
 963 /*! \fn QMap::iterator QMap::insertMulti(const Key &key, const T &value)
 964
 965     Inserts a new item with the key \a key and a value of \a value.
 966
 967     If there is already an item with the same key in the map, this
 968     function will simply create a new one. (This behavior is
 969     different from insert(), which overwrites the value of an
 970     existing item.)
 971
 972     \sa insert(), values()
 973 */
 974
 975 /*! \fn QMap<Key, T> &QMap::unite(const QMap<Key, T> &other)
 976
 977     Inserts all the items in the \a other map into this map. If a
 978     key is common to both maps, the resulting map will contain the
 979     key multiple times.
 980
 981     \sa insertMulti()
 982 */
 983
 984 /*! \typedef QMap::Iterator
 985
 986     Qt-style synonym for QMap::iterator.
 987 */
 988
 989 /*! \typedef QMap::ConstIterator
 990
 991     Qt-style synonym for QMap::const_iterator.
 992 */
 993
 994 /*! \typedef QMap::difference_type
 995
 996     Typedef for ptrdiff_t. Provided for STL compatibility.
 997 */
 998
 999 /*! \typedef QMap::key_type
1000
1001     Typedef for Key. Provided for STL compatibility.
1002 */
1003
1004 /*! \typedef QMap::mapped_type
1005
1006     Typedef for T. Provided for STL compatibility.
1007 */
1008
1009 /*! \typedef QMap::size_type
1010
1011     Typedef for int. Provided for STL compatibility.
1012 */
1013
1014 /*!
1015     \fn bool QMap::empty() const
1016
1017     This function is provided for STL compatibility. It is equivalent
1018     to isEmpty(), returning true if the map is empty; otherwise
1019     returning false.
1020 */
1021
1022 /*! \class QMap::iterator
1023     \brief The QMap::iterator class provides an STL-style non-const iterator for QMap and QMultiMap.
1024
1025     QMap features both \l{STL-style iterators} and \l{Java-style
1026     iterators}. The STL-style iterators are more low-level and more
1027     cumbersome to use; on the other hand, they are slightly faster
1028     and, for developers who already know STL, have the advantage of
1029     familiarity.
1030
1031     QMap\<Key, T\>::iterator allows you to iterate over a QMap (or
1032     QMultiMap) and to modify the value (but not the key) stored under
1033     a particular key. If you want to iterate over a const QMap, you
1034     should use QMap::const_iterator. It is generally good practice to
1035     use QMap::const_iterator on a non-const QMap as well, unless you
1036     need to change the QMap through the iterator. Const iterators are
1037     slightly faster, and can improve code readability.
1038
1039     The default QMap::iterator constructor creates an uninitialized
1040     iterator. You must initialize it using a QMap function like
1041     QMap::begin(), QMap::end(), or QMap::find() before you can
1042     start iterating. Here's a typical loop that prints all the (key,
1043     value) pairs stored in a map:
1044
1045     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 18
1046
1047     Unlike QHash, which stores its items in an arbitrary order, QMap
1048     stores its items ordered by key. Items that share the same key
1049     (because they were inserted using QMap::insertMulti(), or due to a
1050     unite()) will appear consecutively, from the most recently to the
1051     least recently inserted value.
1052
1053     Let's see a few examples of things we can do with a
1054     QMap::iterator that we cannot do with a QMap::const_iterator.
1055     Here's an example that increments every value stored in the QMap
1056     by 2:
1057
1058     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 19
1059
1060     Here's an example that removes all the items whose key is a
1061     string that starts with an underscore character:
1062
1063     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 20
1064
1065     The call to QMap::erase() removes the item pointed to by the
1066     iterator from the map, and returns an iterator to the next item.
1067     Here's another way of removing an item while iterating:
1068
1069     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 21
1070
1071     It might be tempting to write code like this:
1072
1073     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 22
1074
1075     However, this will potentially crash in \c{++i}, because \c i is
1076     a dangling iterator after the call to erase().
1077
1078     Multiple iterators can be used on the same map. If you add items
1079     to the map, existing iterators will remain valid. If you remove
1080     items from the map, iterators that point to the removed items
1081     will become dangling iterators.
1082
1083     \sa QMap::const_iterator, QMutableMapIterator
1084 */
1085
1086 /*! \fn QMap::iterator::operator QMapData::Node *() const
1087
1088     \internal
1089 */
1090
1091 /*! \typedef QMap::iterator::difference_type
1092
1093     \internal
1094 */
1095
1096 /*! \typedef QMap::iterator::iterator_category
1097
1098   A synonym for \e {std::bidirectional_iterator_tag} indicating
1099   this iterator is a bidirectional iterator.
1100 */
1101
1102 /*! \typedef QMap::iterator::pointer
1103
1104     \internal
1105 */
1106
1107 /*! \typedef QMap::iterator::reference
1108
1109     \internal
1110 */
1111
1112 /*! \typedef QMap::iterator::value_type
1113
1114     \internal
1115 */
1116
1117 /*! \fn QMap::iterator::iterator()
1118
1119     Constructs an uninitialized iterator.
1120
1121     Functions like key(), value(), and operator++() must not be
1122     called on an uninitialized iterator. Use operator=() to assign a
1123     value to it before using it.
1124
1125     \sa QMap::begin() QMap::end()
1126 */
1127
1128 /*! \fn QMap::iterator::iterator(QMapData::Node *node)
1129
1130     \internal
1131 */
1132
1133 /*! \fn const Key &QMap::iterator::key() const
1134
1135     Returns the current item's key as a const reference.
1136
1137     There is no direct way of changing an item's key through an
1138     iterator, although it can be done by calling QMap::erase()
1139     followed by QMap::insert() or QMap::insertMulti().
1140
1141     \sa value()
1142 */
1143
1144 /*! \fn T &QMap::iterator::value() const
1145
1146     Returns a modifiable reference to the current item's value.
1147
1148     You can change the value of an item by using value() on
1149     the left side of an assignment, for example:
1150
1151     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 23
1152
1153     \sa key(), operator*()
1154 */
1155
1156 /*! \fn T &QMap::iterator::operator*() const
1157
1158     Returns a modifiable reference to the current item's value.
1159
1160     Same as value().
1161
1162     \sa key()
1163 */
1164
1165 /*! \fn T *QMap::iterator::operator->() const
1166
1167     Returns a pointer to the current item's value.
1168
1169     \sa value()
1170 */
1171
1172 /*!
1173     \fn bool QMap::iterator::operator==(const iterator &other) const
1174     \fn bool QMap::iterator::operator==(const const_iterator &other) const
1175
1176     Returns true if \a other points to the same item as this
1177     iterator; otherwise returns false.
1178
1179     \sa operator!=()
1180 */
1181
1182 /*!
1183     \fn bool QMap::iterator::operator!=(const iterator &other) const
1184     \fn bool QMap::iterator::operator!=(const const_iterator &other) const
1185
1186     Returns true if \a other points to a different item than this
1187     iterator; otherwise returns false.
1188
1189     \sa operator==()
1190 */
1191
1192 /*! \fn QMap::iterator QMap::iterator::operator++()
1193
1194     The prefix ++ operator (\c{++i}) advances the iterator to the
1195     next item in the map and returns an iterator to the new current
1196     item.
1197
1198     Calling this function on QMap::end() leads to undefined results.
1199
1200     \sa operator--()
1201 */
1202
1203 /*! \fn QMap::iterator QMap::iterator::operator++(int)
1204
1205     \overload
1206
1207     The postfix ++ operator (\c{i++}) advances the iterator to the
1208     next item in the map and returns an iterator to the previously
1209     current item.
1210 */
1211
1212 /*! \fn QMap::iterator QMap::iterator::operator--()
1213
1214     The prefix -- operator (\c{--i}) makes the preceding item
1215     current and returns an iterator pointing to the new current item.
1216
1217     Calling this function on QMap::begin() leads to undefined
1218     results.
1219
1220     \sa operator++()
1221 */
1222
1223 /*! \fn QMap::iterator QMap::iterator::operator--(int)
1224
1225     \overload
1226
1227     The postfix -- operator (\c{i--}) makes the preceding item
1228     current and returns an iterator pointing to the previously
1229     current item.
1230 */
1231
1232 /*! \fn QMap::iterator QMap::iterator::operator+(int j) const
1233
1234     Returns an iterator to the item at \a j positions forward from
1235     this iterator. (If \a j is negative, the iterator goes backward.)
1236
1237     This operation can be slow for large \a j values.
1238
1239     \sa operator-()
1240
1241 */
1242
1243 /*! \fn QMap::iterator QMap::iterator::operator-(int j) const
1244
1245     Returns an iterator to the item at \a j positions backward from
1246     this iterator. (If \a j is negative, the iterator goes forward.)
1247
1248     This operation can be slow for large \a j values.
1249
1250     \sa operator+()
1251 */
1252
1253 /*! \fn QMap::iterator &QMap::iterator::operator+=(int j)
1254
1255     Advances the iterator by \a j items. (If \a j is negative, the
1256     iterator goes backward.)
1257
1258     \sa operator-=(), operator+()
1259 */
1260
1261 /*! \fn QMap::iterator &QMap::iterator::operator-=(int j)
1262
1263     Makes the iterator go back by \a j items. (If \a j is negative,
1264     the iterator goes forward.)
1265
1266     \sa operator+=(), operator-()
1267 */
1268
1269 /*! \class QMap::const_iterator
1270     \brief The QMap::const_iterator class provides an STL-style const iterator for QMap and QMultiMap.
1271
1272     QMap features both \l{STL-style iterators} and \l{Java-style
1273     iterators}. The STL-style iterators are more low-level and more
1274     cumbersome to use; on the other hand, they are slightly faster
1275     and, for developers who already know STL, have the advantage of
1276     familiarity.
1277
1278     QMap\<Key, T\>::const_iterator allows you to iterate over a QMap
1279     (or a QMultiMap). If you want to modify the QMap as you iterate
1280     over it, you must use QMap::iterator instead. It is generally
1281     good practice to use QMap::const_iterator on a non-const QMap as
1282     well, unless you need to change the QMap through the iterator.
1283     Const iterators are slightly faster, and can improve code
1284     readability.
1285
1286     The default QMap::const_iterator constructor creates an
1287     uninitialized iterator. You must initialize it using a QMap
1288     function like QMap::constBegin(), QMap::constEnd(), or
1289     QMap::find() before you can start iterating. Here's a typical
1290     loop that prints all the (key, value) pairs stored in a map:
1291
1292     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 24
1293
1294     Unlike QHash, which stores its items in an arbitrary order, QMap
1295     stores its items ordered by key. Items that share the same key
1296     (because they were inserted using QMap::insertMulti()) will
1297     appear consecutively, from the most recently to the least
1298     recently inserted value.
1299
1300     Multiple iterators can be used on the same map. If you add items
1301     to the map, existing iterators will remain valid. If you remove
1302     items from the map, iterators that point to the removed items
1303     will become dangling iterators.
1304
1305     \sa QMap::iterator, QMapIterator
1306 */
1307
1308 /*! \fn QMap::const_iterator::operator QMapData::Node *() const
1309
1310     \internal
1311 */
1312
1313 /*! \typedef QMap::const_iterator::difference_type
1314
1315     \internal
1316 */
1317
1318 /*! \typedef QMap::const_iterator::iterator_category
1319
1320   A synonym for \e {std::bidirectional_iterator_tag} indicating
1321   this iterator is a bidirectional iterator.
1322 */
1323
1324 /*! \typedef QMap::const_iterator::pointer
1325
1326     \internal
1327 */
1328
1329 /*! \typedef QMap::const_iterator::reference
1330
1331     \internal
1332 */
1333
1334 /*! \typedef QMap::const_iterator::value_type
1335
1336     \internal
1337 */
1338
1339 /*! \fn QMap::const_iterator::const_iterator()
1340
1341     Constructs an uninitialized iterator.
1342
1343     Functions like key(), value(), and operator++() must not be
1344     called on an uninitialized iterator. Use operator=() to assign a
1345     value to it before using it.
1346
1347     \sa QMap::constBegin() QMap::constEnd()
1348 */
1349
1350 /*! \fn QMap::const_iterator::const_iterator(QMapData::Node *node)
1351
1352     \internal
1353 */
1354
1355 /*! \fn QMap::const_iterator::const_iterator(const iterator &other)
1356
1357     Constructs a copy of \a other.
1358 */
1359
1360 /*! \fn const Key &QMap::const_iterator::key() const
1361
1362     Returns the current item's key.
1363
1364     \sa value()
1365 */
1366
1367 /*! \fn const T &QMap::const_iterator::value() const
1368
1369     Returns the current item's value.
1370
1371     \sa key(), operator*()
1372 */
1373
1374 /*! \fn const T &QMap::const_iterator::operator*() const
1375
1376     Returns the current item's value.
1377
1378     Same as value().
1379
1380     \sa key()
1381 */
1382
1383 /*! \fn const T *QMap::const_iterator::operator->() const
1384
1385     Returns a pointer to the current item's value.
1386
1387     \sa value()
1388 */
1389
1390 /*! \fn bool QMap::const_iterator::operator==(const const_iterator &other) const
1391
1392     Returns true if \a other points to the same item as this
1393     iterator; otherwise returns false.
1394
1395     \sa operator!=()
1396 */
1397
1398 /*! \fn bool QMap::const_iterator::operator!=(const const_iterator &other) const
1399
1400     Returns true if \a other points to a different item than this
1401     iterator; otherwise returns false.
1402
1403     \sa operator==()
1404 */
1405
1406 /*! \fn QMap::const_iterator QMap::const_iterator::operator++()
1407
1408     The prefix ++ operator (\c{++i}) advances the iterator to the
1409     next item in the map and returns an iterator to the new current
1410     item.
1411
1412     Calling this function on QMap::end() leads to undefined results.
1413
1414     \sa operator--()
1415 */
1416
1417 /*! \fn QMap::const_iterator QMap::const_iterator::operator++(int)
1418
1419     \overload
1420
1421     The postfix ++ operator (\c{i++}) advances the iterator to the
1422     next item in the map and returns an iterator to the previously
1423     current item.
1424 */
1425
1426 /*! \fn QMap::const_iterator &QMap::const_iterator::operator--()
1427
1428     The prefix -- operator (\c{--i}) makes the preceding item
1429     current and returns an iterator pointing to the new current item.
1430
1431     Calling this function on QMap::begin() leads to undefined
1432     results.
1433
1434     \sa operator++()
1435 */
1436
1437 /*! \fn QMap::const_iterator QMap::const_iterator::operator--(int)
1438
1439     \overload
1440
1441     The postfix -- operator (\c{i--}) makes the preceding item
1442     current and returns an iterator pointing to the previously
1443     current item.
1444 */
1445
1446 /*! \fn QMap::const_iterator QMap::const_iterator::operator+(int j) const
1447
1448     Returns an iterator to the item at \a j positions forward from
1449     this iterator. (If \a j is negative, the iterator goes backward.)
1450
1451     This operation can be slow for large \a j values.
1452
1453     \sa operator-()
1454 */
1455
1456 /*! \fn QMap::const_iterator QMap::const_iterator::operator-(int j) const
1457
1458     Returns an iterator to the item at \a j positions backward from
1459     this iterator. (If \a j is negative, the iterator goes forward.)
1460
1461     This operation can be slow for large \a j values.
1462
1463     \sa operator+()
1464 */
1465
1466 /*! \fn QMap::const_iterator &QMap::const_iterator::operator+=(int j)
1467
1468     Advances the iterator by \a j items. (If \a j is negative, the
1469     iterator goes backward.)
1470
1471     This operation can be slow for large \a j values.
1472
1473     \sa operator-=(), operator+()
1474 */
1475
1476 /*! \fn QMap::const_iterator &QMap::const_iterator::operator-=(int j)
1477
1478     Makes the iterator go back by \a j items. (If \a j is negative,
1479     the iterator goes forward.)
1480
1481     This operation can be slow for large \a j values.
1482
1483     \sa operator+=(), operator-()
1484 */
1485
1486 /*! \fn QDataStream &operator<<(QDataStream &out, const QMap<Key, T> &map)
1487     \relates QMap
1488
1489     Writes the map \a map to stream \a out.
1490
1491     This function requires the key and value types to implement \c
1492     operator<<().
1493
1494     \sa \link datastreamformat.html Format of the QDataStream operators \endlink
1495 */
1496
1497 /*! \fn QDataStream &operator>>(QDataStream &in, QMap<Key, T> &map)
1498     \relates QMap
1499
1500     Reads a map from stream \a in into \a map.
1501
1502     This function requires the key and value types to implement \c
1503     operator>>().
1504
1505     \sa \link datastreamformat.html Format of the QDataStream operators \endlink
1506 */
1507
1508 /*! \class QMultiMap
1509     \brief The QMultiMap class is a convenience QMap subclass that provides multi-valued maps.
1510
1511     \ingroup tools
1512     \ingroup shared
1513
1514     \reentrant
1515
1516     QMultiMap\<Key, T\> is one of Qt's generic \l{container classes}.
1517     It inherits QMap and extends it with a few convenience functions
1518     that make it more suitable than QMap for storing multi-valued
1519     maps. A multi-valued map is a map that allows multiple values
1520     with the same key; QMap normally doesn't allow that, unless you
1521     call QMap::insertMulti().
1522
1523     Because QMultiMap inherits QMap, all of QMap's functionality also
1524     applies to QMultiMap. For example, you can use isEmpty() to test
1525     whether the map is empty, and you can traverse a QMultiMap using
1526     QMap's iterator classes (for example, QMapIterator). But in
1527     addition, it provides an insert() function that corresponds to
1528     QMap::insertMulti(), and a replace() function that corresponds to
1529     QMap::insert(). It also provides convenient operator+() and
1530     operator+=().
1531
1532     Example:
1533     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 25
1534
1535     Unlike QMap, QMultiMap provides no operator[]. Use value() or
1536     replace() if you want to access the most recently inserted item
1537     with a certain key.
1538
1539     If you want to retrieve all the values for a single key, you can
1540     use values(const Key &key), which returns a QList<T>:
1541
1542     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 26
1543
1544     The items that share the same key are available from most
1545     recently to least recently inserted.
1546
1547     If you prefer the STL-style iterators, you can call find() to get
1548     the iterator for the first item with a key and iterate from
1549     there:
1550
1551     \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 27
1552
1553     QMultiMap's key and value data types must be \l{assignable data
1554     types}. This covers most data types you are likely to encounter,
1555     but the compiler won't let you, for example, store a QWidget as a
1556     value; instead, store a QWidget *. In addition, QMultiMap's key type
1557     must provide operator<(). See the QMap documentation for details.
1558
1559     \sa QMap, QMapIterator, QMutableMapIterator, QMultiHash
1560 */
1561
1562 /*! \fn QMultiMap::QMultiMap()
1563
1564     Constructs an empty map.
1565 */
1566
1567 /*! \fn QMultiMap::QMultiMap(const QMap<Key, T> &other)
1568
1569     Constructs a copy of \a other (which can be a QMap or a
1570     QMultiMap).
1571
1572     \sa operator=()
1573 */
1574
1575 /*! \fn QMultiMap::iterator QMultiMap::replace(const Key &key, const T &value)
1576
1577     Inserts a new item with the key \a key and a value of \a value.
1578
1579     If there is already an item with the key \a key, that item's value
1580     is replaced with \a value.
1581
1582     If there are multiple items with the key \a key, the most
1583     recently inserted item's value is replaced with \a value.
1584
1585     \sa insert()
1586 */
1587
1588 /*! \fn QMultiMap::iterator QMultiMap::insert(const Key &key, const T &value)
1589
1590     Inserts a new item with the key \a key and a value of \a value.
1591
1592     If there is already an item with the same key in the map, this
1593     function will simply create a new one. (This behavior is
1594     different from replace(), which overwrites the value of an
1595     existing item.)
1596
1597     \sa replace()
1598 */
1599
1600 /*! \fn QMultiMap &QMultiMap::operator+=(const QMultiMap &other)
1601
1602     Inserts all the items in the \a other map into this map and
1603     returns a reference to this map.
1604
1605     \sa insert(), operator+()
1606 */
1607
1608 /*! \fn QMultiMap QMultiMap::operator+(const QMultiMap &other) const
1609
1610     Returns a map that contains all the items in this map in
1611     addition to all the items in \a other. If a key is common to both
1612     maps, the resulting map will contain the key multiple times.
1613
1614     \sa operator+=()
1615 */
1616
1617 /*!
1618     \fn bool QMultiMap::contains(const Key &key, const T &value) const
1619     \since 4.3
1620
1621     Returns true if the map contains an item with key \a key and
1622     value \a value; otherwise returns false.
1623
1624     \sa QMap::contains()
1625 */
1626
1627 /*!
1628     \fn bool QMultiMap::contains(const Key &key) const
1629     \overload
1630     \sa QMap::contains()
1631 */
1632
1633 /*!
1634     \fn int QMultiMap::remove(const Key &key, const T &value)
1635     \since 4.3
1636
1637     Removes all the items that have the key \a key and the value \a
1638     value from the map. Returns the number of items removed.
1639
1640     \sa QMap::remove()
1641 */
1642
1643 /*!
1644     \fn int QMultiMap::remove(const Key &key)
1645     \overload
1646     \sa QMap::remove()
1647 */
1648
1649 /*!
1650     \fn int QMultiMap::count(const Key &key, const T &value) const
1651     \since 4.3
1652
1653     Returns the number of items with key \a key and value \a value.
1654
1655     \sa QMap::count()
1656 */
1657
1658 /*!
1659     \fn int QMultiMap::count(const Key &key) const
1660     \overload
1661     \sa QMap::count()
1662 */
1663
1664 /*!
1665     \fn int QMultiMap::count() const
1666     \overload
1667     \sa QMap::count()
1668 */
1669
1670 /*!
1671     \fn typename QMap<Key, T>::iterator QMultiMap::find(const Key &key, const T &value)
1672     \since 4.3
1673
1674     Returns an iterator pointing to the item with key \a key and
1675     value \a value in the map.
1676
1677     If the map contains no such item, the function returns end().
1678
1679     If the map contains multiple items with key \a key, this
1680     function returns an iterator that points to the most recently
1681     inserted value.
1682
1683     \sa QMap::find()
1684 */
1685
1686 /*!
1687     \fn typename QMap<Key, T>::iterator QMultiMap::find(const Key &key)
1688     \overload
1689     \sa QMap::find()
1690 */
1691
1692 /*!
1693     \fn typename QMap<Key, T>::const_iterator QMultiMap::find(const Key &key, const T &value) const
1694     \since 4.3
1695     \overload
1696
1697     Returns a const iterator pointing to the item with the given \a key and
1698     \a value in the map.
1699
1700     If the map contains no such item, the function returns end().
1701
1702     If the map contains multiple items with the specified \a key, this
1703     function returns a const iterator that points to the most recently
1704     inserted value.
1705
1706     \sa QMap::find()
1707 */
1708
1709 /*!
1710     \fn typename QMap<Key, T>::const_iterator QMultiMap::find(const Key &key) const
1711     \since 4.3
1712     \overload
1713     \sa QMap::find()
1714 */
1715
1716 /*!
1717     \fn typename QMap<Key, T>::const_iterator QMultiMap::constFind(const Key &key, const T &value) const
1718     \since 4.3
1719
1720     Returns an iterator pointing to the item with key \a key and the
1721     value \a value in the map.
1722
1723     If the map contains no such item, the function returns
1724     constEnd().
1725
1726     \sa QMap::constFind()
1727 */
1728
1729 /*!
1730     \fn typename QMap<Key, T>::const_iterator QMultiMap::constFind(const Key &key) const
1731     \overload
1732     \sa QMap::constFind()
1733 */
1734
1735 QT_END_NAMESPACE