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(C: h2, D: qFromUnaligned<qlonglong>(src: p - 8));
113 h = h2;
114 p -= 8;
115
116 len = e - p;
117 if (len & 4) {
118 h = _mm_crc32_u32(C: h, D: qFromUnaligned<uint>(src: 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(C: h, D: qFromUnaligned<ushort>(src: p));
130 p += 2;
131 }
132 if (sizeof(Char) == 1 && len & 1)
133 h = _mm_crc32_u8(C: h, D: *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(ptr: 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(p: static_cast<const uchar*>(p), len: 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(ptr: 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(p: reinterpret_cast<const uchar *>(key.constData()), len: 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(p: key.unicode(), len: size_t(key.size()), seed);
240}
241
242uint qHash(const QStringRef &key, uint seed) noexcept
243{
244 return hash(p: key.unicode(), len: size_t(key.size()), seed);
245}
246#endif
247
248uint qHash(QStringView key, uint seed) noexcept
249{
250 return hash(p: key.data(), len: 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(p: reinterpret_cast<const uchar *>(bitArray.d.constData()),
257 len: size_t(qMax(a: 0, b: 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(i: m)) & ((1 << n) - 1);
264 return result;
265}
266
267uint qHash(QLatin1String key, uint seed) noexcept
268{
269 return hash(p: reinterpret_cast<const uchar *>(key.data()), len: 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(varName: "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, format: "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(expectedValue: -1, newValue: 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(varName: "QT_HASH_SEED"))
372 return;
373 if (newSeed == -1) {
374 int x(qt_create_qhash_seed() & INT_MAX);
375 qt_qhash_seed.storeRelaxed(newValue: x);
376 } else {
377 if (newSeed) {
378 // can't use qWarning here (reentrancy)
379 fprintf(stderr, format: "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(newValue: 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 .fakeNext: nullptr, .buckets: nullptr, Q_REFCOUNT_INITIALIZE_STATIC, .size: 0, .nodeSize: 0, .userNumBits: MinNumBits, .numBits: 0, .numBuckets: 0, .seed: 0, .sharable: true, .strictAlignment: false, .reserved: 0
475};
476
477void *QHashData::allocateNode(int nodeAlign)
478{
479 void *ptr = strictAlignment ? qMallocAligned(size: nodeSize, alignment: nodeAlign) : malloc(size: nodeSize);
480 Q_CHECK_PTR(ptr);
481 return ptr;
482}
483
484void QHashData::freeNode(void *node)
485{
486 if (strictAlignment)
487 qFreeAligned(ptr: node);
488 else
489 free(ptr: 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( node: 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(node: 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: -hint);
650 if (hint < MinNumBits)
651 hint = MinNumBits;
652 userNumBits = hint;
653 while (primeForNumBits(numBits: 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(numBits: 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(p: reinterpret_cast<const uchar *>(&key), len: 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(p: reinterpret_cast<const uchar *>(&key), len: 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(p: reinterpret_cast<const uchar *>(&key), len: 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 If you only need to extract the values from a hash (not the keys),
1124 you can also use \l{foreach}:
1125
1126 \snippet code/src_corelib_tools_qhash.cpp 12
1127
1128 Items can be removed from the hash in several ways. One way is to
1129 call remove(); this will remove any item with the given key.
1130 Another way is to use QMutableHashIterator::remove(). In addition,
1131 you can clear the entire hash using clear().
1132
1133 QHash's key and value data types must be \l{assignable data
1134 types}. You cannot, for example, store a QWidget as a value;
1135 instead, store a QWidget *.
1136
1137 \target qHash
1138 \section2 The qHash() hashing function
1139
1140 A QHash's key type has additional requirements other than being an
1141 assignable data type: it must provide operator==(), and there must also be
1142 a qHash() function in the type's namespace that returns a hash value for an
1143 argument of the key's type.
1144
1145 The qHash() function computes a numeric value based on a key. It
1146 can use any algorithm imaginable, as long as it always returns
1147 the same value if given the same argument. In other words, if
1148 \c{e1 == e2}, then \c{qHash(e1) == qHash(e2)} must hold as well.
1149 However, to obtain good performance, the qHash() function should
1150 attempt to return different hash values for different keys to the
1151 largest extent possible.
1152
1153 For a key type \c{K}, the qHash function must have one of these signatures:
1154
1155 \snippet code/src_corelib_tools_qhash.cpp 32
1156
1157 The two-arguments overloads take an unsigned integer that should be used to
1158 seed the calculation of the hash function. This seed is provided by QHash
1159 in order to prevent a family of \l{algorithmic complexity attacks}. If both
1160 a one-argument and a two-arguments overload are defined for a key type,
1161 the latter is used by QHash (note that you can simply define a
1162 two-arguments version, and use a default value for the seed parameter).
1163
1164 Here's a partial list of the C++ and Qt types that can serve as keys in a
1165 QHash: any integer type (char, unsigned long, etc.), any pointer type,
1166 QChar, QString, and QByteArray. For all of these, the \c <QHash> header
1167 defines a qHash() function that computes an adequate hash value. Many other
1168 Qt classes also declare a qHash overload for their type; please refer to
1169 the documentation of each class.
1170
1171 If you want to use other types as the key, make sure that you provide
1172 operator==() and a qHash() implementation.
1173
1174 Example:
1175 \snippet code/src_corelib_tools_qhash.cpp 13
1176
1177 In the example above, we've relied on Qt's global qHash(const
1178 QString &, uint) to give us a hash value for the employee's name, and
1179 XOR'ed this with the day they were born to help produce unique
1180 hashes for people with the same name.
1181
1182 Note that the implementation of the qHash() overloads offered by Qt
1183 may change at any time. You \b{must not} rely on the fact that qHash()
1184 will give the same results (for the same inputs) across different Qt
1185 versions.
1186
1187 \section2 Algorithmic complexity attacks
1188
1189 All hash tables are vulnerable to a particular class of denial of service
1190 attacks, in which the attacker carefully pre-computes a set of different
1191 keys that are going to be hashed in the same bucket of a hash table (or
1192 even have the very same hash value). The attack aims at getting the
1193 worst-case algorithmic behavior (O(n) instead of amortized O(1), see
1194 \l{Algorithmic Complexity} for the details) when the data is fed into the
1195 table.
1196
1197 In order to avoid this worst-case behavior, the calculation of the hash
1198 value done by qHash() can be salted by a random seed, that nullifies the
1199 attack's extent. This seed is automatically generated by QHash once per
1200 process, and then passed by QHash as the second argument of the
1201 two-arguments overload of the qHash() function.
1202
1203 This randomization of QHash is enabled by default. Even though programs
1204 should never depend on a particular QHash ordering, there may be situations
1205 where you temporarily need deterministic behavior, for example for debugging or
1206 regression testing. To disable the randomization, define the environment
1207 variable \c QT_HASH_SEED to have the value 0. Alternatively, you can call
1208 the qSetGlobalQHashSeed() function with the value 0.
1209
1210 \sa QHashIterator, QMutableHashIterator, QMap, QSet
1211*/
1212
1213/*! \fn template <class Key, class T> QHash<Key, T>::QHash()
1214
1215 Constructs an empty hash.
1216
1217 \sa clear()
1218*/
1219
1220/*!
1221 \fn template <class Key, class T> QHash<Key, T>::QHash(QHash &&other)
1222
1223 Move-constructs a QHash instance, making it point at the same
1224 object that \a other was pointing to.
1225
1226 \since 5.2
1227*/
1228
1229/*! \fn template <class Key, class T> QHash<Key, T>::QHash(std::initializer_list<std::pair<Key,T> > list)
1230 \since 5.1
1231
1232 Constructs a hash with a copy of each of the elements in the
1233 initializer list \a list.
1234
1235 This function is only available if the program is being
1236 compiled in C++11 mode.
1237*/
1238
1239/*! \fn template <class Key, class T> template <class InputIterator> QHash<Key, T>::QHash(InputIterator begin, InputIterator end)
1240 \since 5.14
1241
1242 Constructs a hash with a copy of each of the elements in the iterator range
1243 [\a begin, \a end). Either the elements iterated by the range must be
1244 objects with \c{first} and \c{second} data members (like \c{QPair},
1245 \c{std::pair}, etc.) convertible to \c Key and to \c T respectively; or the
1246 iterators must have \c{key()} and \c{value()} member functions, returning a
1247 key convertible to \c Key and a value convertible to \c T respectively.
1248*/
1249
1250/*! \fn template <class Key, class T> QHash<Key, T>::QHash(const QHash &other)
1251
1252 Constructs a copy of \a other.
1253
1254 This operation occurs in \l{constant time}, because QHash is
1255 \l{implicitly shared}. This makes returning a QHash from a
1256 function very fast. If a shared instance is modified, it will be
1257 copied (copy-on-write), and this takes \l{linear time}.
1258
1259 \sa operator=()
1260*/
1261
1262/*! \fn template <class Key, class T> QHash<Key, T>::~QHash()
1263
1264 Destroys the hash. References to the values in the hash and all
1265 iterators of this hash become invalid.
1266*/
1267
1268/*! \fn template <class Key, class T> QHash &QHash<Key, T>::operator=(const QHash &other)
1269
1270 Assigns \a other to this hash and returns a reference to this hash.
1271*/
1272
1273/*!
1274 \fn template <class Key, class T> QHash &QHash<Key, T>::operator=(QHash &&other)
1275
1276 Move-assigns \a other to this QHash instance.
1277
1278 \since 5.2
1279*/
1280
1281/*! \fn template <class Key, class T> void QHash<Key, T>::swap(QHash &other)
1282 \since 4.8
1283
1284 Swaps hash \a other with this hash. This operation is very
1285 fast and never fails.
1286*/
1287
1288/*! \fn template <class Key, class T> void QMultiHash<Key, T>::swap(QMultiHash &other)
1289 \since 4.8
1290
1291 Swaps hash \a other with this hash. This operation is very
1292 fast and never fails.
1293*/
1294
1295/*! \fn template <class Key, class T> bool QHash<Key, T>::operator==(const QHash &other) const
1296
1297 Returns \c true if \a other is equal to this hash; otherwise returns
1298 false.
1299
1300 Two hashes are considered equal if they contain the same (key,
1301 value) pairs.
1302
1303 This function requires the value type to implement \c operator==().
1304
1305 \sa operator!=()
1306*/
1307
1308/*! \fn template <class Key, class T> bool QHash<Key, T>::operator!=(const QHash &other) const
1309
1310 Returns \c true if \a other is not equal to this hash; otherwise
1311 returns \c false.
1312
1313 Two hashes are considered equal if they contain the same (key,
1314 value) pairs.
1315
1316 This function requires the value type to implement \c operator==().
1317
1318 \sa operator==()
1319*/
1320
1321/*! \fn template <class Key, class T> int QHash<Key, T>::size() const
1322
1323 Returns the number of items in the hash.
1324
1325 \sa isEmpty(), count()
1326*/
1327
1328/*! \fn template <class Key, class T> bool QHash<Key, T>::isEmpty() const
1329
1330 Returns \c true if the hash contains no items; otherwise returns
1331 false.
1332
1333 \sa size()
1334*/
1335
1336/*! \fn template <class Key, class T> int QHash<Key, T>::capacity() const
1337
1338 Returns the number of buckets in the QHash's internal hash table.
1339
1340 The sole purpose of this function is to provide a means of fine
1341 tuning QHash's memory usage. In general, you will rarely ever
1342 need to call this function. If you want to know how many items are
1343 in the hash, call size().
1344
1345 \sa reserve(), squeeze()
1346*/
1347
1348/*! \fn template <class Key, class T> void QHash<Key, T>::reserve(int size)
1349
1350 Ensures that the QHash's internal hash table consists of at least
1351 \a size buckets.
1352
1353 This function is useful for code that needs to build a huge hash
1354 and wants to avoid repeated reallocation. For example:
1355
1356 \snippet code/src_corelib_tools_qhash.cpp 14
1357
1358 Ideally, \a size should be slightly more than the maximum number
1359 of items expected in the hash. \a size doesn't have to be prime,
1360 because QHash will use a prime number internally anyway. If \a size
1361 is an underestimate, the worst that will happen is that the QHash
1362 will be a bit slower.
1363
1364 In general, you will rarely ever need to call this function.
1365 QHash's internal hash table automatically shrinks or grows to
1366 provide good performance without wasting too much memory.
1367
1368 \sa squeeze(), capacity()
1369*/
1370
1371/*! \fn template <class Key, class T> void QHash<Key, T>::squeeze()
1372
1373 Reduces the size of the QHash's internal hash table to save
1374 memory.
1375
1376 The sole purpose of this function is to provide a means of fine
1377 tuning QHash's memory usage. In general, you will rarely ever
1378 need to call this function.
1379
1380 \sa reserve(), capacity()
1381*/
1382
1383/*! \fn template <class Key, class T> void QHash<Key, T>::detach()
1384
1385 \internal
1386
1387 Detaches this hash from any other hashes with which it may share
1388 data.
1389
1390 \sa isDetached()
1391*/
1392
1393/*! \fn template <class Key, class T> bool QHash<Key, T>::isDetached() const
1394
1395 \internal
1396
1397 Returns \c true if the hash's internal data isn't shared with any
1398 other hash object; otherwise returns \c false.
1399
1400 \sa detach()
1401*/
1402
1403/*! \fn template <class Key, class T> void QHash<Key, T>::setSharable(bool sharable)
1404
1405 \internal
1406*/
1407
1408/*! \fn template <class Key, class T> bool QHash<Key, T>::isSharedWith(const QHash &other) const
1409
1410 \internal
1411*/
1412
1413/*! \fn template <class Key, class T> void QHash<Key, T>::clear()
1414
1415 Removes all items from the hash.
1416
1417 \sa remove()
1418*/
1419
1420/*! \fn template <class Key, class T> int QHash<Key, T>::remove(const Key &key)
1421
1422 Removes all the items that have the \a key from the hash.
1423 Returns the number of items removed which is 1 if the key exists in the hash,
1424 and 0 otherwise.
1425
1426 \sa clear(), take(), QMultiHash::remove()
1427*/
1428
1429/*! \fn template <class Key, class T> T QHash<Key, T>::take(const Key &key)
1430
1431 Removes the item with the \a key from the hash and returns
1432 the value associated with it.
1433
1434 If the item does not exist in the hash, the function simply
1435 returns a \l{default-constructed value}. If there are multiple
1436 items for \a key in the hash, only the most recently inserted one
1437 is removed.
1438
1439 If you don't use the return value, remove() is more efficient.
1440
1441 \sa remove()
1442*/
1443
1444/*! \fn template <class Key, class T> bool QHash<Key, T>::contains(const Key &key) const
1445
1446 Returns \c true if the hash contains an item with the \a key;
1447 otherwise returns \c false.
1448
1449 \sa count(), QMultiHash::contains()
1450*/
1451
1452/*! \fn template <class Key, class T> const T QHash<Key, T>::value(const Key &key) const
1453
1454 Returns the value associated with the \a key.
1455
1456 If the hash contains no item with the \a key, the function
1457 returns a \l{default-constructed value}. If there are multiple
1458 items for the \a key in the hash, the value of the most recently
1459 inserted one is returned.
1460
1461 \sa key(), values(), contains(), operator[]()
1462*/
1463
1464/*! \fn template <class Key, class T> const T QHash<Key, T>::value(const Key &key, const T &defaultValue) const
1465 \overload
1466
1467 If the hash contains no item with the given \a key, the function returns
1468 \a defaultValue.
1469*/
1470
1471/*! \fn template <class Key, class T> T &QHash<Key, T>::operator[](const Key &key)
1472
1473 Returns the value associated with the \a key as a modifiable
1474 reference.
1475
1476 If the hash contains no item with the \a key, the function inserts
1477 a \l{default-constructed value} into the hash with the \a key, and
1478 returns a reference to it. If the hash contains multiple items
1479 with the \a key, this function returns a reference to the most
1480 recently inserted value.
1481
1482 \sa insert(), value()
1483*/
1484
1485/*! \fn template <class Key, class T> const T QHash<Key, T>::operator[](const Key &key) const
1486
1487 \overload
1488
1489 Same as value().
1490*/
1491
1492/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::uniqueKeys() const
1493 \since 4.2
1494 \obsolete Use QMultiHash for storing multiple values with the same key.
1495
1496 Returns a list containing all the keys in the map. Keys that occur multiple
1497 times in the map (because items were inserted with insertMulti(), or
1498 unite() was used) occur only once in the returned list.
1499
1500 \sa QMultiHash::uniqueKeys()
1501*/
1502
1503/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys() const
1504
1505 Returns a list containing all the keys in the hash, in an
1506 arbitrary order. Keys that occur multiple times in the hash
1507 (because the method is operating on a QMultiHash) also occur
1508 multiple times in the list.
1509
1510 The order is guaranteed to be the same as that used by values().
1511
1512 \sa QMultiMap::uniqueKeys(), values(), key()
1513*/
1514
1515/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys(const T &value) const
1516
1517 \overload
1518
1519 Returns a list containing all the keys associated with value \a
1520 value, in an arbitrary order.
1521
1522 This function can be slow (\l{linear time}), because QHash's
1523 internal data structure is optimized for fast lookup by key, not
1524 by value.
1525*/
1526
1527/*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values() const
1528
1529 Returns a list containing all the values in the hash, in an
1530 arbitrary order. If a key is associated with multiple values, all of
1531 its values will be in the list, and not just the most recently
1532 inserted one.
1533
1534 The order is guaranteed to be the same as that used by keys().
1535
1536 \sa keys(), value()
1537*/
1538
1539/*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values(const Key &key) const
1540 \overload
1541 \obsolete Use QMultiHash for storing multiple values with the same key.
1542
1543 Returns a list of all the values associated with the \a key,
1544 from the most recently inserted to the least recently inserted.
1545
1546 \sa count(), insertMulti()
1547*/
1548
1549/*! \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value) const
1550
1551 Returns the first key mapped to \a value.
1552
1553 If the hash contains no item with the \a value, the function
1554 returns a \l{default-constructed value}{default-constructed key}.
1555
1556 This function can be slow (\l{linear time}), because QHash's
1557 internal data structure is optimized for fast lookup by key, not
1558 by value.
1559
1560 \sa value(), keys()
1561*/
1562
1563/*!
1564 \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value, const Key &defaultKey) const
1565 \since 4.3
1566 \overload
1567
1568 Returns the first key mapped to \a value, or \a defaultKey if the
1569 hash contains no item mapped to \a value.
1570
1571 This function can be slow (\l{linear time}), because QHash's
1572 internal data structure is optimized for fast lookup by key, not
1573 by value.
1574*/
1575
1576/*! \fn template <class Key, class T> int QHash<Key, T>::count(const Key &key) const
1577
1578 Returns the number of items associated with the \a key.
1579
1580 \sa contains(), insertMulti()
1581*/
1582
1583/*! \fn template <class Key, class T> int QHash<Key, T>::count() const
1584
1585 \overload
1586
1587 Same as size().
1588*/
1589
1590/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::begin()
1591
1592 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
1593 the hash.
1594
1595 \sa constBegin(), end()
1596*/
1597
1598/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::begin() const
1599
1600 \overload
1601*/
1602
1603/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cbegin() const
1604 \since 5.0
1605
1606 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1607 in the hash.
1608
1609 \sa begin(), cend()
1610*/
1611
1612/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constBegin() const
1613
1614 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1615 in the hash.
1616
1617 \sa begin(), constEnd()
1618*/
1619
1620/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyBegin() const
1621 \since 5.6
1622
1623 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
1624 in the hash.
1625
1626 \sa keyEnd()
1627*/
1628
1629/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::end()
1630
1631 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
1632 after the last item in the hash.
1633
1634 \sa begin(), constEnd()
1635*/
1636
1637/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::end() const
1638
1639 \overload
1640*/
1641
1642/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constEnd() const
1643
1644 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1645 item after the last item in the hash.
1646
1647 \sa constBegin(), end()
1648*/
1649
1650/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cend() const
1651 \since 5.0
1652
1653 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1654 item after the last item in the hash.
1655
1656 \sa cbegin(), end()
1657*/
1658
1659/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyEnd() const
1660 \since 5.6
1661
1662 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1663 item after the last key in the hash.
1664
1665 \sa keyBegin()
1666*/
1667
1668/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueBegin()
1669 \since 5.10
1670
1671 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
1672 in the hash.
1673
1674 \sa keyValueEnd()
1675*/
1676
1677/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueEnd()
1678 \since 5.10
1679
1680 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1681 entry after the last entry in the hash.
1682
1683 \sa keyValueBegin()
1684*/
1685
1686/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueBegin() const
1687 \since 5.10
1688
1689 Returns a const \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>::const_key_value_iterator QHash<Key, T>::constKeyValueBegin() const
1696 \since 5.10
1697
1698 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
1699 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>::keyValueEnd() const
1705 \since 5.10
1706
1707 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1708 entry after the last entry in the hash.
1709
1710 \sa keyValueBegin()
1711*/
1712
1713/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueEnd() const
1714 \since 5.10
1715
1716 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1717 entry after the last entry in the hash.
1718
1719 \sa constKeyValueBegin()
1720*/
1721
1722/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator pos)
1723 \since 5.7
1724
1725 Removes the (key, value) pair associated with the iterator \a pos
1726 from the hash, and returns an iterator to the next item in the
1727 hash.
1728
1729 Unlike remove() and take(), this function never causes QHash to
1730 rehash its internal data structure. This means that it can safely
1731 be called while iterating, and won't affect the order of items in
1732 the hash. For example:
1733
1734 \snippet code/src_corelib_tools_qhash.cpp 15
1735
1736 \sa remove(), take(), find()
1737*/
1738
1739/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(iterator pos)
1740 \overload
1741*/
1742
1743/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::find(const Key &key)
1744
1745 Returns an iterator pointing to the item with the \a key in the
1746 hash.
1747
1748 If the hash contains no item with the \a key, the function
1749 returns end().
1750
1751 If the hash contains multiple items with the \a key, this
1752 function returns an iterator that points to the most recently
1753 inserted value. The other values are accessible by incrementing
1754 the iterator. For example, here's some code that iterates over all
1755 the items with the same key:
1756
1757 \snippet code/src_corelib_tools_qhash.cpp 16
1758
1759 \sa value(), values(), QMultiHash::find()
1760*/
1761
1762/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &key) const
1763
1764 \overload
1765*/
1766
1767/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &key) const
1768 \since 4.1
1769
1770 Returns an iterator pointing to the item with the \a key in the
1771 hash.
1772
1773 If the hash contains no item with the \a key, the function
1774 returns constEnd().
1775
1776 \sa find(), QMultiHash::constFind()
1777*/
1778
1779/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &key, const T &value)
1780
1781 Inserts a new item with the \a key and a value of \a value.
1782
1783 If there is already an item with the \a key, that item's value
1784 is replaced with \a value.
1785
1786 If there are multiple items with the \a key, the most
1787 recently inserted item's value is replaced with \a value.
1788*/
1789
1790/*! \fn template <class Key, class T> void QHash<Key, T>::insert(const QHash &other)
1791 \since 5.15
1792
1793 Inserts all the items in the \a other hash into this hash.
1794
1795 If a key is common to both hashes, its value will be replaced with the
1796 value stored in \a other.
1797
1798 \note If \a other contains multiple entries with the same key then the
1799 final value of the key is undefined.
1800*/
1801
1802/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &key, const T &value)
1803 \obsolete
1804
1805 Inserts a new item with the \a key and a value of \a value.
1806
1807 If there is already an item with the same key in the hash, this
1808 function will simply create a new one. (This behavior is
1809 different from insert(), which overwrites the value of an
1810 existing item.)
1811
1812 This function is obsolete. Use QMultiHash or QMultiMap instead.
1813
1814 \sa insert(), values()
1815*/
1816
1817/*! \fn template <class Key, class T> QHash &QHash<Key, T>::unite(const QHash &other)
1818 \obsolete
1819
1820 Inserts all the items in the \a other hash into this hash. If a
1821 key is common to both hashes, the resulting hash will contain the
1822 key multiple times.
1823*/
1824
1825/*! \fn template <class Key, class T> bool QHash<Key, T>::empty() const
1826
1827 This function is provided for STL compatibility. It is equivalent
1828 to isEmpty(), returning true if the hash is empty; otherwise
1829 returns \c false.
1830*/
1831
1832/*! \fn template <class Key, class T> QPair<iterator, iterator> QHash<Key, T>::equal_range(const Key &key)
1833 \since 5.7
1834
1835 Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
1836 are stored under \a key. If the range is empty then both iterators will be equal to end().
1837*/
1838
1839/*!
1840 \fn template <class Key, class T> QPair<const_iterator, const_iterator> QHash<Key, T>::equal_range(const Key &key) const
1841 \overload
1842 \since 5.7
1843*/
1844
1845/*! \typedef QHash::ConstIterator
1846
1847 Qt-style synonym for QHash::const_iterator.
1848*/
1849
1850/*! \typedef QHash::Iterator
1851
1852 Qt-style synonym for QHash::iterator.
1853*/
1854
1855/*! \typedef QHash::difference_type
1856
1857 Typedef for ptrdiff_t. Provided for STL compatibility.
1858*/
1859
1860/*! \typedef QHash::key_type
1861
1862 Typedef for Key. Provided for STL compatibility.
1863*/
1864
1865/*! \typedef QHash::mapped_type
1866
1867 Typedef for T. Provided for STL compatibility.
1868*/
1869
1870/*! \typedef QHash::size_type
1871
1872 Typedef for int. Provided for STL compatibility.
1873*/
1874
1875/*! \typedef QHash::iterator::difference_type
1876 \internal
1877*/
1878
1879/*! \typedef QHash::iterator::iterator_category
1880 \internal
1881*/
1882
1883/*! \typedef QHash::iterator::pointer
1884 \internal
1885*/
1886
1887/*! \typedef QHash::iterator::reference
1888 \internal
1889*/
1890
1891/*! \typedef QHash::iterator::value_type
1892 \internal
1893*/
1894
1895/*! \typedef QHash::const_iterator::difference_type
1896 \internal
1897*/
1898
1899/*! \typedef QHash::const_iterator::iterator_category
1900 \internal
1901*/
1902
1903/*! \typedef QHash::const_iterator::pointer
1904 \internal
1905*/
1906
1907/*! \typedef QHash::const_iterator::reference
1908 \internal
1909*/
1910
1911/*! \typedef QHash::const_iterator::value_type
1912 \internal
1913*/
1914
1915/*! \typedef QHash::key_iterator::difference_type
1916 \internal
1917*/
1918
1919/*! \typedef QHash::key_iterator::iterator_category
1920 \internal
1921*/
1922
1923/*! \typedef QHash::key_iterator::pointer
1924 \internal
1925*/
1926
1927/*! \typedef QHash::key_iterator::reference
1928 \internal
1929*/
1930
1931/*! \typedef QHash::key_iterator::value_type
1932 \internal
1933*/
1934
1935/*! \class QHash::iterator
1936 \inmodule QtCore
1937 \brief The QHash::iterator class provides an STL-style non-const iterator for QHash and QMultiHash.
1938
1939 QHash features both \l{STL-style iterators} and \l{Java-style
1940 iterators}. The STL-style iterators are more low-level and more
1941 cumbersome to use; on the other hand, they are slightly faster
1942 and, for developers who already know STL, have the advantage of
1943 familiarity.
1944
1945 QHash\<Key, T\>::iterator allows you to iterate over a QHash (or
1946 QMultiHash) and to modify the value (but not the key) associated
1947 with a particular key. If you want to iterate over a const QHash,
1948 you should use QHash::const_iterator. It is generally good
1949 practice to use QHash::const_iterator on a non-const QHash as
1950 well, unless you need to change the QHash through the iterator.
1951 Const iterators are slightly faster, and can improve code
1952 readability.
1953
1954 The default QHash::iterator constructor creates an uninitialized
1955 iterator. You must initialize it using a QHash function like
1956 QHash::begin(), QHash::end(), or QHash::find() before you can
1957 start iterating. Here's a typical loop that prints all the (key,
1958 value) pairs stored in a hash:
1959
1960 \snippet code/src_corelib_tools_qhash.cpp 17
1961
1962 Unlike QMap, which orders its items by key, QHash stores its
1963 items in an arbitrary order.
1964
1965 Let's see a few examples of things we can do with a
1966 QHash::iterator that we cannot do with a QHash::const_iterator.
1967 Here's an example that increments every value stored in the QHash
1968 by 2:
1969
1970 \snippet code/src_corelib_tools_qhash.cpp 18
1971
1972 Here's an example that removes all the items whose key is a
1973 string that starts with an underscore character:
1974
1975 \snippet code/src_corelib_tools_qhash.cpp 19
1976
1977 The call to QHash::erase() removes the item pointed to by the
1978 iterator from the hash, and returns an iterator to the next item.
1979 Here's another way of removing an item while iterating:
1980
1981 \snippet code/src_corelib_tools_qhash.cpp 20
1982
1983 It might be tempting to write code like this:
1984
1985 \snippet code/src_corelib_tools_qhash.cpp 21
1986
1987 However, this will potentially crash in \c{++i}, because \c i is
1988 a dangling iterator after the call to erase().
1989
1990 Multiple iterators can be used on the same hash. However, be
1991 aware that any modification performed directly on the QHash has
1992 the potential of dramatically changing the order in which the
1993 items are stored in the hash, as they might cause QHash to rehash
1994 its internal data structure. There is one notable exception:
1995 QHash::erase(). This function can safely be called while
1996 iterating, and won't affect the order of items in the hash. If you
1997 need to keep iterators over a long period of time, we recommend
1998 that you use QMap rather than QHash.
1999
2000 \warning Iterators on implicitly shared containers do not work
2001 exactly like STL-iterators. You should avoid copying a container
2002 while iterators are active on that container. For more information,
2003 read \l{Implicit sharing iterator problem}.
2004
2005 \sa QHash::const_iterator, QHash::key_iterator, QMutableHashIterator
2006*/
2007
2008/*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator()
2009
2010 Constructs an uninitialized iterator.
2011
2012 Functions like key(), value(), and operator++() must not be
2013 called on an uninitialized iterator. Use operator=() to assign a
2014 value to it before using it.
2015
2016 \sa QHash::begin(), QHash::end()
2017*/
2018
2019/*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator(void *node)
2020
2021 \internal
2022*/
2023
2024/*! \fn template <class Key, class T> const Key &QHash<Key, T>::iterator::key() const
2025
2026 Returns the current item's key as a const reference.
2027
2028 There is no direct way of changing an item's key through an
2029 iterator, although it can be done by calling QHash::erase()
2030 followed by QHash::insert().
2031
2032 \sa value()
2033*/
2034
2035/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::value() const
2036
2037 Returns a modifiable reference to the current item's value.
2038
2039 You can change the value of an item by using value() on
2040 the left side of an assignment, for example:
2041
2042 \snippet code/src_corelib_tools_qhash.cpp 22
2043
2044 \sa key(), operator*()
2045*/
2046
2047/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::operator*() const
2048
2049 Returns a modifiable reference to the current item's value.
2050
2051 Same as value().
2052
2053 \sa key()
2054*/
2055
2056/*! \fn template <class Key, class T> T *QHash<Key, T>::iterator::operator->() const
2057
2058 Returns a pointer to the current item's value.
2059
2060 \sa value()
2061*/
2062
2063/*!
2064 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const iterator &other) const
2065 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const const_iterator &other) const
2066
2067 Returns \c true if \a other points to the same item as this
2068 iterator; otherwise returns \c false.
2069
2070 \sa operator!=()
2071*/
2072
2073/*!
2074 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const iterator &other) const
2075 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const const_iterator &other) const
2076
2077 Returns \c true if \a other points to a different item than this
2078 iterator; otherwise returns \c false.
2079
2080 \sa operator==()
2081*/
2082
2083/*!
2084 \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator++()
2085
2086 The prefix ++ operator (\c{++i}) advances the iterator to the
2087 next item in the hash and returns an iterator to the new current
2088 item.
2089
2090 Calling this function on QHash::end() leads to undefined results.
2091
2092 \sa operator--()
2093*/
2094
2095/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator++(int)
2096
2097 \overload
2098
2099 The postfix ++ operator (\c{i++}) advances the iterator to the
2100 next item in the hash and returns an iterator to the previously
2101 current item.
2102*/
2103
2104/*!
2105 \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator--()
2106 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2107
2108 The prefix -- operator (\c{--i}) makes the preceding item
2109 current and returns an iterator pointing to the new current item.
2110
2111 Calling this function on QHash::begin() leads to undefined
2112 results.
2113
2114 \sa operator++()
2115*/
2116
2117/*!
2118 \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator--(int)
2119 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2120
2121 \overload
2122
2123 The postfix -- operator (\c{i--}) makes the preceding item
2124 current and returns an iterator pointing to the previously
2125 current item.
2126*/
2127
2128/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator+(int j) const
2129 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2130
2131 Returns an iterator to the item at \a j positions forward from
2132 this iterator. (If \a j is negative, the iterator goes backward.)
2133
2134 This operation can be slow for large \a j values.
2135
2136 \sa operator-()
2137
2138*/
2139
2140/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator-(int j) const
2141 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2142
2143 Returns an iterator to the item at \a j positions backward from
2144 this iterator. (If \a j is negative, the iterator goes forward.)
2145
2146 This operation can be slow for large \a j values.
2147
2148 \sa operator+()
2149*/
2150
2151/*! \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator+=(int j)
2152 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2153
2154 Advances the iterator by \a j items. (If \a j is negative, the
2155 iterator goes backward.)
2156
2157 \sa operator-=(), operator+()
2158*/
2159
2160/*! \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator-=(int j)
2161 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2162
2163 Makes the iterator go back by \a j items. (If \a j is negative,
2164 the iterator goes forward.)
2165
2166 \sa operator+=(), operator-()
2167*/
2168
2169/*! \class QHash::const_iterator
2170 \inmodule QtCore
2171 \brief The QHash::const_iterator class provides an STL-style const iterator for QHash and QMultiHash.
2172
2173 QHash features both \l{STL-style iterators} and \l{Java-style
2174 iterators}. The STL-style iterators are more low-level and more
2175 cumbersome to use; on the other hand, they are slightly faster
2176 and, for developers who already know STL, have the advantage of
2177 familiarity.
2178
2179 QHash\<Key, T\>::const_iterator allows you to iterate over a
2180 QHash (or a QMultiHash). If you want to modify the QHash as you
2181 iterate over it, you must use QHash::iterator instead. It is
2182 generally good practice to use QHash::const_iterator on a
2183 non-const QHash as well, unless you need to change the QHash
2184 through the iterator. Const iterators are slightly faster, and
2185 can improve code readability.
2186
2187 The default QHash::const_iterator constructor creates an
2188 uninitialized iterator. You must initialize it using a QHash
2189 function like QHash::constBegin(), QHash::constEnd(), or
2190 QHash::find() before you can start iterating. Here's a typical
2191 loop that prints all the (key, value) pairs stored in a hash:
2192
2193 \snippet code/src_corelib_tools_qhash.cpp 23
2194
2195 Unlike QMap, which orders its items by key, QHash stores its
2196 items in an arbitrary order. The only guarantee is that items that
2197 share the same key (because they were inserted using
2198 a QMultiHash) will appear consecutively, from the most
2199 recently to the least recently inserted value.
2200
2201 Multiple iterators can be used on the same hash. However, be aware
2202 that any modification performed directly on the QHash has the
2203 potential of dramatically changing the order in which the items
2204 are stored in the hash, as they might cause QHash to rehash its
2205 internal data structure. If you need to keep iterators over a long
2206 period of time, we recommend that you use QMap rather than QHash.
2207
2208 \warning Iterators on implicitly shared containers do not work
2209 exactly like STL-iterators. You should avoid copying a container
2210 while iterators are active on that container. For more information,
2211 read \l{Implicit sharing iterator problem}.
2212
2213 \sa QHash::iterator, QHashIterator
2214*/
2215
2216/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator()
2217
2218 Constructs an uninitialized iterator.
2219
2220 Functions like key(), value(), and operator++() must not be
2221 called on an uninitialized iterator. Use operator=() to assign a
2222 value to it before using it.
2223
2224 \sa QHash::constBegin(), QHash::constEnd()
2225*/
2226
2227/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(void *node)
2228
2229 \internal
2230*/
2231
2232/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(const iterator &other)
2233
2234 Constructs a copy of \a other.
2235*/
2236
2237/*! \fn template <class Key, class T> const Key &QHash<Key, T>::const_iterator::key() const
2238
2239 Returns the current item's key.
2240
2241 \sa value()
2242*/
2243
2244/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::value() const
2245
2246 Returns the current item's value.
2247
2248 \sa key(), operator*()
2249*/
2250
2251/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::operator*() const
2252
2253 Returns the current item's value.
2254
2255 Same as value().
2256
2257 \sa key()
2258*/
2259
2260/*! \fn template <class Key, class T> const T *QHash<Key, T>::const_iterator::operator->() const
2261
2262 Returns a pointer to the current item's value.
2263
2264 \sa value()
2265*/
2266
2267/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator==(const const_iterator &other) const
2268
2269 Returns \c true if \a other points to the same item as this
2270 iterator; otherwise returns \c false.
2271
2272 \sa operator!=()
2273*/
2274
2275/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator!=(const const_iterator &other) const
2276
2277 Returns \c true if \a other points to a different item than this
2278 iterator; otherwise returns \c false.
2279
2280 \sa operator==()
2281*/
2282
2283/*!
2284 \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator++()
2285
2286 The prefix ++ operator (\c{++i}) advances the iterator to the
2287 next item in the hash and returns an iterator to the new current
2288 item.
2289
2290 Calling this function on QHash::end() leads to undefined results.
2291
2292 \sa operator--()
2293*/
2294
2295/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator++(int)
2296
2297 \overload
2298
2299 The postfix ++ operator (\c{i++}) advances the iterator to the
2300 next item in the hash and returns an iterator to the previously
2301 current item.
2302*/
2303
2304/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator--()
2305 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2306
2307 The prefix -- operator (\c{--i}) makes the preceding item
2308 current and returns an iterator pointing to the new current item.
2309
2310 Calling this function on QHash::begin() leads to undefined
2311 results.
2312
2313 \sa operator++()
2314*/
2315
2316/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator--(int)
2317 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2318
2319 \overload
2320
2321 The postfix -- operator (\c{i--}) makes the preceding item
2322 current and returns an iterator pointing to the previously
2323 current item.
2324*/
2325
2326/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator+(int j) const
2327 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
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 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2339
2340 Returns an iterator to the item at \a j positions backward from
2341 this iterator. (If \a j is negative, the iterator goes forward.)
2342
2343 This operation can be slow for large \a j values.
2344
2345 \sa operator+()
2346*/
2347
2348/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator+=(int j)
2349 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2350
2351 Advances the iterator by \a j items. (If \a j is negative, the
2352 iterator goes backward.)
2353
2354 This operation can be slow for large \a j values.
2355
2356 \sa operator-=(), operator+()
2357*/
2358
2359/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator-=(int j)
2360 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2361
2362 Makes the iterator go back by \a j items. (If \a j is negative,
2363 the iterator goes forward.)
2364
2365 This operation can be slow for large \a j values.
2366
2367 \sa operator+=(), operator-()
2368*/
2369
2370/*! \class QHash::key_iterator
2371 \inmodule QtCore
2372 \since 5.6
2373 \brief The QHash::key_iterator class provides an STL-style const iterator for QHash and QMultiHash keys.
2374
2375 QHash::key_iterator is essentially the same as QHash::const_iterator
2376 with the difference that operator*() and operator->() return a key
2377 instead of a value.
2378
2379 For most uses QHash::iterator and QHash::const_iterator should be used,
2380 you can easily access the key by calling QHash::iterator::key():
2381
2382 \snippet code/src_corelib_tools_qhash.cpp 27
2383
2384 However, to have interoperability between QHash's keys and STL-style
2385 algorithms we need an iterator that dereferences to a key instead
2386 of a value. With QHash::key_iterator we can apply an algorithm to a
2387 range of keys without having to call QHash::keys(), which is inefficient
2388 as it costs one QHash iteration and memory allocation to create a temporary
2389 QList.
2390
2391 \snippet code/src_corelib_tools_qhash.cpp 28
2392
2393 QHash::key_iterator is const, it's not possible to modify the key.
2394
2395 The default QHash::key_iterator constructor creates an uninitialized
2396 iterator. You must initialize it using a QHash function like
2397 QHash::keyBegin() or QHash::keyEnd().
2398
2399 \warning Iterators on implicitly shared containers do not work
2400 exactly like STL-iterators. You should avoid copying a container
2401 while iterators are active on that container. For more information,
2402 read \l{Implicit sharing iterator problem}.
2403
2404 \sa QHash::const_iterator, QHash::iterator
2405*/
2406
2407/*! \fn template <class Key, class T> const T &QHash<Key, T>::key_iterator::operator*() const
2408
2409 Returns the current item's key.
2410*/
2411
2412/*! \fn template <class Key, class T> const T *QHash<Key, T>::key_iterator::operator->() const
2413
2414 Returns a pointer to the current item's key.
2415*/
2416
2417/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator==(key_iterator other) const
2418
2419 Returns \c true if \a other points to the same item as this
2420 iterator; otherwise returns \c false.
2421
2422 \sa operator!=()
2423*/
2424
2425/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator!=(key_iterator other) const
2426
2427 Returns \c true if \a other points to a different item than this
2428 iterator; otherwise returns \c false.
2429
2430 \sa operator==()
2431*/
2432
2433/*!
2434 \fn template <class Key, class T> QHash<Key, T>::key_iterator &QHash<Key, T>::key_iterator::operator++()
2435
2436 The prefix ++ operator (\c{++i}) advances the iterator to the
2437 next item in the hash and returns an iterator to the new current
2438 item.
2439
2440 Calling this function on QHash::keyEnd() leads to undefined results.
2441
2442 \sa operator--()
2443*/
2444
2445/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator++(int)
2446
2447 \overload
2448
2449 The postfix ++ operator (\c{i++}) advances the iterator to the
2450 next item in the hash and returns an iterator to the previous
2451 item.
2452*/
2453
2454/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator &QHash<Key, T>::key_iterator::operator--()
2455 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2456
2457 The prefix -- operator (\c{--i}) makes the preceding item
2458 current and returns an iterator pointing to the new current item.
2459
2460 Calling this function on QHash::keyBegin() leads to undefined
2461 results.
2462
2463 \sa operator++()
2464*/
2465
2466/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator--(int)
2467 \obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2468
2469 \overload
2470
2471 The postfix -- operator (\c{i--}) makes the preceding item
2472 current and returns an iterator pointing to the previous
2473 item.
2474*/
2475
2476/*! \fn template <class Key, class T> const_iterator QHash<Key, T>::key_iterator::base() const
2477 Returns the underlying const_iterator this key_iterator is based on.
2478*/
2479
2480/*! \typedef QHash::const_key_value_iterator
2481 \inmodule QtCore
2482 \since 5.10
2483 \brief The QMap::const_key_value_iterator typedef provides an STL-style const iterator for QHash and QMultiHash.
2484
2485 QHash::const_key_value_iterator is essentially the same as QHash::const_iterator
2486 with the difference that operator*() returns a key/value pair instead of a
2487 value.
2488
2489 \sa QKeyValueIterator
2490*/
2491
2492/*! \typedef QHash::key_value_iterator
2493 \inmodule QtCore
2494 \since 5.10
2495 \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QHash and QMultiHash.
2496
2497 QHash::key_value_iterator is essentially the same as QHash::iterator
2498 with the difference that operator*() returns a key/value pair instead of a
2499 value.
2500
2501 \sa QKeyValueIterator
2502*/
2503
2504/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash)
2505 \relates QHash
2506
2507 Writes the hash \a hash to stream \a out.
2508
2509 This function requires the key and value types to implement \c
2510 operator<<().
2511
2512 \sa {Serializing Qt Data Types}
2513*/
2514
2515/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QHash<Key, T> &hash)
2516 \relates QHash
2517
2518 Reads a hash from stream \a in into \a hash.
2519
2520 This function requires the key and value types to implement \c
2521 operator>>().
2522
2523 \sa {Serializing Qt Data Types}
2524*/
2525
2526/*! \class QMultiHash
2527 \inmodule QtCore
2528 \brief The QMultiHash class is a convenience QHash subclass that provides multi-valued hashes.
2529
2530 \ingroup tools
2531 \ingroup shared
2532
2533 \reentrant
2534
2535 QMultiHash\<Key, T\> is one of Qt's generic \l{container classes}.
2536 It inherits QHash and extends it with a few convenience functions
2537 that make it more suitable than QHash for storing multi-valued
2538 hashes. A multi-valued hash is a hash that allows multiple values
2539 with the same key.
2540
2541 Because QMultiHash inherits QHash, all of QHash's functionality also
2542 applies to QMultiHash. For example, you can use isEmpty() to test
2543 whether the hash is empty, and you can traverse a QMultiHash using
2544 QHash's iterator classes (for example, QHashIterator). But opposed to
2545 QHash, it provides an insert() function will allow the insertion of
2546 multiple items with the same key. The replace() function corresponds to
2547 QHash::insert(). It also provides convenient operator+() and
2548 operator+=().
2549
2550 Unlike QMultiMap, QMultiHash does not provide and ordering of the
2551 inserted items. The only guarantee is that items that
2552 share the same key will appear consecutively, from the most
2553 recently to the least recently inserted value.
2554
2555 Example:
2556 \snippet code/src_corelib_tools_qhash.cpp 24
2557
2558 Unlike QHash, QMultiHash provides no operator[]. Use value() or
2559 replace() if you want to access the most recently inserted item
2560 with a certain key.
2561
2562 If you want to retrieve all the values for a single key, you can
2563 use values(const Key &key), which returns a QList<T>:
2564
2565 \snippet code/src_corelib_tools_qhash.cpp 25
2566
2567 The items that share the same key are available from most
2568 recently to least recently inserted.
2569
2570 A more efficient approach is to call find() to get
2571 the STL-style iterator for the first item with a key and iterate from
2572 there:
2573
2574 \snippet code/src_corelib_tools_qhash.cpp 26
2575
2576 QMultiHash's key and value data types must be \l{assignable data
2577 types}. You cannot, for example, store a QWidget as a value;
2578 instead, store a QWidget *. In addition, QMultiHash's key type
2579 must provide operator==(), and there must also be a qHash() function
2580 in the type's namespace that returns a hash value for an argument of the
2581 key's type. See the QHash documentation for details.
2582
2583 \sa QHash, QHashIterator, QMutableHashIterator, QMultiMap
2584*/
2585
2586/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash()
2587
2588 Constructs an empty hash.
2589*/
2590
2591/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(std::initializer_list<std::pair<Key,T> > list)
2592 \since 5.1
2593
2594 Constructs a multi-hash with a copy of each of the elements in the
2595 initializer list \a list.
2596
2597 This function is only available if the program is being
2598 compiled in C++11 mode.
2599*/
2600
2601/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(const QHash<Key, T> &other)
2602
2603 Constructs a copy of \a other (which can be a QHash or a
2604 QMultiHash).
2605
2606 \sa operator=()
2607*/
2608
2609/*! \fn template <class Key, class T> template <class InputIterator> QMultiHash<Key, T>::QMultiHash(InputIterator begin, InputIterator end)
2610 \since 5.14
2611
2612 Constructs a multi-hash with a copy of each of the elements in the iterator range
2613 [\a begin, \a end). Either the elements iterated by the range must be
2614 objects with \c{first} and \c{second} data members (like \c{QPair},
2615 \c{std::pair}, etc.) convertible to \c Key and to \c T respectively; or the
2616 iterators must have \c{key()} and \c{value()} member functions, returning a
2617 key convertible to \c Key and a value convertible to \c T respectively.
2618*/
2619
2620/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::replace(const Key &key, const T &value)
2621
2622 Inserts a new item with the \a key and a value of \a value.
2623
2624 If there is already an item with the \a key, that item's value
2625 is replaced with \a value.
2626
2627 If there are multiple items with the \a key, the most
2628 recently inserted item's value is replaced with \a value.
2629
2630 \sa insert()
2631*/
2632
2633/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &key, const T &value)
2634
2635 Inserts a new item with the \a key and a value of \a value.
2636
2637 If there is already an item with the same key in the hash, this
2638 function will simply create a new one. (This behavior is
2639 different from replace(), which overwrites the value of an
2640 existing item.)
2641
2642 \sa replace()
2643*/
2644
2645/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QMultiHash &other)
2646 \since 5.13
2647
2648 Inserts all the items in the \a other hash into this hash
2649 and returns a reference to this hash.
2650
2651 \sa insert()
2652*/
2653
2654/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::uniqueKeys() const
2655 \since 5.13
2656
2657 Returns a list containing all the keys in the map. Keys that occur multiple
2658 times in the map occur only once in the returned list.
2659
2660 \sa keys(), values()
2661*/
2662
2663/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values(const Key &key) const
2664 \overload
2665
2666 Returns a list of all the values associated with the \a key,
2667 from the most recently inserted to the least recently inserted.
2668
2669 \sa count(), insert()
2670*/
2671
2672/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::operator+=(const QMultiHash &other)
2673
2674 Inserts all the items in the \a other hash into this hash
2675 and returns a reference to this hash.
2676
2677 \sa unite(), insert()
2678*/
2679
2680/*! \fn template <class Key, class T> QMultiHash QMultiHash<Key, T>::operator+(const QMultiHash &other) const
2681
2682 Returns a hash that contains all the items in this hash in
2683 addition to all the items in \a other. If a key is common to both
2684 hashes, the resulting hash will contain the key multiple times.
2685
2686 \sa operator+=()
2687*/
2688
2689/*!
2690 \fn template <class Key, class T> bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
2691 \since 4.3
2692
2693 Returns \c true if the hash contains an item with the \a key and
2694 \a value; otherwise returns \c false.
2695
2696 \sa QHash::contains()
2697*/
2698
2699/*!
2700 \fn template <class Key, class T> int QMultiHash<Key, T>::remove(const Key &key, const T &value)
2701 \since 4.3
2702
2703 Removes all the items that have the \a key and the value \a
2704 value from the hash. Returns the number of items removed.
2705
2706 \sa QHash::remove()
2707*/
2708
2709/*!
2710 \fn template <class Key, class T> int QMultiHash<Key, T>::count(const Key &key, const T &value) const
2711 \since 4.3
2712
2713 Returns the number of items with the \a key and \a value.
2714
2715 \sa QHash::count()
2716*/
2717
2718/*!
2719 \fn template <class Key, class T> typename QHash<Key, T>::iterator QMultiHash<Key, T>::find(const Key &key, const T &value)
2720 \since 4.3
2721
2722 Returns an iterator pointing to the item with the \a key and \a value.
2723 If the hash contains no such item, the function returns end().
2724
2725 If the hash contains multiple items with the \a key and \a value, the
2726 iterator returned points to the most recently inserted item.
2727
2728 \sa QHash::find()
2729*/
2730
2731/*!
2732 \fn template <class Key, class T> typename QHash<Key, T>::const_iterator QMultiHash<Key, T>::find(const Key &key, const T &value) const
2733 \since 4.3
2734 \overload
2735*/
2736
2737/*!
2738 \fn template <class Key, class T> typename QHash<Key, T>::const_iterator QMultiHash<Key, T>::constFind(const Key &key, const T &value) const
2739 \since 4.3
2740
2741 Returns an iterator pointing to the item with the \a key and the
2742 \a value in the hash.
2743
2744 If the hash contains no such item, the function returns
2745 constEnd().
2746
2747 \sa QHash::constFind()
2748*/
2749
2750/*!
2751 \fn template <class Key, class T> uint qHash(const QHash<Key, T> &key, uint seed = 0)
2752 \since 5.8
2753 \relates QHash
2754
2755 Returns the hash value for the \a key, using \a seed to seed the calculation.
2756
2757 Type \c T must be supported by qHash().
2758*/
2759
2760/*!
2761 \fn template <class Key, class T> uint qHash(const QMultiHash<Key, T> &key, uint seed = 0)
2762 \since 5.8
2763 \relates QMultiHash
2764
2765 Returns the hash value for the \a key, using \a seed to seed the calculation.
2766
2767 Type \c T must be supported by qHash().
2768*/
2769
2770QT_END_NAMESPACE
2771

source code of qtbase/src/corelib/tools/qhash.cpp