1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Copyright (C) 2016 Intel Corporation.
5** Copyright (C) 2012 Giuseppe D'Angelo <dangelog@gmail.com>.
6** Contact: https://www.qt.io/licensing/
7**
8** This file is part of the QtCore module of the Qt Toolkit.
9**
10** $QT_BEGIN_LICENSE:LGPL$
11** Commercial License Usage
12** Licensees holding valid commercial Qt licenses may use this file in
13** accordance with the commercial license agreement provided with the
14** Software or, alternatively, in accordance with the terms contained in
15** a written agreement between you and The Qt Company. For licensing terms
16** and conditions see https://www.qt.io/terms-conditions. For further
17** information use the contact form at https://www.qt.io/contact-us.
18**
19** GNU Lesser General Public License Usage
20** Alternatively, this file may be used under the terms of the GNU Lesser
21** General Public License version 3 as published by the Free Software
22** Foundation and appearing in the file LICENSE.LGPL3 included in the
23** packaging of this file. Please review the following information to
24** ensure the GNU Lesser General Public License version 3 requirements
25** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
26**
27** GNU General Public License Usage
28** Alternatively, this file may be used under the terms of the GNU
29** General Public License version 2.0 or (at your option) the GNU General
30** Public license version 3 or any later version approved by the KDE Free
31** Qt Foundation. The licenses are as published by the Free Software
32** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
33** included in the packaging of this file. Please review the following
34** information to ensure the GNU General Public License requirements will
35** be met: https://www.gnu.org/licenses/gpl-2.0.html and
36** https://www.gnu.org/licenses/gpl-3.0.html.
37**
38** $QT_END_LICENSE$
39**
40****************************************************************************/
41
42// for rand_s, _CRT_RAND_S must be #defined before #including stdlib.h.
43// put it at the beginning so some indirect inclusion doesn't break it
44#ifndef _CRT_RAND_S
45#define _CRT_RAND_S
46#endif
47#include <stdlib.h>
48
49#include "qhash.h"
50
51#ifdef truncate
52#undef truncate
53#endif
54
55#include <qbitarray.h>
56#include <qstring.h>
57#include <qglobal.h>
58#include <qbytearray.h>
59#include <qdatetime.h>
60#include <qbasicatomic.h>
61#include <qendian.h>
62#include <private/qsimd_p.h>
63
64#ifndef QT_BOOTSTRAPPED
65#include <qcoreapplication.h>
66#include <qrandom.h>
67#endif // QT_BOOTSTRAPPED
68
69#include <limits.h>
70
71QT_BEGIN_NAMESPACE
72
73/*
74 The Java's hashing algorithm for strings is a variation of D. J. Bernstein
75 hashing algorithm appeared here http://cr.yp.to/cdb/cdb.txt
76 and informally known as DJB33XX - DJB's 33 Times Xor.
77 Java uses DJB31XA, that is, 31 Times Add.
78
79 The original algorithm was a loop around
80 (h << 5) + h ^ c
81 (which is indeed h*33 ^ c); it was then changed to
82 (h << 5) - h ^ c
83 (so h*31^c: DJB31XX), and the XOR changed to a sum:
84 (h << 5) - h + c
85 (DJB31XA), which can save some assembly instructions.
86
87 Still, we can avoid writing the multiplication as "(h << 5) - h"
88 -- the compiler will turn it into a shift and an addition anyway
89 (for instance, gcc 4.4 does that even at -O0).
90*/
91
92#if QT_COMPILER_SUPPORTS_HERE(SSE4_2)
93static inline bool hasFastCrc32()
94{
95 return qCpuHasFeature(SSE4_2);
96}
97
98template <typename Char>
99QT_FUNCTION_TARGET(SSE4_2)
100static uint crc32(const Char *ptr, size_t len, uint h)
101{
102 // The CRC32 instructions from Nehalem calculate a 32-bit CRC32 checksum
103 const uchar *p = reinterpret_cast<const uchar *>(ptr);
104 const uchar *const e = p + (len * sizeof(Char));
105# ifdef Q_PROCESSOR_X86_64
106 // The 64-bit instruction still calculates only 32-bit, but without this
107 // variable GCC 4.9 still tries to clear the high bits on every loop
108 qulonglong h2 = h;
109
110 p += 8;
111 for ( ; p <= e; p += 8)
112 h2 = _mm_crc32_u64(h2, qFromUnaligned<qlonglong>(p - 8));
113 h = h2;
114 p -= 8;
115
116 len = e - p;
117 if (len & 4) {
118 h = _mm_crc32_u32(h, qFromUnaligned<uint>(p));
119 p += 4;
120 }
121# else
122 p += 4;
123 for ( ; p <= e; p += 4)
124 h = _mm_crc32_u32(h, qFromUnaligned<uint>(p - 4));
125 p -= 4;
126 len = e - p;
127# endif
128 if (len & 2) {
129 h = _mm_crc32_u16(h, qFromUnaligned<ushort>(p));
130 p += 2;
131 }
132 if (sizeof(Char) == 1 && len & 1)
133 h = _mm_crc32_u8(h, *p);
134 return h;
135}
136#elif defined(__ARM_FEATURE_CRC32)
137static inline bool hasFastCrc32()
138{
139 return qCpuHasFeature(CRC32);
140}
141
142template <typename Char>
143#if defined(Q_PROCESSOR_ARM_64)
144QT_FUNCTION_TARGET(CRC32)
145#endif
146static uint crc32(const Char *ptr, size_t len, uint h)
147{
148 // The crc32[whbd] instructions on Aarch64/Aarch32 calculate a 32-bit CRC32 checksum
149 const uchar *p = reinterpret_cast<const uchar *>(ptr);
150 const uchar *const e = p + (len * sizeof(Char));
151
152#ifndef __ARM_FEATURE_UNALIGNED
153 if (Q_UNLIKELY(reinterpret_cast<quintptr>(p) & 7)) {
154 if ((sizeof(Char) == 1) && (reinterpret_cast<quintptr>(p) & 1) && (e - p > 0)) {
155 h = __crc32b(h, *p);
156 ++p;
157 }
158 if ((reinterpret_cast<quintptr>(p) & 2) && (e >= p + 2)) {
159 h = __crc32h(h, *reinterpret_cast<const uint16_t *>(p));
160 p += 2;
161 }
162 if ((reinterpret_cast<quintptr>(p) & 4) && (e >= p + 4)) {
163 h = __crc32w(h, *reinterpret_cast<const uint32_t *>(p));
164 p += 4;
165 }
166 }
167#endif
168
169 for ( ; p + 8 <= e; p += 8)
170 h = __crc32d(h, *reinterpret_cast<const uint64_t *>(p));
171
172 len = e - p;
173 if (len == 0)
174 return h;
175 if (len & 4) {
176 h = __crc32w(h, *reinterpret_cast<const uint32_t *>(p));
177 p += 4;
178 }
179 if (len & 2) {
180 h = __crc32h(h, *reinterpret_cast<const uint16_t *>(p));
181 p += 2;
182 }
183 if (sizeof(Char) == 1 && len & 1)
184 h = __crc32b(h, *p);
185 return h;
186}
187#else
188static inline bool hasFastCrc32()
189{
190 return false;
191}
192
193static uint crc32(...)
194{
195 Q_UNREACHABLE();
196 return 0;
197}
198#endif
199
200static inline uint hash(const uchar *p, size_t len, uint seed) noexcept
201{
202 uint h = seed;
203
204 if (seed && hasFastCrc32())
205 return crc32(p, len, h);
206
207 for (size_t i = 0; i < len; ++i)
208 h = 31 * h + p[i];
209
210 return h;
211}
212
213uint qHashBits(const void *p, size_t len, uint seed) noexcept
214{
215 return hash(static_cast<const uchar*>(p), int(len), seed);
216}
217
218static inline uint hash(const QChar *p, size_t len, uint seed) noexcept
219{
220 uint h = seed;
221
222 if (seed && hasFastCrc32())
223 return crc32(p, len, h);
224
225 for (size_t i = 0; i < len; ++i)
226 h = 31 * h + p[i].unicode();
227
228 return h;
229}
230
231uint qHash(const QByteArray &key, uint seed) noexcept
232{
233 return hash(reinterpret_cast<const uchar *>(key.constData()), size_t(key.size()), seed);
234}
235
236#if QT_STRINGVIEW_LEVEL < 2
237uint qHash(const QString &key, uint seed) noexcept
238{
239 return hash(key.unicode(), size_t(key.size()), seed);
240}
241
242uint qHash(const QStringRef &key, uint seed) noexcept
243{
244 return hash(key.unicode(), size_t(key.size()), seed);
245}
246#endif
247
248uint qHash(QStringView key, uint seed) noexcept
249{
250 return hash(key.data(), key.size(), seed);
251}
252
253uint qHash(const QBitArray &bitArray, uint seed) noexcept
254{
255 int m = bitArray.d.size() - 1;
256 uint result = hash(reinterpret_cast<const uchar *>(bitArray.d.constData()),
257 size_t(qMax(0, m)), seed);
258
259 // deal with the last 0 to 7 bits manually, because we can't trust that
260 // the padding is initialized to 0 in bitArray.d
261 int n = bitArray.size();
262 if (n & 0x7)
263 result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1);
264 return result;
265}
266
267uint qHash(QLatin1String key, uint seed) noexcept
268{
269 return hash(reinterpret_cast<const uchar *>(key.data()), size_t(key.size()), seed);
270}
271
272/*!
273 \internal
274
275 Creates the QHash random seed from various sources.
276 In order of decreasing precedence:
277 - under Unix, it attemps to read from /dev/urandom;
278 - under Unix, it attemps to read from /dev/random;
279 - under Windows, it attempts to use rand_s;
280 - as a general fallback, the application's PID, a timestamp and the
281 address of a stack-local variable are used.
282*/
283static uint qt_create_qhash_seed()
284{
285 uint seed = 0;
286
287#ifndef QT_BOOTSTRAPPED
288 QByteArray envSeed = qgetenv("QT_HASH_SEED");
289 if (!envSeed.isNull()) {
290 uint seed = envSeed.toUInt();
291 if (seed) {
292 // can't use qWarning here (reentrancy)
293 fprintf(stderr, "QT_HASH_SEED: forced seed value is not 0, cannot guarantee that the "
294 "hashing functions will produce a stable value.");
295 }
296 return seed;
297 }
298
299 seed = QRandomGenerator::system()->generate();
300#endif // QT_BOOTSTRAPPED
301
302 return seed;
303}
304
305/*
306 The QHash seed itself.
307*/
308static QBasicAtomicInt qt_qhash_seed = Q_BASIC_ATOMIC_INITIALIZER(-1);
309
310/*!
311 \internal
312
313 Seed == -1 means it that it was not initialized yet.
314
315 We let qt_create_qhash_seed return any unsigned integer,
316 but convert it to signed in order to initialize the seed.
317
318 We don't actually care about the fact that different calls to
319 qt_create_qhash_seed() might return different values,
320 as long as in the end everyone uses the very same value.
321*/
322static void qt_initialize_qhash_seed()
323{
324 if (qt_qhash_seed.loadRelaxed() == -1) {
325 int x(qt_create_qhash_seed() & INT_MAX);
326 qt_qhash_seed.testAndSetRelaxed(-1, x);
327 }
328}
329
330/*! \relates QHash
331 \since 5.6
332
333 Returns the current global QHash seed.
334
335 The seed is set in any newly created QHash. See \l{qHash} about how this seed
336 is being used by QHash.
337
338 \sa qSetGlobalQHashSeed
339 */
340int qGlobalQHashSeed()
341{
342 qt_initialize_qhash_seed();
343 return qt_qhash_seed.loadRelaxed();
344}
345
346/*! \relates QHash
347 \since 5.6
348
349 Sets the global QHash seed to \a newSeed.
350
351 Manually setting the global QHash seed value should be done only for testing
352 and debugging purposes, when deterministic and reproducible behavior on a QHash
353 is needed. We discourage to do it in production code as it can make your
354 application susceptible to \l{algorithmic complexity attacks}.
355
356 From Qt 5.10 and onwards, the only allowed values are 0 and -1. Passing the
357 value -1 will reinitialize the global QHash seed to a random value, while
358 the value of 0 is used to request a stable algorithm for C++ primitive
359 types types (like \c int) and string types (QString, QByteArray).
360
361 The seed is set in any newly created QHash. See \l{qHash} about how this seed
362 is being used by QHash.
363
364 If the environment variable \c QT_HASH_SEED is set, calling this function will
365 result in a no-op.
366
367 \sa qGlobalQHashSeed
368 */
369void qSetGlobalQHashSeed(int newSeed)
370{
371 if (qEnvironmentVariableIsSet("QT_HASH_SEED"))
372 return;
373 if (newSeed == -1) {
374 int x(qt_create_qhash_seed() & INT_MAX);
375 qt_qhash_seed.storeRelaxed(x);
376 } else {
377 if (newSeed) {
378 // can't use qWarning here (reentrancy)
379 fprintf(stderr, "qSetGlobalQHashSeed: forced seed value is not 0, cannot guarantee that the "
380 "hashing functions will produce a stable value.");
381 }
382 qt_qhash_seed.storeRelaxed(newSeed & INT_MAX);
383 }
384}
385
386/*!
387 \internal
388
389 Private copy of the implementation of the Qt 4 qHash algorithm for strings,
390 (that is, QChar-based arrays, so all QString-like classes),
391 to be used wherever the result is somehow stored or reused across multiple
392 Qt versions. The public qHash implementation can change at any time,
393 therefore one must not rely on the fact that it will always give the same
394 results.
395
396 The qt_hash functions must *never* change their results.
397
398 This function can hash discontiguous memory by invoking it on each chunk,
399 passing the previous's result in the next call's \a chained argument.
400*/
401uint qt_hash(QStringView key, uint chained) noexcept
402{
403 auto n = key.size();
404 auto p = key.utf16();
405
406 uint h = chained;
407
408 while (n--) {
409 h = (h << 4) + *p++;
410 h ^= (h & 0xf0000000) >> 23;
411 h &= 0x0fffffff;
412 }
413 return h;
414}
415
416/*
417 The prime_deltas array contains the difference between a power
418 of two and the next prime number:
419
420 prime_deltas[i] = nextprime(2^i) - 2^i
421
422 Basically, it's sequence A092131 from OEIS, assuming:
423 - nextprime(1) = 1
424 - nextprime(2) = 2
425 and
426 - left-extending it for the offset 0 (A092131 starts at i=1)
427 - stopping the sequence at i = 28 (the table is big enough...)
428*/
429
430static const uchar prime_deltas[] = {
431 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 17, 27, 3,
432 1, 29, 3, 21, 7, 17, 15, 9, 43, 35, 15, 0, 0, 0, 0, 0
433};
434
435/*
436 The primeForNumBits() function returns the prime associated to a
437 power of two. For example, primeForNumBits(8) returns 257.
438*/
439
440static inline int primeForNumBits(int numBits)
441{
442 return (1 << numBits) + prime_deltas[numBits];
443}
444
445/*
446 Returns the smallest integer n such that
447 primeForNumBits(n) >= hint.
448*/
449static int countBits(int hint)
450{
451 int numBits = 0;
452 int bits = hint;
453
454 while (bits > 1) {
455 bits >>= 1;
456 numBits++;
457 }
458
459 if (numBits >= (int)sizeof(prime_deltas)) {
460 numBits = sizeof(prime_deltas) - 1;
461 } else if (primeForNumBits(numBits) < hint) {
462 ++numBits;
463 }
464 return numBits;
465}
466
467/*
468 A QHash has initially around pow(2, MinNumBits) buckets. For
469 example, if MinNumBits is 4, it has 17 buckets.
470*/
471const int MinNumBits = 4;
472
473const QHashData QHashData::shared_null = {
474 nullptr, nullptr, Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, MinNumBits, 0, 0, 0, true, false, 0
475};
476
477void *QHashData::allocateNode(int nodeAlign)
478{
479 void *ptr = strictAlignment ? qMallocAligned(nodeSize, nodeAlign) : malloc(nodeSize);
480 Q_CHECK_PTR(ptr);
481 return ptr;
482}
483
484void QHashData::freeNode(void *node)
485{
486 if (strictAlignment)
487 qFreeAligned(node);
488 else
489 free(node);
490}
491
492QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *),
493 void (*node_delete)(Node *),
494 int nodeSize,
495 int nodeAlign)
496{
497 union {
498 QHashData *d;
499 Node *e;
500 };
501 if (this == &shared_null)
502 qt_initialize_qhash_seed(); // may throw
503 d = new QHashData;
504 d->fakeNext = nullptr;
505 d->buckets = nullptr;
506 d->ref.initializeOwned();
507 d->size = size;
508 d->nodeSize = nodeSize;
509 d->userNumBits = userNumBits;
510 d->numBits = numBits;
511 d->numBuckets = numBuckets;
512 d->seed = (this == &shared_null) ? uint(qt_qhash_seed.loadRelaxed()) : seed;
513 d->sharable = true;
514 d->strictAlignment = nodeAlign > 8;
515 d->reserved = 0;
516
517 if (numBuckets) {
518 QT_TRY {
519 d->buckets = new Node *[numBuckets];
520 } QT_CATCH(...) {
521 // restore a consistent state for d
522 d->numBuckets = 0;
523 // roll back
524 d->free_helper(node_delete);
525 QT_RETHROW;
526 }
527
528 Node *this_e = reinterpret_cast<Node *>(this);
529 for (int i = 0; i < numBuckets; ++i) {
530 Node **nextNode = &d->buckets[i];
531 Node *oldNode = buckets[i];
532 while (oldNode != this_e) {
533 QT_TRY {
534 Node *dup = static_cast<Node *>(allocateNode(nodeAlign));
535
536 QT_TRY {
537 node_duplicate(oldNode, dup);
538 } QT_CATCH(...) {
539 freeNode( dup );
540 QT_RETHROW;
541 }
542
543 *nextNode = dup;
544 nextNode = &dup->next;
545 oldNode = oldNode->next;
546 } QT_CATCH(...) {
547 // restore a consistent state for d
548 *nextNode = e;
549 d->numBuckets = i+1;
550 // roll back
551 d->free_helper(node_delete);
552 QT_RETHROW;
553 }
554 }
555 *nextNode = e;
556 }
557 }
558 return d;
559}
560
561void QHashData::free_helper(void (*node_delete)(Node *))
562{
563 if (node_delete) {
564 Node *this_e = reinterpret_cast<Node *>(this);
565 Node **bucket = reinterpret_cast<Node **>(this->buckets);
566
567 int n = numBuckets;
568 while (n--) {
569 Node *cur = *bucket++;
570 while (cur != this_e) {
571 Node *next = cur->next;
572 node_delete(cur);
573 freeNode(cur);
574 cur = next;
575 }
576 }
577 }
578 delete [] buckets;
579 delete this;
580}
581
582QHashData::Node *QHashData::nextNode(Node *node)
583{
584 union {
585 Node *next;
586 Node *e;
587 QHashData *d;
588 };
589 next = node->next;
590 Q_ASSERT_X(next, "QHash", "Iterating beyond end()");
591 if (next->next)
592 return next;
593
594 int start = (node->h % d->numBuckets) + 1;
595 Node **bucket = d->buckets + start;
596 int n = d->numBuckets - start;
597 while (n--) {
598 if (*bucket != e)
599 return *bucket;
600 ++bucket;
601 }
602 return e;
603}
604
605QHashData::Node *QHashData::previousNode(Node *node)
606{
607 union {
608 Node *e;
609 QHashData *d;
610 };
611
612 e = node;
613 while (e->next)
614 e = e->next;
615
616 int start;
617 if (node == e)
618 start = d->numBuckets - 1;
619 else
620 start = node->h % d->numBuckets;
621
622 Node *sentinel = node;
623 Node **bucket = d->buckets + start;
624 while (start >= 0) {
625 if (*bucket != sentinel) {
626 Node *prev = *bucket;
627 while (prev->next != sentinel)
628 prev = prev->next;
629 return prev;
630 }
631
632 sentinel = e;
633 --bucket;
634 --start;
635 }
636 Q_ASSERT_X(start >= 0, "QHash", "Iterating backward beyond begin()");
637 return e;
638}
639
640/*
641 If hint is negative, -hint gives the approximate number of
642 buckets that should be used for the hash table. If hint is
643 nonnegative, (1 << hint) gives the approximate number
644 of buckets that should be used.
645*/
646void QHashData::rehash(int hint)
647{
648 if (hint < 0) {
649 hint = countBits(-hint);
650 if (hint < MinNumBits)
651 hint = MinNumBits;
652 userNumBits = hint;
653 while (primeForNumBits(hint) < (size >> 1))
654 ++hint;
655 } else if (hint < MinNumBits) {
656 hint = MinNumBits;
657 }
658
659 if (numBits != hint) {
660 Node *e = reinterpret_cast<Node *>(this);
661 Node **oldBuckets = buckets;
662 int oldNumBuckets = numBuckets;
663
664 int nb = primeForNumBits(hint);
665 buckets = new Node *[nb];
666 numBits = hint;
667 numBuckets = nb;
668 for (int i = 0; i < numBuckets; ++i)
669 buckets[i] = e;
670
671 for (int i = 0; i < oldNumBuckets; ++i) {
672 Node *firstNode = oldBuckets[i];
673 while (firstNode != e) {
674 uint h = firstNode->h;
675 Node *lastNode = firstNode;
676 while (lastNode->next != e && lastNode->next->h == h)
677 lastNode = lastNode->next;
678
679 Node *afterLastNode = lastNode->next;
680 Node **beforeFirstNode = &buckets[h % numBuckets];
681 while (*beforeFirstNode != e)
682 beforeFirstNode = &(*beforeFirstNode)->next;
683 lastNode->next = *beforeFirstNode;
684 *beforeFirstNode = firstNode;
685 firstNode = afterLastNode;
686 }
687 }
688 delete [] oldBuckets;
689 }
690}
691
692#ifdef QT_QHASH_DEBUG
693
694void QHashData::dump()
695{
696 qDebug("Hash data (ref = %d, size = %d, nodeSize = %d, userNumBits = %d, numBits = %d, numBuckets = %d)",
697 int(ref), size, nodeSize, userNumBits, numBits,
698 numBuckets);
699 qDebug(" %p (fakeNode = %p)", this, fakeNext);
700 for (int i = 0; i < numBuckets; ++i) {
701 Node *n = buckets[i];
702 if (n != reinterpret_cast<Node *>(this)) {
703 QString line = QString::asprintf("%d:", i);
704 while (n != reinterpret_cast<Node *>(this)) {
705 line += QString::asprintf(" -> [%p]", n);
706 if (!n) {
707 line += " (CORRUPT)";
708 break;
709 }
710 n = n->next;
711 }
712 qDebug("%ls", qUtf16Printable(line));
713 }
714 }
715}
716
717void QHashData::checkSanity()
718{
719 if (Q_UNLIKELY(fakeNext))
720 qFatal("Fake next isn't 0");
721
722 for (int i = 0; i < numBuckets; ++i) {
723 Node *n = buckets[i];
724 Node *p = n;
725 if (Q_UNLIKELY(!n))
726 qFatal("%d: Bucket entry is 0", i);
727 if (n != reinterpret_cast<Node *>(this)) {
728 while (n != reinterpret_cast<Node *>(this)) {
729 if (Q_UNLIKELY(!n->next))
730 qFatal("%d: Next of %p is 0, should be %p", i, n, this);
731 n = n->next;
732 }
733 }
734 }
735}
736#endif
737
738/*!
739 \fn template <typename T1, typename T2> uint qHash(const QPair<T1, T2> &key, uint seed = 0)
740 \since 5.0
741 \relates QHash
742
743 Returns the hash value for the \a key, using \a seed to seed the calculation.
744
745 Types \c T1 and \c T2 must be supported by qHash().
746*/
747
748/*!
749 \fn template <typename T1, typename T2> uint qHash(const std::pair<T1, T2> &key, uint seed = 0)
750 \since 5.7
751 \relates QHash
752
753 Returns the hash value for the \a key, using \a seed to seed the calculation.
754
755 Types \c T1 and \c T2 must be supported by qHash().
756
757 \note The return type of this function is \e{not} the same as that of
758 \snippet code/src_corelib_tools_qhash.cpp 29
759 The two functions use different hashing algorithms; due to binary compatibility
760 constraints, we cannot change the QPair algorithm to match the std::pair one before Qt 6.
761*/
762
763/*! \fn template <typename InputIterator> uint qHashRange(InputIterator first, InputIterator last, uint seed = 0)
764 \relates QHash
765 \since 5.5
766
767 Returns the hash value for the range [\a{first},\a{last}), using \a seed
768 to seed the calculation, by successively applying qHash() to each
769 element and combining the hash values into a single one.
770
771 The return value of this function depends on the order of elements
772 in the range. That means that
773
774 \snippet code/src_corelib_tools_qhash.cpp 30
775
776 and
777 \snippet code/src_corelib_tools_qhash.cpp 31
778
779 hash to \b{different} values. If order does not matter, for example for hash
780 tables, use qHashRangeCommutative() instead. If you are hashing raw
781 memory, use qHashBits().
782
783 Use this function only to implement qHash() for your own custom
784 types. For example, here's how you could implement a qHash() overload for
785 std::vector<int>:
786
787 \snippet code/src_corelib_tools_qhash.cpp qhashrange
788
789 It bears repeating that the implementation of qHashRange() - like
790 the qHash() overloads offered by Qt - may change at any time. You
791 \b{must not} rely on the fact that qHashRange() will give the same
792 results (for the same inputs) across different Qt versions, even
793 if qHash() for the element type would.
794
795 \sa qHashBits(), qHashRangeCommutative()
796*/
797
798/*! \fn template <typename InputIterator> uint qHashRangeCommutative(InputIterator first, InputIterator last, uint seed = 0)
799 \relates QHash
800 \since 5.5
801
802 Returns the hash value for the range [\a{first},\a{last}), using \a seed
803 to seed the calculation, by successively applying qHash() to each
804 element and combining the hash values into a single one.
805
806 The return value of this function does not depend on the order of
807 elements in the range. That means that
808
809 \snippet code/src_corelib_tools_qhash.cpp 30
810
811 and
812 \snippet code/src_corelib_tools_qhash.cpp 31
813
814 hash to the \b{same} values. If order matters, for example, for vectors
815 and arrays, use qHashRange() instead. If you are hashing raw
816 memory, use qHashBits().
817
818 Use this function only to implement qHash() for your own custom
819 types. For example, here's how you could implement a qHash() overload for
820 std::unordered_set<int>:
821
822 \snippet code/src_corelib_tools_qhash.cpp qhashrangecommutative
823
824 It bears repeating that the implementation of
825 qHashRangeCommutative() - like the qHash() overloads offered by Qt
826 - may change at any time. You \b{must not} rely on the fact that
827 qHashRangeCommutative() will give the same results (for the same
828 inputs) across different Qt versions, even if qHash() for the
829 element type would.
830
831 \sa qHashBits(), qHashRange()
832*/
833
834/*! \fn uint qHashBits(const void *p, size_t len, uint seed = 0)
835 \relates QHash
836 \since 5.4
837
838 Returns the hash value for the memory block of size \a len pointed
839 to by \a p, using \a seed to seed the calculation.
840
841 Use this function only to implement qHash() for your own custom
842 types. For example, here's how you could implement a qHash() overload for
843 std::vector<int>:
844
845 \snippet code/src_corelib_tools_qhash.cpp qhashbits
846
847 This takes advantage of the fact that std::vector lays out its data
848 contiguously. If that is not the case, or the contained type has
849 padding, you should use qHashRange() instead.
850
851 It bears repeating that the implementation of qHashBits() - like
852 the qHash() overloads offered by Qt - may change at any time. You
853 \b{must not} rely on the fact that qHashBits() will give the same
854 results (for the same inputs) across different Qt versions.
855
856 \sa qHashRange(), qHashRangeCommutative()
857*/
858
859/*! \fn uint qHash(char key, uint seed = 0)
860 \relates QHash
861 \since 5.0
862
863 Returns the hash value for the \a key, using \a seed to seed the calculation.
864*/
865
866/*! \fn uint qHash(uchar key, uint seed = 0)
867 \relates QHash
868 \since 5.0
869
870 Returns the hash value for the \a key, using \a seed to seed the calculation.
871*/
872
873/*! \fn uint qHash(signed char key, uint seed = 0)
874 \relates QHash
875 \since 5.0
876
877 Returns the hash value for the \a key, using \a seed to seed the calculation.
878*/
879
880/*! \fn uint qHash(ushort key, uint seed = 0)
881 \relates QHash
882 \since 5.0
883
884 Returns the hash value for the \a key, using \a seed to seed the calculation.
885*/
886
887/*! \fn uint qHash(short key, uint seed = 0)
888 \relates QHash
889 \since 5.0
890
891 Returns the hash value for the \a key, using \a seed to seed the calculation.
892*/
893
894/*! \fn uint qHash(uint key, uint seed = 0)
895 \relates QHash
896 \since 5.0
897
898 Returns the hash value for the \a key, using \a seed to seed the calculation.
899*/
900
901/*! \fn uint qHash(int key, uint seed = 0)
902 \relates QHash
903 \since 5.0
904
905 Returns the hash value for the \a key, using \a seed to seed the calculation.
906*/
907
908/*! \fn uint qHash(ulong key, uint seed = 0)
909 \relates QHash
910 \since 5.0
911
912 Returns the hash value for the \a key, using \a seed to seed the calculation.
913*/
914
915/*! \fn uint qHash(long key, uint seed = 0)
916 \relates QHash
917 \since 5.0
918
919 Returns the hash value for the \a key, using \a seed to seed the calculation.
920*/
921
922/*! \fn uint qHash(quint64 key, uint seed = 0)
923 \relates QHash
924 \since 5.0
925
926 Returns the hash value for the \a key, using \a seed to seed the calculation.
927*/
928
929/*! \fn uint qHash(qint64 key, uint seed = 0)
930 \relates QHash
931 \since 5.0
932
933 Returns the hash value for the \a key, using \a seed to seed the calculation.
934*/
935
936/*! \relates QHash
937 \since 5.3
938
939 Returns the hash value for the \a key, using \a seed to seed the calculation.
940*/
941uint qHash(float key, uint seed) noexcept
942{
943 return key != 0.0f ? hash(reinterpret_cast<const uchar *>(&key), sizeof(key), seed) : seed ;
944}
945
946/*! \relates QHash
947 \since 5.3
948
949 Returns the hash value for the \a key, using \a seed to seed the calculation.
950*/
951uint qHash(double key, uint seed) noexcept
952{
953 return key != 0.0 ? hash(reinterpret_cast<const uchar *>(&key), sizeof(key), seed) : seed ;
954}
955
956#if !defined(Q_OS_DARWIN) || defined(Q_CLANG_QDOC)
957/*! \relates QHash
958 \since 5.3
959
960 Returns the hash value for the \a key, using \a seed to seed the calculation.
961*/
962uint qHash(long double key, uint seed) noexcept
963{
964 return key != 0.0L ? hash(reinterpret_cast<const uchar *>(&key), sizeof(key), seed) : seed ;
965}
966#endif
967
968/*! \fn uint qHash(const QChar key, uint seed = 0)
969 \relates QHash
970 \since 5.0
971
972 Returns the hash value for the \a key, using \a seed to seed the calculation.
973*/
974
975/*! \fn uint qHash(const QByteArray &key, uint seed = 0)
976 \relates QHash
977 \since 5.0
978
979 Returns the hash value for the \a key, using \a seed to seed the calculation.
980*/
981
982/*! \fn uint qHash(const QBitArray &key, uint seed = 0)
983 \relates QHash
984 \since 5.0
985
986 Returns the hash value for the \a key, using \a seed to seed the calculation.
987*/
988
989/*! \fn uint qHash(const QString &key, uint seed = 0)
990 \relates QHash
991 \since 5.0
992
993 Returns the hash value for the \a key, using \a seed to seed the calculation.
994*/
995
996/*! \fn uint qHash(const QStringRef &key, uint seed = 0)
997 \relates QHash
998 \since 5.0
999
1000 Returns the hash value for the \a key, using \a seed to seed the calculation.
1001*/
1002
1003/*! \fn uint qHash(QStringView key, uint seed = 0)
1004 \relates QStringView
1005 \since 5.10
1006
1007 Returns the hash value for the \a key, using \a seed to seed the calculation.
1008*/
1009
1010/*! \fn uint qHash(QLatin1String key, uint seed = 0)
1011 \relates QHash
1012 \since 5.0
1013
1014 Returns the hash value for the \a key, using \a seed to seed the calculation.
1015*/
1016
1017/*! \fn template <class T> uint qHash(const T *key, uint seed = 0)
1018 \relates QHash
1019 \since 5.0
1020
1021 Returns the hash value for the \a key, using \a seed to seed the calculation.
1022*/
1023
1024/*!
1025 \class QHash
1026 \inmodule QtCore
1027 \brief The QHash class is a template class that provides a hash-table-based dictionary.
1028
1029 \ingroup tools
1030 \ingroup shared
1031
1032 \reentrant
1033
1034 QHash\<Key, T\> is one of Qt's generic \l{container classes}. It
1035 stores (key, value) pairs and provides very fast lookup of the
1036 value associated with a key.
1037
1038 QHash provides very similar functionality to QMap. The
1039 differences are:
1040
1041 \list
1042 \li QHash provides faster lookups than QMap. (See \l{Algorithmic
1043 Complexity} for details.)
1044 \li When iterating over a QMap, the items are always sorted by
1045 key. With QHash, the items are arbitrarily ordered.
1046 \li The key type of a QMap must provide operator<(). The key
1047 type of a QHash must provide operator==() and a global
1048 hash function called qHash() (see \l{qHash}).
1049 \endlist
1050
1051 Here's an example QHash with QString keys and \c int values:
1052 \snippet code/src_corelib_tools_qhash.cpp 0
1053
1054 To insert a (key, value) pair into the hash, you can use operator[]():
1055
1056 \snippet code/src_corelib_tools_qhash.cpp 1
1057
1058 This inserts the following three (key, value) pairs into the
1059 QHash: ("one", 1), ("three", 3), and ("seven", 7). Another way to
1060 insert items into the hash is to use insert():
1061
1062 \snippet code/src_corelib_tools_qhash.cpp 2
1063
1064 To look up a value, use operator[]() or value():
1065
1066 \snippet code/src_corelib_tools_qhash.cpp 3
1067
1068 If there is no item with the specified key in the hash, these
1069 functions return a \l{default-constructed value}.
1070
1071 If you want to check whether the hash contains a particular key,
1072 use contains():
1073
1074 \snippet code/src_corelib_tools_qhash.cpp 4
1075
1076 There is also a value() overload that uses its second argument as
1077 a default value if there is no item with the specified key:
1078
1079 \snippet code/src_corelib_tools_qhash.cpp 5
1080
1081 In general, we recommend that you use contains() and value()
1082 rather than operator[]() for looking up a key in a hash. The
1083 reason is that operator[]() silently inserts an item into the
1084 hash if no item exists with the same key (unless the hash is
1085 const). For example, the following code snippet will create 1000
1086 items in memory:
1087
1088 \snippet code/src_corelib_tools_qhash.cpp 6
1089
1090 To avoid this problem, replace \c hash[i] with \c hash.value(i)
1091 in the code above.
1092
1093 Internally, QHash uses a hash table to perform lookups. This
1094 hash table automatically grows and shrinks to
1095 provide fast lookups without wasting too much memory. You can
1096 still control the size of the hash table by calling reserve() if
1097 you already know approximately how many items the QHash will
1098 contain, but this isn't necessary to obtain good performance. You
1099 can also call capacity() to retrieve the hash table's size.
1100
1101 If you want to navigate through all the (key, value) pairs stored
1102 in a QHash, you can use an iterator. QHash provides both
1103 \l{Java-style iterators} (QHashIterator and QMutableHashIterator)
1104 and \l{STL-style iterators} (QHash::const_iterator and
1105 QHash::iterator). Here's how to iterate over a QHash<QString,
1106 int> using a Java-style iterator:
1107
1108 \snippet code/src_corelib_tools_qhash.cpp 7
1109
1110 Here's the same code, but using an STL-style iterator:
1111
1112 \snippet code/src_corelib_tools_qhash.cpp 8
1113
1114 QHash is unordered, so an iterator's sequence cannot be assumed
1115 to be predictable. If ordering by key is required, use a QMap.
1116
1117 Normally, a QHash allows only one value per key. If you call
1118 insert() with a key that already exists in the QHash, the
1119 previous value is erased. For example:
1120
1121 \snippet code/src_corelib_tools_qhash.cpp 9
1122
1123 However, you can store multiple values per key by using
1124 insertMulti() instead of insert() (or using the convenience
1125 subclass QMultiHash). If you want to retrieve all
1126 the values for a single key, you can use values(const Key &key),
1127 which returns a QList<T>:
1128
1129 \snippet code/src_corelib_tools_qhash.cpp 10
1130
1131 The items that share the same key are available from most
1132 recently to least recently inserted. A more efficient approach is
1133 to call find() to get the iterator for the first item with a key
1134 and iterate from there:
1135
1136 \snippet code/src_corelib_tools_qhash.cpp 11
1137
1138 If you only need to extract the values from a hash (not the keys),
1139 you can also use \l{foreach}:
1140
1141 \snippet code/src_corelib_tools_qhash.cpp 12
1142
1143 Items can be removed from the hash in several ways. One way is to
1144 call remove(); this will remove any item with the given key.
1145 Another way is to use QMutableHashIterator::remove(). In addition,
1146 you can clear the entire hash using clear().
1147
1148 QHash's key and value data types must be \l{assignable data
1149 types}. You cannot, for example, store a QWidget as a value;
1150 instead, store a QWidget *.
1151
1152 \target qHash
1153 \section2 The qHash() hashing function
1154
1155 A QHash's key type has additional requirements other than being an
1156 assignable data type: it must provide operator==(), and there must also be
1157 a qHash() function in the type's namespace that returns a hash value for an
1158 argument of the key's type.
1159
1160 The qHash() function computes a numeric value based on a key. It
1161 can use any algorithm imaginable, as long as it always returns
1162 the same value if given the same argument. In other words, if
1163 \c{e1 == e2}, then \c{qHash(e1) == qHash(e2)} must hold as well.
1164 However, to obtain good performance, the qHash() function should
1165 attempt to return different hash values for different keys to the
1166 largest extent possible.
1167
1168 For a key type \c{K}, the qHash function must have one of these signatures:
1169
1170 \snippet code/src_corelib_tools_qhash.cpp 32
1171
1172 The two-arguments overloads take an unsigned integer that should be used to
1173 seed the calculation of the hash function. This seed is provided by QHash
1174 in order to prevent a family of \l{algorithmic complexity attacks}. If both
1175 a one-argument and a two-arguments overload are defined for a key type,
1176 the latter is used by QHash (note that you can simply define a
1177 two-arguments version, and use a default value for the seed parameter).
1178
1179 Here's a partial list of the C++ and Qt types that can serve as keys in a
1180 QHash: any integer type (char, unsigned long, etc.), any pointer type,
1181 QChar, QString, and QByteArray. For all of these, the \c <QHash> header
1182 defines a qHash() function that computes an adequate hash value. Many other
1183 Qt classes also declare a qHash overload for their type; please refer to
1184 the documentation of each class.
1185
1186 If you want to use other types as the key, make sure that you provide
1187 operator==() and a qHash() implementation.
1188
1189 Example:
1190 \snippet code/src_corelib_tools_qhash.cpp 13
1191
1192 In the example above, we've relied on Qt's global qHash(const
1193 QString &, uint) to give us a hash value for the employee's name, and
1194 XOR'ed this with the day they were born to help produce unique
1195 hashes for people with the same name.
1196
1197 Note that the implementation of the qHash() overloads offered by Qt
1198 may change at any time. You \b{must not} rely on the fact that qHash()
1199 will give the same results (for the same inputs) across different Qt
1200 versions.
1201
1202 \section2 Algorithmic complexity attacks
1203
1204 All hash tables are vulnerable to a particular class of denial of service
1205 attacks, in which the attacker carefully pre-computes a set of different
1206 keys that are going to be hashed in the same bucket of a hash table (or
1207 even have the very same hash value). The attack aims at getting the
1208 worst-case algorithmic behavior (O(n) instead of amortized O(1), see
1209 \l{Algorithmic Complexity} for the details) when the data is fed into the
1210 table.
1211
1212 In order to avoid this worst-case behavior, the calculation of the hash
1213 value done by qHash() can be salted by a random seed, that nullifies the
1214 attack's extent. This seed is automatically generated by QHash once per
1215 process, and then passed by QHash as the second argument of the
1216 two-arguments overload of the qHash() function.
1217
1218 This randomization of QHash is enabled by default. Even though programs
1219 should never depend on a particular QHash ordering, there may be situations
1220 where you temporarily need deterministic behavior, for example for debugging or
1221 regression testing. To disable the randomization, define the environment
1222 variable \c QT_HASH_SEED to have the value 0. Alternatively, you can call
1223 the qSetGlobalQHashSeed() function with the value 0.
1224
1225 \sa QHashIterator, QMutableHashIterator, QMap, QSet
1226*/
1227
1228/*! \fn template <class Key, class T> QHash<Key, T>::QHash()
1229
1230 Constructs an empty hash.
1231
1232 \sa clear()
1233*/
1234
1235/*!
1236 \fn template <class Key, class T> QHash<Key, T>::QHash(QHash &&other)
1237
1238 Move-constructs a QHash instance, making it point at the same
1239 object that \a other was pointing to.
1240
1241 \since 5.2
1242*/
1243
1244/*! \fn template <class Key, class T> QHash<Key, T>::QHash(std::initializer_list<std::pair<Key,T> > list)
1245 \since 5.1
1246
1247 Constructs a hash with a copy of each of the elements in the
1248 initializer list \a list.
1249
1250 This function is only available if the program is being
1251 compiled in C++11 mode.
1252*/
1253
1254/*! \fn template <class Key, class T> template <class InputIterator> QHash<Key, T>::QHash(InputIterator begin, InputIterator end)
1255 \since 5.14
1256
1257 Constructs a hash with a copy of each of the elements in the iterator range
1258 [\a begin, \a end). Either the elements iterated by the range must be
1259 objects with \c{first} and \c{second} data members (like \c{QPair},
1260 \c{std::pair}, etc.) convertible to \c Key and to \c T respectively; or the
1261 iterators must have \c{key()} and \c{value()} member functions, returning a
1262 key convertible to \c Key and a value convertible to \c T respectively.
1263*/
1264
1265/*! \fn template <class Key, class T> QHash<Key, T>::QHash(const QHash &other)
1266
1267 Constructs a copy of \a other.
1268
1269 This operation occurs in \l{constant time}, because QHash is
1270 \l{implicitly shared}. This makes returning a QHash from a
1271 function very fast. If a shared instance is modified, it will be
1272 copied (copy-on-write), and this takes \l{linear time}.
1273
1274 \sa operator=()
1275*/
1276
1277/*! \fn template <class Key, class T> QHash<Key, T>::~QHash()
1278
1279 Destroys the hash. References to the values in the hash and all
1280 iterators of this hash become invalid.
1281*/
1282
1283/*! \fn template <class Key, class T> QHash &QHash<Key, T>::operator=(const QHash &other)
1284
1285 Assigns \a other to this hash and returns a reference to this hash.
1286*/
1287
1288/*!
1289 \fn template <class Key, class T> QHash &QHash<Key, T>::operator=(QHash &&other)
1290
1291 Move-assigns \a other to this QHash instance.
1292
1293 \since 5.2
1294*/
1295
1296/*! \fn template <class Key, class T> void QHash<Key, T>::swap(QHash &other)
1297 \since 4.8
1298
1299 Swaps hash \a other with this hash. This operation is very
1300 fast and never fails.
1301*/
1302
1303/*! \fn template <class Key, class T> void QMultiHash<Key, T>::swap(QMultiHash &other)
1304 \since 4.8
1305
1306 Swaps hash \a other with this hash. This operation is very
1307 fast and never fails.
1308*/
1309
1310/*! \fn template <class Key, class T> bool QHash<Key, T>::operator==(const QHash &other) const
1311
1312 Returns \c true if \a other is equal to this hash; otherwise returns
1313 false.
1314
1315 Two hashes are considered equal if they contain the same (key,
1316 value) pairs.
1317
1318 This function requires the value type to implement \c operator==().
1319
1320 \sa operator!=()
1321*/
1322
1323/*! \fn template <class Key, class T> bool QHash<Key, T>::operator!=(const QHash &other) const
1324
1325 Returns \c true if \a other is not equal to this hash; otherwise
1326 returns \c false.
1327
1328 Two hashes are considered equal if they contain the same (key,
1329 value) pairs.
1330
1331 This function requires the value type to implement \c operator==().
1332
1333 \sa operator==()
1334*/
1335
1336/*! \fn template <class Key, class T> int QHash<Key, T>::size() const
1337
1338 Returns the number of items in the hash.
1339
1340 \sa isEmpty(), count()
1341*/
1342
1343/*! \fn template <class Key, class T> bool QHash<Key, T>::isEmpty() const
1344
1345 Returns \c true if the hash contains no items; otherwise returns
1346 false.
1347
1348 \sa size()
1349*/
1350
1351/*! \fn template <class Key, class T> int QHash<Key, T>::capacity() const
1352
1353 Returns the number of buckets in the QHash's internal hash table.
1354
1355 The sole purpose of this function is to provide a means of fine
1356 tuning QHash's memory usage. In general, you will rarely ever
1357 need to call this function. If you want to know how many items are
1358 in the hash, call size().
1359
1360 \sa reserve(), squeeze()
1361*/
1362
1363/*! \fn template <class Key, class T> void QHash<Key, T>::reserve(int size)
1364
1365 Ensures that the QHash's internal hash table consists of at least
1366 \a size buckets.
1367
1368 This function is useful for code that needs to build a huge hash
1369 and wants to avoid repeated reallocation. For example:
1370
1371 \snippet code/src_corelib_tools_qhash.cpp 14
1372
1373 Ideally, \a size should be slightly more than the maximum number
1374 of items expected in the hash. \a size doesn't have to be prime,
1375 because QHash will use a prime number internally anyway. If \a size
1376 is an underestimate, the worst that will happen is that the QHash
1377 will be a bit slower.
1378
1379 In general, you will rarely ever need to call this function.
1380 QHash's internal hash table automatically shrinks or grows to
1381 provide good performance without wasting too much memory.
1382
1383 \sa squeeze(), capacity()
1384*/
1385
1386/*! \fn template <class Key, class T> void QHash<Key, T>::squeeze()
1387
1388 Reduces the size of the QHash's internal hash table to save
1389 memory.
1390
1391 The sole purpose of this function is to provide a means of fine
1392 tuning QHash's memory usage. In general, you will rarely ever
1393 need to call this function.
1394
1395 \sa reserve(), capacity()
1396*/
1397
1398/*! \fn template <class Key, class T> void QHash<Key, T>::detach()
1399
1400 \internal
1401
1402 Detaches this hash from any other hashes with which it may share
1403 data.
1404
1405 \sa isDetached()
1406*/
1407
1408/*! \fn template <class Key, class T> bool QHash<Key, T>::isDetached() const
1409
1410 \internal
1411
1412 Returns \c true if the hash's internal data isn't shared with any
1413 other hash object; otherwise returns \c false.
1414
1415 \sa detach()
1416*/
1417
1418/*! \fn template <class Key, class T> void QHash<Key, T>::setSharable(bool sharable)
1419
1420 \internal
1421*/
1422
1423/*! \fn template <class Key, class T> bool QHash<Key, T>::isSharedWith(const QHash &other) const
1424
1425 \internal
1426*/
1427
1428/*! \fn template <class Key, class T> void QHash<Key, T>::clear()
1429
1430 Removes all items from the hash.
1431
1432 \sa remove()
1433*/
1434
1435/*! \fn template <class Key, class T> int QHash<Key, T>::remove(const Key &key)
1436
1437 Removes all the items that have the \a key from the hash.
1438 Returns the number of items removed which is usually 1 but will
1439 be 0 if the key isn't in the hash, or greater than 1 if
1440 insertMulti() has been used with the \a key.
1441
1442 \sa clear(), take(), QMultiHash::remove()
1443*/
1444
1445/*! \fn template <class Key, class T> T QHash<Key, T>::take(const Key &key)
1446
1447 Removes the item with the \a key from the hash and returns
1448 the value associated with it.
1449
1450 If the item does not exist in the hash, the function simply
1451 returns a \l{default-constructed value}. If there are multiple
1452 items for \a key in the hash, only the most recently inserted one
1453 is removed.
1454
1455 If you don't use the return value, remove() is more efficient.
1456
1457 \sa remove()
1458*/
1459
1460/*! \fn template <class Key, class T> bool QHash<Key, T>::contains(const Key &key) const
1461
1462 Returns \c true if the hash contains an item with the \a key;
1463 otherwise returns \c false.
1464
1465 \sa count(), QMultiHash::contains()
1466*/
1467
1468/*! \fn template <class Key, class T> const T QHash<Key, T>::value(const Key &key) const
1469
1470 Returns the value associated with the \a key.
1471
1472 If the hash contains no item with the \a key, the function
1473 returns a \l{default-constructed value}. If there are multiple
1474 items for the \a key in the hash, the value of the most recently
1475 inserted one is returned.
1476
1477 \sa key(), values(), contains(), operator[]()
1478*/
1479
1480/*! \fn template <class Key, class T> const T QHash<Key, T>::value(const Key &key, const T &defaultValue) const
1481 \overload
1482
1483 If the hash contains no item with the given \a key, the function returns
1484 \a defaultValue.
1485*/
1486
1487/*! \fn template <class Key, class T> T &QHash<Key, T>::operator[](const Key &key)
1488
1489 Returns the value associated with the \a key as a modifiable
1490 reference.
1491
1492 If the hash contains no item with the \a key, the function inserts
1493 a \l{default-constructed value} into the hash with the \a key, and
1494 returns a reference to it. If the hash contains multiple items
1495 with the \a key, this function returns a reference to the most
1496 recently inserted value.
1497
1498 \sa insert(), value()
1499*/
1500
1501/*! \fn template <class Key, class T> const T QHash<Key, T>::operator[](const Key &key) const
1502
1503 \overload
1504
1505 Same as value().
1506*/
1507
1508/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::uniqueKeys() const
1509 \since 4.2
1510
1511 Returns a list containing all the keys in the map. Keys that occur multiple
1512 times in the map (because items were inserted with insertMulti(), or
1513 unite() was used) occur only once in the returned list.
1514
1515 \sa keys(), values()
1516*/
1517
1518/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys() const
1519
1520 Returns a list containing all the keys in the hash, in an
1521 arbitrary order. Keys that occur multiple times in the hash
1522 (because items were inserted with insertMulti(), or unite() was
1523 used) also occur multiple times in the list.
1524
1525 To obtain a list of unique keys, where each key from the map only
1526 occurs once, use uniqueKeys().
1527
1528 The order is guaranteed to be the same as that used by values().
1529
1530 \sa uniqueKeys(), values(), key()
1531*/
1532
1533/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys(const T &value) const
1534
1535 \overload
1536
1537 Returns a list containing all the keys associated with value \a
1538 value, in an arbitrary order.
1539
1540 This function can be slow (\l{linear time}), because QHash's
1541 internal data structure is optimized for fast lookup by key, not
1542 by value.
1543*/
1544
1545/*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values() const
1546
1547 Returns a list containing all the values in the hash, in an
1548 arbitrary order. If a key is associated with multiple values, all of
1549 its values will be in the list, and not just the most recently
1550 inserted one.
1551
1552 The order is guaranteed to be the same as that used by keys().
1553
1554 \sa keys(), value()
1555*/
1556
1557/*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values(const Key &key) const
1558
1559 \overload
1560
1561 Returns a list of all the values associated with the \a key,
1562 from the most recently inserted to the least recently inserted.
1563
1564 \sa count(), insertMulti()
1565*/
1566
1567/*! \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value) const
1568
1569 Returns the first key mapped to \a value.
1570
1571 If the hash contains no item with the \a value, the function
1572 returns a \l{default-constructed value}{default-constructed key}.
1573
1574 This function can be slow (\l{linear time}), because QHash's
1575 internal data structure is optimized for fast lookup by key, not
1576 by value.
1577
1578 \sa value(), keys()
1579*/
1580
1581/*!
1582 \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value, const Key &defaultKey) const
1583 \since 4.3
1584 \overload
1585
1586 Returns the first key mapped to \a value, or \a defaultKey if the
1587 hash contains no item mapped to \a value.
1588
1589 This function can be slow (\l{linear time}), because QHash's
1590 internal data structure is optimized for fast lookup by key, not
1591 by value.
1592*/
1593
1594/*! \fn template <class Key, class T> int QHash<Key, T>::count(const Key &key) const
1595
1596 Returns the number of items associated with the \a key.
1597
1598 \sa contains(), insertMulti()
1599*/
1600
1601/*! \fn template <class Key, class T> int QHash<Key, T>::count() const
1602
1603 \overload
1604
1605 Same as size().
1606*/
1607
1608/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::begin()
1609
1610 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
1611 the hash.
1612
1613 \sa constBegin(), end()
1614*/
1615
1616/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::begin() const
1617
1618 \overload
1619*/
1620
1621/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cbegin() const
1622 \since 5.0
1623
1624 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1625 in the hash.
1626
1627 \sa begin(), cend()
1628*/
1629
1630/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constBegin() const
1631
1632 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1633 in the hash.
1634
1635 \sa begin(), constEnd()
1636*/
1637
1638/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyBegin() const
1639 \since 5.6
1640
1641 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
1642 in the hash.
1643
1644 \sa keyEnd()
1645*/
1646
1647/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::end()
1648
1649 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
1650 after the last item in the hash.
1651
1652 \sa begin(), constEnd()
1653*/
1654
1655/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::end() const
1656
1657 \overload
1658*/
1659
1660/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constEnd() const
1661
1662 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1663 item after the last item in the hash.
1664
1665 \sa constBegin(), end()
1666*/
1667
1668/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cend() const
1669 \since 5.0
1670
1671 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1672 item after the last item in the hash.
1673
1674 \sa cbegin(), end()
1675*/
1676
1677/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyEnd() const
1678 \since 5.6
1679
1680 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1681 item after the last key in the hash.
1682
1683 \sa keyBegin()
1684*/
1685
1686/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueBegin()
1687 \since 5.10
1688
1689 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
1690 in the hash.
1691
1692 \sa keyValueEnd()
1693*/
1694
1695/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueEnd()
1696 \since 5.10
1697
1698 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1699 entry after the last entry in the hash.
1700
1701 \sa keyValueBegin()
1702*/
1703
1704/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueBegin() const
1705 \since 5.10
1706
1707 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
1708 in the hash.
1709
1710 \sa keyValueEnd()
1711*/
1712
1713/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueBegin() const
1714 \since 5.10
1715
1716 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
1717 in the hash.
1718
1719 \sa keyValueBegin()
1720*/
1721
1722/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueEnd() const
1723 \since 5.10
1724
1725 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1726 entry after the last entry in the hash.
1727
1728 \sa keyValueBegin()
1729*/
1730
1731/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueEnd() const
1732 \since 5.10
1733
1734 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1735 entry after the last entry in the hash.
1736
1737 \sa constKeyValueBegin()
1738*/
1739
1740/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator pos)
1741 \since 5.7
1742
1743 Removes the (key, value) pair associated with the iterator \a pos
1744 from the hash, and returns an iterator to the next item in the
1745 hash.
1746
1747 Unlike remove() and take(), this function never causes QHash to
1748 rehash its internal data structure. This means that it can safely
1749 be called while iterating, and won't affect the order of items in
1750 the hash. For example:
1751
1752 \snippet code/src_corelib_tools_qhash.cpp 15
1753
1754 \sa remove(), take(), find()
1755*/
1756
1757/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(iterator pos)
1758 \overload
1759*/
1760
1761/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::find(const Key &key)
1762
1763 Returns an iterator pointing to the item with the \a key in the
1764 hash.
1765
1766 If the hash contains no item with the \a key, the function
1767 returns end().
1768
1769 If the hash contains multiple items with the \a key, this
1770 function returns an iterator that points to the most recently
1771 inserted value. The other values are accessible by incrementing
1772 the iterator. For example, here's some code that iterates over all
1773 the items with the same key:
1774
1775 \snippet code/src_corelib_tools_qhash.cpp 16
1776
1777 \sa value(), values(), QMultiHash::find()
1778*/
1779
1780/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &key) const
1781
1782 \overload
1783*/
1784
1785/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &key) const
1786 \since 4.1
1787
1788 Returns an iterator pointing to the item with the \a key in the
1789 hash.
1790
1791 If the hash contains no item with the \a key, the function
1792 returns constEnd().
1793
1794 \sa find(), QMultiHash::constFind()
1795*/
1796
1797/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &key, const T &value)
1798
1799 Inserts a new item with the \a key and a value of \a value.
1800
1801 If there is already an item with the \a key, that item's value
1802 is replaced with \a value.
1803
1804 If there are multiple items with the \a key, the most
1805 recently inserted item's value is replaced with \a value.
1806
1807 \sa insertMulti()
1808*/
1809
1810/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &key, const T &value)
1811
1812 Inserts a new item with the \a key and a value of \a value.
1813
1814 If there is already an item with the same key in the hash, this
1815 function will simply create a new one. (This behavior is
1816 different from insert(), which overwrites the value of an
1817 existing item.)
1818
1819 \sa insert(), values()
1820*/
1821
1822/*! \fn template <class Key, class T> QHash &QHash<Key, T>::unite(const QHash &other)
1823
1824 Inserts all the items in the \a other hash into this hash. If a
1825 key is common to both hashes, the resulting hash will contain the
1826 key multiple times.
1827
1828 \sa insertMulti()
1829*/
1830
1831/*! \fn template <class Key, class T> bool QHash<Key, T>::empty() const
1832
1833 This function is provided for STL compatibility. It is equivalent
1834 to isEmpty(), returning true if the hash is empty; otherwise
1835 returns \c false.
1836*/
1837
1838/*! \fn template <class Key, class T> QPair<iterator, iterator> QHash<Key, T>::equal_range(const Key &key)
1839 \since 5.7
1840
1841 Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
1842 are stored under \a key. If the range is empty then both iterators will be equal to end().
1843*/
1844
1845/*!
1846 \fn template <class Key, class T> QPair<const_iterator, const_iterator> QHash<Key, T>::equal_range(const Key &key) const
1847 \overload
1848 \since 5.7
1849*/
1850
1851/*! \typedef QHash::ConstIterator
1852
1853 Qt-style synonym for QHash::const_iterator.
1854*/
1855
1856/*! \typedef QHash::Iterator
1857
1858 Qt-style synonym for QHash::iterator.
1859*/
1860
1861/*! \typedef QHash::difference_type
1862
1863 Typedef for ptrdiff_t. Provided for STL compatibility.
1864*/
1865
1866/*! \typedef QHash::key_type
1867
1868 Typedef for Key. Provided for STL compatibility.
1869*/
1870
1871/*! \typedef QHash::mapped_type
1872
1873 Typedef for T. Provided for STL compatibility.
1874*/
1875
1876/*! \typedef QHash::size_type
1877
1878 Typedef for int. Provided for STL compatibility.
1879*/
1880
1881/*! \typedef QHash::iterator::difference_type
1882 \internal
1883*/
1884
1885/*! \typedef QHash::iterator::iterator_category
1886 \internal
1887*/
1888
1889/*! \typedef QHash::iterator::pointer
1890 \internal
1891*/
1892
1893/*! \typedef QHash::iterator::reference
1894 \internal
1895*/
1896
1897/*! \typedef QHash::iterator::value_type
1898 \internal
1899*/
1900
1901/*! \typedef QHash::const_iterator::difference_type
1902 \internal
1903*/
1904
1905/*! \typedef QHash::const_iterator::iterator_category
1906 \internal
1907*/
1908
1909/*! \typedef QHash::const_iterator::pointer
1910 \internal
1911*/
1912
1913/*! \typedef QHash::const_iterator::reference
1914 \internal
1915*/
1916
1917/*! \typedef QHash::const_iterator::value_type
1918 \internal
1919*/
1920
1921/*! \typedef QHash::key_iterator::difference_type
1922 \internal
1923*/
1924
1925/*! \typedef QHash::key_iterator::iterator_category
1926 \internal
1927*/
1928
1929/*! \typedef QHash::key_iterator::pointer
1930 \internal
1931*/
1932
1933/*! \typedef QHash::key_iterator::reference
1934 \internal
1935*/
1936
1937/*! \typedef QHash::key_iterator::value_type
1938 \internal
1939*/
1940
1941/*! \class QHash::iterator
1942 \inmodule QtCore
1943 \brief The QHash::iterator class provides an STL-style non-const iterator for QHash and QMultiHash.
1944
1945 QHash features both \l{STL-style iterators} and \l{Java-style
1946 iterators}. The STL-style iterators are more low-level and more
1947 cumbersome to use; on the other hand, they are slightly faster
1948 and, for developers who already know STL, have the advantage of
1949 familiarity.
1950
1951 QHash\<Key, T\>::iterator allows you to iterate over a QHash (or
1952 QMultiHash) and to modify the value (but not the key) associated
1953 with a particular key. If you want to iterate over a const QHash,
1954 you should use QHash::const_iterator. It is generally good
1955 practice to use QHash::const_iterator on a non-const QHash as
1956 well, unless you need to change the QHash through the iterator.
1957 Const iterators are slightly faster, and can improve code
1958 readability.
1959
1960 The default QHash::iterator constructor creates an uninitialized
1961 iterator. You must initialize it using a QHash function like
1962 QHash::begin(), QHash::end(), or QHash::find() before you can
1963 start iterating. Here's a typical loop that prints all the (key,
1964 value) pairs stored in a hash:
1965
1966 \snippet code/src_corelib_tools_qhash.cpp 17
1967
1968 Unlike QMap, which orders its items by key, QHash stores its
1969 items in an arbitrary order. The only guarantee is that items that
1970 share the same key (because they were inserted using
1971 QHash::insertMulti()) will appear consecutively, from the most
1972 recently to the least recently inserted value.
1973
1974 Let's see a few examples of things we can do with a
1975 QHash::iterator that we cannot do with a QHash::const_iterator.
1976 Here's an example that increments every value stored in the QHash
1977 by 2:
1978
1979 \snippet code/src_corelib_tools_qhash.cpp 18
1980
1981 Here's an example that removes all the items whose key is a
1982 string that starts with an underscore character:
1983
1984 \snippet code/src_corelib_tools_qhash.cpp 19
1985
1986 The call to QHash::erase() removes the item pointed to by the
1987 iterator from the hash, and returns an iterator to the next item.
1988 Here's another way of removing an item while iterating:
1989
1990 \snippet code/src_corelib_tools_qhash.cpp 20
1991
1992 It might be tempting to write code like this:
1993
1994 \snippet code/src_corelib_tools_qhash.cpp 21
1995
1996 However, this will potentially crash in \c{++i}, because \c i is
1997 a dangling iterator after the call to erase().
1998
1999 Multiple iterators can be used on the same hash. However, be
2000 aware that any modification performed directly on the QHash has
2001 the potential of dramatically changing the order in which the
2002 items are stored in the hash, as they might cause QHash to rehash
2003 its internal data structure. There is one notable exception:
2004 QHash::erase(). This function can safely be called while
2005 iterating, and won't affect the order of items in the hash. If you
2006 need to keep iterators over a long period of time, we recommend
2007 that you use QMap rather than QHash.
2008
2009 \warning Iterators on implicitly shared containers do not work
2010 exactly like STL-iterators. You should avoid copying a container
2011 while iterators are active on that container. For more information,
2012 read \l{Implicit sharing iterator problem}.
2013
2014 \sa QHash::const_iterator, QHash::key_iterator, QMutableHashIterator
2015*/
2016
2017/*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator()
2018
2019 Constructs an uninitialized iterator.
2020
2021 Functions like key(), value(), and operator++() must not be
2022 called on an uninitialized iterator. Use operator=() to assign a
2023 value to it before using it.
2024
2025 \sa QHash::begin(), QHash::end()
2026*/
2027
2028/*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator(void *node)
2029
2030 \internal
2031*/
2032
2033/*! \fn template <class Key, class T> const Key &QHash<Key, T>::iterator::key() const
2034
2035 Returns the current item's key as a const reference.
2036
2037 There is no direct way of changing an item's key through an
2038 iterator, although it can be done by calling QHash::erase()
2039 followed by QHash::insert() or QHash::insertMulti().
2040
2041 \sa value()
2042*/
2043
2044/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::value() const
2045
2046 Returns a modifiable reference to the current item's value.
2047
2048 You can change the value of an item by using value() on
2049 the left side of an assignment, for example:
2050
2051 \snippet code/src_corelib_tools_qhash.cpp 22
2052
2053 \sa key(), operator*()
2054*/
2055
2056/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::operator*() const
2057
2058 Returns a modifiable reference to the current item's value.
2059
2060 Same as value().
2061
2062 \sa key()
2063*/
2064
2065/*! \fn template <class Key, class T> T *QHash<Key, T>::iterator::operator->() const
2066
2067 Returns a pointer to the current item's value.
2068
2069 \sa value()
2070*/
2071
2072/*!
2073 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const iterator &other) const
2074 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const const_iterator &other) const
2075
2076 Returns \c true if \a other points to the same item as this
2077 iterator; otherwise returns \c false.
2078
2079 \sa operator!=()
2080*/
2081
2082/*!
2083 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const iterator &other) const
2084 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const const_iterator &other) const
2085
2086 Returns \c true if \a other points to a different item than this
2087 iterator; otherwise returns \c false.
2088
2089 \sa operator==()
2090*/
2091
2092/*!
2093 \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator++()
2094
2095 The prefix ++ operator (\c{++i}) advances the iterator to the
2096 next item in the hash and returns an iterator to the new current
2097 item.
2098
2099 Calling this function on QHash::end() leads to undefined results.
2100
2101 \sa operator--()
2102*/
2103
2104/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator++(int)
2105
2106 \overload
2107
2108 The postfix ++ operator (\c{i++}) advances the iterator to the
2109 next item in the hash and returns an iterator to the previously
2110 current item.
2111*/
2112
2113/*!
2114 \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator--()
2115
2116 The prefix -- operator (\c{--i}) makes the preceding item
2117 current and returns an iterator pointing to the new current item.
2118
2119 Calling this function on QHash::begin() leads to undefined
2120 results.
2121
2122 \sa operator++()
2123*/
2124
2125/*!
2126 \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator--(int)
2127
2128 \overload
2129
2130 The postfix -- operator (\c{i--}) makes the preceding item
2131 current and returns an iterator pointing to the previously
2132 current item.
2133*/
2134
2135/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator+(int j) const
2136
2137 Returns an iterator to the item at \a j positions forward from
2138 this iterator. (If \a j is negative, the iterator goes backward.)
2139
2140 This operation can be slow for large \a j values.
2141
2142 \sa operator-()
2143
2144*/
2145
2146/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator-(int j) const
2147
2148 Returns an iterator to the item at \a j positions backward from
2149 this iterator. (If \a j is negative, the iterator goes forward.)
2150
2151 This operation can be slow for large \a j values.
2152
2153 \sa operator+()
2154*/
2155
2156/*! \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator+=(int j)
2157
2158 Advances the iterator by \a j items. (If \a j is negative, the
2159 iterator goes backward.)
2160
2161 \sa operator-=(), operator+()
2162*/
2163
2164/*! \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator-=(int j)
2165
2166 Makes the iterator go back by \a j items. (If \a j is negative,
2167 the iterator goes forward.)
2168
2169 \sa operator+=(), operator-()
2170*/
2171
2172/*! \class QHash::const_iterator
2173 \inmodule QtCore
2174 \brief The QHash::const_iterator class provides an STL-style const iterator for QHash and QMultiHash.
2175
2176 QHash features both \l{STL-style iterators} and \l{Java-style
2177 iterators}. The STL-style iterators are more low-level and more
2178 cumbersome to use; on the other hand, they are slightly faster
2179 and, for developers who already know STL, have the advantage of
2180 familiarity.
2181
2182 QHash\<Key, T\>::const_iterator allows you to iterate over a
2183 QHash (or a QMultiHash). If you want to modify the QHash as you
2184 iterate over it, you must use QHash::iterator instead. It is
2185 generally good practice to use QHash::const_iterator on a
2186 non-const QHash as well, unless you need to change the QHash
2187 through the iterator. Const iterators are slightly faster, and
2188 can improve code readability.
2189
2190 The default QHash::const_iterator constructor creates an
2191 uninitialized iterator. You must initialize it using a QHash
2192 function like QHash::constBegin(), QHash::constEnd(), or
2193 QHash::find() before you can start iterating. Here's a typical
2194 loop that prints all the (key, value) pairs stored in a hash:
2195
2196 \snippet code/src_corelib_tools_qhash.cpp 23
2197
2198 Unlike QMap, which orders its items by key, QHash stores its
2199 items in an arbitrary order. The only guarantee is that items that
2200 share the same key (because they were inserted using
2201 QHash::insertMulti()) will appear consecutively, from the most
2202 recently to the least recently inserted value.
2203
2204 Multiple iterators can be used on the same hash. However, be aware
2205 that any modification performed directly on the QHash has the
2206 potential of dramatically changing the order in which the items
2207 are stored in the hash, as they might cause QHash to rehash its
2208 internal data structure. If you need to keep iterators over a long
2209 period of time, we recommend that you use QMap rather than QHash.
2210
2211 \warning Iterators on implicitly shared containers do not work
2212 exactly like STL-iterators. You should avoid copying a container
2213 while iterators are active on that container. For more information,
2214 read \l{Implicit sharing iterator problem}.
2215
2216 \sa QHash::iterator, QHashIterator
2217*/
2218
2219/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator()
2220
2221 Constructs an uninitialized iterator.
2222
2223 Functions like key(), value(), and operator++() must not be
2224 called on an uninitialized iterator. Use operator=() to assign a
2225 value to it before using it.
2226
2227 \sa QHash::constBegin(), QHash::constEnd()
2228*/
2229
2230/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(void *node)
2231
2232 \internal
2233*/
2234
2235/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(const iterator &other)
2236
2237 Constructs a copy of \a other.
2238*/
2239
2240/*! \fn template <class Key, class T> const Key &QHash<Key, T>::const_iterator::key() const
2241
2242 Returns the current item's key.
2243
2244 \sa value()
2245*/
2246
2247/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::value() const
2248
2249 Returns the current item's value.
2250
2251 \sa key(), operator*()
2252*/
2253
2254/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::operator*() const
2255
2256 Returns the current item's value.
2257
2258 Same as value().
2259
2260 \sa key()
2261*/
2262
2263/*! \fn template <class Key, class T> const T *QHash<Key, T>::const_iterator::operator->() const
2264
2265 Returns a pointer to the current item's value.
2266
2267 \sa value()
2268*/
2269
2270/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator==(const const_iterator &other) const
2271
2272 Returns \c true if \a other points to the same item as this
2273 iterator; otherwise returns \c false.
2274
2275 \sa operator!=()
2276*/
2277
2278/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator!=(const const_iterator &other) const
2279
2280 Returns \c true if \a other points to a different item than this
2281 iterator; otherwise returns \c false.
2282
2283 \sa operator==()
2284*/
2285
2286/*!
2287 \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator++()
2288
2289 The prefix ++ operator (\c{++i}) advances the iterator to the
2290 next item in the hash and returns an iterator to the new current
2291 item.
2292
2293 Calling this function on QHash::end() leads to undefined results.
2294
2295 \sa operator--()
2296*/
2297
2298/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator++(int)
2299
2300 \overload
2301
2302 The postfix ++ operator (\c{i++}) advances the iterator to the
2303 next item in the hash and returns an iterator to the previously
2304 current item.
2305*/
2306
2307/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator--()
2308
2309 The prefix -- operator (\c{--i}) makes the preceding item
2310 current and returns an iterator pointing to the new current item.
2311
2312 Calling this function on QHash::begin() leads to undefined
2313 results.
2314
2315 \sa operator++()
2316*/
2317
2318/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator--(int)
2319
2320 \overload
2321
2322 The postfix -- operator (\c{i--}) makes the preceding item
2323 current and returns an iterator pointing to the previously
2324 current item.
2325*/
2326
2327/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator+(int j) const
2328
2329 Returns an iterator to the item at \a j positions forward from
2330 this iterator. (If \a j is negative, the iterator goes backward.)
2331
2332 This operation can be slow for large \a j values.
2333
2334 \sa operator-()
2335*/
2336
2337/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator-(int j) const
2338
2339 Returns an iterator to the item at \a j positions backward from
2340 this iterator. (If \a j is negative, the iterator goes forward.)
2341
2342 This operation can be slow for large \a j values.
2343
2344 \sa operator+()
2345*/
2346
2347/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator+=(int j)
2348
2349 Advances the iterator by \a j items. (If \a j is negative, the
2350 iterator goes backward.)
2351
2352 This operation can be slow for large \a j values.
2353
2354 \sa operator-=(), operator+()
2355*/
2356
2357/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator-=(int j)
2358
2359 Makes the iterator go back by \a j items. (If \a j is negative,
2360 the iterator goes forward.)
2361
2362 This operation can be slow for large \a j values.
2363
2364 \sa operator+=(), operator-()
2365*/
2366
2367/*! \class QHash::key_iterator
2368 \inmodule QtCore
2369 \since 5.6
2370 \brief The QHash::key_iterator class provides an STL-style const iterator for QHash and QMultiHash keys.
2371
2372 QHash::key_iterator is essentially the same as QHash::const_iterator
2373 with the difference that operator*() and operator->() return a key
2374 instead of a value.
2375
2376 For most uses QHash::iterator and QHash::const_iterator should be used,
2377 you can easily access the key by calling QHash::iterator::key():
2378
2379 \snippet code/src_corelib_tools_qhash.cpp 27
2380
2381 However, to have interoperability between QHash's keys and STL-style
2382 algorithms we need an iterator that dereferences to a key instead
2383 of a value. With QHash::key_iterator we can apply an algorithm to a
2384 range of keys without having to call QHash::keys(), which is inefficient
2385 as it costs one QHash iteration and memory allocation to create a temporary
2386 QList.
2387
2388 \snippet code/src_corelib_tools_qhash.cpp 28
2389
2390 QHash::key_iterator is const, it's not possible to modify the key.
2391
2392 The default QHash::key_iterator constructor creates an uninitialized
2393 iterator. You must initialize it using a QHash function like
2394 QHash::keyBegin() or QHash::keyEnd().
2395
2396 \warning Iterators on implicitly shared containers do not work
2397 exactly like STL-iterators. You should avoid copying a container
2398 while iterators are active on that container. For more information,
2399 read \l{Implicit sharing iterator problem}.
2400
2401 \sa QHash::const_iterator, QHash::iterator
2402*/
2403
2404/*! \fn template <class Key, class T> const T &QHash<Key, T>::key_iterator::operator*() const
2405
2406 Returns the current item's key.
2407*/
2408
2409/*! \fn template <class Key, class T> const T *QHash<Key, T>::key_iterator::operator->() const
2410
2411 Returns a pointer to the current item's key.
2412*/
2413
2414/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator==(key_iterator other) const
2415
2416 Returns \c true if \a other points to the same item as this
2417 iterator; otherwise returns \c false.
2418
2419 \sa operator!=()
2420*/
2421
2422/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator!=(key_iterator other) const
2423
2424 Returns \c true if \a other points to a different item than this
2425 iterator; otherwise returns \c false.
2426
2427 \sa operator==()
2428*/
2429
2430/*!
2431 \fn template <class Key, class T> QHash<Key, T>::key_iterator &QHash<Key, T>::key_iterator::operator++()
2432
2433 The prefix ++ operator (\c{++i}) advances the iterator to the
2434 next item in the hash and returns an iterator to the new current
2435 item.
2436
2437 Calling this function on QHash::keyEnd() leads to undefined results.
2438
2439 \sa operator--()
2440*/
2441
2442/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator++(int)
2443
2444 \overload
2445
2446 The postfix ++ operator (\c{i++}) advances the iterator to the
2447 next item in the hash and returns an iterator to the previous
2448 item.
2449*/
2450
2451/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator &QHash<Key, T>::key_iterator::operator--()
2452
2453 The prefix -- operator (\c{--i}) makes the preceding item
2454 current and returns an iterator pointing to the new current item.
2455
2456 Calling this function on QHash::keyBegin() leads to undefined
2457 results.
2458
2459 \sa operator++()
2460*/
2461
2462/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator--(int)
2463
2464 \overload
2465
2466 The postfix -- operator (\c{i--}) makes the preceding item
2467 current and returns an iterator pointing to the previous
2468 item.
2469*/
2470
2471/*! \fn template <class Key, class T> const_iterator QHash<Key, T>::key_iterator::base() const
2472 Returns the underlying const_iterator this key_iterator is based on.
2473*/
2474
2475/*! \typedef QHash::const_key_value_iterator
2476 \inmodule QtCore
2477 \since 5.10
2478 \brief The QMap::const_key_value_iterator typedef provides an STL-style const iterator for QHash and QMultiHash.
2479
2480 QHash::const_key_value_iterator is essentially the same as QHash::const_iterator
2481 with the difference that operator*() returns a key/value pair instead of a
2482 value.
2483
2484 \sa QKeyValueIterator
2485*/
2486
2487/*! \typedef QHash::key_value_iterator
2488 \inmodule QtCore
2489 \since 5.10
2490 \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QHash and QMultiHash.
2491
2492 QHash::key_value_iterator is essentially the same as QHash::iterator
2493 with the difference that operator*() returns a key/value pair instead of a
2494 value.
2495
2496 \sa QKeyValueIterator
2497*/
2498
2499/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash)
2500 \relates QHash
2501
2502 Writes the hash \a hash to stream \a out.
2503
2504 This function requires the key and value types to implement \c
2505 operator<<().
2506
2507 \sa {Serializing Qt Data Types}
2508*/
2509
2510/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QHash<Key, T> &hash)
2511 \relates QHash
2512
2513 Reads a hash from stream \a in into \a hash.
2514
2515 This function requires the key and value types to implement \c
2516 operator>>().
2517
2518 \sa {Serializing Qt Data Types}
2519*/
2520
2521/*! \class QMultiHash
2522 \inmodule QtCore
2523 \brief The QMultiHash class is a convenience QHash subclass that provides multi-valued hashes.
2524
2525 \ingroup tools
2526 \ingroup shared
2527
2528 \reentrant
2529
2530 QMultiHash\<Key, T\> is one of Qt's generic \l{container classes}.
2531 It inherits QHash and extends it with a few convenience functions
2532 that make it more suitable than QHash for storing multi-valued
2533 hashes. A multi-valued hash is a hash that allows multiple values
2534 with the same key; QHash normally doesn't allow that, unless you
2535 call QHash::insertMulti().
2536
2537 Because QMultiHash inherits QHash, all of QHash's functionality also
2538 applies to QMultiHash. For example, you can use isEmpty() to test
2539 whether the hash is empty, and you can traverse a QMultiHash using
2540 QHash's iterator classes (for example, QHashIterator). But in
2541 addition, it provides an insert() function that corresponds to
2542 QHash::insertMulti(), and a replace() function that corresponds to
2543 QHash::insert(). It also provides convenient operator+() and
2544 operator+=().
2545
2546 Example:
2547 \snippet code/src_corelib_tools_qhash.cpp 24
2548
2549 Unlike QHash, QMultiHash provides no operator[]. Use value() or
2550 replace() if you want to access the most recently inserted item
2551 with a certain key.
2552
2553 If you want to retrieve all the values for a single key, you can
2554 use values(const Key &key), which returns a QList<T>:
2555
2556 \snippet code/src_corelib_tools_qhash.cpp 25
2557
2558 The items that share the same key are available from most
2559 recently to least recently inserted.
2560
2561 A more efficient approach is to call find() to get
2562 the STL-style iterator for the first item with a key and iterate from
2563 there:
2564
2565 \snippet code/src_corelib_tools_qhash.cpp 26
2566
2567 QMultiHash's key and value data types must be \l{assignable data
2568 types}. You cannot, for example, store a QWidget as a value;
2569 instead, store a QWidget *. In addition, QMultiHash's key type
2570 must provide operator==(), and there must also be a qHash() function
2571 in the type's namespace that returns a hash value for an argument of the
2572 key's type. See the QHash documentation for details.
2573
2574 \sa QHash, QHashIterator, QMutableHashIterator, QMultiMap
2575*/
2576
2577/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash()
2578
2579 Constructs an empty hash.
2580*/
2581
2582/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(std::initializer_list<std::pair<Key,T> > list)
2583 \since 5.1
2584
2585 Constructs a multi-hash with a copy of each of the elements in the
2586 initializer list \a list.
2587
2588 This function is only available if the program is being
2589 compiled in C++11 mode.
2590*/
2591
2592/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(const QHash<Key, T> &other)
2593
2594 Constructs a copy of \a other (which can be a QHash or a
2595 QMultiHash).
2596
2597 \sa operator=()
2598*/
2599
2600/*! \fn template <class Key, class T> template <class InputIterator> QMultiHash::QMultiHash(InputIterator begin, InputIterator end)
2601 \since 5.14
2602
2603 Constructs a multi-hash with a copy of each of the elements in the iterator range
2604 [\a begin, \a end). Either the elements iterated by the range must be
2605 objects with \c{first} and \c{second} data members (like \c{QPair},
2606 \c{std::pair}, etc.) convertible to \c Key and to \c T respectively; or the
2607 iterators must have \c{key()} and \c{value()} member functions, returning a
2608 key convertible to \c Key and a value convertible to \c T respectively.
2609*/
2610
2611/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::replace(const Key &key, const T &value)
2612
2613 Inserts a new item with the \a key and a value of \a value.
2614
2615 If there is already an item with the \a key, that item's value
2616 is replaced with \a value.
2617
2618 If there are multiple items with the \a key, the most
2619 recently inserted item's value is replaced with \a value.
2620
2621 \sa insert()
2622*/
2623
2624/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &key, const T &value)
2625
2626 Inserts a new item with the \a key and a value of \a value.
2627
2628 If there is already an item with the same key in the hash, this
2629 function will simply create a new one. (This behavior is
2630 different from replace(), which overwrites the value of an
2631 existing item.)
2632
2633 \sa replace()
2634*/
2635
2636/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::operator+=(const QMultiHash &other)
2637
2638 Inserts all the items in the \a other hash into this hash
2639 and returns a reference to this hash.
2640
2641 \sa insert()
2642*/
2643
2644/*! \fn template <class Key, class T> QMultiHash QMultiHash<Key, T>::operator+(const QMultiHash &other) const
2645
2646 Returns a hash that contains all the items in this hash in
2647 addition to all the items in \a other. If a key is common to both
2648 hashes, the resulting hash will contain the key multiple times.
2649
2650 \sa operator+=()
2651*/
2652
2653/*!
2654 \fn template <class Key, class T> bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
2655 \since 4.3
2656
2657 Returns \c true if the hash contains an item with the \a key and
2658 \a value; otherwise returns \c false.
2659
2660 \sa QHash::contains()
2661*/
2662
2663/*!
2664 \fn template <class Key, class T> int QMultiHash<Key, T>::remove(const Key &key, const T &value)
2665 \since 4.3
2666
2667 Removes all the items that have the \a key and the value \a
2668 value from the hash. Returns the number of items removed.
2669
2670 \sa QHash::remove()
2671*/
2672
2673/*!
2674 \fn template <class Key, class T> int QMultiHash<Key, T>::count(const Key &key, const T &value) const
2675 \since 4.3
2676
2677 Returns the number of items with the \a key and \a value.
2678
2679 \sa QHash::count()
2680*/
2681
2682/*!
2683 \fn template <class Key, class T> typename QHash<Key, T>::iterator QMultiHash<Key, T>::find(const Key &key, const T &value)
2684 \since 4.3
2685
2686 Returns an iterator pointing to the item with the \a key and \a value.
2687 If the hash contains no such item, the function returns end().
2688
2689 If the hash contains multiple items with the \a key and \a value, the
2690 iterator returned points to the most recently inserted item.
2691
2692 \sa QHash::find()
2693*/
2694
2695/*!
2696 \fn template <class Key, class T> typename QHash<Key, T>::const_iterator QMultiHash<Key, T>::find(const Key &key, const T &value) const
2697 \since 4.3
2698 \overload
2699*/
2700
2701/*!
2702 \fn template <class Key, class T> typename QHash<Key, T>::const_iterator QMultiHash<Key, T>::constFind(const Key &key, const T &value) const
2703 \since 4.3
2704
2705 Returns an iterator pointing to the item with the \a key and the
2706 \a value in the hash.
2707
2708 If the hash contains no such item, the function returns
2709 constEnd().
2710
2711 \sa QHash::constFind()
2712*/
2713
2714/*!
2715 \fn template <class Key, class T> uint qHash(const QHash<Key, T> &key, uint seed = 0)
2716 \since 5.8
2717 \relates QHash
2718
2719 Returns the hash value for the \a key, using \a seed to seed the calculation.
2720
2721 Type \c T must be supported by qHash().
2722*/
2723
2724/*!
2725 \fn template <class Key, class T> uint qHash(const QMultiHash<Key, T> &key, uint seed = 0)
2726 \since 5.8
2727 \relates QMultiHash
2728
2729 Returns the hash value for the \a key, using \a seed to seed the calculation.
2730
2731 Type \c T must be supported by qHash().
2732*/
2733
2734QT_END_NAMESPACE
2735