Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-08-05 09:27:37 

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