1/****************************************************************************
2**
3** Copyright (C) 2020 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#include <stdint.h>
49
50#include "qhash.h"
51
52#ifdef truncate
53#undef truncate
54#endif
55
56#include <qbitarray.h>
57#include <qstring.h>
58#include <qglobal.h>
59#include <qbytearray.h>
60#include <qdatetime.h>
61#include <qbasicatomic.h>
62#include <qendian.h>
63#include <private/qsimd_p.h>
64
65#ifndef QT_BOOTSTRAPPED
66#include <qcoreapplication.h>
67#include <qrandom.h>
68#endif // QT_BOOTSTRAPPED
69
70#include <limits.h>
71
72QT_BEGIN_NAMESPACE
73
74// We assume that pointers and size_t have the same size. If that assumption should fail
75// on a platform the code selecting the different methods below needs to be fixed.
76static_assert(sizeof(size_t) == QT_POINTER_SIZE, "size_t and pointers have different size.");
77
78/*
79 * Hashing for memory segments is based on the public domain MurmurHash2 by
80 * Austin Appleby. See http://murmurhash.googlepages.com/
81 */
82#if QT_POINTER_SIZE == 4
83
84static inline uint murmurhash(const void *key, uint len, uint seed) noexcept
85{
86 // 'm' and 'r' are mixing constants generated offline.
87 // They're not really 'magic', they just happen to work well.
88
89 const unsigned int m = 0x5bd1e995;
90 const int r = 24;
91
92 // Initialize the hash to a 'random' value
93
94 unsigned int h = seed ^ len;
95
96 // Mix 4 bytes at a time into the hash
97
98 const unsigned char *data = reinterpret_cast<const unsigned char *>(key);
99 const unsigned char *end = data + (len & ~3);
100
101 while (data != end) {
102 size_t k;
103 memcpy(&k, data, sizeof(uint));
104
105 k *= m;
106 k ^= k >> r;
107 k *= m;
108
109 h *= m;
110 h ^= k;
111
112 data += 4;
113 }
114
115 // Handle the last few bytes of the input array
116 len &= 3;
117 if (len) {
118 unsigned int k = 0;
119 end += len;
120
121 while (data != end) {
122 k <<= 8;
123 k |= *data;
124 ++data;
125 }
126 h ^= k;
127 h *= m;
128 }
129
130 // Do a few final mixes of the hash to ensure the last few
131 // bytes are well-incorporated.
132
133 h ^= h >> 13;
134 h *= m;
135 h ^= h >> 15;
136
137 return h;
138}
139
140#else
141
142static inline uint64_t murmurhash(const void *key, uint64_t len, uint64_t seed) noexcept
143{
144 const uint64_t m = 0xc6a4a7935bd1e995ULL;
145 const int r = 47;
146
147 uint64_t h = seed ^ (len * m);
148
149 const unsigned char *data = reinterpret_cast<const unsigned char *>(key);
150 const unsigned char *end = data + (len & ~7ul);
151
152 while (data != end) {
153 uint64_t k;
154 memcpy(&k, data, sizeof(uint64_t));
155
156 k *= m;
157 k ^= k >> r;
158 k *= m;
159
160 h ^= k;
161 h *= m;
162
163 data += 8;
164 }
165
166 len &= 7;
167 if (len) {
168 // handle the last few bytes of input
169 size_t k = 0;
170 end += len;
171
172 while (data != end) {
173 k <<= 8;
174 k |= *data;
175 ++data;
176 }
177 h ^= k;
178 h *= m;
179 }
180
181 h ^= h >> r;
182 h *= m;
183 h ^= h >> r;
184
185 return h;
186}
187
188#endif
189
190#if QT_POINTER_SIZE == 8
191// This is an inlined version of the SipHash implementation that is
192// trying to avoid some memcpy's from uint64 to uint8[] and back.
193//
194// The original algorithm uses a 128bit seed. Our public API only allows
195// for a 64bit seed, so we mix in the length of the string to get some more
196// bits for the seed.
197//
198// Use SipHash-1-2, which has similar performance characteristics as
199// stablehash() above, instead of the SipHash-2-4 default
200#define cROUNDS 1
201#define dROUNDS 2
202
203#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
204
205#define SIPROUND \
206 do { \
207 v0 += v1; \
208 v1 = ROTL(v1, 13); \
209 v1 ^= v0; \
210 v0 = ROTL(v0, 32); \
211 v2 += v3; \
212 v3 = ROTL(v3, 16); \
213 v3 ^= v2; \
214 v0 += v3; \
215 v3 = ROTL(v3, 21); \
216 v3 ^= v0; \
217 v2 += v1; \
218 v1 = ROTL(v1, 17); \
219 v1 ^= v2; \
220 v2 = ROTL(v2, 32); \
221 } while (0)
222
223
224static uint64_t siphash(const uint8_t *in, uint64_t inlen, const uint64_t seed)
225{
226 /* "somepseudorandomlygeneratedbytes" */
227 uint64_t v0 = 0x736f6d6570736575ULL;
228 uint64_t v1 = 0x646f72616e646f6dULL;
229 uint64_t v2 = 0x6c7967656e657261ULL;
230 uint64_t v3 = 0x7465646279746573ULL;
231 uint64_t b;
232 uint64_t k0 = seed;
233 uint64_t k1 = seed ^ inlen;
234 int i;
235 const uint8_t *end = in + (inlen & ~7ULL);
236 const int left = inlen & 7;
237 b = inlen << 56;
238 v3 ^= k1;
239 v2 ^= k0;
240 v1 ^= k1;
241 v0 ^= k0;
242
243 for (; in != end; in += 8) {
244 uint64_t m = qFromUnaligned<uint64_t>(in);
245 v3 ^= m;
246
247 for (i = 0; i < cROUNDS; ++i)
248 SIPROUND;
249
250 v0 ^= m;
251 }
252
253
254#if defined(Q_CC_GNU) && Q_CC_GNU >= 700
255 QT_WARNING_DISABLE_GCC("-Wimplicit-fallthrough")
256#endif
257 switch (left) {
258 case 7:
259 b |= ((uint64_t)in[6]) << 48;
260 case 6:
261 b |= ((uint64_t)in[5]) << 40;
262 case 5:
263 b |= ((uint64_t)in[4]) << 32;
264 case 4:
265 b |= ((uint64_t)in[3]) << 24;
266 case 3:
267 b |= ((uint64_t)in[2]) << 16;
268 case 2:
269 b |= ((uint64_t)in[1]) << 8;
270 case 1:
271 b |= ((uint64_t)in[0]);
272 break;
273 case 0:
274 break;
275 }
276
277 v3 ^= b;
278
279 for (i = 0; i < cROUNDS; ++i)
280 SIPROUND;
281
282 v0 ^= b;
283
284 v2 ^= 0xff;
285
286 for (i = 0; i < dROUNDS; ++i)
287 SIPROUND;
288
289 b = v0 ^ v1 ^ v2 ^ v3;
290 return b;
291}
292#else
293// This is a "SipHash" implementation adopted for 32bit platforms. It performs
294// basically the same operations as the 64bit version using 4 byte at a time
295// instead of 8.
296//
297// To make this work, we also need to change the constants for the mixing
298// rotations in ROTL. We're simply using half of the 64bit constants, rounded up
299// for odd numbers.
300//
301// For the v0-v4 constants, simply use the first four bytes of the 64 bit versions.
302//
303// Use SipHash-1-2, which has similar performance characteristics as
304// stablehash() above, instead of the SipHash-2-4 default
305#define cROUNDS 1
306#define dROUNDS 2
307
308#define ROTL(x, b) (uint32_t)(((x) << (b)) | ((x) >> (32 - (b))))
309
310#define SIPROUND \
311 do { \
312 v0 += v1; \
313 v1 = ROTL(v1, 7); \
314 v1 ^= v0; \
315 v0 = ROTL(v0, 16); \
316 v2 += v3; \
317 v3 = ROTL(v3, 8); \
318 v3 ^= v2; \
319 v0 += v3; \
320 v3 = ROTL(v3, 11); \
321 v3 ^= v0; \
322 v2 += v1; \
323 v1 = ROTL(v1, 9); \
324 v1 ^= v2; \
325 v2 = ROTL(v2, 16); \
326 } while (0)
327
328
329static uint siphash(const uint8_t *in, uint inlen, const uint seed)
330{
331 /* "somepseudorandomlygeneratedbytes" */
332 uint v0 = 0x736f6d65U;
333 uint v1 = 0x646f7261U;
334 uint v2 = 0x6c796765U;
335 uint v3 = 0x74656462U;
336 uint b;
337 uint k0 = seed;
338 uint k1 = seed ^ inlen;
339 int i;
340 const uint8_t *end = in + (inlen & ~3ULL);
341 const int left = inlen & 3;
342 b = inlen << 24;
343 v3 ^= k1;
344 v2 ^= k0;
345 v1 ^= k1;
346 v0 ^= k0;
347
348 for (; in != end; in += 4) {
349 uint m = qFromUnaligned<uint>(in);
350 v3 ^= m;
351
352 for (i = 0; i < cROUNDS; ++i)
353 SIPROUND;
354
355 v0 ^= m;
356 }
357
358#if defined(Q_CC_GNU) && Q_CC_GNU >= 700
359 QT_WARNING_DISABLE_GCC("-Wimplicit-fallthrough")
360#endif
361 switch (left) {
362 case 3:
363 b |= ((uint)in[2]) << 16;
364 case 2:
365 b |= ((uint)in[1]) << 8;
366 case 1:
367 b |= ((uint)in[0]);
368 break;
369 case 0:
370 break;
371 }
372
373 v3 ^= b;
374
375 for (i = 0; i < cROUNDS; ++i)
376 SIPROUND;
377
378 v0 ^= b;
379
380 v2 ^= 0xff;
381
382 for (i = 0; i < dROUNDS; ++i)
383 SIPROUND;
384
385 b = v0 ^ v1 ^ v2 ^ v3;
386 return b;
387}
388#endif
389
390#if defined(__SANITIZE_ADDRESS__) || defined(__SANITIZE_THREAD__) // GCC
391# define QHASH_AES_SANITIZER_BUILD
392#elif QT_HAS_FEATURE(address_sanitizer) || QT_HAS_FEATURE(thread_sanitizer) // Clang
393# define QHASH_AES_SANITIZER_BUILD
394#endif
395
396// When built with a sanitizer, aeshash() is rightfully reported to have a
397// heap-buffer-overflow issue. However, we consider it to be safe in this
398// specific case and overcome the problem by correctly discarding the
399// out-of-range bits. To allow building the code with sanitizer,
400// QHASH_AES_SANITIZER_BUILD is used to disable aeshash() usage.
401#if QT_COMPILER_SUPPORTS_HERE(AES) && QT_COMPILER_SUPPORTS_HERE(SSE4_2) && \
402 !defined(QHASH_AES_SANITIZER_BUILD)
403# define AESHASH
404
405#undef QHASH_AES_SANITIZER_BUILD
406
407QT_FUNCTION_TARGET(AES)
408static size_t aeshash(const uchar *p, size_t len, size_t seed) noexcept
409{
410 __m128i key;
411 if (sizeof(size_t) == 8) {
412#ifdef Q_PROCESSOR_X86_64
413 quint64 seededlen = seed ^ len;
414 __m128i mseed = _mm_cvtsi64_si128(seed);
415 key = _mm_insert_epi64(mseed, seededlen, 1);
416#endif
417 } else {
418 quint32 replicated_len = quint16(len) | (quint32(quint16(len)) << 16);
419 __m128i mseed = _mm_cvtsi32_si128(seed);
420 key = _mm_insert_epi32(mseed, replicated_len, 1);
421 key = _mm_unpacklo_epi64(key, key);
422 }
423
424 // This is inspired by the algorithm in the Go language. See:
425 // https://github.com/golang/go/blob/894abb5f680c040777f17f9f8ee5a5ab3a03cb94/src/runtime/asm_386.s#L902
426 // https://github.com/golang/go/blob/894abb5f680c040777f17f9f8ee5a5ab3a03cb94/src/runtime/asm_amd64.s#L903
427 //
428 // Even though we're using the AESENC instruction from the CPU, this code
429 // is not encryption and this routine makes no claim to be
430 // cryptographically secure. We're simply using the instruction that performs
431 // the scrambling round (step 3 in [1]) because it's just very good at
432 // spreading the bits around.
433 //
434 // [1] https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#High-level_description_of_the_algorithm
435
436 // hash 16 bytes, running 3 scramble rounds of AES on itself (like label "final1")
437 const auto hash16bytes = [](__m128i &state0, __m128i data) QT_FUNCTION_TARGET(AES) {
438 state0 = _mm_xor_si128(state0, data);
439 state0 = _mm_aesenc_si128(state0, state0);
440 state0 = _mm_aesenc_si128(state0, state0);
441 state0 = _mm_aesenc_si128(state0, state0);
442 };
443
444 __m128i state0 = key;
445 auto src = reinterpret_cast<const __m128i *>(p);
446
447 if (len < 16)
448 goto lt16;
449 if (len < 32)
450 goto lt32;
451
452 // rounds of 32 bytes
453 {
454 // Make state1 = ~state0:
455 __m128i one = _mm_cmpeq_epi64(key, key);
456 __m128i state1 = _mm_xor_si128(state0, one);
457
458 // do simplified rounds of 32 bytes: unlike the Go code, we only
459 // scramble twice and we keep 256 bits of state
460 const auto srcend = src + (len / 32);
461 while (src < srcend) {
462 __m128i data0 = _mm_loadu_si128(src);
463 __m128i data1 = _mm_loadu_si128(src + 1);
464 state0 = _mm_xor_si128(data0, state0);
465 state1 = _mm_xor_si128(data1, state1);
466 state0 = _mm_aesenc_si128(state0, state0);
467 state1 = _mm_aesenc_si128(state1, state1);
468 state0 = _mm_aesenc_si128(state0, state0);
469 state1 = _mm_aesenc_si128(state1, state1);
470 src += 2;
471 }
472 state0 = _mm_xor_si128(state0, state1);
473 }
474 len &= 0x1f;
475
476 // do we still have 16 or more bytes?
477 if (len & 0x10) {
478lt32:
479 __m128i data = _mm_loadu_si128(src);
480 hash16bytes(state0, data);
481 ++src;
482 }
483 len &= 0xf;
484
485lt16:
486 if (len) {
487 // load the last chunk of data
488 // We're going to load 16 bytes and mask zero the part we don't care
489 // (the hash of a short string is different from the hash of a longer
490 // including NULLs at the end because the length is in the key)
491 // WARNING: this may produce valgrind warnings, but it's safe
492
493 __m128i data;
494
495 if (Q_LIKELY(quintptr(src + 1) & 0xff0)) {
496 // same page, we definitely can't fault:
497 // load all 16 bytes and mask off the bytes past the end of the source
498 static const qint8 maskarray[] = {
499 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
500 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
501 };
502 __m128i mask = _mm_loadu_si128(reinterpret_cast<const __m128i *>(maskarray + 15 - len));
503 data = _mm_loadu_si128(src);
504 data = _mm_and_si128(data, mask);
505 } else {
506 // too close to the end of the page, it could fault:
507 // load 16 bytes ending at the data end, then shuffle them to the beginning
508 static const qint8 shufflecontrol[] = {
509 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
510 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
511 };
512 __m128i control = _mm_loadu_si128(reinterpret_cast<const __m128i *>(shufflecontrol + 15 - len));
513 p = reinterpret_cast<const uchar *>(src - 1);
514 data = _mm_loadu_si128(reinterpret_cast<const __m128i *>(p + len));
515 data = _mm_shuffle_epi8(data, control);
516 }
517
518 hash16bytes(state0, data);
519 }
520
521 // extract state0
522# if QT_POINTER_SIZE == 8
523 return _mm_cvtsi128_si64(state0);
524# else
525 return _mm_cvtsi128_si32(state0);
526# endif
527}
528#endif
529
530size_t qHashBits(const void *p, size_t size, size_t seed) noexcept
531{
532#ifdef QT_BOOTSTRAPPED
533 // the seed is always 0 in bootstrapped mode (no seed generation code),
534 // so help the compiler do dead code elimination
535 seed = 0;
536#endif
537#ifdef AESHASH
538 if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2))
539 return aeshash(reinterpret_cast<const uchar *>(p), size, seed);
540#endif
541 if (size <= QT_POINTER_SIZE)
542 return murmurhash(p, size, seed);
543
544 return siphash(reinterpret_cast<const uchar *>(p), size, seed);
545}
546
547size_t qHash(const QByteArray &key, size_t seed) noexcept
548{
549 return qHashBits(key.constData(), size_t(key.size()), seed);
550}
551
552size_t qHash(const QByteArrayView &key, size_t seed) noexcept
553{
554 return qHashBits(key.constData(), size_t(key.size()), seed);
555}
556
557size_t qHash(QStringView key, size_t seed) noexcept
558{
559 return qHashBits(key.data(), key.size()*sizeof(QChar), seed);
560}
561
562size_t qHash(const QBitArray &bitArray, size_t seed) noexcept
563{
564 qsizetype m = bitArray.d.size() - 1;
565 size_t result = qHashBits(reinterpret_cast<const uchar *>(bitArray.d.constData()), size_t(qMax(0, m)), seed);
566
567 // deal with the last 0 to 7 bits manually, because we can't trust that
568 // the padding is initialized to 0 in bitArray.d
569 qsizetype n = bitArray.size();
570 if (n & 0x7)
571 result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1);
572 return result;
573}
574
575size_t qHash(QLatin1String key, size_t seed) noexcept
576{
577 return qHashBits(reinterpret_cast<const uchar *>(key.data()), size_t(key.size()), seed);
578}
579
580/*!
581 \internal
582*/
583static uint qt_create_qhash_seed()
584{
585 uint seed = 0;
586
587#ifndef QT_BOOTSTRAPPED
588 QByteArray envSeed = qgetenv("QT_HASH_SEED");
589 if (!envSeed.isNull()) {
590 uint seed = envSeed.toUInt();
591 if (seed) {
592 // can't use qWarning here (reentrancy)
593 fprintf(stderr, "QT_HASH_SEED: forced seed value is not 0, cannot guarantee that the "
594 "hashing functions will produce a stable value.");
595 }
596 return seed;
597 }
598
599 seed = QRandomGenerator::system()->generate();
600#endif // QT_BOOTSTRAPPED
601
602 return seed;
603}
604
605/*
606 The QHash seed itself.
607*/
608static QBasicAtomicInt qt_qhash_seed = Q_BASIC_ATOMIC_INITIALIZER(-1);
609
610/*!
611 \internal
612
613 Seed == -1 means it that it was not initialized yet.
614
615 We let qt_create_qhash_seed return any unsigned integer,
616 but convert it to signed in order to initialize the seed.
617
618 We don't actually care about the fact that different calls to
619 qt_create_qhash_seed() might return different values,
620 as long as in the end everyone uses the very same value.
621*/
622static void qt_initialize_qhash_seed()
623{
624 if (qt_qhash_seed.loadRelaxed() == -1) {
625 int x(qt_create_qhash_seed() & INT_MAX);
626 qt_qhash_seed.testAndSetRelaxed(-1, x);
627 }
628}
629
630/*! \relates QHash
631 \since 5.6
632
633 Returns the current global QHash seed.
634
635 The seed is set in any newly created QHash. See \l{qHash} about how this seed
636 is being used by QHash.
637
638 \sa qSetGlobalQHashSeed
639 */
640int qGlobalQHashSeed()
641{
642 qt_initialize_qhash_seed();
643 return qt_qhash_seed.loadRelaxed();
644}
645
646/*! \relates QHash
647 \since 5.6
648
649 Sets the global QHash seed to \a newSeed.
650
651 Manually setting the global QHash seed value should be done only for testing
652 and debugging purposes, when deterministic and reproducible behavior on a QHash
653 is needed. We discourage to do it in production code as it can make your
654 application susceptible to \l{algorithmic complexity attacks}.
655
656 From Qt 5.10 and onwards, the only allowed values are 0 and -1. Passing the
657 value -1 will reinitialize the global QHash seed to a random value, while
658 the value of 0 is used to request a stable algorithm for C++ primitive
659 types types (like \c int) and string types (QString, QByteArray).
660
661 The seed is set in any newly created QHash. See \l{qHash} about how this seed
662 is being used by QHash.
663
664 If the environment variable \c QT_HASH_SEED is set, calling this function will
665 result in a no-op.
666
667 \sa qGlobalQHashSeed
668 */
669void qSetGlobalQHashSeed(int newSeed)
670{
671 if (qEnvironmentVariableIsSet("QT_HASH_SEED"))
672 return;
673 if (newSeed == -1) {
674 int x(qt_create_qhash_seed() & INT_MAX);
675 qt_qhash_seed.storeRelaxed(x);
676 } else {
677 if (newSeed) {
678 // can't use qWarning here (reentrancy)
679 fprintf(stderr, "qSetGlobalQHashSeed: forced seed value is not 0, cannot guarantee that the "
680 "hashing functions will produce a stable value.");
681 }
682 qt_qhash_seed.storeRelaxed(newSeed & INT_MAX);
683 }
684}
685
686/*!
687 \internal
688
689 Private copy of the implementation of the Qt 4 qHash algorithm for strings,
690 (that is, QChar-based arrays, so all QString-like classes),
691 to be used wherever the result is somehow stored or reused across multiple
692 Qt versions. The public qHash implementation can change at any time,
693 therefore one must not rely on the fact that it will always give the same
694 results.
695
696 The qt_hash functions must *never* change their results.
697
698 This function can hash discontiguous memory by invoking it on each chunk,
699 passing the previous's result in the next call's \a chained argument.
700*/
701uint qt_hash(QStringView key, uint chained) noexcept
702{
703 auto n = key.size();
704 auto p = key.utf16();
705
706 uint h = chained;
707
708 while (n--) {
709 h = (h << 4) + *p++;
710 h ^= (h & 0xf0000000) >> 23;
711 h &= 0x0fffffff;
712 }
713 return h;
714}
715
716/*!
717 \fn template <typename T1, typename T2> size_t qHash(const QPair<T1, T2> &key, size_t seed = 0)
718 \since 5.0
719 \relates QHash
720
721 Returns the hash value for the \a key, using \a seed to seed the calculation.
722
723 Types \c T1 and \c T2 must be supported by qHash().
724*/
725
726/*!
727 \fn template <typename T1, typename T2> size_t qHash(const std::pair<T1, T2> &key, size_t seed = 0)
728 \since 5.7
729 \relates QHash
730
731 Returns the hash value for the \a key, using \a seed to seed the calculation.
732
733 Types \c T1 and \c T2 must be supported by qHash().
734
735 \note The return type of this function is \e{not} the same as that of
736 \snippet code/src_corelib_tools_qhash.cpp 29
737 The two functions use different hashing algorithms; due to binary compatibility
738 constraints, we cannot change the QPair algorithm to match the std::pair one before Qt 6.
739*/
740
741/*!
742 \fn template <typename... T> size_t qHashMulti(size_t seed, const T &...args)
743 \relates QHash
744 \since 6.0
745
746 Returns the hash value for the \a{args}, using \a seed to seed
747 the calculation, by successively applying qHash() to each
748 element and combining the hash values into a single one.
749
750 Note that the order of the arguments is significant. If order does
751 not matter, use qHashMultiCommutative() instead. If you are hashing raw
752 memory, use qHashBits(); if you are hashing a range, use qHashRange().
753
754 This function is provided as a convenience to implement qHash() for
755 your own custom types. For example, here's how you could implement
756 a qHash() overload for a class \c{Employee}:
757
758 \snippet code/src_corelib_tools_qhash.cpp 13
759
760 \sa qHashMultiCommutative, qHashRange
761*/
762
763/*!
764 \fn template <typename... T> size_t qHashMultiCommutative(size_t seed, const T &...args)
765 \relates QHash
766 \since 6.0
767
768 Returns the hash value for the \a{args}, using \a seed to seed
769 the calculation, by successively applying qHash() to each
770 element and combining the hash values into a single one.
771
772 The order of the arguments is insignificant. If order does
773 matter, use qHashMulti() instead, as it may produce better quality
774 hashing. If you are hashing raw memory, use qHashBits(); if you are
775 hashing a range, use qHashRange().
776
777 This function is provided as a convenience to implement qHash() for
778 your own custom types.
779
780 \sa qHashMulti, qHashRange
781*/
782
783/*! \fn template <typename InputIterator> size_t qHashRange(InputIterator first, InputIterator last, size_t seed = 0)
784 \relates QHash
785 \since 5.5
786
787 Returns the hash value for the range [\a{first},\a{last}), using \a seed
788 to seed the calculation, by successively applying qHash() to each
789 element and combining the hash values into a single one.
790
791 The return value of this function depends on the order of elements
792 in the range. That means that
793
794 \snippet code/src_corelib_tools_qhash.cpp 30
795
796 and
797 \snippet code/src_corelib_tools_qhash.cpp 31
798
799 hash to \b{different} values. If order does not matter, for example for hash
800 tables, use qHashRangeCommutative() instead. If you are hashing raw
801 memory, use qHashBits().
802
803 Use this function only to implement qHash() for your own custom
804 types. For example, here's how you could implement a qHash() overload for
805 std::vector<int>:
806
807 \snippet code/src_corelib_tools_qhash.cpp qhashrange
808
809 It bears repeating that the implementation of qHashRange() - like
810 the qHash() overloads offered by Qt - may change at any time. You
811 \b{must not} rely on the fact that qHashRange() will give the same
812 results (for the same inputs) across different Qt versions, even
813 if qHash() for the element type would.
814
815 \sa qHashBits(), qHashRangeCommutative()
816*/
817
818/*! \fn template <typename InputIterator> size_t qHashRangeCommutative(InputIterator first, InputIterator last, size_t seed = 0)
819 \relates QHash
820 \since 5.5
821
822 Returns the hash value for the range [\a{first},\a{last}), using \a seed
823 to seed the calculation, by successively applying qHash() to each
824 element and combining the hash values into a single one.
825
826 The return value of this function does not depend on the order of
827 elements in the range. That means that
828
829 \snippet code/src_corelib_tools_qhash.cpp 30
830
831 and
832 \snippet code/src_corelib_tools_qhash.cpp 31
833
834 hash to the \b{same} values. If order matters, for example, for vectors
835 and arrays, use qHashRange() instead. If you are hashing raw
836 memory, use qHashBits().
837
838 Use this function only to implement qHash() for your own custom
839 types. For example, here's how you could implement a qHash() overload for
840 std::unordered_set<int>:
841
842 \snippet code/src_corelib_tools_qhash.cpp qhashrangecommutative
843
844 It bears repeating that the implementation of
845 qHashRangeCommutative() - like the qHash() overloads offered by Qt
846 - may change at any time. You \b{must not} rely on the fact that
847 qHashRangeCommutative() will give the same results (for the same
848 inputs) across different Qt versions, even if qHash() for the
849 element type would.
850
851 \sa qHashBits(), qHashRange()
852*/
853
854/*! \fn size_t qHashBits(const void *p, size_t len, size_t seed = 0)
855 \relates QHash
856 \since 5.4
857
858 Returns the hash value for the memory block of size \a len pointed
859 to by \a p, using \a seed to seed the calculation.
860
861 Use this function only to implement qHash() for your own custom
862 types. For example, here's how you could implement a qHash() overload for
863 std::vector<int>:
864
865 \snippet code/src_corelib_tools_qhash.cpp qhashbits
866
867 This takes advantage of the fact that std::vector lays out its data
868 contiguously. If that is not the case, or the contained type has
869 padding, you should use qHashRange() instead.
870
871 It bears repeating that the implementation of qHashBits() - like
872 the qHash() overloads offered by Qt - may change at any time. You
873 \b{must not} rely on the fact that qHashBits() will give the same
874 results (for the same inputs) across different Qt versions.
875
876 \sa qHashRange(), qHashRangeCommutative()
877*/
878
879/*! \fn size_t qHash(char key, size_t seed = 0)
880 \relates QHash
881 \since 5.0
882
883 Returns the hash value for the \a key, using \a seed to seed the calculation.
884*/
885
886/*! \fn size_t qHash(uchar key, size_t seed = 0)
887 \relates QHash
888 \since 5.0
889
890 Returns the hash value for the \a key, using \a seed to seed the calculation.
891*/
892
893/*! \fn size_t qHash(signed char key, size_t seed = 0)
894 \relates QHash
895 \since 5.0
896
897 Returns the hash value for the \a key, using \a seed to seed the calculation.
898*/
899
900/*! \fn size_t qHash(ushort key, size_t seed = 0)
901 \relates QHash
902 \since 5.0
903
904 Returns the hash value for the \a key, using \a seed to seed the calculation.
905*/
906
907/*! \fn size_t qHash(short key, size_t seed = 0)
908 \relates QHash
909 \since 5.0
910
911 Returns the hash value for the \a key, using \a seed to seed the calculation.
912*/
913
914/*! \fn size_t qHash(uint key, size_t seed = 0)
915 \relates QHash
916 \since 5.0
917
918 Returns the hash value for the \a key, using \a seed to seed the calculation.
919*/
920
921/*! \fn size_t qHash(int key, size_t seed = 0)
922 \relates QHash
923 \since 5.0
924
925 Returns the hash value for the \a key, using \a seed to seed the calculation.
926*/
927
928/*! \fn size_t qHash(ulong key, size_t seed = 0)
929 \relates QHash
930 \since 5.0
931
932 Returns the hash value for the \a key, using \a seed to seed the calculation.
933*/
934
935/*! \fn size_t qHash(long key, size_t seed = 0)
936 \relates QHash
937 \since 5.0
938
939 Returns the hash value for the \a key, using \a seed to seed the calculation.
940*/
941
942/*! \fn size_t qHash(quint64 key, size_t seed = 0)
943 \relates QHash
944 \since 5.0
945
946 Returns the hash value for the \a key, using \a seed to seed the calculation.
947*/
948
949/*! \fn size_t qHash(qint64 key, size_t seed = 0)
950 \relates QHash
951 \since 5.0
952
953 Returns the hash value for the \a key, using \a seed to seed the calculation.
954*/
955
956/*! \fn size_t qHash(char8_t key, size_t seed = 0)
957 \relates QHash
958 \since 6.0
959
960 Returns the hash value for the \a key, using \a seed to seed the calculation.
961*/
962
963/*! \fn size_t qHash(char16_t key, size_t seed = 0)
964 \relates QHash
965 \since 6.0
966
967 Returns the hash value for the \a key, using \a seed to seed the calculation.
968*/
969
970/*! \fn size_t qHash(char32_t key, size_t seed = 0)
971 \relates QHash
972 \since 6.0
973
974 Returns the hash value for the \a key, using \a seed to seed the calculation.
975*/
976
977/*! \fn size_t qHash(wchar_t key, size_t seed = 0)
978 \relates QHash
979 \since 6.0
980
981 Returns the hash value for the \a key, using \a seed to seed the calculation.
982*/
983
984/*! \fn size_t qHash(float key, size_t seed) noexcept
985 \relates QHash
986 \since 5.3
987
988 Returns the hash value for the \a key, using \a seed to seed the calculation.
989*/
990
991/*! \relates QHash
992 \since 5.3
993
994 Returns the hash value for the \a key, using \a seed to seed the calculation.
995*/
996size_t qHash(double key, size_t seed) noexcept
997{
998 // ensure -0 gets mapped to 0
999 key += 0.0;
1000 if constexpr (sizeof(double) == sizeof(size_t)) {
1001 size_t k;
1002 memcpy(&k, &key, sizeof(double));
1003 return QHashPrivate::hash(k, seed);
1004 } else {
1005 return murmurhash(&key, sizeof(key), seed);
1006 }
1007}
1008
1009#if !defined(Q_OS_DARWIN) || defined(Q_CLANG_QDOC)
1010/*! \relates QHash
1011 \since 5.3
1012
1013 Returns the hash value for the \a key, using \a seed to seed the calculation.
1014*/
1015size_t qHash(long double key, size_t seed) noexcept
1016{
1017 // ensure -0 gets mapped to 0
1018 key += static_cast<long double>(0.0);
1019 if constexpr (sizeof(long double) == sizeof(size_t)) {
1020 size_t k;
1021 memcpy(&k, &key, sizeof(long double));
1022 return QHashPrivate::hash(k, seed);
1023 } else {
1024 return murmurhash(&key, sizeof(key), seed);
1025 }
1026}
1027#endif
1028
1029/*! \fn size_t qHash(const QChar key, size_t seed = 0)
1030 \relates QHash
1031 \since 5.0
1032
1033 Returns the hash value for the \a key, using \a seed to seed the calculation.
1034*/
1035
1036/*! \fn size_t qHash(const QByteArray &key, size_t seed = 0)
1037 \relates QHash
1038 \since 5.0
1039
1040 Returns the hash value for the \a key, using \a seed to seed the calculation.
1041*/
1042
1043/*! \fn size_t qHash(const QByteArrayView &key, size_t seed = 0)
1044 \relates QHash
1045 \since 6.0
1046
1047 Returns the hash value for the \a key, using \a seed to seed the calculation.
1048*/
1049
1050/*! \fn size_t qHash(const QBitArray &key, size_t seed = 0)
1051 \relates QHash
1052 \since 5.0
1053
1054 Returns the hash value for the \a key, using \a seed to seed the calculation.
1055*/
1056
1057/*! \fn size_t qHash(const QString &key, size_t seed = 0)
1058 \relates QHash
1059 \since 5.0
1060
1061 Returns the hash value for the \a key, using \a seed to seed the calculation.
1062*/
1063
1064/*! \fn size_t qHash(QStringView key, size_t seed = 0)
1065 \relates QStringView
1066 \since 5.10
1067
1068 Returns the hash value for the \a key, using \a seed to seed the calculation.
1069*/
1070
1071/*! \fn size_t qHash(QLatin1String key, size_t seed = 0)
1072 \relates QHash
1073 \since 5.0
1074
1075 Returns the hash value for the \a key, using \a seed to seed the calculation.
1076*/
1077
1078/*! \fn template <class T> size_t qHash(const T *key, size_t seed = 0)
1079 \relates QHash
1080 \since 5.0
1081
1082 Returns the hash value for the \a key, using \a seed to seed the calculation.
1083*/
1084
1085/*! \fn template <class T> size_t qHash(std::nullptr_t key, size_t seed = 0)
1086 \relates QHash
1087 \since 6.0
1088
1089 Returns the hash value for the \a key, using \a seed to seed the calculation.
1090*/
1091
1092/*!
1093 \class QHash
1094 \inmodule QtCore
1095 \brief The QHash class is a template class that provides a hash-table-based dictionary.
1096
1097 \ingroup tools
1098 \ingroup shared
1099
1100 \reentrant
1101
1102 QHash\<Key, T\> is one of Qt's generic \l{container classes}. It
1103 stores (key, value) pairs and provides very fast lookup of the
1104 value associated with a key.
1105
1106 QHash provides very similar functionality to QMap. The
1107 differences are:
1108
1109 \list
1110 \li QHash provides faster lookups than QMap. (See \l{Algorithmic
1111 Complexity} for details.)
1112 \li When iterating over a QMap, the items are always sorted by
1113 key. With QHash, the items are arbitrarily ordered.
1114 \li The key type of a QMap must provide operator<(). The key
1115 type of a QHash must provide operator==() and a global
1116 hash function called qHash() (see \l{qHash}).
1117 \endlist
1118
1119 Here's an example QHash with QString keys and \c int values:
1120 \snippet code/src_corelib_tools_qhash.cpp 0
1121
1122 To insert a (key, value) pair into the hash, you can use operator[]():
1123
1124 \snippet code/src_corelib_tools_qhash.cpp 1
1125
1126 This inserts the following three (key, value) pairs into the
1127 QHash: ("one", 1), ("three", 3), and ("seven", 7). Another way to
1128 insert items into the hash is to use insert():
1129
1130 \snippet code/src_corelib_tools_qhash.cpp 2
1131
1132 To look up a value, use operator[]() or value():
1133
1134 \snippet code/src_corelib_tools_qhash.cpp 3
1135
1136 If there is no item with the specified key in the hash, these
1137 functions return a \l{default-constructed value}.
1138
1139 If you want to check whether the hash contains a particular key,
1140 use contains():
1141
1142 \snippet code/src_corelib_tools_qhash.cpp 4
1143
1144 There is also a value() overload that uses its second argument as
1145 a default value if there is no item with the specified key:
1146
1147 \snippet code/src_corelib_tools_qhash.cpp 5
1148
1149 In general, we recommend that you use contains() and value()
1150 rather than operator[]() for looking up a key in a hash. The
1151 reason is that operator[]() silently inserts an item into the
1152 hash if no item exists with the same key (unless the hash is
1153 const). For example, the following code snippet will create 1000
1154 items in memory:
1155
1156 \snippet code/src_corelib_tools_qhash.cpp 6
1157
1158 To avoid this problem, replace \c hash[i] with \c hash.value(i)
1159 in the code above.
1160
1161 Internally, QHash uses a hash table to perform lookups. This
1162 hash table automatically grows to
1163 provide fast lookups without wasting too much memory. You can
1164 still control the size of the hash table by calling reserve() if
1165 you already know approximately how many items the QHash will
1166 contain, but this isn't necessary to obtain good performance. You
1167 can also call capacity() to retrieve the hash table's size.
1168
1169 QHash will not shrink automatically if items are removed from the
1170 table. To minimize the memory used by the hash, call squeeze().
1171
1172 If you want to navigate through all the (key, value) pairs stored
1173 in a QHash, you can use an iterator. QHash provides both
1174 \l{Java-style iterators} (QHashIterator and QMutableHashIterator)
1175 and \l{STL-style iterators} (QHash::const_iterator and
1176 QHash::iterator). Here's how to iterate over a QHash<QString,
1177 int> using a Java-style iterator:
1178
1179 \snippet code/src_corelib_tools_qhash.cpp 7
1180
1181 Here's the same code, but using an STL-style iterator:
1182
1183 \snippet code/src_corelib_tools_qhash.cpp 8
1184
1185 QHash is unordered, so an iterator's sequence cannot be assumed
1186 to be predictable. If ordering by key is required, use a QMap.
1187
1188 A QHash allows only one value per key. If you call
1189 insert() with a key that already exists in the QHash, the
1190 previous value is erased. For example:
1191
1192 \snippet code/src_corelib_tools_qhash.cpp 9
1193
1194 If you need to store multiple entries for the same key in the
1195 hash table, use \l{QMultiHash}.
1196
1197 If you only need to extract the values from a hash (not the keys),
1198 you can also use \l{foreach}:
1199
1200 \snippet code/src_corelib_tools_qhash.cpp 12
1201
1202 Items can be removed from the hash in several ways. One way is to
1203 call remove(); this will remove any item with the given key.
1204 Another way is to use QMutableHashIterator::remove(). In addition,
1205 you can clear the entire hash using clear().
1206
1207 QHash's key and value data types must be \l{assignable data
1208 types}. You cannot, for example, store a QWidget as a value;
1209 instead, store a QWidget *.
1210
1211 \target qHash
1212 \section2 The qHash() hashing function
1213
1214 A QHash's key type has additional requirements other than being an
1215 assignable data type: it must provide operator==(), and there must also be
1216 a qHash() function in the type's namespace that returns a hash value for an
1217 argument of the key's type.
1218
1219 The qHash() function computes a numeric value based on a key. It
1220 can use any algorithm imaginable, as long as it always returns
1221 the same value if given the same argument. In other words, if
1222 \c{e1 == e2}, then \c{qHash(e1) == qHash(e2)} must hold as well.
1223 However, to obtain good performance, the qHash() function should
1224 attempt to return different hash values for different keys to the
1225 largest extent possible.
1226
1227 For a key type \c{K}, the qHash function must have one of these signatures:
1228
1229 \snippet code/src_corelib_tools_qhash.cpp 32
1230
1231 The two-arguments overloads take an unsigned integer that should be used to
1232 seed the calculation of the hash function. This seed is provided by QHash
1233 in order to prevent a family of \l{algorithmic complexity attacks}. If both
1234 a one-argument and a two-arguments overload are defined for a key type,
1235 the latter is used by QHash (note that you can simply define a
1236 two-arguments version, and use a default value for the seed parameter).
1237
1238 Here's a partial list of the C++ and Qt types that can serve as keys in a
1239 QHash: any integer type (char, unsigned long, etc.), any pointer type,
1240 QChar, QString, and QByteArray. For all of these, the \c <QHash> header
1241 defines a qHash() function that computes an adequate hash value. Many other
1242 Qt classes also declare a qHash overload for their type; please refer to
1243 the documentation of each class.
1244
1245 If you want to use other types as the key, make sure that you provide
1246 operator==() and a qHash() implementation. The convenience qHashMulti()
1247 function can be used to implement qHash() for a custom type, where
1248 one usually wants to produce a hash value from multiple fields:
1249
1250 Example:
1251 \snippet code/src_corelib_tools_qhash.cpp 13
1252
1253 In the example above, we've relied on Qt's own implementation of
1254 qHash() for QString and QDate to give us a hash value for the
1255 employee's name and date of birth respectively.
1256
1257 Note that the implementation of the qHash() overloads offered by Qt
1258 may change at any time. You \b{must not} rely on the fact that qHash()
1259 will give the same results (for the same inputs) across different Qt
1260 versions.
1261
1262 \section2 Algorithmic complexity attacks
1263
1264 All hash tables are vulnerable to a particular class of denial of service
1265 attacks, in which the attacker carefully pre-computes a set of different
1266 keys that are going to be hashed in the same bucket of a hash table (or
1267 even have the very same hash value). The attack aims at getting the
1268 worst-case algorithmic behavior (O(n) instead of amortized O(1), see
1269 \l{Algorithmic Complexity} for the details) when the data is fed into the
1270 table.
1271
1272 In order to avoid this worst-case behavior, the calculation of the hash
1273 value done by qHash() can be salted by a random seed, that nullifies the
1274 attack's extent. This seed is automatically generated by QHash once per
1275 process, and then passed by QHash as the second argument of the
1276 two-arguments overload of the qHash() function.
1277
1278 This randomization of QHash is enabled by default. Even though programs
1279 should never depend on a particular QHash ordering, there may be situations
1280 where you temporarily need deterministic behavior, for example for debugging or
1281 regression testing. To disable the randomization, define the environment
1282 variable \c QT_HASH_SEED to have the value 0. Alternatively, you can call
1283 the qSetGlobalQHashSeed() function with the value 0.
1284
1285 \sa QHashIterator, QMutableHashIterator, QMap, QSet
1286*/
1287
1288/*! \fn template <class Key, class T> QHash<Key, T>::QHash()
1289
1290 Constructs an empty hash.
1291
1292 \sa clear()
1293*/
1294
1295/*!
1296 \fn template <class Key, class T> QHash<Key, T>::QHash(QHash &&other)
1297
1298 Move-constructs a QHash instance, making it point at the same
1299 object that \a other was pointing to.
1300
1301 \since 5.2
1302*/
1303
1304/*! \fn template <class Key, class T> QHash<Key, T>::QHash(std::initializer_list<std::pair<Key,T> > list)
1305 \since 5.1
1306
1307 Constructs a hash with a copy of each of the elements in the
1308 initializer list \a list.
1309*/
1310
1311/*! \fn template <class Key, class T> template <class InputIterator> QHash<Key, T>::QHash(InputIterator begin, InputIterator end)
1312 \since 5.14
1313
1314 Constructs a hash with a copy of each of the elements in the iterator range
1315 [\a begin, \a end). Either the elements iterated by the range must be
1316 objects with \c{first} and \c{second} data members (like \c{QPair},
1317 \c{std::pair}, etc.) convertible to \c Key and to \c T respectively; or the
1318 iterators must have \c{key()} and \c{value()} member functions, returning a
1319 key convertible to \c Key and a value convertible to \c T respectively.
1320*/
1321
1322/*! \fn template <class Key, class T> QHash<Key, T>::QHash(const QHash &other)
1323
1324 Constructs a copy of \a other.
1325
1326 This operation occurs in \l{constant time}, because QHash is
1327 \l{implicitly shared}. This makes returning a QHash from a
1328 function very fast. If a shared instance is modified, it will be
1329 copied (copy-on-write), and this takes \l{linear time}.
1330
1331 \sa operator=()
1332*/
1333
1334/*! \fn template <class Key, class T> QHash<Key, T>::~QHash()
1335
1336 Destroys the hash. References to the values in the hash and all
1337 iterators of this hash become invalid.
1338*/
1339
1340/*! \fn template <class Key, class T> QHash &QHash<Key, T>::operator=(const QHash &other)
1341
1342 Assigns \a other to this hash and returns a reference to this hash.
1343*/
1344
1345/*!
1346 \fn template <class Key, class T> QHash &QHash<Key, T>::operator=(QHash &&other)
1347
1348 Move-assigns \a other to this QHash instance.
1349
1350 \since 5.2
1351*/
1352
1353/*! \fn template <class Key, class T> void QHash<Key, T>::swap(QHash &other)
1354 \since 4.8
1355
1356 Swaps hash \a other with this hash. This operation is very
1357 fast and never fails.
1358*/
1359
1360/*! \fn template <class Key, class T> void QMultiHash<Key, T>::swap(QMultiHash &other)
1361 \since 4.8
1362
1363 Swaps hash \a other with this hash. This operation is very
1364 fast and never fails.
1365*/
1366
1367/*! \fn template <class Key, class T> bool QHash<Key, T>::operator==(const QHash &other) const
1368
1369 Returns \c true if \a other is equal to this hash; otherwise returns
1370 false.
1371
1372 Two hashes are considered equal if they contain the same (key,
1373 value) pairs.
1374
1375 This function requires the value type to implement \c operator==().
1376
1377 \sa operator!=()
1378*/
1379
1380/*! \fn template <class Key, class T> bool QHash<Key, T>::operator!=(const QHash &other) const
1381
1382 Returns \c true if \a other is not equal to this hash; otherwise
1383 returns \c false.
1384
1385 Two hashes are considered equal if they contain the same (key,
1386 value) pairs.
1387
1388 This function requires the value type to implement \c operator==().
1389
1390 \sa operator==()
1391*/
1392
1393/*! \fn template <class Key, class T> int QHash<Key, T>::size() const
1394
1395 Returns the number of items in the hash.
1396
1397 \sa isEmpty(), count()
1398*/
1399
1400/*! \fn template <class Key, class T> bool QHash<Key, T>::isEmpty() const
1401
1402 Returns \c true if the hash contains no items; otherwise returns
1403 false.
1404
1405 \sa size()
1406*/
1407
1408/*! \fn template <class Key, class T> int QHash<Key, T>::capacity() const
1409
1410 Returns the number of buckets in the QHash's internal hash table.
1411
1412 The sole purpose of this function is to provide a means of fine
1413 tuning QHash's memory usage. In general, you will rarely ever
1414 need to call this function. If you want to know how many items are
1415 in the hash, call size().
1416
1417 \sa reserve(), squeeze()
1418*/
1419
1420/*! \fn template <class Key, class T> float QHash<Key, T>::load_factor() const noexcept
1421
1422 Returns the current load factor of the QHash's internal hash table.
1423 This is the same as capacity()/size(). The implementation used
1424 will aim to keep the load factor between 0.25 and 0.5. This avoids
1425 having too many hash table collisions that would degrade performance.
1426
1427 Even with a low load factor, the implementation of the hash table has a
1428 very low memory overhead.
1429
1430 This method purely exists for diagnostic purposes and you should rarely
1431 need to call it yourself.
1432
1433 \sa reserve(), squeeze()
1434*/
1435
1436
1437/*! \fn template <class Key, class T> void QHash<Key, T>::reserve(qsizetype size)
1438
1439 Ensures that the QHash's internal hash table has space to store at
1440 least \a size items without having to grow the hash table.
1441
1442 This implies that the hash table will contain at least 2 * \a size buckets
1443 to ensure good performance
1444
1445 This function is useful for code that needs to build a huge hash
1446 and wants to avoid repeated reallocation. For example:
1447
1448 \snippet code/src_corelib_tools_qhash.cpp 14
1449
1450 Ideally, \a size should be the maximum number of items expected
1451 in the hash. QHash will then choose the smallest possible
1452 number of buckets that will allow storing \a size items in the table
1453 without having to grow the internal hash table. If \a size
1454 is an underestimate, the worst that will happen is that the QHash
1455 will be a bit slower.
1456
1457 In general, you will rarely ever need to call this function.
1458 QHash's internal hash table automatically grows to
1459 provide good performance without wasting too much memory.
1460
1461 \sa squeeze(), capacity()
1462*/
1463
1464/*! \fn template <class Key, class T> void QHash<Key, T>::squeeze()
1465
1466 Reduces the size of the QHash's internal hash table to save
1467 memory.
1468
1469 The sole purpose of this function is to provide a means of fine
1470 tuning QHash's memory usage. In general, you will rarely ever
1471 need to call this function.
1472
1473 \sa reserve(), capacity()
1474*/
1475
1476/*! \fn template <class Key, class T> void QHash<Key, T>::detach()
1477
1478 \internal
1479
1480 Detaches this hash from any other hashes with which it may share
1481 data.
1482
1483 \sa isDetached()
1484*/
1485
1486/*! \fn template <class Key, class T> bool QHash<Key, T>::isDetached() const
1487
1488 \internal
1489
1490 Returns \c true if the hash's internal data isn't shared with any
1491 other hash object; otherwise returns \c false.
1492
1493 \sa detach()
1494*/
1495
1496/*! \fn template <class Key, class T> bool QHash<Key, T>::isSharedWith(const QHash &other) const
1497
1498 \internal
1499
1500 Returns true if the internal hash table of this QHash is shared with \a other, otherwise false.
1501*/
1502
1503/*! \fn template <class Key, class T> void QHash<Key, T>::clear()
1504
1505 Removes all items from the hash and frees up all memory used by it.
1506
1507 \sa remove()
1508*/
1509
1510/*! \fn template <class Key, class T> bool QHash<Key, T>::remove(const Key &key)
1511
1512 Removes the item that has the \a key from the hash.
1513 Returns true if the key exists in the hash and the item has been removed,
1514 and false otherwise.
1515
1516 \sa clear(), take()
1517*/
1518
1519/*! \fn template <class Key, class T> T QHash<Key, T>::take(const Key &key)
1520
1521 Removes the item with the \a key from the hash and returns
1522 the value associated with it.
1523
1524 If the item does not exist in the hash, the function simply
1525 returns a \l{default-constructed value}.
1526
1527 If you don't use the return value, remove() is more efficient.
1528
1529 \sa remove()
1530*/
1531
1532/*! \fn template <class Key, class T> bool QHash<Key, T>::contains(const Key &key) const
1533
1534 Returns \c true if the hash contains an item with the \a key;
1535 otherwise returns \c false.
1536
1537 \sa count(), QMultiHash::contains()
1538*/
1539
1540/*! \fn template <class Key, class T> T QHash<Key, T>::value(const Key &key, const T &defaultValue = T()) const
1541 \overload
1542
1543 Returns the value associated with the \a key.
1544
1545 If the hash contains no item with the \a key, the function
1546 returns \a defaultValue, which is a \l{default-constructed value} if the
1547 parameter has not been specified.
1548*/
1549
1550/*! \fn template <class Key, class T> T &QHash<Key, T>::operator[](const Key &key)
1551
1552 Returns the value associated with the \a key as a modifiable
1553 reference.
1554
1555 If the hash contains no item with the \a key, the function inserts
1556 a \l{default-constructed value} into the hash with the \a key, and
1557 returns a reference to it.
1558
1559 \sa insert(), value()
1560*/
1561
1562/*! \fn template <class Key, class T> const T QHash<Key, T>::operator[](const Key &key) const
1563
1564 \overload
1565
1566 Same as value().
1567*/
1568
1569/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys() const
1570
1571 Returns a list containing all the keys in the hash, in an
1572 arbitrary order.
1573
1574 The order is guaranteed to be the same as that used by values().
1575
1576 This function creates a new list, in \l {linear time}. The time and memory
1577 use that entails can be avoided by iterating from \l keyBegin() to
1578 \l keyEnd().
1579
1580 \sa values(), key()
1581*/
1582
1583/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys(const T &value) const
1584
1585 \overload
1586
1587 Returns a list containing all the keys associated with value \a
1588 value, in an arbitrary order.
1589
1590 This function can be slow (\l{linear time}), because QHash's
1591 internal data structure is optimized for fast lookup by key, not
1592 by value.
1593*/
1594
1595/*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values() const
1596
1597 Returns a list containing all the values in the hash, in an
1598 arbitrary order.
1599
1600 The order is guaranteed to be the same as that used by keys().
1601
1602 This function creates a new list, in \l {linear time}. The time and memory
1603 use that entails can be avoided by iterating from \l keyValueBegin() to
1604 \l keyValueEnd().
1605
1606 \sa keys(), value()
1607*/
1608
1609/*!
1610 \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value, const Key &defaultKey = Key()) const
1611 \since 4.3
1612
1613 Returns the first key mapped to \a value, or \a defaultKey if the
1614 hash contains no item mapped to \a value.
1615
1616 This function can be slow (\l{linear time}), because QHash's
1617 internal data structure is optimized for fast lookup by key, not
1618 by value.
1619*/
1620
1621/*! \fn template <class Key, class T> int QHash<Key, T>::count(const Key &key) const
1622
1623 Returns the number of items associated with the \a key.
1624
1625 \sa contains()
1626*/
1627
1628/*! \fn template <class Key, class T> int QHash<Key, T>::count() const
1629
1630 \overload
1631
1632 Same as size().
1633*/
1634
1635/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::begin()
1636
1637 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
1638 the hash.
1639
1640 \sa constBegin(), end()
1641*/
1642
1643/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::begin() const
1644
1645 \overload
1646*/
1647
1648/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cbegin() const
1649 \since 5.0
1650
1651 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1652 in the hash.
1653
1654 \sa begin(), cend()
1655*/
1656
1657/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constBegin() const
1658
1659 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1660 in the hash.
1661
1662 \sa begin(), constEnd()
1663*/
1664
1665/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyBegin() const
1666 \since 5.6
1667
1668 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
1669 in the hash.
1670
1671 \sa keyEnd()
1672*/
1673
1674/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::end()
1675
1676 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
1677 after the last item in the hash.
1678
1679 \sa begin(), constEnd()
1680*/
1681
1682/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::end() const
1683
1684 \overload
1685*/
1686
1687/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constEnd() const
1688
1689 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1690 item after the last item in the hash.
1691
1692 \sa constBegin(), end()
1693*/
1694
1695/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cend() const
1696 \since 5.0
1697
1698 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1699 item after the last item in the hash.
1700
1701 \sa cbegin(), end()
1702*/
1703
1704/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyEnd() const
1705 \since 5.6
1706
1707 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1708 item after the last key in the hash.
1709
1710 \sa keyBegin()
1711*/
1712
1713/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueBegin()
1714 \since 5.10
1715
1716 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
1717 in the hash.
1718
1719 \sa keyValueEnd()
1720*/
1721
1722/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueEnd()
1723 \since 5.10
1724
1725 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1726 entry after the last entry in the hash.
1727
1728 \sa keyValueBegin()
1729*/
1730
1731/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueBegin() const
1732 \since 5.10
1733
1734 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
1735 in the hash.
1736
1737 \sa keyValueEnd()
1738*/
1739
1740/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueBegin() const
1741 \since 5.10
1742
1743 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
1744 in the hash.
1745
1746 \sa keyValueBegin()
1747*/
1748
1749/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueEnd() const
1750 \since 5.10
1751
1752 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1753 entry after the last entry in the hash.
1754
1755 \sa keyValueBegin()
1756*/
1757
1758/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueEnd() const
1759 \since 5.10
1760
1761 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1762 entry after the last entry in the hash.
1763
1764 \sa constKeyValueBegin()
1765*/
1766
1767/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator pos)
1768 \since 5.7
1769
1770 Removes the (key, value) pair associated with the iterator \a pos
1771 from the hash, and returns an iterator to the next item in the
1772 hash.
1773
1774 This function never causes QHash to
1775 rehash its internal data structure. This means that it can safely
1776 be called while iterating, and won't affect the order of items in
1777 the hash. For example:
1778
1779 \snippet code/src_corelib_tools_qhash.cpp 15
1780
1781 \sa remove(), take(), find()
1782*/
1783
1784/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::find(const Key &key)
1785
1786 Returns an iterator pointing to the item with the \a key in the
1787 hash.
1788
1789 If the hash contains no item with the \a key, the function
1790 returns end().
1791
1792 If the hash contains multiple items with the \a key, this
1793 function returns an iterator that points to the most recently
1794 inserted value. The other values are accessible by incrementing
1795 the iterator. For example, here's some code that iterates over all
1796 the items with the same key:
1797
1798 \snippet code/src_corelib_tools_qhash.cpp 16
1799
1800 \sa value(), values()
1801*/
1802
1803/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &key) const
1804
1805 \overload
1806*/
1807
1808/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &key) const
1809 \since 4.1
1810
1811 Returns an iterator pointing to the item with the \a key in the
1812 hash.
1813
1814 If the hash contains no item with the \a key, the function
1815 returns constEnd().
1816
1817 \sa find()
1818*/
1819
1820/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &key, const T &value)
1821
1822 Inserts a new item with the \a key and a value of \a value.
1823
1824 If there is already an item with the \a key, that item's value
1825 is replaced with \a value.
1826*/
1827
1828/*!
1829 \fn template <class Key, class T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(const Key &key, Args&&... args)
1830 \fn template <class Key, class T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(Key &&key, Args&&... args)
1831
1832 Inserts a new element into the container. This new element
1833 is constructed in-place using \a args as the arguments for its
1834 construction.
1835
1836 Returns an iterator pointing to the new element.
1837*/
1838
1839
1840/*! \fn template <class Key, class T> void QHash<Key, T>::insert(const QHash &other)
1841 \since 5.15
1842
1843 Inserts all the items in the \a other hash into this hash.
1844
1845 If a key is common to both hashes, its value will be replaced with the
1846 value stored in \a other.
1847
1848 \note If \a other contains multiple entries with the same key then the
1849 final value of the key is undefined.
1850*/
1851
1852/*! \fn template <class Key, class T> bool QHash<Key, T>::empty() const
1853
1854 This function is provided for STL compatibility. It is equivalent
1855 to isEmpty(), returning true if the hash is empty; otherwise
1856 returns \c false.
1857*/
1858
1859/*! \fn template <class Key, class T> QPair<iterator, iterator> QMultiHash<Key, T>::equal_range(const Key &key)
1860 \since 5.7
1861
1862 Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
1863 are stored under \a key. If the range is empty then both iterators will be equal to end().
1864*/
1865
1866/*!
1867 \fn template <class Key, class T> QPair<const_iterator, const_iterator> QMultiHash<Key, T>::equal_range(const Key &key) const
1868 \overload
1869 \since 5.7
1870*/
1871
1872/*! \typedef QHash::ConstIterator
1873
1874 Qt-style synonym for QHash::const_iterator.
1875*/
1876
1877/*! \typedef QHash::Iterator
1878
1879 Qt-style synonym for QHash::iterator.
1880*/
1881
1882/*! \typedef QHash::difference_type
1883
1884 Typedef for ptrdiff_t. Provided for STL compatibility.
1885*/
1886
1887/*! \typedef QHash::key_type
1888
1889 Typedef for Key. Provided for STL compatibility.
1890*/
1891
1892/*! \typedef QHash::mapped_type
1893
1894 Typedef for T. Provided for STL compatibility.
1895*/
1896
1897/*! \typedef QHash::size_type
1898
1899 Typedef for int. Provided for STL compatibility.
1900*/
1901
1902/*! \typedef QHash::iterator::difference_type
1903 \internal
1904*/
1905
1906/*! \typedef QHash::iterator::iterator_category
1907 \internal
1908*/
1909
1910/*! \typedef QHash::iterator::pointer
1911 \internal
1912*/
1913
1914/*! \typedef QHash::iterator::reference
1915 \internal
1916*/
1917
1918/*! \typedef QHash::iterator::value_type
1919 \internal
1920*/
1921
1922/*! \typedef QHash::const_iterator::difference_type
1923 \internal
1924*/
1925
1926/*! \typedef QHash::const_iterator::iterator_category
1927 \internal
1928*/
1929
1930/*! \typedef QHash::const_iterator::pointer
1931 \internal
1932*/
1933
1934/*! \typedef QHash::const_iterator::reference
1935 \internal
1936*/
1937
1938/*! \typedef QHash::const_iterator::value_type
1939 \internal
1940*/
1941
1942/*! \typedef QHash::key_iterator::difference_type
1943 \internal
1944*/
1945
1946/*! \typedef QHash::key_iterator::iterator_category
1947 \internal
1948*/
1949
1950/*! \typedef QHash::key_iterator::pointer
1951 \internal
1952*/
1953
1954/*! \typedef QHash::key_iterator::reference
1955 \internal
1956*/
1957
1958/*! \typedef QHash::key_iterator::value_type
1959 \internal
1960*/
1961
1962/*! \class QHash::iterator
1963 \inmodule QtCore
1964 \brief The QHash::iterator class provides an STL-style non-const iterator for QHash.
1965
1966 QHash features both \l{STL-style iterators} and \l{Java-style
1967 iterators}. The STL-style iterators are more low-level and more
1968 cumbersome to use; on the other hand, they are slightly faster
1969 and, for developers who already know STL, have the advantage of
1970 familiarity.
1971
1972 QHash\<Key, T\>::iterator allows you to iterate over a QHash
1973 and to modify the value (but not the key) associated
1974 with a particular key. If you want to iterate over a const QHash,
1975 you should use QHash::const_iterator. It is generally good
1976 practice to use QHash::const_iterator on a non-const QHash as
1977 well, unless you need to change the QHash through the iterator.
1978 Const iterators are slightly faster, and can improve code
1979 readability.
1980
1981 The default QHash::iterator constructor creates an uninitialized
1982 iterator. You must initialize it using a QHash function like
1983 QHash::begin(), QHash::end(), or QHash::find() before you can
1984 start iterating. Here's a typical loop that prints all the (key,
1985 value) pairs stored in a hash:
1986
1987 \snippet code/src_corelib_tools_qhash.cpp 17
1988
1989 Unlike QMap, which orders its items by key, QHash stores its
1990 items in an arbitrary order.
1991
1992 Let's see a few examples of things we can do with a
1993 QHash::iterator that we cannot do with a QHash::const_iterator.
1994 Here's an example that increments every value stored in the QHash
1995 by 2:
1996
1997 \snippet code/src_corelib_tools_qhash.cpp 18
1998
1999 Here's an example that removes all the items whose key is a
2000 string that starts with an underscore character:
2001
2002 \snippet code/src_corelib_tools_qhash.cpp 19
2003
2004 The call to QHash::erase() removes the item pointed to by the
2005 iterator from the hash, and returns an iterator to the next item.
2006 Here's another way of removing an item while iterating:
2007
2008 \snippet code/src_corelib_tools_qhash.cpp 20
2009
2010 It might be tempting to write code like this:
2011
2012 \snippet code/src_corelib_tools_qhash.cpp 21
2013
2014 However, this will potentially crash in \c{++i}, because \c i is
2015 a dangling iterator after the call to erase().
2016
2017 Multiple iterators can be used on the same hash. However, be aware
2018 that any modification performed directly on the QHash (inserting and
2019 removing items) can cause the iterators to become invalid.
2020
2021 Inserting items into the hash or calling methods such as QHash::reserve()
2022 or QHash::squeeze() can invalidate all iterators pointing into the hash.
2023 Iterators are guaranteed to stay valid only as long as the QHash doesn't have
2024 to grow/shrink its internal hash table.
2025 Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
2026
2027 You can however safely use iterators to remove entries from the hash
2028 using the QHash::erase() method. This function can safely be called while
2029 iterating, and won't affect the order of items in the hash.
2030
2031 If you need to keep iterators over a long period of time, we recommend
2032 that you use QMap rather than QHash.
2033
2034 \warning Iterators on implicitly shared containers do not work
2035 exactly like STL-iterators. You should avoid copying a container
2036 while iterators are active on that container. For more information,
2037 read \l{Implicit sharing iterator problem}.
2038
2039 \sa QHash::const_iterator, QHash::key_iterator, QMutableHashIterator
2040*/
2041
2042/*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator()
2043
2044 Constructs an uninitialized iterator.
2045
2046 Functions like key(), value(), and operator++() must not be
2047 called on an uninitialized iterator. Use operator=() to assign a
2048 value to it before using it.
2049
2050 \sa QHash::begin(), QHash::end()
2051*/
2052
2053/*! \fn template <class Key, class T> const Key &QHash<Key, T>::iterator::key() const
2054
2055 Returns the current item's key as a const reference.
2056
2057 There is no direct way of changing an item's key through an
2058 iterator, although it can be done by calling QHash::erase()
2059 followed by QHash::insert().
2060
2061 \sa value()
2062*/
2063
2064/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::value() const
2065
2066 Returns a modifiable reference to the current item's value.
2067
2068 You can change the value of an item by using value() on
2069 the left side of an assignment, for example:
2070
2071 \snippet code/src_corelib_tools_qhash.cpp 22
2072
2073 \sa key(), operator*()
2074*/
2075
2076/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::operator*() const
2077
2078 Returns a modifiable reference to the current item's value.
2079
2080 Same as value().
2081
2082 \sa key()
2083*/
2084
2085/*! \fn template <class Key, class T> T *QHash<Key, T>::iterator::operator->() const
2086
2087 Returns a pointer to the current item's value.
2088
2089 \sa value()
2090*/
2091
2092/*!
2093 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const iterator &other) const
2094 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const const_iterator &other) const
2095
2096 Returns \c true if \a other points to the same item as this
2097 iterator; otherwise returns \c false.
2098
2099 \sa operator!=()
2100*/
2101
2102/*!
2103 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const iterator &other) const
2104 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const const_iterator &other) const
2105
2106 Returns \c true if \a other points to a different item than this
2107 iterator; otherwise returns \c false.
2108
2109 \sa operator==()
2110*/
2111
2112/*!
2113 \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator++()
2114
2115 The prefix ++ operator (\c{++i}) advances the iterator to the
2116 next item in the hash and returns an iterator to the new current
2117 item.
2118
2119 Calling this function on QHash::end() leads to undefined results.
2120*/
2121
2122/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator++(int)
2123
2124 \overload
2125
2126 The postfix ++ operator (\c{i++}) advances the iterator to the
2127 next item in the hash and returns an iterator to the previously
2128 current item.
2129*/
2130
2131/*! \class QHash::const_iterator
2132 \inmodule QtCore
2133 \brief The QHash::const_iterator class provides an STL-style const iterator for QHash.
2134
2135 QHash features both \l{STL-style iterators} and \l{Java-style
2136 iterators}. The STL-style iterators are more low-level and more
2137 cumbersome to use; on the other hand, they are slightly faster
2138 and, for developers who already know STL, have the advantage of
2139 familiarity.
2140
2141 QHash\<Key, T\>::const_iterator allows you to iterate over a
2142 QHash. If you want to modify the QHash as you
2143 iterate over it, you must use QHash::iterator instead. It is
2144 generally good practice to use QHash::const_iterator on a
2145 non-const QHash as well, unless you need to change the QHash
2146 through the iterator. Const iterators are slightly faster, and
2147 can improve code readability.
2148
2149 The default QHash::const_iterator constructor creates an
2150 uninitialized iterator. You must initialize it using a QHash
2151 function like QHash::constBegin(), QHash::constEnd(), or
2152 QHash::find() before you can start iterating. Here's a typical
2153 loop that prints all the (key, value) pairs stored in a hash:
2154
2155 \snippet code/src_corelib_tools_qhash.cpp 23
2156
2157 Unlike QMap, which orders its items by key, QHash stores its
2158 items in an arbitrary order. The only guarantee is that items that
2159 share the same key (because they were inserted using
2160 a QMultiHash) will appear consecutively, from the most
2161 recently to the least recently inserted value.
2162
2163 Multiple iterators can be used on the same hash. However, be aware
2164 that any modification performed directly on the QHash (inserting and
2165 removing items) can cause the iterators to become invalid.
2166
2167 Inserting items into the hash or calling methods such as QHash::reserve()
2168 or QHash::squeeze() can invalidate all iterators pointing into the hash.
2169 Iterators are guaranteed to stay valid only as long as the QHash doesn't have
2170 to grow/shrink its internal hash table.
2171 Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
2172
2173 \warning Iterators on implicitly shared containers do not work
2174 exactly like STL-iterators. You should avoid copying a container
2175 while iterators are active on that container. For more information,
2176 read \l{Implicit sharing iterator problem}.
2177
2178 \sa QHash::iterator, QHashIterator
2179*/
2180
2181/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator()
2182
2183 Constructs an uninitialized iterator.
2184
2185 Functions like key(), value(), and operator++() must not be
2186 called on an uninitialized iterator. Use operator=() to assign a
2187 value to it before using it.
2188
2189 \sa QHash::constBegin(), QHash::constEnd()
2190*/
2191
2192/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(const iterator &other)
2193
2194 Constructs a copy of \a other.
2195*/
2196
2197/*! \fn template <class Key, class T> const Key &QHash<Key, T>::const_iterator::key() const
2198
2199 Returns the current item's key.
2200
2201 \sa value()
2202*/
2203
2204/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::value() const
2205
2206 Returns the current item's value.
2207
2208 \sa key(), operator*()
2209*/
2210
2211/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::operator*() const
2212
2213 Returns the current item's value.
2214
2215 Same as value().
2216
2217 \sa key()
2218*/
2219
2220/*! \fn template <class Key, class T> const T *QHash<Key, T>::const_iterator::operator->() const
2221
2222 Returns a pointer to the current item's value.
2223
2224 \sa value()
2225*/
2226
2227/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator==(const const_iterator &other) const
2228
2229 Returns \c true if \a other points to the same item as this
2230 iterator; otherwise returns \c false.
2231
2232 \sa operator!=()
2233*/
2234
2235/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator!=(const const_iterator &other) const
2236
2237 Returns \c true if \a other points to a different item than this
2238 iterator; otherwise returns \c false.
2239
2240 \sa operator==()
2241*/
2242
2243/*!
2244 \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator++()
2245
2246 The prefix ++ operator (\c{++i}) advances the iterator to the
2247 next item in the hash and returns an iterator to the new current
2248 item.
2249
2250 Calling this function on QHash::end() leads to undefined results.
2251*/
2252
2253/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator++(int)
2254
2255 \overload
2256
2257 The postfix ++ operator (\c{i++}) advances the iterator to the
2258 next item in the hash and returns an iterator to the previously
2259 current item.
2260*/
2261
2262/*! \class QHash::key_iterator
2263 \inmodule QtCore
2264 \since 5.6
2265 \brief The QHash::key_iterator class provides an STL-style const iterator for QHash keys.
2266
2267 QHash::key_iterator is essentially the same as QHash::const_iterator
2268 with the difference that operator*() and operator->() return a key
2269 instead of a value.
2270
2271 For most uses QHash::iterator and QHash::const_iterator should be used,
2272 you can easily access the key by calling QHash::iterator::key():
2273
2274 \snippet code/src_corelib_tools_qhash.cpp 27
2275
2276 However, to have interoperability between QHash's keys and STL-style
2277 algorithms we need an iterator that dereferences to a key instead
2278 of a value. With QHash::key_iterator we can apply an algorithm to a
2279 range of keys without having to call QHash::keys(), which is inefficient
2280 as it costs one QHash iteration and memory allocation to create a temporary
2281 QList.
2282
2283 \snippet code/src_corelib_tools_qhash.cpp 28
2284
2285 QHash::key_iterator is const, it's not possible to modify the key.
2286
2287 The default QHash::key_iterator constructor creates an uninitialized
2288 iterator. You must initialize it using a QHash function like
2289 QHash::keyBegin() or QHash::keyEnd().
2290
2291 \warning Iterators on implicitly shared containers do not work
2292 exactly like STL-iterators. You should avoid copying a container
2293 while iterators are active on that container. For more information,
2294 read \l{Implicit sharing iterator problem}.
2295
2296 \sa QHash::const_iterator, QHash::iterator
2297*/
2298
2299/*! \fn template <class Key, class T> const T &QHash<Key, T>::key_iterator::operator*() const
2300
2301 Returns the current item's key.
2302*/
2303
2304/*! \fn template <class Key, class T> const T *QHash<Key, T>::key_iterator::operator->() const
2305
2306 Returns a pointer to the current item's key.
2307*/
2308
2309/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator==(key_iterator other) const
2310
2311 Returns \c true if \a other points to the same item as this
2312 iterator; otherwise returns \c false.
2313
2314 \sa operator!=()
2315*/
2316
2317/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator!=(key_iterator other) const
2318
2319 Returns \c true if \a other points to a different item than this
2320 iterator; otherwise returns \c false.
2321
2322 \sa operator==()
2323*/
2324
2325/*!
2326 \fn template <class Key, class T> QHash<Key, T>::key_iterator &QHash<Key, T>::key_iterator::operator++()
2327
2328 The prefix ++ operator (\c{++i}) advances the iterator to the
2329 next item in the hash and returns an iterator to the new current
2330 item.
2331
2332 Calling this function on QHash::keyEnd() leads to undefined results.
2333
2334*/
2335
2336/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator++(int)
2337
2338 \overload
2339
2340 The postfix ++ operator (\c{i++}) advances the iterator to the
2341 next item in the hash and returns an iterator to the previous
2342 item.
2343*/
2344
2345/*! \fn template <class Key, class T> const_iterator QHash<Key, T>::key_iterator::base() const
2346 Returns the underlying const_iterator this key_iterator is based on.
2347*/
2348
2349/*! \typedef QHash::const_key_value_iterator
2350 \inmodule QtCore
2351 \since 5.10
2352 \brief The QHash::const_key_value_iterator typedef provides an STL-style const iterator for QHash.
2353
2354 QHash::const_key_value_iterator is essentially the same as QHash::const_iterator
2355 with the difference that operator*() returns a key/value pair instead of a
2356 value.
2357
2358 \sa QKeyValueIterator
2359*/
2360
2361/*! \typedef QHash::key_value_iterator
2362 \inmodule QtCore
2363 \since 5.10
2364 \brief The QHash::key_value_iterator typedef provides an STL-style iterator for QHash.
2365
2366 QHash::key_value_iterator is essentially the same as QHash::iterator
2367 with the difference that operator*() returns a key/value pair instead of a
2368 value.
2369
2370 \sa QKeyValueIterator
2371*/
2372
2373/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash)
2374 \relates QHash
2375
2376 Writes the hash \a hash to stream \a out.
2377
2378 This function requires the key and value types to implement \c
2379 operator<<().
2380
2381 \sa {Serializing Qt Data Types}
2382*/
2383
2384/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QHash<Key, T> &hash)
2385 \relates QHash
2386
2387 Reads a hash from stream \a in into \a hash.
2388
2389 This function requires the key and value types to implement \c
2390 operator>>().
2391
2392 \sa {Serializing Qt Data Types}
2393*/
2394
2395/*! \class QMultiHash
2396 \inmodule QtCore
2397 \brief The QMultiHash class is a convenience QHash subclass that provides multi-valued hashes.
2398
2399 \ingroup tools
2400 \ingroup shared
2401
2402 \reentrant
2403
2404 QMultiHash\<Key, T\> is one of Qt's generic \l{container classes}.
2405 It inherits QHash and extends it with a few convenience functions
2406 that make it more suitable than QHash for storing multi-valued
2407 hashes. A multi-valued hash is a hash that allows multiple values
2408 with the same key.
2409
2410 Because QMultiHash inherits QHash, all of QHash's functionality also
2411 applies to QMultiHash. For example, you can use isEmpty() to test
2412 whether the hash is empty, and you can traverse a QMultiHash using
2413 QHash's iterator classes (for example, QHashIterator). But opposed to
2414 QHash, it provides an insert() function will allow the insertion of
2415 multiple items with the same key. The replace() function corresponds to
2416 QHash::insert(). It also provides convenient operator+() and
2417 operator+=().
2418
2419 Unlike QMultiMap, QMultiHash does not provide and ordering of the
2420 inserted items. The only guarantee is that items that
2421 share the same key will appear consecutively, from the most
2422 recently to the least recently inserted value.
2423
2424 Example:
2425 \snippet code/src_corelib_tools_qhash.cpp 24
2426
2427 Unlike QHash, QMultiHash provides no operator[]. Use value() or
2428 replace() if you want to access the most recently inserted item
2429 with a certain key.
2430
2431 If you want to retrieve all the values for a single key, you can
2432 use values(const Key &key), which returns a QList<T>:
2433
2434 \snippet code/src_corelib_tools_qhash.cpp 25
2435
2436 The items that share the same key are available from most
2437 recently to least recently inserted.
2438
2439 A more efficient approach is to call find() to get
2440 the STL-style iterator for the first item with a key and iterate from
2441 there:
2442
2443 \snippet code/src_corelib_tools_qhash.cpp 26
2444
2445 QMultiHash's key and value data types must be \l{assignable data
2446 types}. You cannot, for example, store a QWidget as a value;
2447 instead, store a QWidget *. In addition, QMultiHash's key type
2448 must provide operator==(), and there must also be a qHash() function
2449 in the type's namespace that returns a hash value for an argument of the
2450 key's type. See the QHash documentation for details.
2451
2452 \sa QHash, QHashIterator, QMutableHashIterator, QMultiMap
2453*/
2454
2455/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash()
2456
2457 Constructs an empty hash.
2458*/
2459
2460/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(std::initializer_list<std::pair<Key,T> > list)
2461 \since 5.1
2462
2463 Constructs a multi-hash with a copy of each of the elements in the
2464 initializer list \a list.
2465
2466 This function is only available if the program is being
2467 compiled in C++11 mode.
2468*/
2469
2470/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(const QHash<Key, T> &other)
2471
2472 Constructs a copy of \a other (which can be a QHash or a
2473 QMultiHash).
2474*/
2475
2476/*! \fn template <class Key, class T> template <class InputIterator> QMultiHash<Key, T>::QMultiHash(InputIterator begin, InputIterator end)
2477 \since 5.14
2478
2479 Constructs a multi-hash with a copy of each of the elements in the iterator range
2480 [\a begin, \a end). Either the elements iterated by the range must be
2481 objects with \c{first} and \c{second} data members (like \c{QPair},
2482 \c{std::pair}, etc.) convertible to \c Key and to \c T respectively; or the
2483 iterators must have \c{key()} and \c{value()} member functions, returning a
2484 key convertible to \c Key and a value convertible to \c T respectively.
2485*/
2486
2487/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::replace(const Key &key, const T &value)
2488
2489 Inserts a new item with the \a key and a value of \a value.
2490
2491 If there is already an item with the \a key, that item's value
2492 is replaced with \a value.
2493
2494 If there are multiple items with the \a key, the most
2495 recently inserted item's value is replaced with \a value.
2496
2497 \sa insert()
2498*/
2499
2500/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &key, const T &value)
2501
2502 Inserts a new item with the \a key and a value of \a value.
2503
2504 If there is already an item with the same key in the hash, this
2505 function will simply create a new one. (This behavior is
2506 different from replace(), which overwrites the value of an
2507 existing item.)
2508
2509 \sa replace()
2510*/
2511
2512/*!
2513 \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(const Key &key, Args&&... args)
2514 \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(Key &&key, Args&&... args)
2515
2516 Inserts a new element into the container. This new element
2517 is constructed in-place using \a args as the arguments for its
2518 construction.
2519
2520 If there is already an item with the same key in the hash, this
2521 function will simply create a new one. (This behavior is
2522 different from replace(), which overwrites the value of an
2523 existing item.)
2524
2525 Returns an iterator pointing to the new element.
2526
2527 \sa insert
2528*/
2529
2530/*!
2531 \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(const Key &key, Args&&... args)
2532 \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(Key &&key, Args&&... args)
2533
2534 Inserts a new element into the container. This new element
2535 is constructed in-place using \a args as the arguments for its
2536 construction.
2537
2538 If there is already an item with the same key in the hash, that item's
2539 value is replaced with a value constructed from \a args.
2540
2541 Returns an iterator pointing to the new element.
2542
2543 \sa replace, emplace
2544*/
2545
2546
2547/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QMultiHash &other)
2548 \since 5.13
2549
2550 Inserts all the items in the \a other hash into this hash
2551 and returns a reference to this hash.
2552
2553 \sa insert()
2554*/
2555
2556/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::uniqueKeys() const
2557 \since 5.13
2558
2559 Returns a list containing all the keys in the map. Keys that occur multiple
2560 times in the map occur only once in the returned list.
2561
2562 \sa keys(), values()
2563*/
2564
2565/*! \fn template <class Key, class T> T QMultiHash<Key, T>::value(const Key &key, const T &defaultValue = T()) const
2566 \overload
2567
2568 Returns the value associated with the \a key.
2569
2570 If the hash contains no item with the \a key, the function
2571 returns \a defaultValue, which is a \l{default-constructed value} if the
2572 parameter has not been specified.
2573
2574 If there are multiple
2575 items for the \a key in the hash, the value of the most recently
2576 inserted one is returned.
2577*/
2578
2579/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values(const Key &key) const
2580 \overload
2581
2582 Returns a list of all the values associated with the \a key,
2583 from the most recently inserted to the least recently inserted.
2584
2585 \sa count(), insert()
2586*/
2587
2588/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::operator[](const Key &key)
2589
2590 Returns the value associated with the \a key as a modifiable reference.
2591
2592 If the hash contains no item with the \a key, the function inserts
2593 a \l{default-constructed value} into the hash with the \a key, and
2594 returns a reference to it.
2595
2596 If the hash contains multiple items with the \a key, this function returns
2597 a reference to the most recently inserted value.
2598
2599 \sa insert(), value()
2600*/
2601
2602/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::operator+=(const QMultiHash &other)
2603
2604 Inserts all the items in the \a other hash into this hash
2605 and returns a reference to this hash.
2606
2607 \sa unite(), insert()
2608*/
2609
2610/*! \fn template <class Key, class T> QMultiHash QMultiHash<Key, T>::operator+(const QMultiHash &other) const
2611
2612 Returns a hash that contains all the items in this hash in
2613 addition to all the items in \a other. If a key is common to both
2614 hashes, the resulting hash will contain the key multiple times.
2615
2616 \sa operator+=()
2617*/
2618
2619/*!
2620 \fn template <class Key, class T> bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
2621 \since 4.3
2622
2623 Returns \c true if the hash contains an item with the \a key and
2624 \a value; otherwise returns \c false.
2625
2626 \sa contains()
2627*/
2628
2629/*!
2630 \fn template <class Key, class T> int QMultiHash<Key, T>::remove(const Key &key, const T &value)
2631 \since 4.3
2632
2633 Removes all the items that have the \a key and the value \a
2634 value from the hash. Returns the number of items removed.
2635
2636 \sa remove()
2637*/
2638
2639/*! \fn template <class Key, class T> T QMultiHash<Key, T>::take(const Key &key)
2640
2641 Removes the item with the \a key from the hash and returns
2642 the value associated with it.
2643
2644 If the item does not exist in the hash, the function simply
2645 returns a \l{default-constructed value}. If there are multiple
2646 items for \a key in the hash, only the most recently inserted one
2647 is removed.
2648
2649 If you don't use the return value, remove() is more efficient.
2650
2651 \sa remove()
2652*/
2653
2654/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::keys() const
2655
2656 Returns a list containing all the keys in the hash, in an
2657 arbitrary order. Keys that occur multiple times in the hash
2658 also occur multiple times in the list.
2659
2660 The order is guaranteed to be the same as that used by values().
2661
2662 This function creates a new list, in \l {linear time}. The time and memory
2663 use that entails can be avoided by iterating from \l keyBegin() to
2664 \l keyEnd().
2665
2666 \sa values(), key()
2667*/
2668
2669/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values() const
2670
2671 Returns a list containing all the values in the hash, in an
2672 arbitrary order. If a key is associated with multiple values, all of
2673 its values will be in the list, and not just the most recently
2674 inserted one.
2675
2676 The order is guaranteed to be the same as that used by keys().
2677
2678 This function creates a new list, in \l {linear time}. The time and memory
2679 use that entails can be avoided by iterating from \l keyValueBegin() to
2680 \l keyValueEnd().
2681
2682 \sa keys(), value()
2683*/
2684
2685/*!
2686 \fn template <class Key, class T> Key QMultiHash<Key, T>::key(const T &value, const Key &defaultKey = Key()) const
2687 \since 4.3
2688
2689 Returns the first key mapped to \a value, or \a defaultKey if the
2690 hash contains no item mapped to \a value.
2691
2692 This function can be slow (\l{linear time}), because QMultiHash's
2693 internal data structure is optimized for fast lookup by key, not
2694 by value.
2695*/
2696
2697/*!
2698 \fn template <class Key, class T> int QMultiHash<Key, T>::count(const Key &key, const T &value) const
2699 \since 4.3
2700
2701 Returns the number of items with the \a key and \a value.
2702
2703 \sa count()
2704*/
2705
2706/*!
2707 \fn template <class Key, class T> typename QMultiHash<Key, T>::iterator QMultiHash<Key, T>::find(const Key &key, const T &value)
2708 \since 4.3
2709
2710 Returns an iterator pointing to the item with the \a key and \a value.
2711 If the hash contains no such item, the function returns end().
2712
2713 If the hash contains multiple items with the \a key and \a value, the
2714 iterator returned points to the most recently inserted item.
2715*/
2716
2717/*!
2718 \fn template <class Key, class T> typename QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::find(const Key &key, const T &value) const
2719 \since 4.3
2720 \overload
2721*/
2722
2723/*!
2724 \fn template <class Key, class T> typename QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constFind(const Key &key, const T &value) const
2725 \since 4.3
2726
2727 Returns an iterator pointing to the item with the \a key and the
2728 \a value in the hash.
2729
2730 If the hash contains no such item, the function returns
2731 constEnd().
2732*/
2733
2734/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::begin()
2735
2736 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
2737 the hash.
2738
2739 \sa constBegin(), end()
2740*/
2741
2742/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::begin() const
2743
2744 \overload
2745*/
2746
2747/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::cbegin() const
2748 \since 5.0
2749
2750 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
2751 in the hash.
2752
2753 \sa begin(), cend()
2754*/
2755
2756/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constBegin() const
2757
2758 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
2759 in the hash.
2760
2761 \sa begin(), constEnd()
2762*/
2763
2764/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::keyBegin() const
2765 \since 5.6
2766
2767 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
2768 in the hash.
2769
2770 \sa keyEnd()
2771*/
2772
2773/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::end()
2774
2775 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
2776 after the last item in the hash.
2777
2778 \sa begin(), constEnd()
2779*/
2780
2781/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::end() const
2782
2783 \overload
2784*/
2785
2786/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constEnd() const
2787
2788 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2789 item after the last item in the hash.
2790
2791 \sa constBegin(), end()
2792*/
2793
2794/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::cend() const
2795 \since 5.0
2796
2797 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2798 item after the last item in the hash.
2799
2800 \sa cbegin(), end()
2801*/
2802
2803/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::keyEnd() const
2804 \since 5.6
2805
2806 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2807 item after the last key in the hash.
2808
2809 \sa keyBegin()
2810*/
2811
2812/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_value_iterator QMultiHash<Key, T>::keyValueBegin()
2813 \since 5.10
2814
2815 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2816 in the hash.
2817
2818 \sa keyValueEnd()
2819*/
2820
2821/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_value_iterator QMultiHash<Key, T>::keyValueEnd()
2822 \since 5.10
2823
2824 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2825 entry after the last entry in the hash.
2826
2827 \sa keyValueBegin()
2828*/
2829
2830/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::keyValueBegin() const
2831 \since 5.10
2832
2833 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2834 in the hash.
2835
2836 \sa keyValueEnd()
2837*/
2838
2839/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::constKeyValueBegin() const
2840 \since 5.10
2841
2842 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2843 in the hash.
2844
2845 \sa keyValueBegin()
2846*/
2847
2848/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::keyValueEnd() const
2849 \since 5.10
2850
2851 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2852 entry after the last entry in the hash.
2853
2854 \sa keyValueBegin()
2855*/
2856
2857/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::constKeyValueEnd() const
2858 \since 5.10
2859
2860 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2861 entry after the last entry in the hash.
2862
2863 \sa constKeyValueBegin()
2864*/
2865
2866
2867/*! \class QMultiHash::iterator
2868 \inmodule QtCore
2869 \brief The QMultiHash::iterator class provides an STL-style non-const iterator for QMultiHash.
2870
2871 QMultiHash features both \l{STL-style iterators} and \l{Java-style
2872 iterators}. The STL-style iterators are more low-level and more
2873 cumbersome to use; on the other hand, they are slightly faster
2874 and, for developers who already know STL, have the advantage of
2875 familiarity.
2876
2877 QMultiHash\<Key, T\>::iterator allows you to iterate over a QMultiHash
2878 and to modify the value (but not the key) associated
2879 with a particular key. If you want to iterate over a const QMultiHash,
2880 you should use QMultiHash::const_iterator. It is generally good
2881 practice to use QMultiHash::const_iterator on a non-const QMultiHash as
2882 well, unless you need to change the QMultiHash through the iterator.
2883 Const iterators are slightly faster, and can improve code
2884 readability.
2885
2886 The default QMultiHash::iterator constructor creates an uninitialized
2887 iterator. You must initialize it using a QMultiHash function like
2888 QMultiHash::begin(), QMultiHash::end(), or QMultiHash::find() before you can
2889 start iterating. Here's a typical loop that prints all the (key,
2890 value) pairs stored in a hash:
2891
2892 \snippet code/src_corelib_tools_qhash.cpp 17
2893
2894 Unlike QMap, which orders its items by key, QMultiHash stores its
2895 items in an arbitrary order.
2896
2897 Let's see a few examples of things we can do with a
2898 QMultiHash::iterator that we cannot do with a QMultiHash::const_iterator.
2899 Here's an example that increments every value stored in the QMultiHash
2900 by 2:
2901
2902 \snippet code/src_corelib_tools_qhash.cpp 18
2903
2904 Here's an example that removes all the items whose key is a
2905 string that starts with an underscore character:
2906
2907 \snippet code/src_corelib_tools_qhash.cpp 19
2908
2909 The call to QMultiHash::erase() removes the item pointed to by the
2910 iterator from the hash, and returns an iterator to the next item.
2911 Here's another way of removing an item while iterating:
2912
2913 \snippet code/src_corelib_tools_qhash.cpp 20
2914
2915 It might be tempting to write code like this:
2916
2917 \snippet code/src_corelib_tools_qhash.cpp 21
2918
2919 However, this will potentially crash in \c{++i}, because \c i is
2920 a dangling iterator after the call to erase().
2921
2922 Multiple iterators can be used on the same hash. However, be aware
2923 that any modification performed directly on the QHash (inserting and
2924 removing items) can cause the iterators to become invalid.
2925
2926 Inserting items into the hash or calling methods such as QHash::reserve()
2927 or QHash::squeeze() can invalidate all iterators pointing into the hash.
2928 Iterators are guaranteed to stay valid only as long as the QHash doesn't have
2929 to grow/shrink its internal hash table.
2930 Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
2931
2932 You can however safely use iterators to remove entries from the hash
2933 using the QHash::erase() method. This function can safely be called while
2934 iterating, and won't affect the order of items in the hash.
2935
2936 If you need to keep iterators over a long period of time, we recommend
2937 that you use QMultiMap rather than QHash.
2938
2939 \warning Iterators on implicitly shared containers do not work
2940 exactly like STL-iterators. You should avoid copying a container
2941 while iterators are active on that container. For more information,
2942 read \l{Implicit sharing iterator problem}.
2943
2944 \sa QMultiHash::const_iterator, QMultiHash::key_iterator, QMutableHashIterator
2945*/
2946
2947/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator::iterator()
2948
2949 Constructs an uninitialized iterator.
2950
2951 Functions like key(), value(), and operator++() must not be
2952 called on an uninitialized iterator. Use operator=() to assign a
2953 value to it before using it.
2954
2955 \sa QMultiHash::begin(), QMultiHash::end()
2956*/
2957
2958/*! \fn template <class Key, class T> const Key &QMultiHash<Key, T>::iterator::key() const
2959
2960 Returns the current item's key as a const reference.
2961
2962 There is no direct way of changing an item's key through an
2963 iterator, although it can be done by calling QMultiHash::erase()
2964 followed by QMultiHash::insert().
2965
2966 \sa value()
2967*/
2968
2969/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::iterator::value() const
2970
2971 Returns a modifiable reference to the current item's value.
2972
2973 You can change the value of an item by using value() on
2974 the left side of an assignment, for example:
2975
2976 \snippet code/src_corelib_tools_qhash.cpp 22
2977
2978 \sa key(), operator*()
2979*/
2980
2981/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::iterator::operator*() const
2982
2983 Returns a modifiable reference to the current item's value.
2984
2985 Same as value().
2986
2987 \sa key()
2988*/
2989
2990/*! \fn template <class Key, class T> T *QMultiHash<Key, T>::iterator::operator->() const
2991
2992 Returns a pointer to the current item's value.
2993
2994 \sa value()
2995*/
2996
2997/*!
2998 \fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator==(const iterator &other) const
2999 \fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator==(const const_iterator &other) const
3000
3001 Returns \c true if \a other points to the same item as this
3002 iterator; otherwise returns \c false.
3003
3004 \sa operator!=()
3005*/
3006
3007/*!
3008 \fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator!=(const iterator &other) const
3009 \fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator!=(const const_iterator &other) const
3010
3011 Returns \c true if \a other points to a different item than this
3012 iterator; otherwise returns \c false.
3013
3014 \sa operator==()
3015*/
3016
3017/*!
3018 \fn template <class Key, class T> QMultiHash<Key, T>::iterator &QMultiHash<Key, T>::iterator::operator++()
3019
3020 The prefix ++ operator (\c{++i}) advances the iterator to the
3021 next item in the hash and returns an iterator to the new current
3022 item.
3023
3024 Calling this function on QMultiHash::end() leads to undefined results.
3025*/
3026
3027/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::iterator::operator++(int)
3028
3029 \overload
3030
3031 The postfix ++ operator (\c{i++}) advances the iterator to the
3032 next item in the hash and returns an iterator to the previously
3033 current item.
3034*/
3035
3036/*! \class QMultiHash::const_iterator
3037 \inmodule QtCore
3038 \brief The QMultiHash::const_iterator class provides an STL-style const iterator for QMultiHash.
3039
3040 QMultiHash features both \l{STL-style iterators} and \l{Java-style
3041 iterators}. The STL-style iterators are more low-level and more
3042 cumbersome to use; on the other hand, they are slightly faster
3043 and, for developers who already know STL, have the advantage of
3044 familiarity.
3045
3046 QMultiHash\<Key, T\>::const_iterator allows you to iterate over a
3047 QMultiHash. If you want to modify the QMultiHash as you
3048 iterate over it, you must use QMultiHash::iterator instead. It is
3049 generally good practice to use QMultiHash::const_iterator on a
3050 non-const QMultiHash as well, unless you need to change the QMultiHash
3051 through the iterator. Const iterators are slightly faster, and
3052 can improve code readability.
3053
3054 The default QMultiHash::const_iterator constructor creates an
3055 uninitialized iterator. You must initialize it using a QMultiHash
3056 function like QMultiHash::constBegin(), QMultiHash::constEnd(), or
3057 QMultiHash::find() before you can start iterating. Here's a typical
3058 loop that prints all the (key, value) pairs stored in a hash:
3059
3060 \snippet code/src_corelib_tools_qhash.cpp 23
3061
3062 Unlike QMap, which orders its items by key, QMultiHash stores its
3063 items in an arbitrary order. The only guarantee is that items that
3064 share the same key (because they were inserted using
3065 a QMultiHash) will appear consecutively, from the most
3066 recently to the least recently inserted value.
3067
3068 Multiple iterators can be used on the same hash. However, be aware
3069 that any modification performed directly on the QHash (inserting and
3070 removing items) can cause the iterators to become invalid.
3071
3072 Inserting items into the hash or calling methods such as QHash::reserve()
3073 or QHash::squeeze() can invalidate all iterators pointing into the hash.
3074 Iterators are guaranteed to stay valid only as long as the QHash doesn't have
3075 to grow/shrink it's internal hash table.
3076 Using any iterator after a rehashing operation ahs occurred will lead to undefined behavior.
3077
3078 You can however safely use iterators to remove entries from the hash
3079 using the QHash::erase() method. This function can safely be called while
3080 iterating, and won't affect the order of items in the hash.
3081
3082 If you need to keep iterators over a long period of time, we recommend
3083 that you use QMap rather than QHash.
3084
3085 \warning Iterators on implicitly shared containers do not work
3086 exactly like STL-iterators. You should avoid copying a container
3087 while iterators are active on that container. For more information,
3088 read \l{Implicit sharing iterator problem}.
3089
3090 \sa QMultiHash::iterator
3091*/
3092
3093/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator::const_iterator()
3094
3095 Constructs an uninitialized iterator.
3096
3097 Functions like key(), value(), and operator++() must not be
3098 called on an uninitialized iterator. Use operator=() to assign a
3099 value to it before using it.
3100
3101 \sa QMultiHash::constBegin(), QMultiHash::constEnd()
3102*/
3103
3104/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator::const_iterator(const iterator &other)
3105
3106 Constructs a copy of \a other.
3107*/
3108
3109/*! \fn template <class Key, class T> const Key &QMultiHash<Key, T>::const_iterator::key() const
3110
3111 Returns the current item's key.
3112
3113 \sa value()
3114*/
3115
3116/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::const_iterator::value() const
3117
3118 Returns the current item's value.
3119
3120 \sa key(), operator*()
3121*/
3122
3123/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::const_iterator::operator*() const
3124
3125 Returns the current item's value.
3126
3127 Same as value().
3128
3129 \sa key()
3130*/
3131
3132/*! \fn template <class Key, class T> const T *QMultiHash<Key, T>::const_iterator::operator->() const
3133
3134 Returns a pointer to the current item's value.
3135
3136 \sa value()
3137*/
3138
3139/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::const_iterator::operator==(const const_iterator &other) const
3140
3141 Returns \c true if \a other points to the same item as this
3142 iterator; otherwise returns \c false.
3143
3144 \sa operator!=()
3145*/
3146
3147/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::const_iterator::operator!=(const const_iterator &other) const
3148
3149 Returns \c true if \a other points to a different item than this
3150 iterator; otherwise returns \c false.
3151
3152 \sa operator==()
3153*/
3154
3155/*!
3156 \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator &QMultiHash<Key, T>::const_iterator::operator++()
3157
3158 The prefix ++ operator (\c{++i}) advances the iterator to the
3159 next item in the hash and returns an iterator to the new current
3160 item.
3161
3162 Calling this function on QMultiHash::end() leads to undefined results.
3163*/
3164
3165/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::const_iterator::operator++(int)
3166
3167 \overload
3168
3169 The postfix ++ operator (\c{i++}) advances the iterator to the
3170 next item in the hash and returns an iterator to the previously
3171 current item.
3172*/
3173
3174/*! \class QMultiHash::key_iterator
3175 \inmodule QtCore
3176 \since 5.6
3177 \brief The QMultiHash::key_iterator class provides an STL-style const iterator for QMultiHash keys.
3178
3179 QMultiHash::key_iterator is essentially the same as QMultiHash::const_iterator
3180 with the difference that operator*() and operator->() return a key
3181 instead of a value.
3182
3183 For most uses QMultiHash::iterator and QMultiHash::const_iterator should be used,
3184 you can easily access the key by calling QMultiHash::iterator::key():
3185
3186 \snippet code/src_corelib_tools_qhash.cpp 27
3187
3188 However, to have interoperability between QMultiHash's keys and STL-style
3189 algorithms we need an iterator that dereferences to a key instead
3190 of a value. With QMultiHash::key_iterator we can apply an algorithm to a
3191 range of keys without having to call QMultiHash::keys(), which is inefficient
3192 as it costs one QMultiHash iteration and memory allocation to create a temporary
3193 QList.
3194
3195 \snippet code/src_corelib_tools_qhash.cpp 28
3196
3197 QMultiHash::key_iterator is const, it's not possible to modify the key.
3198
3199 The default QMultiHash::key_iterator constructor creates an uninitialized
3200 iterator. You must initialize it using a QMultiHash function like
3201 QMultiHash::keyBegin() or QMultiHash::keyEnd().
3202
3203 \warning Iterators on implicitly shared containers do not work
3204 exactly like STL-iterators. You should avoid copying a container
3205 while iterators are active on that container. For more information,
3206 read \l{Implicit sharing iterator problem}.
3207
3208 \sa QMultiHash::const_iterator, QMultiHash::iterator
3209*/
3210
3211/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::key_iterator::operator*() const
3212
3213 Returns the current item's key.
3214*/
3215
3216/*! \fn template <class Key, class T> const T *QMultiHash<Key, T>::key_iterator::operator->() const
3217
3218 Returns a pointer to the current item's key.
3219*/
3220
3221/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::key_iterator::operator==(key_iterator other) const
3222
3223 Returns \c true if \a other points to the same item as this
3224 iterator; otherwise returns \c false.
3225
3226 \sa operator!=()
3227*/
3228
3229/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::key_iterator::operator!=(key_iterator other) const
3230
3231 Returns \c true if \a other points to a different item than this
3232 iterator; otherwise returns \c false.
3233
3234 \sa operator==()
3235*/
3236
3237/*!
3238 \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator &QMultiHash<Key, T>::key_iterator::operator++()
3239
3240 The prefix ++ operator (\c{++i}) advances the iterator to the
3241 next item in the hash and returns an iterator to the new current
3242 item.
3243
3244 Calling this function on QMultiHash::keyEnd() leads to undefined results.
3245*/
3246
3247/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::key_iterator::operator++(int)
3248
3249 \overload
3250
3251 The postfix ++ operator (\c{i++}) advances the iterator to the
3252 next item in the hash and returns an iterator to the previous
3253 item.
3254*/
3255
3256/*! \fn template <class Key, class T> const_iterator QMultiHash<Key, T>::key_iterator::base() const
3257 Returns the underlying const_iterator this key_iterator is based on.
3258*/
3259
3260/*! \typedef QMultiHash::const_key_value_iterator
3261 \inmodule QtCore
3262 \since 5.10
3263 \brief The QMap::const_key_value_iterator typedef provides an STL-style const iterator for QMultiHash and QMultiHash.
3264
3265 QMultiHash::const_key_value_iterator is essentially the same as QMultiHash::const_iterator
3266 with the difference that operator*() returns a key/value pair instead of a
3267 value.
3268
3269 \sa QKeyValueIterator
3270*/
3271
3272/*! \typedef QMultiHash::key_value_iterator
3273 \inmodule QtCore
3274 \since 5.10
3275 \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QMultiHash and QMultiHash.
3276
3277 QMultiHash::key_value_iterator is essentially the same as QMultiHash::iterator
3278 with the difference that operator*() returns a key/value pair instead of a
3279 value.
3280
3281 \sa QKeyValueIterator
3282*/
3283
3284/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QMultiHash<Key, T>& hash)
3285 \relates QMultiHash
3286
3287 Writes the hash \a hash to stream \a out.
3288
3289 This function requires the key and value types to implement \c
3290 operator<<().
3291
3292 \sa {Serializing Qt Data Types}
3293*/
3294
3295/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QMultiHash<Key, T> &hash)
3296 \relates QMultiHash
3297
3298 Reads a hash from stream \a in into \a hash.
3299
3300 This function requires the key and value types to implement \c
3301 operator>>().
3302
3303 \sa {Serializing Qt Data Types}
3304*/
3305
3306/*!
3307 \fn template <class Key, class T> size_t qHash(const QHash<Key, T> &key, size_t seed = 0)
3308 \since 5.8
3309 \relates QHash
3310
3311 Returns the hash value for the \a key, using \a seed to seed the calculation.
3312
3313 Type \c T must be supported by qHash().
3314*/
3315
3316/*!
3317 \fn template <class Key, class T> size_t qHash(const QMultiHash<Key, T> &key, size_t seed = 0)
3318 \since 5.8
3319 \relates QMultiHash
3320
3321 Returns the hash value for the \a key, using \a seed to seed the calculation.
3322
3323 Type \c T must be supported by qHash().
3324*/
3325
3326QT_END_NAMESPACE
3327