diff options
Diffstat (limited to 'src/corelib/tools/qset.qdoc')
| -rw-r--r-- | src/corelib/tools/qset.qdoc | 946 |
1 files changed, 946 insertions, 0 deletions
diff --git a/src/corelib/tools/qset.qdoc b/src/corelib/tools/qset.qdoc new file mode 100644 index 0000000000..8748fd94bd --- /dev/null +++ b/src/corelib/tools/qset.qdoc @@ -0,0 +1,946 @@ +/**************************************************************************** +** +** Copyright (C) 2011 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:FDL$ +** 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 Free Documentation License +** 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. +** +** 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.cpp 0 + + To insert a value into the set, use insert(): + + \snippet doc/src/snippets/code/doc_src_qset.cpp 1 + + Another way to insert items into the set is to use operator<<(): + + \snippet doc/src/snippets/code/doc_src_qset.cpp 2 + + To test whether an item belongs to the set or not, use contains(): + + \snippet doc/src/snippets/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<QWidget *> using a Java-style iterator: + + \snippet doc/src/snippets/code/doc_src_qset.cpp 4 + + Here's the same code, but using an STL-style iterator: + + \snippet doc/src/snippets/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 doc/src/snippets/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 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 void QSet::swap(QSet<T> &other) + + Swaps set \a other with this set. This operation is very fast and + never fails. +*/ + +/*! + \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.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 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.cpp 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.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 doc/src/snippets/code/doc_src_qset.cpp 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.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 doc/src/snippets/code/doc_src_qset.cpp 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.cpp 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.cpp 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 +*/ |