1
/****************************************************************************
3
** Copyright (C) 1992-2005 Trolltech AS. All rights reserved.
5
** This file is part of the core module of the Qt Toolkit.
7
** This file may be distributed under the terms of the Q Public License
8
** as defined by Trolltech AS of Norway and appearing in the file
9
** LICENSE.QPL included in the packaging of this file.
11
** This file may be distributed and/or modified under the terms of the
12
** GNU General Public License version 2 as published by the Free Software
13
** Foundation and appearing in the file LICENSE.GPL included in the
14
** packaging of this file.
16
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
17
** information about Qt Commercial License Agreements.
18
** See http://www.trolltech.com/qpl/ for QPL licensing information.
19
** See http://www.trolltech.com/gpl/ for GPL licensing information.
21
** Contact info@trolltech.com if any conditions of this licensing are
24
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
25
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
27
****************************************************************************/
35
#include <qbytearray.h>
40
These functions are based on Peter J. Weinberger's hash function
41
(from the Dragon Book). The constant 24 in the original function
42
was replaced with 23 to produce fewer collisions on input such as
43
"a", "aa", "aaa", "aaaa", ...
46
uint qHash(const QByteArray &key)
48
const uchar *p = reinterpret_cast<const uchar *>(key.data());
55
if ((g = (h & 0xf0000000)) != 0)
62
uint qHash(const QString &key)
64
const QChar *p = key.unicode();
70
h = (h << 4) + (*p++).unicode();
71
if ((g = (h & 0xf0000000)) != 0)
79
The prime_deltas array is a table of selected prime values, even
80
though it doesn't look like one. The primes we are using are 1,
81
2, 5, 11, 17, 37, 67, 131, 257, ..., i.e. primes in the immediate
82
surrounding of a power of two.
84
The primeForNumBits() function returns the prime associated to a
85
power of two. For example, primeForNumBits(8) returns 257.
88
static const uchar prime_deltas[] = {
89
0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3,
90
1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0
93
static inline int primeForNumBits(int numBits)
95
return (1 << numBits) + prime_deltas[numBits];
99
Returns the smallest integer n such that
100
primeForNumBits(n) >= hint.
102
static int countBits(int hint)
112
if (numBits >= (int)sizeof(prime_deltas)) {
113
numBits = sizeof(prime_deltas) - 1;
114
} else if (primeForNumBits(numBits) < hint) {
121
A QHash has initially around pow(2, MinNumBits) buckets. For
122
example, if MinNumBits is 4, it has 17 buckets.
124
const int MinNumBits = 4;
126
QHashData QHashData::shared_null = {
127
0, 0, Q_ATOMIC_INIT(1), 0, 0, MinNumBits, 0, 0, true
130
void *QHashData::allocateNode()
132
return ::malloc(nodeSize);
135
void QHashData::freeNode(void *node)
140
QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize)
151
d->nodeSize = nodeSize;
152
d->userNumBits = userNumBits;
153
d->numBits = numBits;
154
d->numBuckets = numBuckets;
158
d->buckets = new Node *[numBuckets];
159
Node *this_e = reinterpret_cast<Node *>(this);
160
for (int i = 0; i < numBuckets; ++i) {
161
Node **nextNode = &d->buckets[i];
162
Node *oldNode = buckets[i];
163
while (oldNode != this_e) {
164
Node *dup = static_cast<Node *>(allocateNode());
165
node_duplicate(oldNode, dup);
168
nextNode = &dup->next;
169
oldNode = oldNode->next;
177
QHashData::Node *QHashData::nextNode(Node *node)
188
int start = (node->h % d->numBuckets) + 1;
189
Node **bucket = d->buckets + start;
190
int n = d->numBuckets - start;
199
QHashData::Node *QHashData::previousNode(Node *node)
212
start = d->numBuckets - 1;
214
start = node->h % d->numBuckets;
216
Node *sentinel = node;
217
Node **bucket = d->buckets + start;
219
if (*bucket != sentinel) {
220
Node *prev = *bucket;
221
while (prev->next != sentinel)
234
If hint is negative, -hint gives the approximate number of
235
buckets that should be used for the hash table. If hint is
236
nonnegative, (1 << hint) gives the approximate number
237
of buckets that should be used.
239
void QHashData::rehash(int hint)
242
hint = countBits(-hint);
243
if (hint < MinNumBits)
246
while (primeForNumBits(hint) < (size >> 1))
248
} else if (hint < MinNumBits) {
252
if (numBits != hint) {
253
Node *e = reinterpret_cast<Node *>(this);
254
Node **oldBuckets = buckets;
255
int oldNumBuckets = numBuckets;
258
numBuckets = primeForNumBits(hint);
259
buckets = new Node *[numBuckets];
260
for (int i = 0; i < numBuckets; ++i)
263
for (int i = 0; i < oldNumBuckets; ++i) {
264
Node *firstNode = oldBuckets[i];
265
while (firstNode != e) {
266
uint h = firstNode->h;
267
Node *lastNode = firstNode;
268
while (lastNode->next != e && lastNode->next->h == h)
269
lastNode = lastNode->next;
271
Node *afterLastNode = lastNode->next;
272
Node **beforeFirstNode = &buckets[h % numBuckets];
273
while (*beforeFirstNode != e)
274
beforeFirstNode = &(*beforeFirstNode)->next;
275
lastNode->next = *beforeFirstNode;
276
*beforeFirstNode = firstNode;
277
firstNode = afterLastNode;
280
delete [] oldBuckets;
284
void QHashData::destroyAndFree()
292
\brief The QHash class is a template class that provides a hash-table-based dictionary.
299
QHash\<Key, T\> is one of Qt's generic \l{container classes}. It
300
stores (key, value) pairs and provides very fast lookup of the
301
value associated with a key.
303
QHash provides very similar functionality to QMap. The
307
\i QHash provides faster lookups than QMap.
308
\i When iterating over a QMap, the items are always sorted by
309
key. With QHash, the items are arbitrarily ordered.
310
\i The key type of a QMap must provide operator<(). The key
311
type of a QHash must provide operator==() and a global
312
\l{qHash()}{qHash}(Key) function.
315
Here's an example QHash with QString keys and \c int values:
317
QHash<QString, int> hash;
320
To insert a (key, value) pair into the hash, you can use operator[]():
328
This inserts the following three (key, value) pairs into the
329
QHash: ("one", 1), ("three", 3), and ("seven", 7). Another way to
330
insert items into the hash is to use insert():
333
hash.insert("twelve", 12);
336
To look up a value, use operator[]() or value():
339
int num1 = hash["thirteen"];
340
int num2 = hash.value("thirteen");
343
If there is no item with the specified key in the hash, these
344
functions return a \l{default-constructed value}.
346
If you want to check whether the hash contains a particular key,
351
if (hash.contains("TIMEOUT"))
352
timeout = hash.value("TIMEOUT");
355
There is also a value() overload that uses its second argument as
356
a default value if there is no item with the specified key:
359
int timeout = hash.value("TIMEOUT", 30);
362
In general, we recommend that you use contains() and value()
363
rather than operator[]() for looking up a key in a hash. The
364
reason is that operator[]() silently inserts an item into the
365
hash if no item exists with the same key (unless the hash is
366
const). For example, the following code snippet will create 1000
371
QHash<int, QWidget *> hash;
373
for (int i = 0; i < 1000; ++i) {
374
if (hash[i] == okButton)
375
cout << "Found button at index " << i << endl;
379
To avoid this problem, replace \c hash[i] with \c hash.value(i)
382
If you want to navigate through all the (key, value) pairs stored
383
in a QHash, you can use an iterator. QHash provides both
384
\l{Java-style iterators} (QHashIterator and QMutableHashIterator)
385
and \l{STL-style iterators} (QHash::const_iterator and
386
QHash::iterator). Here's how to iterate over a QHash<QString,
387
int> using a Java-style iterator:
390
QHashIterator<QString, int> i(hash);
391
while (i.hasNext()) {
393
cout << i.key() << ": " << i.value() << endl;
397
Here's the same code, but using an STL-style iterator:
400
QHash<QString, int>::const_iterator i = hash.constBegin();
401
while (i != hash.constEnd()) {
402
cout << i.key() << ": " << i.value() << endl;
407
QHash is unordered, so an iterator's sequence cannot be assumed
408
to be predictable. If ordering by key is required, use a QMap.
410
Normally, a QHash allows only one value per key. If you call
411
insert() with a key that already exists in the QHash, the
412
previous value is erased. For example:
415
hash.insert("plenty", 100);
416
hash.insert("plenty", 2000);
417
// hash.value("plenty") == 2000
420
However, you can store multiple values per key by using
421
insertMulti() instead of insert() (or using the convenience
422
subclass QMultiHash). If you want to retrieve all
423
the values for a single key, you can use values(const Key &key),
424
which returns a QList<T>:
427
QList<int> values = hash.values("plenty");
428
for (int i = 0; i < values.size(); ++i)
429
cout << values.at(i) << endl;
432
The items that share the same key are available from most
433
recently to least recently inserted. A more efficient approach is
434
to call find() to get the iterator for the first item with a key
435
and iterate from there:
438
QHash<QString, int>::iterator i = hash.find("plenty");
439
while (i != hash.end() && i.key() == "plenty") {
440
cout << i.value() << endl;
445
If you only need to extract the values from a hash (not the keys),
446
you can also use \l{foreach}:
449
QHash<QString, int> hash;
451
foreach (int value, hash)
452
cout << value << endl;
455
Items can be removed from the hash in several ways. One way is to
456
call remove(); this will remove any item with the given key.
457
Another way is to use QMutableHashIterator::remove(). In addition,
458
you can clear the entire hash using clear().
460
QHash's key and value data types must be \l{assignable data
461
types}. You cannot, for example, store a QWidget as a value;
462
instead, store a QWidget *. In addition, QHash's key type must
463
provide operator==(), and there must also be a global qHash()
464
function that returns a hash value for an argument of the key's
467
Here's a list of the C++ and Qt types that can serve as keys in a
468
QHash: any integer type (char, unsigned long, etc.), any pointer
469
type, QChar, QString, and QByteArray. For all of these, the \c
470
<QHash> header defines a qHash() function that computes an
471
adequate hash value. If you want to use other types as the key,
472
make sure that you provide operator==() and a qHash()
484
Employee(const QString &name, const QDate &dateOfBirth);
492
inline bool operator==(const Employee &e1, const Employee &e2)
494
return e1.name() == e2.name()
495
&& e1.dateOfBirth() == e2.dateOfBirth();
498
inline uint qHash(const Employee &key)
500
return qHash(key.name()) ^ key.dateOfBirth().day();
506
The qHash() function computes a numeric value based on a key. It
507
can use any algorithm imaginable, as long as it always returns
508
the same value if given the same argument. In other words, if
509
\c{e1 == e2}, then \c{qHash(e1) == qHash(e2)} must hold as well.
510
However, to obtain good performance, the qHash() function should
511
attempt to return different hash values for different keys to the
512
largest extent possible.
514
In the example above, we've relied on Qt's global qHash(const
515
QString &) to give us a hash value for the employee's name, and
516
XOR'ed this with the day they were born to help produce unique
517
hashes for people with the same name.
519
Internally, QHash uses a hash table to perform lookups. Unlike Qt
520
3's \c QDict class, which needed to be initialized with a prime
521
number, QHash's hash table automatically grows and shrinks to
522
provide fast lookups without wasting too much memory. You can
523
still control the size of the hash table by calling reserve() if
524
you already know approximately how many items the QHash will
525
contain, but this isn't necessary to obtain good performance. You
526
can also call capacity() to retrieve the hash table's size.
528
\sa QHashIterator, QMutableHashIterator, QMap, QSet
531
/*! \fn QHash::QHash()
533
Constructs an empty hash.
538
/*! \fn QHash::QHash(const QHash<Key, T> &other)
540
Constructs a copy of \a other.
542
This operation occurs in \l{constant time}, because QHash is
543
\l{implicitly shared}. This makes returning a QHash from a
544
function very fast. If a shared instance is modified, it will be
545
copied (copy-on-write), and this takes \l{linear time}.
550
/*! \fn QHash::~QHash()
552
Destroys the hash. References to the values in the hash and all
553
iterators of this hash become invalid.
556
/*! \fn QHash<Key, T> &QHash::operator=(const QHash<Key, T> &other)
558
Assigns \a other to this hash and returns a reference to this hash.
561
/*! \fn bool QHash::operator==(const QHash<Key, T> &other) const
563
Returns true if \a other is equal to this hash; otherwise returns
566
Two hashes are considered equal if they contain the same (key,
569
This function requires the value type to implement \c operator==().
574
/*! \fn bool QHash::operator!=(const QHash<Key, T> &other) const
576
Returns true if \a other is not equal to this hash; otherwise
579
Two hashes are considered equal if they contain the same (key,
582
This function requires the value type to implement \c operator==().
587
/*! \fn int QHash::size() const
589
Returns the number of items in the hash.
591
\sa isEmpty(), count()
594
/*! \fn bool QHash::isEmpty() const
596
Returns true if the hash contains no items; otherwise returns
602
/*! \fn int QHash::capacity() const
604
Returns the number of buckets in the QHash's internal hash table.
606
The sole purpose of this function is to provide a means of fine
607
tuning QHash's memory usage. In general, you will rarely ever
608
need to call this function. If you want to know how many items are
609
in the hash, call size().
611
\sa reserve(), squeeze()
614
/*! \fn void QHash::reserve(int size)
616
Ensures that the QHash's internal hash table consists of at least
619
This function is useful for code that needs to build a huge hash
620
and wants to avoid repeated reallocation. For example:
623
QHash<QString, int> hash;
625
for (int i = 0; i < 20000; ++i)
626
hash.insert(keys[i], values[i]);
629
Ideally, \a size should be slightly more than the maximum number
630
of items expected in the hash. \a size doesn't have to be prime,
631
because QHash will use a prime number internally anyway. If \a size
632
is an underestimate, the worst that will happen is that the QHash
633
will be a bit slower.
635
In general, you will rarely ever need to call this function.
636
QHash's internal hash table automatically shrinks or grows to
637
provide good performance without wasting too much memory.
639
\sa squeeze(), capacity()
642
/*! \fn void QHash::squeeze()
644
Reduces the size of the QHash's internal hash table to save
647
The sole purpose of this function is to provide a means of fine
648
tuning QHash's memory usage. In general, you will rarely ever
649
need to call this function.
651
\sa reserve(), capacity()
654
/*! \fn void QHash::detach()
658
Detaches this hash from any other hashes with which it may share
664
/*! \fn bool QHash::isDetached() const
668
Returns true if the hash's internal data isn't shared with any
669
other hash object; otherwise returns false.
674
/*! \fn void QHash::setSharable(bool sharable)
679
/*! \fn void QHash::clear()
681
Removes all items from the hash.
686
/*! \fn int QHash::remove(const Key &key)
688
Removes all the items that have the key \a key from the hash.
689
Returns the number of items removed which is usually 1 but will
690
be 0 if the key isn't in the hash, or greater than 1 if
691
insertMulti() has been used with the \a key.
696
/*! \fn T QHash::take(const Key &key)
698
Removes the item with the key \a key from the hash and returns
699
the value associated with it.
701
If the item does not exist in the hash, the function simply
702
returns a \l{default-constructed value}. If there are multiple
703
items for \a key in the hash, only the most recently inserted one
706
If you don't use the return value, remove() is more efficient.
711
/*! \fn bool QHash::contains(const Key &key) const
713
Returns true if the hash contains an item with key \a key;
714
otherwise returns false.
719
/*! \fn const T QHash::value(const Key &key) const
721
Returns the value associated with the key \a key.
723
If the hash contains no item with key \a key, the function
724
returns a \l{default-constructed value}. If there are multiple
725
items for \a key in the hash, the value of the most recently
726
inserted one is returned.
728
\sa key(), values(), contains(), operator[]()
731
/*! \fn const T QHash::value(const Key &key, const T &defaultValue) const
735
If the hash contains no item with the given \a key, the function returns
739
/*! \fn T &QHash::operator[](const Key &key)
741
Returns the value associated with the key \a key as a modifiable
744
If the hash contains no item with key \a key, the function inserts
745
a \l{default-constructed value} into the hash with key \a key, and
746
returns a reference to it. If the hash contains multiple items
747
with key \a key, this function returns a reference to the most
748
recently inserted value.
750
\sa insert(), value()
753
/*! \fn const T QHash::operator[](const Key &key) const
760
/*! \fn QList<Key> QHash::keys() const
762
Returns a list containing all the keys in the hash, in an
763
arbitrary order. Keys that occur multiple times in the hash
764
(because items were inserted with insertMulti(), or unite() was
765
used), also occur multiple times in the list.
767
The order is guaranteed to be the same as that used by values().
772
/*! \fn QList<Key> QHash::keys(const T &value) const
776
Returns a list containing all the keys associated with value \a
777
value, in an arbitrary order.
779
This function can be slow (\l{linear time}), because QHash's
780
internal data structure is optimized for fast lookup by key, not
784
/*! \fn QList<T> QHash::values() const
786
Returns a list containing all the values in the hash, in an
787
arbitrary order. If a key is associated multiple values, all of
788
its values will be in the list, and not just the most recently
791
The order is guaranteed to be the same as that used by keys().
796
/*! \fn QList<T> QHash::values(const Key &key) const
800
Returns a list of all the values associated with key \a key,
801
from the most recently inserted to the least recently inserted.
803
\sa count(), insertMulti()
806
/*! \fn Key QHash::key(const T &value) const
808
Returns the first key with value \a value.
810
If the hash contains no item with value \a value, the function
811
returns a \link {default-constructed value} default-constructed
814
This function can be slow (\l{linear time}), because QHash's
815
internal data structure is optimized for fast lookup by key, not
818
\sa value(), values()
821
/*! \fn int QHash::count(const Key &key) const
823
Returns the number of items associated with key \a key.
825
\sa contains(), insertMulti()
828
/*! \fn int QHash::count() const
835
/*! \fn QHash::iterator QHash::begin()
837
Returns a \l{STL-style iterator} pointing to the first item in
840
\sa constBegin(), end()
843
/*! \fn QHash::const_iterator QHash::begin() const
848
/*! \fn QHash::const_iterator QHash::constBegin() const
850
Returns a const \l{STL-style iterator} pointing to the first item
853
\sa begin(), constEnd()
856
/*! \fn QHash::iterator QHash::end()
858
Returns a \l{STL-style iterator} pointing to the imaginary item
859
after the last item in the hash.
861
\sa begin(), constEnd()
864
/*! \fn QHash::const_iterator QHash::end() const
869
/*! \fn QHash::const_iterator QHash::constEnd() const
871
Returns a const \l{STL-style iterator} pointing to the imaginary
872
item after the last item in the hash.
874
\sa constBegin(), end()
877
/*! \fn QHash::iterator QHash::erase(iterator pos)
879
Removes the (key, value) pair associated with the iterator \a pos
880
from the hash, and returns an iterator to the next item in the
886
/*! \fn QHash::iterator QHash::find(const Key &key)
888
Returns an iterator pointing to the item with key \a key in the
891
If the hash contains no item with key \a key, the function
894
If the hash contains multiple items with key \a key, this
895
function returns an iterator that points to the most recently
896
inserted value. The other values are accessible by incrementing
897
the iterator. For example, here's some code that iterates over all
898
the items with the same key:
901
QHash<QString, int> hash;
903
QHash<QString, int>::const_iterator i = hash.find("HDR");
904
while (i != hash.end() && i.key() == "HDR") {
905
cout << i.value() << endl;
910
\sa value(), values()
913
/*! \fn QHash::const_iterator QHash::find(const Key &key) const
918
/*! \fn QHash::iterator QHash::insert(const Key &key, const T &value)
920
Inserts a new item with the key \a key and a value of \a value.
922
If there is already an item with the key \a key, that item's value
923
is replaced with \a value.
925
If there are multiple items with the key \a key, the most
926
recently inserted item's value is replaced with \a value.
931
/*! \fn QHash::iterator QHash::insertMulti(const Key &key, const T &value)
933
Inserts a new item with the key \a key and a value of \a value.
935
If there is already an item with the same key in the hash, this
936
function will simply create a new one. (This behavior is
937
different from insert(), which overwrites the value of an
940
\sa insert(), values()
943
/*! \fn QHash<Key, T> &QHash::unite(const QHash<Key, T> &other)
945
Inserts all the items in the \a other hash into this hash. If a
946
key is common to both hashes, the resulting hash will contain the
952
/*! \fn bool QHash::empty() const
954
This function is provided for STL compatibility. It is equivalent
958
/*! \typedef QHash::ConstIterator
960
Qt-style synonym for QHash::const_iterator.
963
/*! \typedef QHash::Iterator
965
Qt-style synonym for QHash::iterator.
968
/*! \typedef QHash::iterator::difference_type
972
/*! \typedef QHash::iterator::iterator_category
976
/*! \typedef QHash::iterator::pointer
980
/*! \typedef QHash::iterator::reference
984
/*! \typedef QHash::iterator::value_type
988
/*! \typedef QHash::const_iterator::difference_type
992
/*! \typedef QHash::const_iterator::iterator_category
996
/*! \typedef QHash::const_iterator::pointer
1000
/*! \typedef QHash::const_iterator::reference
1004
/*! \typedef QHash::const_iterator::value_type
1008
/*! \class QHash::iterator
1009
\brief The QHash::iterator class provides an STL-style non-const iterator for QHash and QMultiHash.
1011
QHash features both \l{STL-style iterators} and \l{Java-style
1012
iterators}. The STL-style iterators are more low-level and more
1013
cumbersome to use; on the other hand, they are slightly faster
1014
and, for developers who already know STL, have the advantage of
1017
QHash\<Key, T\>::iterator allows you to iterate over a QHash (or
1018
QMultiHash) and to modify the value (but not the key) associated
1019
with a particular key. If you want to iterate over a const QHash,
1020
you should use QHash::const_iterator. It is generally good
1021
practice to use QHash::const_iterator on a non-const QHash as
1022
well, unless you need to change the QHash through the iterator.
1023
Const iterators are slightly faster, and can improve code
1026
The default QHash::iterator constructor creates an uninitialized
1027
iterator. You must initialize it using a QHash function like
1028
QHash::begin(), QHash::end(), or QHash::find() before you can
1029
start iterating. Here's a typical loop that prints all the (key,
1030
value) pairs stored in a hash:
1033
QHash<QString, int> hash;
1034
hash.insert("January", 1);
1035
hash.insert("February", 2);
1037
hash.insert("December", 12);
1039
QHash<QString, int>::iterator i;
1040
for (i = hash.begin(); i != hash.end(); ++i)
1041
cout << i.key() << ": " << i.value() << endl;
1044
Unlike QMap, which orders its items by key, QHash stores its
1045
items in an arbitrary order. The only guarantee is that items that
1046
share the same key (because they were inserted using
1047
QHash::insertMulti()) will appear consecutively, from the most
1048
recently to the least recently inserted value.
1050
Let's see a few examples of things we can do with a
1051
QHash::iterator that we cannot do with a QHash::const_iterator.
1052
Here's an example that increments every value stored in the QHash
1056
QHash<QString, int>::iterator i;
1057
for (i = hash.begin(); i != hash.end(); ++i)
1061
Here's an example that removes all the items whose key is a
1062
string that starts with an underscore character:
1065
QHash<QString, int>::iterator i = hash.begin();
1066
while (i != hash.end()) {
1067
if (i.key().startsWith("_"))
1074
The call to QHash::erase() removes the item pointed to by the
1075
iterator from the hash, and returns an iterator to the next item.
1076
Here's another way of removing an item while iterating:
1079
QHash<QString, int>::iterator i = hash.begin();
1080
while (i != hash.end()) {
1081
QHash<QString, int>::iterator prev = i;
1083
if (prev.key().startsWith("_"))
1088
It might be tempting to write code like this:
1092
while (i != hash.end()) {
1093
if (i.key().startsWith("_"))
1099
However, this will potentially crash in \c{++i}, because \c i is
1100
a dangling iterator after the call to erase().
1102
Multiple iterators can be used on the same hash. However, be
1103
aware that any modification performed directly on the QHash has
1104
the potential of dramatically changing the order in which the
1105
items are stored in the hash, as they might cause QHash to rehash
1106
its internal data structure. There is one notable exception:
1107
QHash::erase(). This function can safely be called while
1108
iterating, and won't affect the order of items in the hash. If you
1109
need to keep iterators over a long period of time, we recommend
1110
that you use QMap rather than QHash.
1112
\sa QHash::const_iterator, QMutableHashIterator
1115
/*! \fn QHash::iterator::operator Node *() const
1120
/*! \fn QHash::iterator::iterator()
1122
Constructs an uninitialized iterator.
1124
Functions like key(), value(), and operator++() must not be
1125
called on an uninitialized iterator. Use operator=() to assign a
1126
value to it before using it.
1128
\sa QHash::begin() QHash::end()
1131
/*! \fn QHash::iterator::iterator(void *node)
1136
/*! \fn const Key &QHash::iterator::key() const
1138
Returns the current item's key as a const reference.
1140
There is no direct way of changing an item's key through an
1141
iterator, although it can be done by calling QHash::erase()
1142
followed by QHash::insert() or QHash::insertMulti().
1147
/*! \fn T &QHash::iterator::value() const
1149
Returns a modifiable reference to the current item's value.
1151
You can change the value of an item by using value() on
1152
the left side of an assignment, for example:
1155
if (i.key() == "Hello")
1156
i.value() = "Bonjour";
1159
\sa key(), operator*()
1162
/*! \fn T &QHash::iterator::operator*() const
1164
Returns a modifiable reference to the current item's value.
1171
/*! \fn T *QHash::iterator::operator->() const
1173
Returns a pointer to the current item's value.
1179
\fn bool QHash::iterator::operator==(const iterator &other) const
1180
\fn bool QHash::iterator::operator==(const const_iterator &other) const
1182
Returns true if \a other points to the same item as this
1183
iterator; otherwise returns false.
1189
\fn bool QHash::iterator::operator!=(const iterator &other) const
1190
\fn bool QHash::iterator::operator!=(const const_iterator &other) const
1192
Returns true if \a other points to a different item than this
1193
iterator; otherwise returns false.
1199
\fn QHash::iterator &QHash::iterator::operator++()
1201
The prefix ++ operator (\c{++i}) advances the iterator to the
1202
next item in the hash and returns an iterator to the new current
1205
Calling this function on QHash::end() leads to undefined results.
1210
/*! \fn QHash::iterator QHash::iterator::operator++(int)
1214
The postfix ++ operator (\c{i++}) advances the iterator to the
1215
next item in the hash and returns an iterator to the previously
1220
\fn QHash::iterator &QHash::iterator::operator--()
1222
The prefix -- operator (\c{--i}) makes the preceding item
1223
current and returns an iterator pointing to the new current item.
1225
Calling this function on QHash::begin() leads to undefined
1232
\fn QHash::iterator QHash::iterator::operator--(int)
1236
The postfix -- operator (\c{i--}) makes the preceding item
1237
current and returns an iterator pointing to the previously
1241
/*! \fn QHash::iterator QHash::iterator::operator+(int j) const
1243
Returns an iterator to the item at \a j positions forward from
1244
this iterator. (If \a j is negative, the iterator goes backward.)
1246
This operation can be slow for large \a j values.
1252
/*! \fn QHash::iterator QHash::iterator::operator-(int j) const
1254
Returns an iterator to the item at \a j positions backward from
1255
this iterator. (If \a j is negative, the iterator goes forward.)
1257
This operation can be slow for large \a j values.
1262
/*! \fn QHash::iterator &QHash::iterator::operator+=(int j)
1264
Advances the iterator by \a j items. (If \a j is negative, the
1265
iterator goes backward.)
1267
\sa operator-=(), operator+()
1270
/*! \fn QHash::iterator &QHash::iterator::operator-=(int j)
1272
Makes the iterator go back by \a j items. (If \a j is negative,
1273
the iterator goes forward.)
1275
\sa operator+=(), operator-()
1278
/*! \class QHash::const_iterator
1279
\brief The QHash::const_iterator class provides an STL-style const iterator for QHash and QMultiHash.
1281
QHash features both \l{STL-style iterators} and \l{Java-style
1282
iterators}. The STL-style iterators are more low-level and more
1283
cumbersome to use; on the other hand, they are slightly faster
1284
and, for developers who already know STL, have the advantage of
1287
QHash\<Key, T\>::const_iterator allows you to iterate over a
1288
QHash (or a QMultiHash). If you want to modify the QHash as you
1289
iterate over it, you must use QHash::iterator instead. It is
1290
generally good practice to use QHash::const_iterator on a
1291
non-const QHash as well, unless you need to change the QHash
1292
through the iterator. Const iterators are slightly faster, and
1293
can improve code readability.
1295
The default QHash::const_iterator constructor creates an
1296
uninitialized iterator. You must initialize it using a QHash
1297
function like QHash::constBegin(), QHash::constEnd(), or
1298
QHash::find() before you can start iterating. Here's a typical
1299
loop that prints all the (key, value) pairs stored in a hash:
1302
QHash<QString, int> hash;
1303
hash.insert("January", 1);
1304
hash.insert("February", 2);
1306
hash.insert("December", 12);
1308
QHash<QString, int>::const_iterator i;
1309
for (i = hash.constBegin(); i != hash.constEnd(); ++i)
1310
cout << i.key() << ": " << i.value() << endl;
1313
Unlike QMap, which orders its items by key, QHash stores its
1314
items in an arbitrary order. The only guarantee is that items that
1315
share the same key (because they were inserted using
1316
QHash::insertMulti()) will appear consecutively, from the most
1317
recently to the least recently inserted value.
1319
Multiple iterators can be used on the same hash. However, be aware
1320
that any modification performed directly on the QHash has the
1321
potential of dramatically changing the order in which the items
1322
are stored in the hash, as they might cause QHash to rehash its
1323
internal data structure. If you need to keep iterators over a long
1324
period of time, we recommend that you use QMap rather than QHash.
1326
\sa QHash::iterator, QHashIterator
1329
/*! \fn QHash::const_iterator::operator Node *() const
1334
/*! \fn QHash::const_iterator::const_iterator()
1336
Constructs an uninitialized iterator.
1338
Functions like key(), value(), and operator++() must not be
1339
called on an uninitialized iterator. Use operator=() to assign a
1340
value to it before using it.
1342
\sa QHash::constBegin() QHash::constEnd()
1345
/*! \fn QHash::const_iterator::const_iterator(void *node)
1350
/*! \fn QHash::const_iterator::const_iterator(const iterator &other)
1352
Constructs a copy of \a other.
1355
/*! \fn const Key &QHash::const_iterator::key() const
1357
Returns the current item's key.
1362
/*! \fn const T &QHash::const_iterator::value() const
1364
Returns the current item's value.
1366
\sa key(), operator*()
1369
/*! \fn const T &QHash::const_iterator::operator*() const
1371
Returns the current item's value.
1378
/*! \fn const T *QHash::const_iterator::operator->() const
1380
Returns a pointer to the current item's value.
1385
/*! \fn bool QHash::const_iterator::operator==(const const_iterator &other) const
1387
Returns true if \a other points to the same item as this
1388
iterator; otherwise returns false.
1393
/*! \fn bool QHash::const_iterator::operator!=(const const_iterator &other) const
1395
Returns true if \a other points to a different item than this
1396
iterator; otherwise returns false.
1402
\fn QHash::const_iterator &QHash::const_iterator::operator++()
1404
The prefix ++ operator (\c{++i}) advances the iterator to the
1405
next item in the hash and returns an iterator to the new current
1408
Calling this function on QHash::end() leads to undefined results.
1413
/*! \fn QHash::const_iterator QHash::const_iterator::operator++(int)
1417
The postfix ++ operator (\c{i++}) advances the iterator to the
1418
next item in the hash and returns an iterator to the previously
1422
/*! \fn QHash::const_iterator &QHash::const_iterator::operator--()
1424
The prefix -- operator (\c{--i}) makes the preceding item
1425
current and returns an iterator pointing to the new current item.
1427
Calling this function on QHash::begin() leads to undefined
1433
/*! \fn QHash::const_iterator QHash::const_iterator::operator--(int)
1437
The postfix -- operator (\c{i--}) makes the preceding item
1438
current and returns an iterator pointing to the previously
1442
/*! \fn QHash::const_iterator QHash::const_iterator::operator+(int j) const
1444
Returns an iterator to the item at \a j positions forward from
1445
this iterator. (If \a j is negative, the iterator goes backward.)
1447
This operation can be slow for large \a j values.
1452
/*! \fn QHash::const_iterator QHash::const_iterator::operator-(int j) const
1454
Returns an iterator to the item at \a j positions backward from
1455
this iterator. (If \a j is negative, the iterator goes forward.)
1457
This operation can be slow for large \a j values.
1462
/*! \fn QHash::const_iterator &QHash::const_iterator::operator+=(int j)
1464
Advances the iterator by \a j items. (If \a j is negative, the
1465
iterator goes backward.)
1467
This operation can be slow for large \a j values.
1469
\sa operator-=(), operator+()
1472
/*! \fn QHash::const_iterator &QHash::const_iterator::operator-=(int j)
1474
Makes the iterator go back by \a j items. (If \a j is negative,
1475
the iterator goes forward.)
1477
This operation can be slow for large \a j values.
1479
\sa operator+=(), operator-()
1482
/*! \fn uint qHash(char key)
1485
Returns the hash value for \a key.
1488
/*! \fn uint qHash(uchar key)
1494
/*! \fn uint qHash(signed char key)
1500
/*! \fn uint qHash(ushort key)
1506
/*! \fn uint qHash(short key)
1512
/*! \fn uint qHash(uint key)
1518
/*! \fn uint qHash(int key)
1524
/*! \fn uint qHash(ulong key)
1530
/*! \fn uint qHash(long key)
1536
/*! \fn uint qHash(quint64 key)
1542
/*! \fn uint qHash(qint64 key)
1548
/*! \fn uint qHash(QChar key)
1554
/*! \fn uint qHash(const QByteArray &key)
1560
/*! \fn uint qHash(const QString &key)
1566
/*! \fn uint qHash(const T *key)
1572
/*! \fn QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash)
1575
Writes the hash \a hash to stream \a out.
1577
This function requires the key and value types to implement \c
1580
\sa {Format of the QDataStream operators}
1583
/*! \fn QDataStream &operator>>(QDataStream &in, QHash<Key, T> &hash)
1586
Reads a hash from stream \a in into \a hash.
1588
This function requires the key and value types to implement \c
1591
\sa {Format of the QDataStream operators}
1594
/*! \class QMultiHash
1595
\brief The QMultiHash class is a convenience QHash subclass that provides multi-valued hashes.
1602
QMultiHash\<Key, T\> is one of Qt's generic \l{container classes}.
1603
It inherits QHash and extends it with a few convenience functions
1604
that make it more suitable than QHash for storing multi-valued
1605
hashes. A multi-valued hash is a hash that allows multiple values
1606
with the same key; QHash normally doesn't allow that, unless you
1607
call QHash::insertMulti().
1609
Because QMultiHash inherits QHash, all of QHash's functionality also
1610
applies to QMultiHash. For example, you can use isEmpty() to test
1611
whether the hash is empty, and you can traverse a QMultiHash using
1612
QHash's iterator classes (for example, QHashIterator). But in
1613
addition, it provides an insert() function that corresponds to
1614
QHash::insertMulti(), and a replace() function that corresponds to
1615
QHash::insert(). It also provides convenient operator+() and
1620
QMultiHash<QString, int> hash1, hash2, hash3;
1622
hash1.insert("plenty", 100);
1623
hash1.insert("plenty", 2000);
1624
// hash1.size() == 2
1626
hash2.insert("plenty", 5000);
1627
// hash2.size() == 1
1629
hash3 = hash1 + hash2;
1630
// hash3.size() == 3
1633
Unlike QHash, QMultiHash provides no operator[]. Use value() or
1634
replace() if you want to access the most recently inserted item
1637
If you want to retrieve all the values for a single key, you can
1638
use values(const Key &key), which returns a QList<T>:
1641
QList<int> values = hash.values("plenty");
1642
for (int i = 0; i < values.size(); ++i)
1643
cout << values.at(i) << endl;
1646
The items that share the same key are available from most
1647
recently to least recently inserted.
1649
A more efficient approach is to use QHashIterator::findNextKey() or
1650
QMutableHashIterator::findNextKey():
1653
QHashIterator<QString, int> i(hash);
1654
while (i.findNextKey("plenty"))
1655
cout << i.value() << endl;
1658
If you prefer the STL-style iterators, you can call find() to get
1659
the iterator for the first item with a key and iterate from
1663
QMultiHash<QString, int>::iterator i = hash.find("plenty");
1664
while (i != hash.end() && i.key() == "plenty") {
1665
cout << i.value() << endl;
1670
QMultiHash's key and value data types must be \l{assignable data
1671
types}. You cannot, for example, store a QWidget as a value;
1672
instead, store a QWidget *. In addition, QMultiHash's key type
1673
must provide operator==(), and there must also be a global
1674
qHash() function that returns a hash value for an argument of the
1675
key's type. See the QHash documentation for details.
1677
\sa QHash, QHashIterator, QMutableHashIterator, QMultiMap
1680
/*! \fn QMultiHash::QMultiHash()
1682
Constructs an empty hash.
1685
/*! \fn QMultiHash::QMultiHash(const QHash<Key, T> &other)
1687
Constructs a copy of \a other (which can be a QHash or a
1693
/*! \fn QMultiHash::iterator QMultiHash::replace(const Key &key, const T &value)
1695
Inserts a new item with the key \a key and a value of \a value.
1697
If there is already an item with the key \a key, that item's value
1698
is replaced with \a value.
1700
If there are multiple items with the key \a key, the most
1701
recently inserted item's value is replaced with \a value.
1706
/*! \fn QMultiHash::iterator QMultiHash::insert(const Key &key, const T &value)
1708
Inserts a new item with the key \a key and a value of \a value.
1710
If there is already an item with the same key in the hash, this
1711
function will simply create a new one. (This behavior is
1712
different from replace(), which overwrites the value of an
1718
/*! \fn QMultiHash &QMultiHash::operator+=(const QMultiHash &other)
1720
Inserts all the items in the \a other hash into this hash
1721
and returns a reference to this hash.
1726
/*! \fn QMultiHash QMultiHash::operator+(const QMultiHash &other) const
1728
Returns a hash that contains all the items in this hash in
1729
addition to all the items in \a other. If a key is common to both
1730
hashes, the resulting hash will contain the key multiple times.
added
removed
src/corelib/tools/qhash.cpp
