1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GFDL-1.3-no-invariants-only
7 \brief The QSet class is a template class that provides a hash-table-based set.
14 QSet<T> is one of Qt's generic \l{container classes}. It stores
15 values in an unspecified order and provides very fast lookup of
16 the values. Internally, QSet<T> is implemented as a QHash.
18 Here's an example QSet with QString values:
20 \snippet code/doc_src_qset.cpp 0
22 To insert a value into the set, use insert():
24 \snippet code/doc_src_qset.cpp 1
26 Another way to insert items into the set is to use \l operator<<():
28 \snippet code/doc_src_qset.cpp 2
30 To test whether an item belongs to the set or not, use contains():
32 \snippet code/doc_src_qset.cpp 3
34 If you want to navigate through all the values stored in a QSet,
35 you can use an iterator. QSet supports both \l{Java-style
36 iterators} (QSetIterator and QMutableSetIterator) and \l{STL-style
37 iterators} (QSet::iterator and QSet::const_iterator). Here's how
38 to iterate over a QSet<QWidget *> using a Java-style iterator:
40 \snippet code/doc_src_qset.cpp 4
42 Here's the same code, but using an STL-style iterator:
44 \snippet code/doc_src_qset.cpp 5
46 QSet is unordered, so an iterator's sequence cannot be assumed to
47 be predictable. If ordering by key is required, use a QMap.
49 To navigate through a QSet, you can also use range-based for:
51 \snippet code/doc_src_qset.cpp 6
53 Items can be removed from the set using remove(). There is also a
54 clear() function that removes all items.
56 QSet's value data type must be an \l{assignable data type}. You
57 cannot, for example, store a QWidget as a value; instead, store a
58 QWidget *. In addition, the type must provide \c operator==(), and
59 there must also be a global qHash() function that returns a hash
60 value for an argument of the key's type. See the QHash
61 documentation for a list of types supported by qHash().
63 Internally, QSet uses a hash table to perform lookups. The hash
64 table automatically grows and shrinks to provide fast lookups
65 without wasting memory. You can still control the size of the hash
66 table by calling reserve(), if you already know approximately how
67 many elements the QSet will contain, but this isn't necessary to
68 obtain good performance. You can also call capacity() to retrieve
69 the hash table's size.
71 \sa QSetIterator, QMutableSetIterator, QHash, QMap
75 \fn template <class T> QSet<T>::QSet()
77 Constructs an empty set.
82/*! \fn template <class T> QSet<T>::QSet(std::initializer_list<T> list)
85 Constructs a set with a copy of each of the elements in the
86 initializer list \a list.
89/*! \fn template <class T> template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true> QSet<T>::QSet(InputIterator first, InputIterator last)
92 Constructs a set with the contents in the iterator range [\a first, \a last).
94 The value type of \c InputIterator must be convertible to \c T.
96 \note If the range [\a first, \a last) contains duplicate elements,
97 the first one is retained.
101 \fn template <class T> void QSet<T>::swap(QSet<T> &other)
103 Swaps set \a other with this set. This operation is very fast and
108 \fn template <class T> bool QSet<T>::operator==(const QSet<T> &other) const
110 Returns \c true if the \a other set is equal to this set; otherwise
113 Two sets are considered equal if they contain the same elements.
115 This function requires the value type to implement \c operator==().
121 \fn template <class T> bool QSet<T>::operator!=(const QSet<T> &other) const
123 Returns \c true if the \a other set is not equal to this set; otherwise
126 Two sets are considered equal if they contain the same elements.
128 This function requires the value type to implement \c operator==().
134 \fn template <class T> int QSet<T>::size() const
136 Returns the number of items in the set.
138 \sa isEmpty(), count()
142 \fn template <class T> bool QSet<T>::isEmpty() const
144 Returns \c true if the set contains no elements; otherwise returns
151 \fn template <class T> int QSet<T>::capacity() const
153 Returns the number of buckets in the set's internal hash
156 The sole purpose of this function is to provide a means of fine
157 tuning QSet's memory usage. In general, you will rarely ever need
158 to call this function. If you want to know how many items are in
159 the set, call size().
161 \sa reserve(), squeeze()
164/*! \fn template <class T> void QSet<T>::reserve(qsizetype size)
166 Ensures that the set's internal hash table consists of at
167 least \a size buckets.
169 This function is useful for code that needs to build a huge set
170 and wants to avoid repeated reallocation. For example:
172 \snippet code/doc_src_qset.cpp 7
174 Ideally, \a size should be slightly more than the maximum number
175 of elements expected in the set. \a size doesn't have to be prime,
176 because QSet will use a prime number internally anyway. If \a size
177 is an underestimate, the worst that will happen is that the QSet
178 will be a bit slower.
180 In general, you will rarely ever need to call this function.
181 QSet's internal hash table automatically shrinks or grows to
182 provide good performance without wasting too much memory.
184 \sa squeeze(), capacity()
188 \fn template <class T> void QSet<T>::squeeze()
190 Reduces the size of the set's internal hash table to save
193 The sole purpose of this function is to provide a means of fine
194 tuning QSet's memory usage. In general, you will rarely ever
195 need to call this function.
197 \sa reserve(), capacity()
201 \fn template <class T> void QSet<T>::detach()
205 Detaches this set from any other sets with which it may share
211/*! \fn template <class T> bool QSet<T>::isDetached() const
215 Returns \c true if the set's internal data isn't shared with any
216 other set object; otherwise returns \c false.
222 \fn template <class T> void QSet<T>::setSharable(bool sharable)
227 \fn template <class T> void QSet<T>::clear()
229 Removes all elements from the set.
235 \fn template <class T> bool QSet<T>::remove(const T &value)
237 Removes any occurrence of item \a value from the set. Returns
238 true if an item was actually removed; otherwise returns \c false.
240 \sa contains(), insert()
244 \fn template <class T> QSet<T>::iterator QSet<T>::erase(const_iterator pos)
247 Removes the item at the iterator position \a pos from the set, and
248 returns an iterator positioned at the next item in the set.
250 Unlike remove(), this function never causes QSet to rehash its
251 internal data structure. This means that it can safely be called
252 while iterating, and won't affect the order of items in the set.
254 \note The iterator \a pos \e must be valid and dereferenceable. Calling this
255 method on any other iterator, including its own \l end(), results in
256 undefined behavior. In particular, even the \l begin() iterator of an empty
257 set cannot be dereferenced.
262/*! \fn template <class T> QSet<T>::const_iterator QSet<T>::find(const T &value) const
265 Returns a const iterator positioned at the item \a value in the
266 set. If the set contains no item \a value, the function returns
269 \sa constFind(), contains()
272/*! \fn template <class T> QSet<T>::iterator QSet<T>::find(const T &value)
276 Returns a non-const iterator positioned at the item \a value in
277 the set. If the set contains no item \a value, the function
281/*! \fn template <class T> QSet<T>::const_iterator QSet<T>::constFind(const T &value) const
284 Returns a const iterator positioned at the item \a value in the
285 set. If the set contains no item \a value, the function returns
288 \sa find(), contains()
292 \fn template <class T> bool QSet<T>::contains(const T &value) const
294 Returns \c true if the set contains item \a value; otherwise returns
297 \sa insert(), remove(), find()
301 \fn template <class T> bool QSet<T>::contains(const QSet<T> &other) const
304 Returns \c true if the set contains all items from the \a other set;
305 otherwise returns \c false.
307 \sa insert(), remove(), find()
310/*! \fn template <class T> QSet<T>::const_iterator QSet<T>::begin() const
312 Returns a const \l{STL-style iterators}{STL-style iterator} positioned at the first
315 \sa constBegin(), end()
318/*! \fn template <class T> QSet<T>::iterator QSet<T>::begin()
322 Returns a non-const \l{STL-style iterators}{STL-style iterator} positioned at the first
326/*! \fn template <class T> QSet<T>::const_iterator QSet<T>::cbegin() const
329 Returns a const \l{STL-style iterators}{STL-style iterator} positioned at the first
335/*! \fn template <class T> QSet<T>::const_iterator QSet<T>::constBegin() const
337 Returns a const \l{STL-style iterators}{STL-style iterator} positioned at the first
340 \sa begin(), constEnd()
343/*! \fn template <class T> QSet<T>::const_iterator QSet<T>::end() const
345 Returns a const \l{STL-style iterators}{STL-style iterator} positioned at the imaginary
346 item after the last item in the set.
348 \sa constEnd(), begin()
351/*! \fn template <class T> QSet<T>::iterator QSet<T>::end()
355 Returns a non-const \l{STL-style iterators}{STL-style iterator} pointing to the
356 imaginary item after the last item in the set.
359/*! \fn template <class T> QSet<T>::const_iterator QSet<T>::cend() const
362 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
363 item after the last item in the set.
368/*! \fn template <class T> QSet<T>::const_iterator QSet<T>::constEnd() const
370 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
371 item after the last item in the set.
373 \sa constBegin(), end()
377 \typedef QSet::Iterator
380 Qt-style synonym for QSet::iterator.
384 \typedef QSet::ConstIterator
386 Qt-style synonym for QSet::const_iterator.
390 \typedef QSet::const_pointer
392 Typedef for const T *. Provided for STL compatibility.
396 \typedef QSet::const_reference
398 Typedef for const T &. Provided for STL compatibility.
402 \typedef QSet::difference_type
404 Typedef for const ptrdiff_t. Provided for STL compatibility.
408 \typedef QSet::key_type
410 Typedef for T. Provided for STL compatibility.
414 \typedef QSet::pointer
416 Typedef for T *. Provided for STL compatibility.
420 \typedef QSet::reference
422 Typedef for T &. Provided for STL compatibility.
426 \typedef QSet::size_type
428 Typedef for int. Provided for STL compatibility.
432 \typedef QSet::value_type
434 Typedef for T. Provided for STL compatibility.
438 \fn template <class T> QSet<T>::iterator QSet<T>::insert(const T &value)
440 Inserts item \a value into the set, if \a value isn't already
441 in the set, and returns an iterator pointing at the inserted
444 \sa operator<<(), remove(), contains()
448 \fn template <class T> QSet<T> &QSet<T>::unite(const QSet<T> &other)
450 Each item in the \a other set that isn't already in this set is
451 inserted into this set. A reference to this set is returned.
453 \sa operator|=(), intersect(), subtract()
457 \fn template <class T> QSet<T> &QSet<T>::intersect(const QSet<T> &other)
459 Removes all items from this set that are not contained in the
460 \a other set. A reference to this set is returned.
462 \sa intersects(), operator&=(), unite(), subtract()
466 \fn template <class T> bool QSet<T>::intersects(const QSet<T> &other) const
469 Returns \c true if this set has at least one item in common with
472 \sa contains(), intersect()
476 \fn template <class T> QSet<T> &QSet<T>::subtract(const QSet<T> &other)
478 Removes all items from this set that are contained in the
479 \a other set. Returns a reference to this set.
481 \sa operator-=(), unite(), intersect()
485 \fn template <class T> bool QSet<T>::empty() const
487 Returns \c true if the set is empty. This function is provided
488 for STL compatibility. It is equivalent to isEmpty().
492 \fn template <class T> QSet<T>::iterator QSet<T>::insert(const_iterator it, const T &value)
496 Inserts item \a value into the set, if \a value isn't already
497 in the set, and returns an iterator pointing at the inserted
500 The iterator \a it is ignored.
502 This function is provided for compatibility with the STL.
504 \sa operator<<(), remove(), contains()
508 \fn template <class T> bool QSet<T>::count() const
514 \fn template <class T> QSet<T> &QSet<T>::operator<<(const T &value)
515 \fn template <class T> QSet<T> &QSet<T>::operator+=(const T &value)
516 \fn template <class T> QSet<T> &QSet<T>::operator|=(const T &value)
518 Inserts a new item \a value and returns a reference to the set.
519 If \a value already exists in the set, the set is left unchanged.
525 \fn template <class T> QSet<T> &QSet<T>::operator-=(const T &value)
527 Removes the occurrence of item \a value from the set, if
528 it is found, and returns a reference to the set. If the
529 \a value is not contained the set, nothing is removed.
535 \fn template <class T> QSet<T> &QSet<T>::operator|=(const QSet<T> &other)
536 \fn template <class T> QSet<T> &QSet<T>::operator+=(const QSet<T> &other)
538 Same as \l {unite()} {unite(\a other)}.
540 \sa operator|(), operator&=(), operator-=()
544 \fn template <class T> QSet<T> &QSet<T>::operator&=(const QSet<T> &other)
546 Same as \l {intersect()} {intersect(\a other)}.
548 \sa operator&(), operator|=(), operator-=()
552 \fn template <class T> QSet<T> &QSet<T>::operator&=(const T &value)
556 Same as \l {intersect()} {intersect(\e{other})}, if we consider \e other to be a set
557 that contains the singleton \a value.
562 \fn template <class T> QSet<T> &QSet<T>::operator-=(const QSet<T> &other)
564 Same as \l {subtract()} {subtract(\a{other})}.
566 \sa operator-(), operator|=(), operator&=()
570 \fn template <class T> QSet<T> QSet<T>::operator|(const QSet &lhs, const QSet &rhs)
571 \fn template <class T> QSet<T> QSet<T>::operator|(QSet &&lhs, const QSet &rhs)
572 \fn template <class T> QSet<T> QSet<T>::operator+(const QSet &lhs, const QSet &rhs)
573 \fn template <class T> QSet<T> QSet<T>::operator+(QSet &&lhs, const QSet &rhs)
575 Returns a new QSet that is the union of sets \a lhs and \a rhs.
577 \sa unite(), operator|=(), operator&(), operator-()
581 \fn template <class T> QSet<T> QSet<T>::operator&(const QSet &lhs, const QSet &rhs)
582 \fn template <class T> QSet<T> QSet<T>::operator&(QSet &&lhs, const QSet &rhs)
584 Returns a new QSet that is the intersection of sets \a lhs and \a rhs.
586 \sa intersect(), operator&=(), operator|(), operator-()
590 \fn template <class T> QSet<T> QSet<T>::operator-(const QSet &lhs, const QSet &rhs)
591 \fn template <class T> QSet<T> QSet<T>::operator-(QSet &&lhs, const QSet &rhs)
593 Returns a new QSet that is the set difference of sets \a lhs and \a rhs.
595 \sa subtract(), operator-=(), operator|(), operator&()
599 \class QSet::iterator
602 \brief The QSet::iterator class provides an STL-style non-const iterator for QSet.
604 QSet features both \l{STL-style iterators} and
605 \l{Java-style iterators}. The STL-style iterators are more
606 low-level and more cumbersome to use; on the other hand, they are
607 slightly faster and, for developers who already know STL, have
608 the advantage of familiarity.
610 QSet<T>::iterator allows you to iterate over a QSet and to remove
611 items (using QSet::erase()) while you iterate. (QSet doesn't let
612 you \e modify a value through an iterator, because that
613 would potentially require moving the value in the internal hash
614 table used by QSet.) If you want to iterate over a const QSet,
615 you should use QSet::const_iterator. It is generally good
616 practice to use QSet::const_iterator on a non-const QSet as well,
617 unless you need to change the QSet through the iterator. Const
618 iterators are slightly faster, and can improve code readability.
620 The default QSet::iterator constructor creates an uninitialized
621 iterator. You must initialize it using a function like
622 QSet::begin(), QSet::end(), or QSet::insert() before you can
623 start iterating. Here's a typical loop that prints all the items
626 \snippet code/doc_src_qset.cpp 8
628 Here's a loop that removes certain items (all those that start
629 with 'J') from a set while iterating:
631 \snippet code/doc_src_qset.cpp 9
633 STL-style iterators can be used as arguments to \l{generic
634 algorithms}. For example, here's how to find an item in the set
635 using the qFind() algorithm:
637 \snippet code/doc_src_qset.cpp 10
639 Multiple iterators can be used on the same set.
641 \warning Iterators on implicitly shared containers do not work
642 exactly like STL-iterators. You should avoid copying a container
643 while iterators are active on that container. For more information,
644 read \l{Implicit sharing iterator problem}.
646 \sa QSet::const_iterator, QMutableSetIterator
650 \class QSet::const_iterator
652 \brief The QSet::const_iterator class provides an STL-style const iterator for QSet.
655 QSet features both \l{STL-style iterators} and
656 \l{Java-style iterators}. The STL-style iterators are more
657 low-level and more cumbersome to use; on the other hand, they are
658 slightly faster and, for developers who already know STL, have
659 the advantage of familiarity.
661 QSet<Key, T>::const_iterator allows you to iterate over a QSet.
662 If you want to modify the QSet as you iterate over it, you must
663 use QSet::iterator instead. It is generally good practice to use
664 QSet::const_iterator on a non-const QSet as well, unless you need
665 to change the QSet through the iterator. Const iterators are
666 slightly faster, and can improve code readability.
668 The default QSet::const_iterator constructor creates an
669 uninitialized iterator. You must initialize it using a function
670 like QSet::begin(), QSet::end(), or QSet::insert() before you can
671 start iterating. Here's a typical loop that prints all the items
674 \snippet code/doc_src_qset.cpp 11
676 STL-style iterators can be used as arguments to \l{generic
677 algorithms}. For example, here's how to find an item in the set
678 using the qFind() algorithm:
680 \snippet code/doc_src_qset.cpp 12
682 \warning Iterators on implicitly shared containers do not work
683 exactly like STL-iterators. You should avoid copying a container
684 while iterators are active on that container. For more information,
685 read \l{Implicit sharing iterator problem}.
687 \sa QSet::iterator, QSetIterator
691 \fn template <class T> QSet<T>::iterator::iterator()
692 \fn template <class T> QSet<T>::const_iterator::const_iterator()
694 Constructs an uninitialized iterator.
696 Functions like operator*() and operator++() should not be called
697 on an uninitialized iterator. Use operator=() to assign a value
698 to it before using it.
700 \sa QSet::begin(), QSet::end()
704 \fn template <class T> QSet<T>::iterator::iterator(typename Hash::iterator i)
705 \fn template <class T> QSet<T>::const_iterator::const_iterator(typename Hash::const_iterator i)
711 \typedef QSet::iterator::iterator_category
712 \typedef QSet::const_iterator::iterator_category
714 Synonyms for \e {std::bidirectional_iterator_tag} indicating
715 these iterators are bidirectional iterators.
719 \typedef QSet::iterator::difference_type
720 \typedef QSet::const_iterator::difference_type
726 \typedef QSet::iterator::value_type
727 \typedef QSet::const_iterator::value_type
733 \typedef QSet::iterator::pointer
734 \typedef QSet::const_iterator::pointer
740 \typedef QSet::iterator::reference
741 \typedef QSet::const_iterator::reference
747 \fn template <class T> QSet<T>::iterator::iterator(const iterator &other)
748 \fn template <class T> QSet<T>::const_iterator::const_iterator(const const_iterator &other)
750 Constructs a copy of \a other.
754 \fn template <class T> QSet<T>::const_iterator::const_iterator(const iterator &other)
758 Constructs a copy of \a other.
762 \fn template <class T> QSet<T>::iterator &QSet<T>::iterator::operator=(const iterator &other)
763 \fn template <class T> QSet<T>::const_iterator &QSet<T>::const_iterator::operator=(const const_iterator &other)
765 Assigns \a other to this iterator.
769 \fn template <class T> const T &QSet<T>::iterator::operator*() const
770 \fn template <class T> const T &QSet<T>::const_iterator::operator*() const
772 Returns a reference to the current item.
778 \fn template <class T> const T *QSet<T>::iterator::operator->() const
779 \fn template <class T> const T *QSet<T>::const_iterator::operator->() const
781 Returns a pointer to the current item.
787 \fn template <class T> bool QSet<T>::iterator::operator==(const iterator &other) const
788 \fn template <class T> bool QSet<T>::const_iterator::operator==(const const_iterator &other) const
790 Returns \c true if \a other points to the same item as this
791 iterator; otherwise returns \c false.
797 \fn template <class T> bool QSet<T>::iterator::operator==(const const_iterator &other) const
798 \fn template <class T> bool QSet<T>::iterator::operator!=(const const_iterator &other) const
804 \fn template <class T> bool QSet<T>::iterator::operator!=(const iterator &other) const
805 \fn template <class T> bool QSet<T>::const_iterator::operator!=(const const_iterator &other) const
807 Returns \c true if \a other points to a different item than this
808 iterator; otherwise returns \c false.
814 \fn template <class T> QSet<T>::iterator &QSet<T>::iterator::operator++()
815 \fn template <class T> QSet<T>::const_iterator &QSet<T>::const_iterator::operator++()
817 The prefix ++ operator (\c{++it}) advances the iterator to the
818 next item in the set and returns an iterator to the new current
821 Calling this function on QSet<T>::constEnd() leads to
826 \fn template <class T> QSet<T>::iterator QSet<T>::iterator::operator++(int)
827 \fn template <class T> QSet<T>::const_iterator QSet<T>::const_iterator::operator++(int)
831 The postfix ++ operator (\c{it++}) advances the iterator to the
832 next item in the set and returns an iterator to the previously
836/*! \fn template <class T> QList<T> QSet<T>::values() const
838 Returns a new QList containing the elements in the set. The
839 order of the elements in the QList is undefined.
841 \include containers-range-constructor.qdocinc
843 This function creates a new list, in \l {linear time}. The time and memory
844 use that entails can be avoided by iterating from \l constBegin() to
850 \fn template <class T> QDataStream &operator<<(QDataStream &out, const QSet<T> &set)
853 Writes the \a set to stream \a out.
855 This function requires the value type to implement \c operator<<().
857 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
861 \fn template <class T> QDataStream &operator>>(QDataStream &in, QSet<T> &set)
864 Reads a set from stream \a in into \a set.
866 This function requires the value type to implement \c operator>>().
868 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
872 \fn template <class T> size_t qHash(const QSet<T> &key, size_t seed = 0)
876 Returns the hash value for the \a key, using \a seed to seed the calculation.
878 The hash value is independent of the order of elements in \a key, that is, sets
879 that contain the same elements hash to the same value.
882/*! \fn template <class T, class Predicate> qsizetype erase_if(QSet<T> &set, Predicate pred)
886 Removes all elements for which the predicate \a pred returns true
887 from the set \a set. Returns the number of elements removed, if
891/*! \fn template <class T> template <class Pred> qsizetype QSet<T>::removeIf(Pred pred)
894 Removes, from this set, all elements for which the predicate \a pred
895 returns \c true. Returns the number of elements removed, if any.