8#include <QtCore/qalgorithms.h>
9#include <QtCore/qcontainertools_impl.h>
10#include <QtCore/qhashfunctions.h>
11#include <QtCore/qiterator.h>
12#include <QtCore/qlist.h>
13#include <QtCore/qrefcount.h>
14#include <QtCore/qttypetraits.h>
16#include <initializer_list>
30template <
typename T,
typename =
void>
35 std::is_convertible_v<decltype(qHash(std::declval<const T &>(), std::declval<size_t>())),
size_t>
38template <
typename T,
typename =
void>
43 std::is_convertible_v<decltype(std::hash<T>()(std::declval<const T &>(), std::declval<size_t>())),
size_t>
46template <
typename T,
typename =
void>
51 std::is_convertible_v<decltype(std::hash<T>()(std::declval<const T &>())),
size_t>
57 if constexpr (HasQHashOverload<T>) {
59 }
else if constexpr (HasStdHashSpecializationWithSeed<T>) {
60 return std::hash<T>()(
t,
seed);
61 }
else if constexpr (HasStdHashSpecializationWithoutSeed<T>) {
63 return std::hash<T>()(
t);
65 static_assert(
sizeof(T) == 0,
"The key type must have a qHash overload or a std::hash specialization");
70template <
typename Key,
typename T>
78 template<
typename ...Args>
80 {
new (
n)
Node{ std::move(k), T(std::forward<Args>(
args)...) }; }
81 template<
typename ...Args>
83 {
new (
n)
Node{
Key(k), T(std::forward<Args>(
args)...) }; }
84 template<
typename ...Args>
91 return std::move(
value);
96template <
typename Key>
102 template<
typename ...Args>
104 {
new (
n)
Node{ std::move(k) }; }
105 template<
typename ...Args>
107 {
new (
n)
Node{ k }; }
108 template<
typename ...Args>
148template <
typename Key,
typename T>
158 template<
typename ...Args>
161 template<
typename ...Args>
203 template<
typename ...Args>
207 e->next = std::exchange(
value, e);
209 template<
typename ...Args>
212 value->value = T(std::forward<Args>(
args)...);
216template<
typename Node>
239template<
typename Node>
269 if constexpr (!std::is_trivially_destructible<Node>::value) {
291 void erase(
size_t bucket)
noexcept(std::is_nothrow_destructible<Node>::value)
344 void moveFromSpan(
Span &fromSpan,
size_t fromIndex,
size_t to)
noexcept(std::is_nothrow_move_constructible_v<Node>)
357 size_t fromOffset = fromSpan.offsets[fromIndex];
359 Entry &fromEntry = fromSpan.entries[fromOffset];
361 if constexpr (isRelocatable<Node>()) {
362 memcpy(&toEntry, &fromEntry,
sizeof(
Entry));
364 new (&toEntry.node())
Node(std::move(fromEntry.node()));
365 fromEntry.node().~Node();
367 fromEntry.nextFree() = fromSpan.nextFree;
368 fromSpan.nextFree =
static_cast<unsigned char>(fromOffset);
398 if constexpr (isRelocatable<Node>()) {
417namespace GrowthPolicy {
420 constexpr int SizeDigits = std::numeric_limits<size_t>::digits;
424 if (requestedCapacity <= 64)
435 return (std::numeric_limits<size_t>::max)();
436 return size_t(1) << (SizeDigits -
count + 1);
440 return hash & (nBuckets - 1);
444template <
typename Node>
447template <
typename Node>
463 return (std::numeric_limits<ptrdiff_t>::max)() /
sizeof(
Span);
488 advance_impl(
d,
d->spans);
492 advance_impl(
d,
nullptr);
518 return lhs.span == rhs.span && lhs.index == rhs.index;
522 void advance_impl(
const Data *
d,
Span *whenAtEnd)
noexcept
542 constexpr qptrdiff MaxSpanCount = (std::numeric_limits<qptrdiff>::max)() /
sizeof(
Span);
551 return R{
new Span[nSpans], nSpans };
563 for (
size_t s = 0;
s < nSpans; ++
s) {
572 new (newNode)
Node(
n);
648 for (
size_t s = 0;
s < oldNSpans; ++
s) {
657 new (newNode)
Node(std::move(
n));
683 static_assert(std::is_same_v<std::remove_cv_t<Key>, K> ||
684 QHashHeterogeneousSearch<std::remove_cv_t<Key>, K>
::value);
706 if (bucket.isUnused())
708 return bucket.node();
723 return {
it.toIterator(
this),
true };
733 return {
it.toIterator(
this),
false };
736 void erase(
Bucket bucket)
noexcept(std::is_nothrow_destructible<Node>::value)
738 Q_ASSERT(bucket.span->hasNode(bucket.index));
739 bucket.span->erase(bucket.index);
745 next.advanceWrapped(
this);
752 if (newBucket ==
next) {
755 }
else if (newBucket == bucket) {
757 if (
next.span == bucket.span) {
758 bucket.span->moveLocal(
next.index, bucket.index);
761 bucket.span->moveFromSpan(*
next.span,
next.index, bucket.index);
766 newBucket.advanceWrapped(
this);
777template <
typename Node>
781 const Data<Node> *
d =
nullptr;
793 bool atEnd() const noexcept {
return !
d; }
812 {
return !(*
this ==
other); }
819template <
typename Key,
typename T>
854 static_assert(std::is_nothrow_destructible_v<Key>,
"Types with throwing destructors are not supported in Qt containers.");
855 static_assert(std::is_nothrow_destructible_v<T>,
"Types with throwing destructors are not supported in Qt containers.");
857 if (
d && !
d->ref.deref())
867 if (
d && !
d->ref.deref())
875 :
d(std::exchange(
other.d,
nullptr))
878 QT_MOVE_ASSIGNMENT_OPERATOR_IMPL_VIA_MOVE_AND_SWAP(
QHash)
880 template <
typename InputIterator>
881 QHash(InputIterator
f, InputIterator l);
883 template <
typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
892 template <
typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
904 template <
typename AKey = Key,
typename AT = T>
914 if (
i ==
end() || !
i.i.node()->valuesEqual(
it.i.node()))
920 template <
typename AKey = Key,
typename AT = T>
922 {
return !(*
this ==
other); }
929 inline bool isEmpty() const noexcept {
return !
d ||
d->size == 0; }
949 inline bool isDetached() const noexcept {
return d && !
d->ref.isShared(); }
954 if (
d && !
d->ref.deref())
961 return removeImpl(
key);
964 template <
typename K>
bool removeImpl(
const K &
key)
968 auto it =
d->findBucket(
key);
969 size_t bucket =
it.toBucketIndex(
d);
971 it =
typename Data::Bucket(
d, bucket);
980 template <
typename Predicate>
988 return takeImpl(
key);
991 template <
typename K> T takeImpl(
const K &
key)
995 auto it =
d->findBucket(
key);
996 size_t bucket =
it.toBucketIndex(
d);
998 it =
typename Data::Bucket(
d, bucket);
1002 T
value =
it.node()->takeValue();
1012 return d->findNode(
key) !=
nullptr;
1020 template <
typename Fn>
Key keyImpl(
const T &
value, Fn &&defaultFn)
const noexcept
1024 while (
i !=
end()) {
1037 return keyImpl(
value, [] {
return Key(); });
1041 return keyImpl(
value, [&] {
return defaultKey; });
1045 template <
typename K,
typename Fn> T valueImpl(
const K &
key, Fn &&defaultValue)
const noexcept
1052 return defaultValue();
1057 return valueImpl(
key, [] {
return T(); });
1062 return valueImpl(
key, [&] {
return defaultValue; });
1067 return operatorIndexImpl(
key);
1070 template <
typename K> T &operatorIndexImpl(
const K &
key)
1078 return result.it.node()->value;
1092 while (
i !=
end()) {
1094 res.append(
i.key());
1121 inline const
Key &
key() const noexcept {
return i.node()->key; }
1122 inline T &
value() const noexcept {
return i.node()->value; }
1164 inline const Key &
key() const noexcept {
return i.node()->key; }
1165 inline const T &
value() const noexcept {
return i.node()->value; }
1166 inline const T &
operator*() const noexcept {
return i.node()->value; }
1167 inline const T *
operator->() const noexcept {
return &
i.node()->value; }
1250 return equal_range_impl(*
this,
key);
1254 return equal_range_impl(*
this,
key);
1257 template <
typename Hash,
typename K>
static auto equal_range_impl(Hash &self,
const K &
key)
1260 auto second =
first;
1261 if (second !=
decltype(
first){})
1263 return std::make_pair(
first, second);
1266 template <
typename K>
iterator findImpl(
const K &
key)
1270 auto it =
d->findBucket(
key);
1271 size_t bucket =
it.toBucketIndex(d);
1273 it =
typename Data::Bucket(d, bucket);
1282 auto it =
d->findBucket(
key);
1294 return findImpl(
key);
1298 return constFindImpl(
key);
1324 template <
typename ...Args>
1331 template <
typename ...Args>
1335 if (
d->shouldGrow())
1336 return emplace_helper(std::move(
key), T(std::forward<Args>(
args)...));
1337 return emplace_helper(std::move(
key), std::forward<Args>(
args)...);
1340 const auto copy = *
this;
1342 return emplace_helper(std::move(
key), std::forward<Args>(
args)...);
1353 template <
typename ...Args>
1360 result.it.node()->emplaceValue(std::forward<Args>(
args)...);
1365#ifdef __cpp_concepts
1366 bool remove(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
1368 return removeImpl(
key);
1370 T
take(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
1372 return takeImpl(
key);
1374 bool contains(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
1378 qsizetype count(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
1382 T
value(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
const noexcept
1384 return valueImpl(
key, [] {
return T(); });
1386 T
value(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key,
const T &defaultValue)
const noexcept
1388 return valueImpl(
key, [&] {
return defaultValue; });
1390 T &
operator[](
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
1392 return operatorIndexImpl(
key);
1394 const T
operator[](
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
const noexcept
1398 std::pair<iterator, iterator>
1399 equal_range(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
1401 return equal_range_impl(*
this,
key);
1403 std::pair<const_iterator, const_iterator>
1404 equal_range(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
const noexcept
1406 return equal_range_impl(*
this,
key);
1408 iterator find(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
1410 return findImpl(
key);
1412 const_iterator find(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
const noexcept
1414 return constFindImpl(
key);
1424template <
typename Key,
typename T>
1451 template <
typename InputIterator>
1454 template <
typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
1462 template <
typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
1478 static_assert(std::is_nothrow_destructible_v<Key>,
"Types with throwing destructors are not supported in Qt containers.");
1479 static_assert(std::is_nothrow_destructible_v<T>,
"Types with throwing destructors are not supported in Qt containers.");
1481 if (
d && !
d->ref.deref())
1491 if (
d && !
d->ref.deref())
1494 m_size =
other.m_size;
1499 :
d(std::exchange(
other.d,
nullptr)),
1500 m_size(std::exchange(
other.m_size, 0))
1522 std::swap(m_size,
other.m_size);
1526 template <
typename AKey = Key,
typename AT = T>
1531 if (m_size !=
other.m_size)
1538 if (
d->size !=
other.d->size)
1541 auto *
n =
d->findNode(
it.node()->key);
1548 if (oe->value == e->
value)
1560 template <
typename AKey = Key,
typename AT = T>
1562 {
return !(*
this ==
other); }
1570 inline bool isEmpty() const noexcept {
return !m_size; }
1586 inline bool isDetached() const noexcept {
return d && !
d->ref.isShared(); }
1591 if (
d && !
d->ref.deref())
1599 return removeImpl(
key);
1602 template <
typename K>
qsizetype removeImpl(
const K &
key)
1606 auto it =
d->findBucket(
key);
1607 size_t bucket =
it.toBucketIndex(d);
1609 it =
typename Data::Bucket(d, bucket);
1621 template <
typename Predicate>
1629 return takeImpl(
key);
1632 template <
typename K> T takeImpl(
const K &
key)
1636 auto it =
d->findBucket(
key);
1637 size_t bucket =
it.toBucketIndex(d);
1639 it =
typename Data::Bucket(d, bucket);
1643 Chain *e =
it.node()->value;
1645 T
t = std::move(e->value);
1647 it.node()->value = e->next;
1663 return d->findNode(
key) !=
nullptr;
1667 template <
typename Fn>
Key keyImpl(
const T &
value, Fn &&defaultValue)
const noexcept
1670 auto i =
d->begin();
1671 while (
i !=
d->end()) {
1672 Chain *e =
i.node()->value;
1673 if (e->contains(
value))
1674 return i.node()->key;
1679 return defaultValue();
1684 return keyImpl(
value, [] {
return Key(); });
1688 return keyImpl(
value, [&] {
return defaultKey; });
1692 template <
typename K,
typename Fn> T valueImpl(
const K &
key, Fn &&defaultValue)
const noexcept
1698 return n->value->value;
1701 return defaultValue();
1706 return valueImpl(
key, [] {
return T(); });
1710 return valueImpl(
key, [&] {
return defaultValue; });
1715 return operatorIndexImpl(
key);
1718 template <
typename K> T &operatorIndexImpl(
const K &
key)
1724 if (!
result.initialized) {
1728 return result.it.node()->value->value;
1741 auto i =
d->begin();
1742 while (
i !=
d->end()) {
1743 res.append(
i.node()->key);
1755 while (
i !=
end()) {
1757 res.append(
i.key());
1766 return valuesImpl(
key);
1769 template <
typename K> QList<T> valuesImpl(
const K &
key)
const
1775 Chain *e =
n->value;
1794 Chain **e =
nullptr;
1797 if (!
it.atEnd() && !e) {
1798 e = &
it.node()->value;
1812 inline const
Key &
key() const noexcept {
return i.node()->key; }
1813 inline T &
value() const noexcept {
return (*e)->value; }
1814 inline T &
operator*() const noexcept {
return (*e)->value; }
1846 Chain **e =
nullptr;
1849 if (!
it.atEnd() && !e) {
1850 e = &
it.node()->value;
1865 inline const Key &
key() const noexcept {
return i.node()->key; }
1866 inline T &
value() const noexcept {
return (*e)->value; }
1867 inline T &
operator*() const noexcept {
return (*e)->value; }
1944 if (
d->ref.isShared()) {
1955 i =
d->detachedIterator(
i);
1976 if (
i.e == &
i.i.node()->value) {
1999 template <
typename K>
iterator findImpl(
const K &
key)
2003 auto it =
d->findBucket(
key);
2004 size_t bucket =
it.toBucketIndex(d);
2006 it =
typename Data::Bucket(d, bucket);
2016 auto it =
d->findBucket(
key);
2024 return findImpl(
key);
2028 return constFindImpl(
key);
2032 return constFindImpl(
key);
2040 template <
typename ...Args>
2046 template <
typename ...Args>
2050 if (
d->shouldGrow())
2051 return emplace_helper(std::move(
key), T(std::forward<Args>(
args)...));
2052 return emplace_helper(std::move(
key), std::forward<Args>(
args)...);
2055 const auto copy = *
this;
2057 return emplace_helper(std::move(
key), std::forward<Args>(
args)...);
2073 template <
typename ...Args>
2079 template <
typename ...Args>
2083 if (
d->shouldGrow())
2084 return emplaceReplace_helper(std::move(
key), T(std::forward<Args>(
args)...));
2085 return emplaceReplace_helper(std::move(
key), std::forward<Args>(
args)...);
2088 const auto copy = *
this;
2090 return emplaceReplace_helper(std::move(
key), std::forward<Args>(
args)...);
2094 { this->
unite(other);
return *
this; }
2103 template <
typename K>
bool containsImpl(
const K &
key,
const T &
value)
const noexcept
2107 auto n =
d->findNode(
key);
2110 return n->value->contains(
value);
2123 auto it =
d->findBucket(
key);
2124 size_t bucket =
it.toBucketIndex(d);
2126 it =
typename Data::Bucket(d, bucket);
2131 Chain **e = &
it.node()->value;
2142 if (!
it.node()->value)
2152 return countImpl(
key);
2155 template <
typename K>
qsizetype countImpl(
const K &
key)
const noexcept
2159 auto it =
d->findBucket(
key);
2163 Chain *e =
it.node()->value;
2178 template <
typename K>
qsizetype countImpl(
const K &
key,
const T &
value)
const noexcept
2182 auto it =
d->findBucket(
key);
2186 Chain *e =
it.node()->value;
2188 if (e->value ==
value)
2209 while (
i !=
end &&
i.key() ==
key) {
2236 }
else if (
other.isEmpty()) {
2241 for (
auto cit =
copy.cbegin(); cit !=
copy.cend(); ++cit)
2249 for (
auto cit =
other.cbegin(); cit !=
other.cend(); ++cit)
2256 if (!
other.isDetached()) {
2262 emplace(std::move(
it.node()->key), std::move(
it.node()->takeValue()));
2269 return equal_range_impl(
key);
2272 template <
typename K> std::pair<iterator, iterator> equal_range_impl(
const K &
key)
2276 auto pair = std::as_const(*this).equal_range(
key);
2283 return equal_range_impl(
key);
2286 template <
typename K> std::pair<const_iterator, const_iterator> equal_range_impl(
const K &
key)
const noexcept
2291 auto bucket =
d->findBucket(
key);
2292 if (bucket.isUnused())
2294 auto it = bucket.toIterator(d);
2300 void detach_helper()
2306 Data *dd =
new Data(*d);
2307 if (!
d->ref.deref())
2312 template<
typename... Args>
2319 result.it.node()->insertMulti(std::forward<Args>(
args)...);
2324 template<
typename... Args>
2328 if (!
result.initialized) {
2332 result.it.node()->emplaceValue(std::forward<Args>(
args)...);
2338#ifdef __cpp_concepts
2341 return removeImpl(
key);
2343 T
take(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
2345 return takeImpl(
key);
2347 bool contains(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
const noexcept
2351 return d->findNode(
key) !=
nullptr;
2353 T
value(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
const noexcept
2355 return valueImpl(
key, [] {
return T(); });
2357 T
value(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key,
const T &defaultValue)
const noexcept
2359 return valueImpl(
key, [&] {
return defaultValue; });
2361 T &
operator[](
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
2363 return operatorIndexImpl(
key);
2365 const T
operator[](
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
const noexcept
2369 QList<T>
values(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
2371 return valuesImpl(
key);
2373 iterator find(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
2375 return findImpl(
key);
2379 return constFindImpl(
key);
2381 const_iterator find(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
const noexcept
2383 return constFindImpl(
key);
2385 bool contains(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key,
const T &
value)
const noexcept
2393 qsizetype count(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
const noexcept
2395 return countImpl(
key);
2397 qsizetype count(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key,
const T &
value)
const noexcept
2401 iterator find(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key,
const T &
value)
2413 std::pair<iterator, iterator>
2414 equal_range(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
2416 return equal_range_impl(
key);
2418 std::pair<const_iterator, const_iterator>
2419 equal_range(
const QHashPrivate::HeterogeneouslySearchableWith<Key>
auto &
key)
const noexcept
2421 return equal_range_impl(
key);
2431template <
class Key,
class T>
2438 size_t h = combine(
seed,
it.key());
2440 hash += combine(
h,
it.value());
2445template <
class Key,
class T>
2452 size_t h = combine(
seed,
it.key());
2454 hash += combine(
h,
it.value());
2459template <
typename Key,
typename T,
typename Predicate>
2465template <
typename Key,
typename T,
typename Predicate>
const_iterator operator++(int) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
bool operator==(const const_iterator &o) const noexcept
Returns true if other points to the same item as this iterator; otherwise returns false.
bool operator!=(const const_iterator &o) const noexcept
Returns true if other points to a different item than this iterator; otherwise returns false.
const T & value() const noexcept
Returns the current item's value.
const T & operator*() const noexcept
Returns the current item's value.
std::forward_iterator_tag iterator_category
constexpr const_iterator() noexcept=default
Constructs an uninitialized iterator.
const_iterator & operator++() noexcept
The prefix ++ operator ({++i}) advances the iterator to the next item in the hash and returns an iter...
const T * operator->() const noexcept
Returns a pointer to the current item's value.
const Key & key() const noexcept
Returns the current item's key.
bool operator==(const const_iterator &o) const noexcept
Returns true if other points to the same item as this iterator; otherwise returns false.
bool operator!=(const const_iterator &o) const noexcept
Returns true if other points to a different item than this iterator; otherwise returns false.
T & value() const noexcept
Returns a modifiable reference to the current item's value.
constexpr iterator() noexcept=default
Constructs an uninitialized iterator.
bool operator==(const iterator &o) const noexcept
std::forward_iterator_tag iterator_category
T * operator->() const noexcept
Returns a pointer to the current item's value.
T & operator*() const noexcept
Returns a modifiable reference to the current item's value.
iterator & operator++() noexcept
The prefix ++ operator ({++i}) advances the iterator to the next item in the hash and returns an iter...
iterator operator++(int) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
bool operator!=(const iterator &o) const noexcept
key_iterator() noexcept=default
key_iterator & operator++() noexcept
The prefix ++ operator ({++i}) advances the iterator to the next item in the hash and returns an iter...
const_iterator base() const noexcept
Returns the underlying const_iterator this key_iterator is based on.
const Key * operator->() const noexcept
Returns a pointer to the current item's key.
bool operator!=(key_iterator o) const noexcept
Returns true if other points to a different item than this iterator; otherwise returns false.
key_iterator operator++(int) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
const_iterator::iterator_category iterator_category
bool operator==(key_iterator o) const noexcept
Returns true if other points to the same item as this iterator; otherwise returns false.
const Key & operator*() const noexcept
Returns the current item's key.
key_iterator keyEnd() const noexcept
void squeeze()
Reduces the size of the QHash's internal hash table to save memory.
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const noexcept
bool remove(const Key &key)
Removes the item that has the key from the hash.
iterator begin()
Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in the hash.
const_iterator cbegin() const noexcept
qsizetype size() const noexcept
Returns the number of items in the hash.
T & operator[](const Key &key)
Returns the value associated with the key as a modifiable reference.
float load_factor() const noexcept
Returns the current load factor of the QHash's internal hash table.
~QHash()
Destroys the hash.
QHash(QHash &&other) noexcept
Move-constructs a QHash instance, making it point at the same object that other was pointing to.
QHash(InputIterator f, InputIterator l)
const_iterator constFind(const Key &key) const noexcept
const_iterator begin() const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
const_iterator constEnd() const noexcept
Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the ...
iterator find(const Key &key)
Returns an iterator pointing to the item with the key in the hash.
qsizetype size_type
Typedef for int.
key_value_iterator keyValueEnd()
QList< T > values() const
Returns a list containing all the values in the hash, in an arbitrary order.
key_value_iterator keyValueBegin()
auto asKeyValueRange() const &&
void reserve(qsizetype size)
Ensures that the QHash's internal hash table has space to store at least size items without having to...
iterator emplace(const Key &key, Args &&... args)
T value(const Key &key, const T &defaultValue) const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
const T operator[](const Key &key) const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
const_iterator constBegin() const noexcept
Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item in the hash.
T take(const Key &key)
Removes the item with the key from the hash and returns the value associated with it.
const_key_value_iterator constKeyValueEnd() const noexcept
qsizetype difference_type
Typedef for ptrdiff_t.
bool isDetached() const noexcept
Key key_type
Typedef for Key.
QKeyValueIterator< const Key &, T &, iterator > key_value_iterator
\inmodule QtCore
iterator Iterator
Qt-style synonym for QHash::iterator.
QKeyValueIterator< const Key &, const T &, const_iterator > const_key_value_iterator
\inmodule QtCore
Key key(const T &value, const Key &defaultKey) const noexcept
static float max_load_factor() noexcept
QList< Key > keys() const
Returns a list containing all the keys in the hash, in an arbitrary order.
iterator erase(const_iterator it)
bool contains(const Key &key) const noexcept
Returns true if the hash contains an item with the key; otherwise returns false.
QTypeTraits::compare_eq_result_container< QHash, AKey, AT > operator==(const QHash &other) const noexcept
Returns true if other is equal to this hash; otherwise returns false.
const_key_value_iterator keyValueEnd() const noexcept
key_iterator keyBegin() const noexcept
const_key_value_iterator keyValueBegin() const noexcept
qsizetype count() const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
qsizetype removeIf(Predicate pred)
T value(const Key &key) const noexcept
void swap(QHash &other) noexcept
bool isSharedWith(const QHash &other) const noexcept
iterator end() noexcept
Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last ...
QHash & operator=(const QHash &other) noexcept(std::is_nothrow_destructible< Node >::value)
Assigns other to this hash and returns a reference to this hash.
size_t bucket_count() const noexcept
void insert(const QHash &hash)
auto asKeyValueRange() &&
friend class const_iterator
const_iterator cend() const noexcept
auto asKeyValueRange() const &
QHash(InputIterator f, InputIterator l)
std::pair< iterator, iterator > equal_range(const Key &key)
const_iterator ConstIterator
Qt-style synonym for QHash::const_iterator.
T mapped_type
Typedef for T.
static size_t max_bucket_count() noexcept
const_iterator find(const Key &key) const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Key key(const T &value) const noexcept
const T & const_reference
void clear() noexcept(std::is_nothrow_destructible< Node >::value)
Removes all items from the hash and frees up all memory used by it.
QList< Key > keys(const T &value) const
This is an overloaded member function, provided for convenience. It differs from the above function o...
QTypeTraits::compare_eq_result_container< QHash, AKey, AT > operator!=(const QHash &other) const noexcept
Returns true if other is not equal to this hash; otherwise returns false.
bool empty() const noexcept
This function is provided for STL compatibility.
qsizetype count(const Key &key) const noexcept
Returns the number of items associated with the key.
qsizetype capacity() const noexcept
Returns the number of buckets in the QHash's internal hash table.
bool isEmpty() const noexcept
Returns true if the hash contains no items; otherwise returns false.
const_iterator end() const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
QHash() noexcept=default
Constructs an empty hash.
iterator emplace(Key &&key, Args &&... args)
Inserts a new element into the container.
QHash(const QHash &other) noexcept
Constructs a copy of other.
const_key_value_iterator constKeyValueBegin() const noexcept
iterator insert(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
const_iterator & operator++() noexcept
The prefix ++ operator ({++i}) advances the iterator to the next item in the hash and returns an iter...
T & value() const noexcept
Returns the current item's value.
const Key & key() const noexcept
Returns the current item's key.
std::forward_iterator_tag iterator_category
bool operator!=(const const_iterator &o) const noexcept
Returns true if other points to a different item than this iterator; otherwise returns false.
T * operator->() const noexcept
Returns a pointer to the current item's value.
constexpr const_iterator() noexcept=default
Constructs an uninitialized iterator.
T & operator*() const noexcept
Returns the current item's value.
const_iterator operator++(int) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
bool operator==(const const_iterator &o) const noexcept
Returns true if other points to the same item as this iterator; otherwise returns false.
T & value() const noexcept
Returns a modifiable reference to the current item's value.
constexpr iterator() noexcept=default
Constructs an uninitialized iterator.
bool operator==(const const_iterator &o) const noexcept
Returns true if other points to the same item as this iterator; otherwise returns false.
T * operator->() const noexcept
Returns a pointer to the current item's value.
bool operator!=(const iterator &o) const noexcept
bool operator!=(const const_iterator &o) const noexcept
Returns true if other points to a different item than this iterator; otherwise returns false.
bool operator==(const iterator &o) const noexcept
T & operator*() const noexcept
Returns a modifiable reference to the current item's value.
iterator & operator++() noexcept
The prefix ++ operator ({++i}) advances the iterator to the next item in the hash and returns an iter...
iterator operator++(int) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
std::forward_iterator_tag iterator_category
const_iterator base() const noexcept
Returns the underlying const_iterator this key_iterator is based on.
const_iterator::iterator_category iterator_category
key_iterator() noexcept=default
const Key * operator->() const noexcept
Returns a pointer to the current item's key.
bool operator!=(key_iterator o) const noexcept
Returns true if other points to a different item than this iterator; otherwise returns false.
key_iterator operator++(int) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
key_iterator & operator++() noexcept
The prefix ++ operator ({++i}) advances the iterator to the next item in the hash and returns an iter...
bool operator==(key_iterator o) const noexcept
Returns true if other points to the same item as this iterator; otherwise returns false.
const Key & operator*() const noexcept
Returns the current item's key.
const_key_value_iterator constKeyValueEnd() const noexcept
const_iterator find(const Key &key) const noexcept
const_key_value_iterator keyValueBegin() const noexcept
const_iterator find(const Key &key, const T &value) const noexcept
const_key_value_iterator keyValueEnd() const noexcept
QMultiHash & unite(const QHash< Key, T > &other)
iterator find(const Key &key, const T &value)
QMultiHash(const QHash< Key, T > &other)
Constructs a copy of other (which can be a QHash or a QMultiHash).
bool contains(const Key &key, const T &value) const noexcept
const_iterator constFind(const Key &key, const T &value) const noexcept
std::pair< iterator, iterator > equal_range(const Key &key)
QMultiHash(QHash< Key, T > &&other)
QTypeTraits::compare_eq_result_container< QMultiHash, AKey, AT > operator==(const QMultiHash &other) const noexcept
iterator find(const Key &key)
auto asKeyValueRange() &&
float load_factor() const noexcept
bool isSharedWith(const QMultiHash &other) const noexcept
key_value_iterator keyValueBegin() noexcept
QMultiHash(const QMultiHash &other) noexcept
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
iterator detach(const_iterator it)
QMultiHash & operator=(QMultiHash &&other) noexcept(std::is_nothrow_destructible< Node >::value)
qsizetype count(const Key &key, const T &value) const noexcept
const_iterator cbegin() const noexcept
key_iterator keyBegin() const noexcept
const_iterator constBegin() const noexcept
Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item in the hash.
iterator emplace(const Key &key, Args &&... args)
QMultiHash(QMultiHash &&other) noexcept
bool empty() const noexcept
auto asKeyValueRange() const &
const_iterator constEnd() const noexcept
Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the ...
static size_t max_bucket_count() noexcept
QMultiHash(InputIterator f, InputIterator l)
QKeyValueIterator< const Key &, const T &, const_iterator > const_key_value_iterator
\inmodule QtCore
bool isDetached() const noexcept
T value(const Key &key) const noexcept
QList< T > values(const Key &key) const
This is an overloaded member function, provided for convenience. It differs from the above function o...
iterator emplace(Key &&key, Args &&... args)
Inserts a new element into the container.
const_iterator cend() const noexcept
qsizetype removeIf(Predicate pred)
iterator emplaceReplace(Key &&key, Args &&... args)
Inserts a new element into the container.
QMultiHash & unite(const QMultiHash &other)
QList< T > values() const
Returns a list containing all the values in the hash, in an arbitrary order.
Key key(const T &value) const noexcept
QMultiHash(InputIterator f, InputIterator l)
qsizetype capacity() const noexcept
bool contains(const Key &key) const noexcept
qsizetype difference_type
QMultiHash & operator+=(const QMultiHash &other)
Inserts all the items in the other hash into this hash and returns a reference to this hash.
QMultiHash & operator=(const QMultiHash &other) noexcept(std::is_nothrow_destructible< Node >::value)
void swap(QMultiHash &other) noexcept
const_iterator begin() const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
T & operator[](const Key &key)
Returns the value associated with the key as a modifiable reference.
T take(const Key &key)
Removes the item with the key from the hash and returns the value associated with it.
qsizetype remove(const Key &key)
const_iterator ConstIterator
iterator insert(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
QMultiHash & unite(QHash< Key, T > &&other)
const T & const_reference
size_t bucket_count() const noexcept
void reserve(qsizetype size)
bool isEmpty() const noexcept
iterator emplaceReplace(const Key &key, Args &&... args)
iterator begin()
Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in the hash.
QList< Key > keys() const
Returns a list containing all the keys in the hash, in an arbitrary order.
QMultiHash() noexcept=default
Constructs an empty hash.
QList< Key > uniqueKeys() const
QList< Key > keys(const T &value) const
T value(const Key &key, const T &defaultValue) const noexcept
Returns the value associated with the key.
qsizetype size() const noexcept
key_value_iterator keyValueEnd() noexcept
iterator replace(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
const_iterator end() const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
friend class const_iterator
qsizetype count(const Key &key) const noexcept
Key key(const T &value, const Key &defaultKey) const noexcept
const_key_value_iterator constKeyValueBegin() const noexcept
void clear() noexcept(std::is_nothrow_destructible< Node >::value)
iterator erase(const_iterator it)
qsizetype remove(const Key &key, const T &value)
key_iterator keyEnd() const noexcept
iterator end() noexcept
Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last ...
qsizetype count() const noexcept
QKeyValueIterator< const Key &, T &, iterator > key_value_iterator
\inmodule QtCore
QTypeTraits::compare_eq_result_container< QMultiHash, AKey, AT > operator!=(const QMultiHash &other) const noexcept
const_iterator constFind(const Key &key) const noexcept
QMultiHash operator+(const QMultiHash &other) const
Returns a hash that contains all the items in this hash in addition to all the items in other.
auto asKeyValueRange() const &&
static float max_load_factor() noexcept
const T operator[](const Key &key) const noexcept
iterator erase(const_iterator i)
iterator insert(const T &value)
QHash< int, QWidget * > hash
[35multi]
QSet< QString >::iterator it
constexpr size_t bucketForHash(size_t nBuckets, size_t hash) noexcept
constexpr size_t bucketsForCapacity(size_t requestedCapacity) noexcept
constexpr bool isRelocatable()
constexpr bool HasStdHashSpecializationWithoutSeed
size_t calculateHash(const T &t, size_t seed=0)
constexpr bool HasQHashOverload
constexpr bool HasStdHashSpecializationWithSeed
Combined button and popup list for selecting options.
std::enable_if_t< std::conjunction_v< QTypeTraits::has_operator_equal_container< Container, T >... >, bool > compare_eq_result_container
auto associative_erase_if(Container &c, Predicate &pred)
QKeyValueRange(Map &) -> QKeyValueRange< Map & >
void reserveIfForwardIterator(Container *, InputIterator, InputIterator)
QT_POPCOUNT_RELAXED_CONSTEXPR uint qCountLeadingZeroBits(quint32 v) noexcept
static jboolean copy(JNIEnv *, jobject)
DBusConnection const char DBusError DBusBusType DBusError return DBusConnection DBusHandleMessageFunction void DBusFreeFunction return DBusConnection return DBusConnection return const char DBusError return DBusConnection DBusMessage dbus_uint32_t return DBusConnection dbus_bool_t DBusConnection DBusAddWatchFunction DBusRemoveWatchFunction DBusWatchToggledFunction void DBusFreeFunction return DBusConnection DBusDispatchStatusFunction void DBusFreeFunction DBusTimeout return DBusTimeout return DBusWatch return DBusWatch unsigned int return DBusError const DBusError return const DBusMessage return DBusMessage return DBusMessage return DBusMessage return DBusMessage return DBusMessage return DBusMessageIter * iter
EGLOutputLayerEXT EGLint EGLAttrib value
[5]
size_t qHash(const QFileSystemWatcherPathKey &key, size_t seed=0)
size_t qHash(const QHash< Key, T > &key, size_t seed=0) noexcept(noexcept(qHash(std::declval< Key & >())) &&noexcept(qHash(std::declval< T & >())))
qsizetype erase_if(QHash< Key, T > &hash, Predicate pred)
bool qHashEquals(const T &a, const T &b)
#define Q_DECLARE_MUTABLE_ASSOCIATIVE_FORWARD_ITERATOR(C)
#define Q_DECLARE_ASSOCIATIVE_FORWARD_ITERATOR(C)
constexpr const T & qMax(const T &a, const T &b)
GLenum GLsizei GLsizei GLint * values
[15]
GLenum GLuint GLintptr GLsizeiptr size
[1]
GLenum GLenum GLsizei count
GLint GLsizei GLsizei GLenum GLenum GLsizei void * data
GLenum GLuint GLintptr offset
GLfloat GLfloat GLfloat GLfloat h
GLuint GLsizei const GLuint const GLintptr * offsets
GLenum GLenum GLsizei void GLsizei void void * span
static Q_CONSTINIT QBasicAtomicInteger< unsigned > seed
constexpr void qt_ptr_swap(T *&lhs, T *&rhs) noexcept
Q_CHECK_PTR(a=new int[80])
bool operator==(const QHashDummyValue &) const noexcept
friend bool operator==(Bucket lhs, Bucket rhs) noexcept
size_t offset() const noexcept
bool isUnused() const noexcept
Bucket(const Data *d, size_t bucket) noexcept
Bucket(Span *s, size_t i) noexcept
void advance(const Data *d) noexcept
Node & nodeAtOffset(size_t offset)
iterator toIterator(const Data *d) const noexcept
friend bool operator!=(Bucket lhs, Bucket rhs) noexcept
void advanceWrapped(const Data *d) noexcept
Bucket(iterator it) noexcept
size_t toBucketIndex(const Data *d) const noexcept
void reallocationHelper(const Data &other, size_t nSpans, bool resized)
iterator begin() const noexcept
QHashPrivate::Span< Node > Span
size_t nextBucket(size_t bucket) const noexcept
typename Node::ValueType T
InsertionResult findOrInsert(const K &key) noexcept
Node * findNode(const K &key) const noexcept
QHashPrivate::iterator< Node > iterator
static Data * detached(Data *d)
iterator detachedIterator(iterator other) const noexcept
constexpr iterator end() const noexcept
bool shouldGrow() const noexcept
typename Node::KeyType Key
void rehash(size_t sizeHint=0)
void erase(Bucket bucket) noexcept(std::is_nothrow_destructible< Node >::value)
static Data * detached(Data *d, size_t size)
float loadFactor() const noexcept
static auto allocateSpans(size_t numBuckets)
Data(const Data &other, size_t reserved)
static constexpr size_t maxNumBuckets() noexcept
Bucket findBucket(const K &key) const noexcept
qsizetype free() noexcept(std::is_nothrow_destructible_v< T >)
bool contains(const T &val) const noexcept
static qsizetype freeChain(MultiNode *n) noexcept(std::is_nothrow_destructible_v< T >)
MultiNode(MultiNode &&other)
void insertMulti(Args &&... args)
MultiNode(const MultiNode &other)
static void createInPlace(MultiNode *n, const Key &k, Args &&... args)
MultiNode(const Key &k, Chain *c)
static void createInPlace(MultiNode *n, Key &&k, Args &&... args)
MultiNode(Key &&k, Chain *c) noexcept(std::is_nothrow_move_assignable_v< Key >)
MultiNodeChain< T > Chain
void emplaceValue(Args &&... args)
static void createInPlace(Node *n, const Key &k, Args &&...)
void emplaceValue(Args &&...)
bool valuesEqual(const Node *) const
static void createInPlace(Node *n, Key &&k, Args &&...)
void emplaceValue(Args &&... args)
bool valuesEqual(const Node *other) const
static void createInPlace(Node *n, const Key &k, Args &&... args)
static void createInPlace(Node *n, Key &&k, Args &&... args)
T && takeValue() noexcept(std::is_nothrow_move_assignable_v< T >)
static constexpr size_t SpanShift
static constexpr size_t LocalBucketMask
static constexpr size_t UnusedEntry
static constexpr size_t NEntries
struct QHashPrivate::Span::Entry::@178 storage
unsigned char & nextFree()
const Node & at(size_t i) const noexcept
void moveLocal(size_t from, size_t to) noexcept
void freeData() noexcept(std::is_nothrow_destructible< Node >::value)
void erase(size_t bucket) noexcept(std::is_nothrow_destructible< Node >::value)
unsigned char offsets[SpanConstants::NEntries]
Node & atOffset(size_t o) noexcept
size_t offset(size_t i) const noexcept
bool hasNode(size_t i) const noexcept
void moveFromSpan(Span &fromSpan, size_t fromIndex, size_t to) noexcept(std::is_nothrow_move_constructible_v< Node >)
const Node & atOffset(size_t o) const noexcept
Node & at(size_t i) noexcept
Node * node() const noexcept
size_t span() const noexcept
iterator operator++() noexcept
size_t index() const noexcept
bool isUnused() const noexcept
bool operator!=(iterator other) const noexcept
bool atEnd() const noexcept
bool operator==(iterator other) const noexcept
static Q_CORE_EXPORT QHashSeed globalSeed() noexcept
\threadsafe