/****************************************************************************
**
** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
** All rights reserved.
** Contact: Nokia Corporation (qt-info@nokia.com)
**
** This file is part of the documentation of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** No Commercial Usage
** This file contains pre-release code and may not be distributed.
** You may use this file in accordance with the terms and conditions
** contained in the Technology Preview License Agreement accompanying
** this package.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 2.1 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 2.1 requirements
** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
**
** In addition, as a special exception, Nokia gives you certain additional
** rights. These rights are described in the Nokia Qt LGPL Exception
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
** If you have questions regarding the use of this file, please contact
** Nokia at qt-info@nokia.com.
**
**
**
**
**
**
**
**
** $QT_END_LICENSE$
**
****************************************************************************/
/*!
\class QSet
\brief The QSet class is a template class that provides a hash-table-based set.
\ingroup tools
\ingroup shared
\reentrant
QSet<T> 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<T> is implemented as a QHash.
Here's an example QSet with QString values:
\snippet doc/src/snippets/code/doc_src_qset.qdoc 0
To insert a value into the set, use insert():
\snippet doc/src/snippets/code/doc_src_qset.qdoc 1
Another way to insert items into the set is to use operator<<():
\snippet doc/src/snippets/code/doc_src_qset.qdoc 2
To test whether an item belongs to the set or not, use contains():
\snippet doc/src/snippets/code/doc_src_qset.qdoc 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<QWidget *> using a Java-style iterator:
\snippet doc/src/snippets/code/doc_src_qset.qdoc 4
Here's the same code, but using an STL-style iterator:
\snippet doc/src/snippets/code/doc_src_qset.qdoc 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 doc/src/snippets/code/doc_src_qset.qdoc 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 QSet::QSet()
Constructs an empty set.
\sa clear()
*/
/*!
\fn QSet::QSet(const QSet<T> &other)
Constructs a copy of \a other.
This operation occurs in \l{constant time}, because QSet is
\l{implicitly shared}. This makes returning a QSet from a
function very fast. If a shared instance is modified, it will be
copied (copy-on-write), and this takes \l{linear time}.
\sa operator=()
*/
/*!
\fn QSet<T> &QSet::operator=(const QSet<T> &other)
Assigns the \a other set to this set and returns a reference to
this set.
*/
/*!
\fn bool QSet::operator==(const QSet<T> &other) const
Returns true if the \a other set is equal to this set; otherwise
returns 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 bool QSet::operator!=(const QSet<T> &other) const
Returns true if the \a other set is not equal to this set; otherwise
returns 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 int QSet::size() const
Returns the number of items in the set.
\sa isEmpty(), count()
*/
/*!
\fn bool QSet::isEmpty() const
Returns true if the set contains no elements; otherwise returns
false.
\sa size()
*/
/*!
\fn 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 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 doc/src/snippets/code/doc_src_qset.qdoc 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 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 void QSet::detach()
\internal
Detaches this set from any other sets with which it may share
data.
\sa isDetached()
*/
/*! \fn bool QSet::isDetached() const
\internal
Returns true if the set's internal data isn't shared with any
other set object; otherwise returns false.
\sa detach()
*/
/*!
\fn void QSet::setSharable(bool sharable)
\internal
*/
/*!
\fn void QSet::clear()
Removes all elements from the set.
\sa remove()
*/
/*!
\fn 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 false.
\sa contains(), insert()
*/
/*!
\fn QSet::iterator QSet::erase(iterator pos)
\since 4.2
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 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 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 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 bool QSet::contains(const T &value) const
Returns true if the set contains item \a value; otherwise returns
false.
\sa insert(), remove(), find()
*/
/*!
\fn bool QSet::contains(const QSet<T> &other) const
\since 4.6
Returns true if the set contains all items from the \a other set;
otherwise returns false.
\sa insert(), remove(), find()
*/
/*! \fn QSet::const_iterator QSet::begin() const
Returns a const \l{STL-style iterator} positioned at the first
item in the set.
\sa constBegin(), end()
*/
/*! \fn QSet::iterator QSet::begin()
\since 4.2
\overload
Returns a non-const \l{STL-style iterator} positioned at the first
item in the set.
*/
/*! \fn QSet::const_iterator QSet::constBegin() const
Returns a const \l{STL-style iterator} positioned at the first
item in the set.
\sa begin(), constEnd()
*/
/*! \fn QSet::const_iterator QSet::end() const
Returns a const \l{STL-style iterator} positioned at the imaginary
item after the last item in the set.
\sa constEnd(), begin()
*/
/*! \fn QSet::iterator QSet::end()
\since 4.2
\overload
Returns a non-const \l{STL-style iterator} pointing to the
imaginary item after the last item in the set.
*/
/*! \fn QSet::const_iterator QSet::constEnd() const
Returns a const \l{STL-style iterator} pointing to the imaginary
item after the last item in the set.
\sa constBegin(), end()
*/
/*!
\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.
*/
/*!
\fn QSet::const_iterator 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 QSet<T> &QSet::unite(const QSet<T> &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 QSet<T> &QSet::intersect(const QSet<T> &other)
Removes all items from this set that are not contained in the
\a other set. A reference to this set is returned.
\sa operator&=(), unite(), subtract()
*/
/*!
\fn QSet<T> &QSet::subtract(const QSet<T> &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 bool QSet::empty() const
Returns true if the set is empty. This function is provided
for STL compatibility. It is equivalent to isEmpty().
*/
/*!
\fn bool QSet::count() const
Same as size().
*/
/*!
\fn QSet<T> &QSet::operator<<(const T &value)
\fn QSet<T> &QSet::operator+=(const T &value)
\fn QSet<T> &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 QSet<T> &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 QSet<T> &QSet::operator|=(const QSet<T> &other)
\fn QSet<T> &QSet::operator+=(const QSet<T> &other)
Same as unite(\a other).
\sa operator|(), operator&=(), operator-=()
*/
/*!
\fn QSet<T> &QSet::operator&=(const QSet<T> &other)
Same as intersect(\a other).
\sa operator&(), operator|=(), operator-=()
*/
/*!
\fn QSet<T> &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 QSet<T> &QSet::operator-=(const QSet<T> &other)
Same as subtract(\a{other}).
\sa operator-(), operator|=(), operator&=()
*/
/*!
\fn QSet<T> QSet::operator|(const QSet<T> &other) const
\fn QSet<T> QSet::operator+(const QSet<T> &other) const
Returns a new QSet that is the union of this set and the
\a other set.
\sa unite(), operator|=(), operator&(), operator-()
*/
/*!
\fn QSet<T> QSet::operator&(const QSet<T> &other) const
Returns a new QSet that is the intersection of this set and the
\a other set.
\sa intersect(), operator&=(), operator|(), operator-()
*/
/*!
\fn QSet<T> QSet::operator-(const QSet<T> &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&()
*/
/*!
\fn QSet<T> QSet::operator-(const QSet<T> &other)
\fn QSet<T> QSet::operator|(const QSet<T> &other)
\fn QSet<T> QSet::operator+(const QSet<T> &other)
\fn QSet<T> QSet::operator&(const QSet<T> &other)
\internal
These will go away in Qt 5.
*/
/*!
\class QSet::iterator
\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<T>::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.
QSet\<T\>::iterator allows you to iterate over a QSet\<T\> and
modify it as you go (using QSet::erase()). However,
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 doc/src/snippets/code/doc_src_qset.qdoc 8
Here's a loop that removes certain items (all those that start
with 'J') from a set while iterating:
\snippet doc/src/snippets/code/doc_src_qset.qdoc 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 doc/src/snippets/code/doc_src_qset.qdoc 10
Multiple iterators can be used on the same set. However, you may
not attempt to modify the container while iterating on it.
\sa QSet::const_iterator, QMutableSetIterator
*/
/*!
\class QSet::const_iterator
\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\<Key, T\>::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 doc/src/snippets/code/doc_src_qset.qdoc 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 doc/src/snippets/code/doc_src_qset.qdoc 12
Multiple iterators can be used on the same set. However, you may
not attempt to modify the container while iterating on it.
\sa QSet::iterator, QSetIterator
*/
/*!
\fn QSet::iterator::iterator()
\fn 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 QSet::iterator::iterator(typename Hash::iterator i)
\fn 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 QSet::iterator::iterator(const iterator &other)
\fn QSet::const_iterator::const_iterator(const const_iterator &other)
Constructs a copy of \a other.
*/
/*!
\fn QSet::const_iterator::const_iterator(const iterator &other)
\since 4.2
\overload
Constructs a copy of \a other.
*/
/*!
\fn QSet::iterator &QSet::iterator::operator=(const iterator &other)
\fn QSet::const_iterator &QSet::const_iterator::operator=(const const_iterator &other)
Assigns \a other to this iterator.
*/
/*!
\fn const T &QSet::iterator::operator*() const
\fn const T &QSet::const_iterator::operator*() const
Returns a reference to the current item.
\sa operator->()
*/
/*!
\fn const T *QSet::iterator::operator->() const
\fn const T *QSet::const_iterator::operator->() const
Returns a pointer to the current item.
\sa operator*()
*/
/*!
\fn bool QSet::iterator::operator==(const iterator &other) const
\fn bool QSet::const_iterator::operator==(const const_iterator &other) const
Returns true if \a other points to the same item as this
iterator; otherwise returns false.
\sa operator!=()
*/
/*!
\fn bool QSet::iterator::operator==(const const_iterator &other) const
\fn bool QSet::iterator::operator!=(const const_iterator &other) const
\overload
*/
/*!
\fn bool QSet::iterator::operator!=(const iterator &other) const
\fn bool QSet::const_iterator::operator!=(const const_iterator &other) const
Returns true if \a other points to a different item than this
iterator; otherwise returns false.
\sa operator==()
*/
/*!
\fn QSet::iterator &QSet::iterator::operator++()
\fn 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 QSet::iterator QSet::iterator::operator++(int)
\fn 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 QSet::iterator &QSet::iterator::operator--()
\fn 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 QSet::iterator QSet::iterator::operator--(int)
\fn 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 QSet::iterator QSet::iterator::operator+(int j) const
\fn 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 QSet::iterator QSet::iterator::operator-(int j) const
\fn 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 QSet::iterator &QSet::iterator::operator+=(int j)
\fn 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 QSet::iterator &QSet::iterator::operator-=(int j)
\fn 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 QList<T> QSet<T>::toList() const
Returns a new QList containing the elements in the set. The
order of the elements in the QList is undefined.
Example:
\snippet doc/src/snippets/code/doc_src_qset.qdoc 13
\sa fromList(), QList::fromSet(), qSort()
*/
/*! \fn QList<T> QSet<T>::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(), qSort()
*/
/*! \fn QSet<T> QSet<T>::fromList(const QList<T> &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 doc/src/snippets/code/doc_src_qset.qdoc 14
\sa toList(), QList::toSet()
*/
/*!
\fn QDataStream &operator<<(QDataStream &out, const QSet<T> &set)
\relates QSet
Writes the \a set to stream \a out.
This function requires the value type to implement \c operator<<().
\sa \link datastreamformat.html Format of the QDataStream operators \endlink
*/
/*!
\fn QDataStream &operator>>(QDataStream &in, QSet<T> &set)
\relates QSet
Reads a set from stream \a in into \a set.
This function requires the value type to implement \c operator>>().
\sa \link datastreamformat.html Format of the QDataStream operators \endlink
*/