Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-05-07 08:48:20 

0001 // Copyright (C) 2016 The Qt Company Ltd.
0002 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0003 
0004 #ifndef QSET_H
0005 #define QSET_H
0006 
0007 #include <QtCore/qhash.h>
0008 #include <QtCore/qcontainertools_impl.h>
0009 #include <QtCore/qttypetraits.h>
0010 
0011 #include <initializer_list>
0012 #include <iterator>
0013 
0014 QT_BEGIN_NAMESPACE
0015 
0016 
0017 template <class T>
0018 class QSet
0019 {
0020     typedef QHash<T, QHashDummyValue> Hash;
0021 
0022 public:
0023     inline QSet() noexcept {}
0024     inline QSet(std::initializer_list<T> list)
0025         : QSet(list.begin(), list.end()) {}
0026     template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
0027     inline QSet(InputIterator first, InputIterator last)
0028     {
0029         QtPrivate::reserveIfForwardIterator(this, first, last);
0030         for (; first != last; ++first)
0031             insert(*first);
0032     }
0033 
0034     // compiler-generated copy/move ctor/assignment operators are fine!
0035     // compiler-generated destructor is fine!
0036 
0037     inline void swap(QSet<T> &other) noexcept { q_hash.swap(other.q_hash); }
0038 
0039 #ifndef Q_QDOC
0040 private:
0041     template <typename U = T, QTypeTraits::compare_eq_result_container<QSet, U> = true>
0042     friend bool comparesEqual(const QSet &lhs, const QSet &rhs) noexcept
0043     {
0044         return lhs.q_hash == rhs.q_hash;
0045     }
0046     QT_DECLARE_EQUALITY_OPERATORS_HELPER(QSet, QSet, /* non-constexpr */, noexcept,
0047             template <typename U = T, QTypeTraits::compare_eq_result_container<QSet, U> = true>)
0048 public:
0049 #else
0050     friend bool operator==(const QSet &lhs, const QSet &rhs) noexcept;
0051     friend bool operator!=(const QSet &lhs, const QSet &rhs) noexcept;
0052 #endif
0053 
0054     inline qsizetype size() const { return q_hash.size(); }
0055 
0056     inline bool isEmpty() const { return q_hash.isEmpty(); }
0057 
0058     inline qsizetype capacity() const { return q_hash.capacity(); }
0059     inline void reserve(qsizetype size);
0060     inline void squeeze() { q_hash.squeeze(); }
0061 
0062     inline void detach() { q_hash.detach(); }
0063     inline bool isDetached() const { return q_hash.isDetached(); }
0064 
0065     inline void clear() { q_hash.clear(); }
0066 
0067     bool remove(const T &value) { return q_hash.remove(value); }
0068 
0069     template <typename Pred>
0070     inline qsizetype removeIf(Pred predicate)
0071     {
0072         return QtPrivate::qset_erase_if(*this, predicate);
0073     }
0074 
0075     inline bool contains(const T &value) const { return q_hash.contains(value); }
0076 
0077     bool contains(const QSet<T> &set) const;
0078 
0079     class const_iterator;
0080 
0081     class iterator
0082     {
0083         typedef QHash<T, QHashDummyValue> Hash;
0084         typename Hash::iterator i;
0085         friend class const_iterator;
0086         friend class QSet<T>;
0087 
0088     public:
0089         typedef std::forward_iterator_tag iterator_category;
0090         typedef qptrdiff difference_type;
0091         typedef T value_type;
0092         typedef const T *pointer;
0093         typedef const T &reference;
0094 
0095         inline iterator() {}
0096         inline iterator(typename Hash::iterator o) : i(o) {}
0097         inline iterator(const iterator &o) : i(o.i) {}
0098         inline iterator &operator=(const iterator &o) { i = o.i; return *this; }
0099         inline const T &operator*() const { return i.key(); }
0100         inline const T *operator->() const { return &i.key(); }
0101         inline bool operator==(const iterator &o) const { return i == o.i; }
0102         inline bool operator!=(const iterator &o) const { return i != o.i; }
0103         inline bool operator==(const const_iterator &o) const
0104             { return i == o.i; }
0105         inline bool operator!=(const const_iterator &o) const
0106             { return i != o.i; }
0107         inline iterator &operator++() { ++i; return *this; }
0108         inline iterator operator++(int) { iterator r = *this; ++i; return r; }
0109     };
0110 
0111     class const_iterator
0112     {
0113         typedef QHash<T, QHashDummyValue> Hash;
0114         typename Hash::const_iterator i;
0115         friend class iterator;
0116         friend class QSet<T>;
0117 
0118     public:
0119         typedef std::forward_iterator_tag iterator_category;
0120         typedef qptrdiff difference_type;
0121         typedef T value_type;
0122         typedef const T *pointer;
0123         typedef const T &reference;
0124 
0125         inline const_iterator() {}
0126         inline const_iterator(typename Hash::const_iterator o) : i(o) {}
0127         inline const_iterator(const const_iterator &o) : i(o.i) {}
0128         inline const_iterator(const iterator &o)
0129             : i(o.i) {}
0130         inline const_iterator &operator=(const const_iterator &o) { i = o.i; return *this; }
0131         inline const T &operator*() const { return i.key(); }
0132         inline const T *operator->() const { return &i.key(); }
0133         inline bool operator==(const const_iterator &o) const { return i == o.i; }
0134         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
0135         inline const_iterator &operator++() { ++i; return *this; }
0136         inline const_iterator operator++(int) { const_iterator r = *this; ++i; return r; }
0137     };
0138 
0139     // STL style
0140     inline iterator begin() { return q_hash.begin(); }
0141     inline const_iterator begin() const noexcept { return q_hash.begin(); }
0142     inline const_iterator cbegin() const noexcept { return q_hash.begin(); }
0143     inline const_iterator constBegin() const noexcept { return q_hash.constBegin(); }
0144     inline iterator end() { return q_hash.end(); }
0145     inline const_iterator end() const noexcept { return q_hash.end(); }
0146     inline const_iterator cend() const noexcept { return q_hash.end(); }
0147     inline const_iterator constEnd() const noexcept { return q_hash.constEnd(); }
0148 
0149     iterator erase(const_iterator i)
0150     {
0151         Q_ASSERT(i != constEnd());
0152         return q_hash.erase(i.i);
0153     }
0154 
0155     // more Qt
0156     typedef iterator Iterator;
0157     typedef const_iterator ConstIterator;
0158     inline qsizetype count() const { return q_hash.size(); }
0159     inline iterator insert(const T &value)
0160         { return q_hash.insert(value, QHashDummyValue()); }
0161     inline iterator insert(T &&value)
0162         { return q_hash.emplace(std::move(value), QHashDummyValue()); }
0163     iterator find(const T &value) { return q_hash.find(value); }
0164     const_iterator find(const T &value) const { return q_hash.find(value); }
0165     inline const_iterator constFind(const T &value) const { return find(value); }
0166     QSet<T> &unite(const QSet<T> &other);
0167     QSet &unite(QSet &&other);
0168     QSet<T> &intersect(const QSet<T> &other);
0169     bool intersects(const QSet<T> &other) const;
0170     QSet<T> &subtract(const QSet<T> &other);
0171 
0172     // STL compatibility
0173     typedef T key_type;
0174     typedef T value_type;
0175     typedef value_type *pointer;
0176     typedef const value_type *const_pointer;
0177     typedef value_type &reference;
0178     typedef const value_type &const_reference;
0179     typedef qptrdiff difference_type;
0180     typedef qsizetype size_type;
0181 
0182     inline bool empty() const { return isEmpty(); }
0183 
0184     iterator insert(const_iterator, const T &value) { return insert(value); }
0185 
0186     // comfort
0187     inline QSet<T> &operator<<(const T &value) { insert(value); return *this; }
0188     inline QSet<T> &operator|=(const QSet<T> &other) { unite(other); return *this; }
0189     QSet &operator|=(QSet &&other) { return unite(std::move(other)); }
0190     inline QSet<T> &operator|=(const T &value) { insert(value); return *this; }
0191     inline QSet<T> &operator&=(const QSet<T> &other) { intersect(other); return *this; }
0192     inline QSet<T> &operator&=(const T &value)
0193         { QSet<T> result; if (contains(value)) result.insert(value); return (*this = result); }
0194     inline QSet<T> &operator+=(const QSet<T> &other) { unite(other); return *this; }
0195     QSet &operator+=(QSet &&other) { return unite(std::move(other)); }
0196     inline QSet<T> &operator+=(const T &value) { insert(value); return *this; }
0197     inline QSet<T> &operator-=(const QSet<T> &other) { subtract(other); return *this; }
0198     inline QSet<T> &operator-=(const T &value) { remove(value); return *this; }
0199 
0200     friend QSet operator|(const QSet &lhs, const QSet &rhs) { return QSet(lhs) |= rhs; }
0201     friend QSet operator|(QSet &&lhs, const QSet &rhs) { lhs |= rhs; return std::move(lhs); }
0202     friend QSet operator|(const QSet &lhs, QSet &&rhs) { return lhs |= std::move(rhs); }
0203     friend QSet operator|(QSet &&lhs, QSet &&rhs) { return std::move(lhs) |= std::move(rhs); }
0204 
0205     friend QSet operator&(const QSet &lhs, const QSet &rhs) { return QSet(lhs) &= rhs; }
0206     friend QSet operator&(QSet &&lhs, const QSet &rhs) { lhs &= rhs; return std::move(lhs); }
0207 
0208     friend QSet operator+(const QSet &lhs, const QSet &rhs) { return QSet(lhs) += rhs; }
0209     friend QSet operator+(QSet &&lhs, const QSet &rhs) { lhs += rhs; return std::move(lhs); }
0210     friend QSet operator+(const QSet &lhs, QSet &&rhs) { return QSet(lhs) += std::move(rhs); }
0211     friend QSet operator+(QSet &&lhs, QSet &&rhs) { return std::move(lhs) += std::move(rhs); }
0212 
0213     friend QSet operator-(const QSet &lhs, const QSet &rhs) { return QSet(lhs) -= rhs; }
0214     friend QSet operator-(QSet &&lhs, const QSet &rhs) { lhs -= rhs; return std::move(lhs); }
0215 
0216     inline QList<T> values() const;
0217 
0218 private:
0219     static inline QSet intersected_helper(const QSet &lhs, const QSet &rhs);
0220 
0221     template <typename E>
0222     void _emplace_or_overwrite(E &&e);
0223 
0224     Hash q_hash;
0225 };
0226 
0227 template <typename InputIterator,
0228           typename ValueType = typename std::iterator_traits<InputIterator>::value_type,
0229           QtPrivate::IfIsInputIterator<InputIterator> = true>
0230 QSet(InputIterator, InputIterator) -> QSet<ValueType>;
0231 
0232 template <typename T>
0233 size_t qHash(const QSet<T> &key, size_t seed = 0)
0234 noexcept(noexcept(qHashRangeCommutative(key.begin(), key.end(), seed)))
0235 {
0236     return qHashRangeCommutative(key.begin(), key.end(), seed);
0237 }
0238 
0239 // inline function implementations
0240 
0241 template <class T>
0242 Q_INLINE_TEMPLATE void QSet<T>::reserve(qsizetype asize) { q_hash.reserve(asize); }
0243 
0244 template <class T>
0245 Q_INLINE_TEMPLATE QSet<T> &QSet<T>::unite(const QSet<T> &other)
0246 {
0247     if (!q_hash.isSharedWith(other.q_hash)) {
0248         for (const T &e : other)
0249             insert(e);
0250     }
0251     return *this;
0252 }
0253 
0254 template <class T>
0255 Q_INLINE_TEMPLATE auto QSet<T>::unite(QSet &&other) -> QSet&
0256 {
0257     if (other.isDetached() && size() < other.size()) {
0258 
0259         // We can change the state of `other`, so take the smaller *this and
0260         // insert it into the larger `other`, making sure we take equivalent
0261         // elements from *this:
0262 
0263         swap(other);
0264 
0265         // Now: iterate over `other`, insert into *this, making sure we take
0266         //      equivalent elements from `other`:
0267 
0268         if (other.isDetached()) { // can move elements from `other`
0269             for (auto &e : other)
0270                 _emplace_or_overwrite(std::move(e));
0271         } else { // need to copy elements from `other`
0272             for (const auto &e : std::as_const(other))
0273                 _emplace_or_overwrite(e);
0274         }
0275 
0276         return *this;
0277     }
0278 
0279     // in all other cases, the lvalue overload is not worse:
0280     return unite(other);
0281 }
0282 
0283 template <class T>
0284 template <typename E>
0285 Q_INLINE_TEMPLATE void QSet<T>::_emplace_or_overwrite(E &&e)
0286 {
0287     const auto r = q_hash.tryEmplace(std::forward<E>(e));
0288     if (!r.inserted) {
0289         // QHash never overwrites the key, but that's what we need
0290         // here, so do it using private QHash API:
0291         // NB: `e` was _not_ moved from by tryEmplace()!
0292         typename Hash::Data::Bucket(r.iterator.i).node()->key = std::forward<E>(e);
0293     }
0294 }
0295 
0296 template <class T>
0297 Q_INLINE_TEMPLATE QSet<T> &QSet<T>::intersect(const QSet<T> &other)
0298 {
0299     if (q_hash.isSharedWith(other.q_hash)) {
0300         // nothing to do
0301     } else if (isEmpty() || other.isEmpty()) {
0302         // any set intersected with the empty set is the empty set
0303         clear();
0304     } else if (q_hash.isDetached()) {
0305         // do it in-place:
0306         removeIf([&other] (const T &e) { return !other.contains(e); });
0307     } else {
0308         // don't detach *this just to remove some items; create a new set
0309         *this = intersected_helper(*this, other);
0310     }
0311     return *this;
0312 }
0313 
0314 template <class T>
0315 // static
0316 auto QSet<T>::intersected_helper(const QSet &lhs, const QSet &rhs) -> QSet
0317 {
0318     QSet r;
0319 
0320     const auto l_size = lhs.size();
0321     const auto r_size = rhs.size();
0322     r.reserve((std::min)(l_size, r_size));
0323 
0324     // Iterate the smaller of the two sets, but always take from lhs, for
0325     // consistency with insert():
0326 
0327     if (l_size <= r_size) {
0328         // lhs is not larger
0329         for (const auto &e : lhs) {
0330             if (rhs.contains(e))
0331                 r.insert(e);
0332         }
0333     } else {
0334         // rhs is smaller
0335         for (const auto &e : rhs) {
0336             if (const auto it = lhs.find(e); it != lhs.end())
0337                 r.insert(*it);
0338         }
0339     }
0340 
0341     return r;
0342 }
0343 
0344 template <class T>
0345 Q_INLINE_TEMPLATE bool QSet<T>::intersects(const QSet<T> &other) const
0346 {
0347     const bool otherIsBigger = other.size() > size();
0348     const QSet &smallestSet = otherIsBigger ? *this : other;
0349     const QSet &biggestSet = otherIsBigger ? other : *this;
0350     typename QSet::const_iterator i = smallestSet.cbegin();
0351     typename QSet::const_iterator e = smallestSet.cend();
0352 
0353     while (i != e) {
0354         if (biggestSet.contains(*i))
0355             return true;
0356         ++i;
0357     }
0358 
0359     return false;
0360 }
0361 
0362 template <class T>
0363 Q_INLINE_TEMPLATE QSet<T> &QSet<T>::subtract(const QSet<T> &other)
0364 {
0365     if (q_hash.isSharedWith(other.q_hash)) {
0366         clear();
0367     } else {
0368         for (const auto &e : other)
0369             remove(e);
0370     }
0371     return *this;
0372 }
0373 
0374 template <class T>
0375 Q_INLINE_TEMPLATE bool QSet<T>::contains(const QSet<T> &other) const
0376 {
0377     typename QSet<T>::const_iterator i = other.constBegin();
0378     while (i != other.constEnd()) {
0379         if (!contains(*i))
0380             return false;
0381         ++i;
0382     }
0383     return true;
0384 }
0385 
0386 template <typename T>
0387 QList<T> QSet<T>::values() const
0388 {
0389     QList<T> result;
0390     result.reserve(size());
0391     typename QSet<T>::const_iterator i = constBegin();
0392     while (i != constEnd()) {
0393         result.append(*i);
0394         ++i;
0395     }
0396     return result;
0397 }
0398 
0399 Q_DECLARE_SEQUENTIAL_ITERATOR(Set)
0400 
0401 #if !defined(QT_NO_JAVA_STYLE_ITERATORS)
0402 template <typename T>
0403 class QMutableSetIterator
0404 {
0405     typedef typename QSet<T>::iterator iterator;
0406     QSet<T> *c;
0407     iterator i, n;
0408     inline bool item_exists() const { return c->constEnd() != n; }
0409 
0410 public:
0411     inline QMutableSetIterator(QSet<T> &container)
0412         : c(&container)
0413     { i = c->begin(); n = c->end(); }
0414     inline QMutableSetIterator &operator=(QSet<T> &container)
0415     { c = &container; i = c->begin(); n = c->end(); return *this; }
0416     inline void toFront() { i = c->begin(); n = c->end(); }
0417     inline void toBack() { i = c->end(); n = i; }
0418     inline bool hasNext() const { return c->constEnd() != i; }
0419     inline const T &next() { n = i++; return *n; }
0420     inline const T &peekNext() const { return *i; }
0421     inline void remove()
0422     { if (c->constEnd() != n) { i = c->erase(n); n = c->end(); } }
0423     inline const T &value() const { Q_ASSERT(item_exists()); return *n; }
0424     inline bool findNext(const T &t)
0425     { while (c->constEnd() != (n = i)) if (*i++ == t) return true; return false; }
0426 };
0427 #endif // QT_NO_JAVA_STYLE_ITERATORS
0428 
0429 template <typename T, typename Predicate>
0430 qsizetype erase_if(QSet<T> &set, Predicate pred)
0431 {
0432     return QtPrivate::qset_erase_if(set, pred);
0433 }
0434 
0435 QT_END_NAMESPACE
0436 
0437 #endif // QSET_H
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!