/**************************************************************************** ** ** Copyright (C) 2016 The Qt Company Ltd. ** Contact: https://www.qt.io/licensing/ ** ** This file is part of the documentation of the Qt Toolkit. ** ** $QT_BEGIN_LICENSE:FDL$ ** Commercial License Usage ** Licensees holding valid commercial Qt licenses may use this file in ** accordance with the commercial license agreement provided with the ** Software or, alternatively, in accordance with the terms contained in ** a written agreement between you and The Qt Company. For licensing terms ** and conditions see https://www.qt.io/terms-conditions. For further ** information use the contact form at https://www.qt.io/contact-us. ** ** GNU Free Documentation License Usage ** Alternatively, this file may be used under the terms of the GNU Free ** Documentation License version 1.3 as published by the Free Software ** Foundation and appearing in the file included in the packaging of ** this file. Please review the following information to ensure ** the GNU Free Documentation License version 1.3 requirements ** will be met: https://www.gnu.org/licenses/fdl-1.3.html. ** $QT_END_LICENSE$ ** ****************************************************************************/ /*! \class QSet \inmodule QtCore \brief The QSet class is a template class that provides a hash-table-based set. \ingroup tools \ingroup shared \reentrant QSet is one of Qt's generic \l{container classes}. It stores values in an unspecified order and provides very fast lookup of the values. Internally, QSet is implemented as a QHash. Here's an example QSet with QString values: \snippet code/doc_src_qset.cpp 0 To insert a value into the set, use insert(): \snippet code/doc_src_qset.cpp 1 Another way to insert items into the set is to use operator<<(): \snippet code/doc_src_qset.cpp 2 To test whether an item belongs to the set or not, use contains(): \snippet code/doc_src_qset.cpp 3 If you want to navigate through all the values stored in a QSet, you can use an iterator. QSet supports both \l{Java-style iterators} (QSetIterator and QMutableSetIterator) and \l{STL-style iterators} (QSet::iterator and QSet::const_iterator). Here's how to iterate over a QSet using a Java-style iterator: \snippet code/doc_src_qset.cpp 4 Here's the same code, but using an STL-style iterator: \snippet code/doc_src_qset.cpp 5 QSet is unordered, so an iterator's sequence cannot be assumed to be predictable. If ordering by key is required, use a QMap. To navigate through a QSet, you can also use \l{foreach}: \snippet code/doc_src_qset.cpp 6 Items can be removed from the set using remove(). There is also a clear() function that removes all items. QSet's value data type must be an \l{assignable data type}. You cannot, for example, store a QWidget as a value; instead, store a QWidget *. In addition, the type must provide \c operator==(), and there must also be a global qHash() function that returns a hash value for an argument of the key's type. See the QHash documentation for a list of types supported by qHash(). Internally, QSet uses a hash table to perform lookups. The hash table automatically grows and shrinks to provide fast lookups without wasting memory. You can still control the size of the hash table by calling reserve(), if you already know approximately how many elements the QSet will contain, but this isn't necessary to obtain good performance. You can also call capacity() to retrieve the hash table's size. \sa QSetIterator, QMutableSetIterator, QHash, QMap */ /*! \fn template QSet::QSet() Constructs an empty set. \sa clear() */ /*! \fn template QSet::QSet(std::initializer_list list) \since 5.1 Constructs a set with a copy of each of the elements in the initializer list \a list. This function is only available if the program is being compiled in C++11 mode. */ /*! \fn template void QSet::swap(QSet &other) Swaps set \a other with this set. This operation is very fast and never fails. */ /*! \fn template bool QSet::operator==(const QSet &other) const Returns \c true if the \a other set is equal to this set; otherwise returns \c false. Two sets are considered equal if they contain the same elements. This function requires the value type to implement \c operator==(). \sa operator!=() */ /*! \fn template bool QSet::operator!=(const QSet &other) const Returns \c true if the \a other set is not equal to this set; otherwise returns \c false. Two sets are considered equal if they contain the same elements. This function requires the value type to implement \c operator==(). \sa operator==() */ /*! \fn template int QSet::size() const Returns the number of items in the set. \sa isEmpty(), count() */ /*! \fn template bool QSet::isEmpty() const Returns \c true if the set contains no elements; otherwise returns false. \sa size() */ /*! \fn template int QSet::capacity() const Returns the number of buckets in the set's internal hash table. The sole purpose of this function is to provide a means of fine tuning QSet's memory usage. In general, you will rarely ever need to call this function. If you want to know how many items are in the set, call size(). \sa reserve(), squeeze() */ /*! \fn template void QSet::reserve(int size) Ensures that the set's internal hash table consists of at least \a size buckets. This function is useful for code that needs to build a huge set and wants to avoid repeated reallocation. For example: \snippet code/doc_src_qset.cpp 7 Ideally, \a size should be slightly more than the maximum number of elements expected in the set. \a size doesn't have to be prime, because QSet will use a prime number internally anyway. If \a size is an underestimate, the worst that will happen is that the QSet will be a bit slower. In general, you will rarely ever need to call this function. QSet's internal hash table automatically shrinks or grows to provide good performance without wasting too much memory. \sa squeeze(), capacity() */ /*! \fn template void QSet::squeeze() Reduces the size of the set's internal hash table to save memory. The sole purpose of this function is to provide a means of fine tuning QSet's memory usage. In general, you will rarely ever need to call this function. \sa reserve(), capacity() */ /*! \fn template void QSet::detach() \internal Detaches this set from any other sets with which it may share data. \sa isDetached() */ /*! \fn template bool QSet::isDetached() const \internal Returns \c true if the set's internal data isn't shared with any other set object; otherwise returns \c false. \sa detach() */ /*! \fn template void QSet::setSharable(bool sharable) \internal */ /*! \fn template void QSet::clear() Removes all elements from the set. \sa remove() */ /*! \fn template bool QSet::remove(const T &value) Removes any occurrence of item \a value from the set. Returns true if an item was actually removed; otherwise returns \c false. \sa contains(), insert() */ /*! \fn template QSet::iterator QSet::erase(const_iterator pos) \since 5.7 Removes the item at the iterator position \a pos from the set, and returns an iterator positioned at the next item in the set. Unlike remove(), this function never causes QSet to rehash its internal data structure. This means that it can safely be called while iterating, and won't affect the order of items in the set. \sa remove(), find() */ /*! \fn template QSet::iterator QSet::erase(iterator pos) \since 4.2 \overload */ /*! \fn template QSet::const_iterator QSet::find(const T &value) const \since 4.2 Returns a const iterator positioned at the item \a value in the set. If the set contains no item \a value, the function returns constEnd(). \sa constFind(), contains() */ /*! \fn template QSet::iterator QSet::find(const T &value) \since 4.2 \overload Returns a non-const iterator positioned at the item \a value in the set. If the set contains no item \a value, the function returns end(). */ /*! \fn template QSet::const_iterator QSet::constFind(const T &value) const \since 4.2 Returns a const iterator positioned at the item \a value in the set. If the set contains no item \a value, the function returns constEnd(). \sa find(), contains() */ /*! \fn template bool QSet::contains(const T &value) const Returns \c true if the set contains item \a value; otherwise returns false. \sa insert(), remove(), find() */ /*! \fn template bool QSet::contains(const QSet &other) const \since 4.6 Returns \c true if the set contains all items from the \a other set; otherwise returns \c false. \sa insert(), remove(), find() */ /*! \fn template QSet::const_iterator QSet::begin() const Returns a const \l{STL-style iterators}{STL-style iterator} positioned at the first item in the set. \sa constBegin(), end() */ /*! \fn template QSet::iterator QSet::begin() \since 4.2 \overload Returns a non-const \l{STL-style iterators}{STL-style iterator} positioned at the first item in the set. */ /*! \fn template QSet::const_iterator QSet::cbegin() const \since 5.0 Returns a const \l{STL-style iterators}{STL-style iterator} positioned at the first item in the set. \sa begin(), cend() */ /*! \fn template QSet::const_iterator QSet::constBegin() const Returns a const \l{STL-style iterators}{STL-style iterator} positioned at the first item in the set. \sa begin(), constEnd() */ /*! \fn template QSet::const_iterator QSet::end() const Returns a const \l{STL-style iterators}{STL-style iterator} positioned at the imaginary item after the last item in the set. \sa constEnd(), begin() */ /*! \fn template QSet::iterator QSet::end() \since 4.2 \overload Returns a non-const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last item in the set. */ /*! \fn template QSet::const_iterator QSet::cend() const \since 5.0 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last item in the set. \sa cbegin(), end() */ /*! \fn template QSet::const_iterator QSet::constEnd() const Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last item in the set. \sa constBegin(), end() */ /*! \fn template QSet::reverse_iterator QSet::rbegin() \since 5.6 Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to the first item in the set, in reverse order. \sa begin(), crbegin(), rend() */ /*! \fn template QSet::const_reverse_iterator QSet::rbegin() const \since 5.6 \overload */ /*! \fn template QSet::const_reverse_iterator QSet::crbegin() const \since 5.6 Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to the first item in the set, in reverse order. \sa begin(), rbegin(), rend() */ /*! \fn template QSet::reverse_iterator QSet::rend() \since 5.6 Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to one past the last item in the set, in reverse order. \sa end(), crend(), rbegin() */ /*! \fn template QSet::const_reverse_iterator QSet::rend() const \since 5.6 \overload */ /*! \fn template QSet::const_reverse_iterator QSet::crend() const \since 5.6 Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to one past the last item in the set, in reverse order. \sa end(), rend(), rbegin() */ /*! \typedef QSet::Iterator \since 4.2 Qt-style synonym for QSet::iterator. */ /*! \typedef QSet::ConstIterator Qt-style synonym for QSet::const_iterator. */ /*! \typedef QSet::const_pointer Typedef for const T *. Provided for STL compatibility. */ /*! \typedef QSet::const_reference Typedef for const T &. Provided for STL compatibility. */ /*! \typedef QSet::difference_type Typedef for const ptrdiff_t. Provided for STL compatibility. */ /*! \typedef QSet::key_type Typedef for T. Provided for STL compatibility. */ /*! \typedef QSet::pointer Typedef for T *. Provided for STL compatibility. */ /*! \typedef QSet::reference Typedef for T &. Provided for STL compatibility. */ /*! \typedef QSet::size_type Typedef for int. Provided for STL compatibility. */ /*! \typedef QSet::value_type Typedef for T. Provided for STL compatibility. */ /*! \typedef QSet::reverse_iterator \since 5.6 The QSet::reverse_iterator typedef provides an STL-style non-const reverse iterator for QSet. It is simply a typedef for \c{std::reverse_iterator}. \warning Iterators on implicitly shared containers do not work exactly like STL-iterators. You should avoid copying a container while iterators are active on that container. For more information, read \l{Implicit sharing iterator problem}. \sa QSet::rbegin(), QSet::rend(), QSet::const_reverse_iterator, QSet::iterator */ /*! \typedef QSet::const_reverse_iterator \since 5.6 The QSet::const_reverse_iterator typedef provides an STL-style const reverse iterator for QSet. It is simply a typedef for \c{std::reverse_iterator}. \warning Iterators on implicitly shared containers do not work exactly like STL-iterators. You should avoid copying a container while iterators are active on that container. For more information, read \l{Implicit sharing iterator problem}. \sa QSet::rbegin(), QSet::rend(), QSet::reverse_iterator, QSet::const_iterator */ /*! \fn template QSet::insert(const T &value) Inserts item \a value into the set, if \a value isn't already in the set, and returns an iterator pointing at the inserted item. \sa operator<<(), remove(), contains() */ /*! \fn template QSet &QSet::unite(const QSet &other) Each item in the \a other set that isn't already in this set is inserted into this set. A reference to this set is returned. \sa operator|=(), intersect(), subtract() */ /*! \fn template QSet &QSet::intersect(const QSet &other) Removes all items from this set that are not contained in the \a other set. A reference to this set is returned. \sa intersects(), operator&=(), unite(), subtract() */ /*! \fn template bool QSet::intersects(const QSet &other) const \since 5.6 Returns \c true if this set has at least one item in common with \a other. \sa contains(), intersect() */ /*! \fn template QSet &QSet::subtract(const QSet &other) Removes all items from this set that are contained in the \a other set. Returns a reference to this set. \sa operator-=(), unite(), intersect() */ /*! \fn template bool QSet::empty() const Returns \c true if the set is empty. This function is provided for STL compatibility. It is equivalent to isEmpty(). */ /*! \fn template bool QSet::count() const Same as size(). */ /*! \fn template QSet &QSet::operator<<(const T &value) \fn template QSet &QSet::operator+=(const T &value) \fn template QSet &QSet::operator|=(const T &value) Inserts a new item \a value and returns a reference to the set. If \a value already exists in the set, the set is left unchanged. \sa insert() */ /*! \fn template QSet &QSet::operator-=(const T &value) Removes the occurrence of item \a value from the set, if it is found, and returns a reference to the set. If the \a value is not contained the set, nothing is removed. \sa remove() */ /*! \fn template QSet &QSet::operator|=(const QSet &other) \fn template QSet &QSet::operator+=(const QSet &other) Same as unite(\a other). \sa operator|(), operator&=(), operator-=() */ /*! \fn template QSet &QSet::operator&=(const QSet &other) Same as intersect(\a other). \sa operator&(), operator|=(), operator-=() */ /*! \fn template QSet &QSet::operator&=(const T &value) \overload Same as intersect(\e{other}), if we consider \e{other} to be a set that contains the singleton \a value. */ /*! \fn template QSet &QSet::operator-=(const QSet &other) Same as subtract(\a{other}). \sa operator-(), operator|=(), operator&=() */ /*! \fn template QSet QSet::operator|(const QSet &other) const \fn template QSet QSet::operator+(const QSet &other) const Returns a new QSet that is the union of this set and the \a other set. \sa unite(), operator|=(), operator&(), operator-() */ /*! \fn template QSet QSet::operator&(const QSet &other) const Returns a new QSet that is the intersection of this set and the \a other set. \sa intersect(), operator&=(), operator|(), operator-() */ /*! \fn template QSet QSet::operator-(const QSet &other) const Returns a new QSet that is the set difference of this set and the \a other set, i.e., this set - \a other set. \sa subtract(), operator-=(), operator|(), operator&() */ /*! \class QSet::iterator \inmodule QtCore \since 4.2 \brief The QSet::iterator class provides an STL-style non-const iterator for QSet. QSet features both \l{STL-style iterators} and \l{Java-style iterators}. The STL-style iterators are more low-level and more cumbersome to use; on the other hand, they are slightly faster and, for developers who already know STL, have the advantage of familiarity. QSet::iterator allows you to iterate over a QSet and to remove items (using QSet::erase()) while you iterate. (QSet doesn't let you \e modify a value through an iterator, because that would potentially require moving the value in the internal hash table used by QSet.) If you want to iterate over a const QSet, you should use QSet::const_iterator. It is generally good practice to use QSet::const_iterator on a non-const QSet as well, unless you need to change the QSet through the iterator. Const iterators are slightly faster, and can improve code readability. The default QSet::iterator constructor creates an uninitialized iterator. You must initialize it using a function like QSet::begin(), QSet::end(), or QSet::insert() before you can start iterating. Here's a typical loop that prints all the items stored in a set: \snippet code/doc_src_qset.cpp 8 Here's a loop that removes certain items (all those that start with 'J') from a set while iterating: \snippet code/doc_src_qset.cpp 9 STL-style iterators can be used as arguments to \l{generic algorithms}. For example, here's how to find an item in the set using the qFind() algorithm: \snippet code/doc_src_qset.cpp 10 Multiple iterators can be used on the same set. \warning Iterators on implicitly shared containers do not work exactly like STL-iterators. You should avoid copying a container while iterators are active on that container. For more information, read \l{Implicit sharing iterator problem}. \sa QSet::const_iterator, QMutableSetIterator */ /*! \class QSet::const_iterator \inmodule QtCore \brief The QSet::const_iterator class provides an STL-style const iterator for QSet. \since 4.2 QSet features both \l{STL-style iterators} and \l{Java-style iterators}. The STL-style iterators are more low-level and more cumbersome to use; on the other hand, they are slightly faster and, for developers who already know STL, have the advantage of familiarity. QSet\::const_iterator allows you to iterate over a QSet. If you want to modify the QSet as you iterate over it, you must use QSet::iterator instead. It is generally good practice to use QSet::const_iterator on a non-const QSet as well, unless you need to change the QSet through the iterator. Const iterators are slightly faster, and can improve code readability. The default QSet::const_iterator constructor creates an uninitialized iterator. You must initialize it using a function like QSet::begin(), QSet::end(), or QSet::insert() before you can start iterating. Here's a typical loop that prints all the items stored in a set: \snippet code/doc_src_qset.cpp 11 STL-style iterators can be used as arguments to \l{generic algorithms}. For example, here's how to find an item in the set using the qFind() algorithm: \snippet code/doc_src_qset.cpp 12 \warning Iterators on implicitly shared containers do not work exactly like STL-iterators. You should avoid copying a container while iterators are active on that container. For more information, read \l{Implicit sharing iterator problem}. \sa QSet::iterator, QSetIterator */ /*! \fn template QSet::iterator::iterator() \fn template QSet::const_iterator::const_iterator() Constructs an uninitialized iterator. Functions like operator*() and operator++() should not be called on an uninitialized iterator. Use operator=() to assign a value to it before using it. \sa QSet::begin(), QSet::end() */ /*! \fn template QSet::iterator::iterator(typename Hash::iterator i) \fn template QSet::const_iterator::const_iterator(typename Hash::const_iterator i) \internal */ /*! \typedef QSet::iterator::iterator_category \typedef QSet::const_iterator::iterator_category Synonyms for \e {std::bidirectional_iterator_tag} indicating these iterators are bidirectional iterators. */ /*! \typedef QSet::iterator::difference_type \typedef QSet::const_iterator::difference_type \internal */ /*! \typedef QSet::iterator::value_type \typedef QSet::const_iterator::value_type \internal */ /*! \typedef QSet::iterator::pointer \typedef QSet::const_iterator::pointer \internal */ /*! \typedef QSet::iterator::reference \typedef QSet::const_iterator::reference \internal */ /*! \fn template QSet::iterator::iterator(const iterator &other) \fn template QSet::const_iterator::const_iterator(const const_iterator &other) Constructs a copy of \a other. */ /*! \fn template QSet::const_iterator::const_iterator(const iterator &other) \since 4.2 \overload Constructs a copy of \a other. */ /*! \fn template QSet::iterator &QSet::iterator::operator=(const iterator &other) \fn template QSet::const_iterator &QSet::const_iterator::operator=(const const_iterator &other) Assigns \a other to this iterator. */ /*! \fn template const T &QSet::iterator::operator*() const \fn template const T &QSet::const_iterator::operator*() const Returns a reference to the current item. \sa operator->() */ /*! \fn template const T *QSet::iterator::operator->() const \fn template const T *QSet::const_iterator::operator->() const Returns a pointer to the current item. \sa operator*() */ /*! \fn template bool QSet::iterator::operator==(const iterator &other) const \fn template bool QSet::const_iterator::operator==(const const_iterator &other) const Returns \c true if \a other points to the same item as this iterator; otherwise returns \c false. \sa operator!=() */ /*! \fn template bool QSet::iterator::operator==(const const_iterator &other) const \fn template bool QSet::iterator::operator!=(const const_iterator &other) const \overload */ /*! \fn template bool QSet::iterator::operator!=(const iterator &other) const \fn template bool QSet::const_iterator::operator!=(const const_iterator &other) const Returns \c true if \a other points to a different item than this iterator; otherwise returns \c false. \sa operator==() */ /*! \fn template QSet::iterator &QSet::iterator::operator++() \fn template QSet::const_iterator &QSet::const_iterator::operator++() The prefix ++ operator (\c{++it}) advances the iterator to the next item in the set and returns an iterator to the new current item. Calling this function on QSet::constEnd() leads to undefined results. \sa operator--() */ /*! \fn template QSet::iterator QSet::iterator::operator++(int) \fn template QSet::const_iterator QSet::const_iterator::operator++(int) \overload The postfix ++ operator (\c{it++}) advances the iterator to the next item in the set and returns an iterator to the previously current item. */ /*! \fn template QSet::iterator &QSet::iterator::operator--() \fn template QSet::const_iterator &QSet::const_iterator::operator--() The prefix -- operator (\c{--it}) makes the preceding item current and returns an iterator to the new current item. Calling this function on QSet::begin() leads to undefined results. \sa operator++() */ /*! \fn template QSet::iterator QSet::iterator::operator--(int) \fn template QSet::const_iterator QSet::const_iterator::operator--(int) \overload The postfix -- operator (\c{it--}) makes the preceding item current and returns an iterator to the previously current item. */ /*! \fn template QSet::iterator QSet::iterator::operator+(int j) const \fn template QSet::const_iterator QSet::const_iterator::operator+(int j) const Returns an iterator to the item at \a j positions forward from this iterator. (If \a j is negative, the iterator goes backward.) This operation can be slow for large \a j values. \sa operator-() */ /*! \fn template QSet::iterator QSet::iterator::operator-(int j) const \fn template QSet::const_iterator QSet::const_iterator::operator-(int j) const Returns an iterator to the item at \a j positions backward from this iterator. (If \a j is negative, the iterator goes forward.) This operation can be slow for large \a j values. \sa operator+() */ /*! \fn template QSet::iterator &QSet::iterator::operator+=(int j) \fn template QSet::const_iterator &QSet::const_iterator::operator+=(int j) Advances the iterator by \a j items. (If \a j is negative, the iterator goes backward.) This operation can be slow for large \a j values. \sa operator-=(), operator+() */ /*! \fn template QSet::iterator &QSet::iterator::operator-=(int j) \fn template QSet::const_iterator &QSet::const_iterator::operator-=(int j) Makes the iterator go back by \a j items. (If \a j is negative, the iterator goes forward.) This operation can be slow for large \a j values. \sa operator+=(), operator-() */ /*! \fn template QList QSet::toList() const Returns a new QList containing the elements in the set. The order of the elements in the QList is undefined. Example: \snippet code/doc_src_qset.cpp 13 \sa fromList(), QList::fromSet() */ /*! \fn template QList QSet::values() const Returns a new QList containing the elements in the set. The order of the elements in the QList is undefined. This is the same as toList(). \sa fromList(), QList::fromSet() */ /*! \fn template QSet QSet::fromList(const QList &list) Returns a new QSet object containing the data contained in \a list. Since QSet doesn't allow duplicates, the resulting QSet might be smaller than the \a list, because QList can contain duplicates. Example: \snippet code/doc_src_qset.cpp 14 \sa toList(), QList::toSet() */ /*! \fn template QDataStream &operator<<(QDataStream &out, const QSet &set) \relates QSet Writes the \a set to stream \a out. This function requires the value type to implement \c operator<<(). \sa{Serializing Qt Data Types}{Format of the QDataStream operators} */ /*! \fn template QDataStream &operator>>(QDataStream &in, QSet &set) \relates QSet Reads a set from stream \a in into \a set. This function requires the value type to implement \c operator>>(). \sa{Serializing Qt Data Types}{Format of the QDataStream operators} */ /*! \fn template uint qHash(const QSet &key, uint seed = 0) \relates QHash \since 5.5 Returns the hash value for the \a key, using \a seed to seed the calculation. The hash value is independent of the order of elements in \a key, that is, sets that contain the same elements hash to the same value. */