1 | // Copyright (C) 2016 The Qt Company Ltd. |
---|---|
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | |
4 | #ifndef QSET_H |
5 | #define QSET_H |
6 | |
7 | #include <QtCore/qhash.h> |
8 | #include <QtCore/qcontainertools_impl.h> |
9 | #include <QtCore/qttypetraits.h> |
10 | |
11 | #include <initializer_list> |
12 | #include <iterator> |
13 | |
14 | QT_BEGIN_NAMESPACE |
15 | |
16 | |
17 | template <class T> |
18 | class QSet |
19 | { |
20 | typedef QHash<T, QHashDummyValue> Hash; |
21 | |
22 | public: |
23 | inline QSet() noexcept {} |
24 | inline QSet(std::initializer_list<T> list) |
25 | : QSet(list.begin(), list.end()) {} |
26 | template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true> |
27 | inline QSet(InputIterator first, InputIterator last) |
28 | { |
29 | QtPrivate::reserveIfForwardIterator(this, first, last); |
30 | for (; first != last; ++first) |
31 | insert(*first); |
32 | } |
33 | |
34 | // compiler-generated copy/move ctor/assignment operators are fine! |
35 | // compiler-generated destructor is fine! |
36 | |
37 | inline void swap(QSet<T> &other) noexcept { q_hash.swap(other.q_hash); } |
38 | |
39 | #ifndef Q_QDOC |
40 | template <typename U = T> |
41 | QTypeTraits::compare_eq_result_container<QSet, U> operator==(const QSet<T> &other) const |
42 | { return q_hash == other.q_hash; } |
43 | template <typename U = T> |
44 | QTypeTraits::compare_eq_result_container<QSet, U> operator!=(const QSet<T> &other) const |
45 | { return q_hash != other.q_hash; } |
46 | #else |
47 | bool operator==(const QSet &other) const; |
48 | bool operator!=(const QSet &other) const; |
49 | #endif |
50 | |
51 | inline qsizetype size() const { return q_hash.size(); } |
52 | |
53 | inline bool isEmpty() const { return q_hash.isEmpty(); } |
54 | |
55 | inline qsizetype capacity() const { return q_hash.capacity(); } |
56 | inline void reserve(qsizetype size); |
57 | inline void squeeze() { q_hash.squeeze(); } |
58 | |
59 | inline void detach() { q_hash.detach(); } |
60 | inline bool isDetached() const { return q_hash.isDetached(); } |
61 | |
62 | inline void clear() { q_hash.clear(); } |
63 | |
64 | bool remove(const T &value) { return q_hash.remove(value); } |
65 | |
66 | template <typename Pred> |
67 | inline qsizetype removeIf(Pred predicate) |
68 | { |
69 | return QtPrivate::qset_erase_if(*this, predicate); |
70 | } |
71 | |
72 | inline bool contains(const T &value) const { return q_hash.contains(value); } |
73 | |
74 | bool contains(const QSet<T> &set) const; |
75 | |
76 | class const_iterator; |
77 | |
78 | class iterator |
79 | { |
80 | typedef QHash<T, QHashDummyValue> Hash; |
81 | typename Hash::iterator i; |
82 | friend class const_iterator; |
83 | friend class QSet<T>; |
84 | |
85 | public: |
86 | typedef std::forward_iterator_tag iterator_category; |
87 | typedef qptrdiff difference_type; |
88 | typedef T value_type; |
89 | typedef const T *pointer; |
90 | typedef const T &reference; |
91 | |
92 | inline iterator() {} |
93 | inline iterator(typename Hash::iterator o) : i(o) {} |
94 | inline iterator(const iterator &o) : i(o.i) {} |
95 | inline iterator &operator=(const iterator &o) { i = o.i; return *this; } |
96 | inline const T &operator*() const { return i.key(); } |
97 | inline const T *operator->() const { return &i.key(); } |
98 | inline bool operator==(const iterator &o) const { return i == o.i; } |
99 | inline bool operator!=(const iterator &o) const { return i != o.i; } |
100 | inline bool operator==(const const_iterator &o) const |
101 | { return i == o.i; } |
102 | inline bool operator!=(const const_iterator &o) const |
103 | { return i != o.i; } |
104 | inline iterator &operator++() { ++i; return *this; } |
105 | inline iterator operator++(int) { iterator r = *this; ++i; return r; } |
106 | }; |
107 | |
108 | class const_iterator |
109 | { |
110 | typedef QHash<T, QHashDummyValue> Hash; |
111 | typename Hash::const_iterator i; |
112 | friend class iterator; |
113 | friend class QSet<T>; |
114 | |
115 | public: |
116 | typedef std::forward_iterator_tag iterator_category; |
117 | typedef qptrdiff difference_type; |
118 | typedef T value_type; |
119 | typedef const T *pointer; |
120 | typedef const T &reference; |
121 | |
122 | inline const_iterator() {} |
123 | inline const_iterator(typename Hash::const_iterator o) : i(o) {} |
124 | inline const_iterator(const const_iterator &o) : i(o.i) {} |
125 | inline const_iterator(const iterator &o) |
126 | : i(o.i) {} |
127 | inline const_iterator &operator=(const const_iterator &o) { i = o.i; return *this; } |
128 | inline const T &operator*() const { return i.key(); } |
129 | inline const T *operator->() const { return &i.key(); } |
130 | inline bool operator==(const const_iterator &o) const { return i == o.i; } |
131 | inline bool operator!=(const const_iterator &o) const { return i != o.i; } |
132 | inline const_iterator &operator++() { ++i; return *this; } |
133 | inline const_iterator operator++(int) { const_iterator r = *this; ++i; return r; } |
134 | }; |
135 | |
136 | // STL style |
137 | inline iterator begin() { return q_hash.begin(); } |
138 | inline const_iterator begin() const noexcept { return q_hash.begin(); } |
139 | inline const_iterator cbegin() const noexcept { return q_hash.begin(); } |
140 | inline const_iterator constBegin() const noexcept { return q_hash.constBegin(); } |
141 | inline iterator end() { return q_hash.end(); } |
142 | inline const_iterator end() const noexcept { return q_hash.end(); } |
143 | inline const_iterator cend() const noexcept { return q_hash.end(); } |
144 | inline const_iterator constEnd() const noexcept { return q_hash.constEnd(); } |
145 | |
146 | iterator erase(const_iterator i) |
147 | { |
148 | Q_ASSERT(i != constEnd()); |
149 | return q_hash.erase(i.i); |
150 | } |
151 | |
152 | // more Qt |
153 | typedef iterator Iterator; |
154 | typedef const_iterator ConstIterator; |
155 | inline qsizetype count() const { return q_hash.size(); } |
156 | inline iterator insert(const T &value) |
157 | { return q_hash.insert(value, QHashDummyValue()); } |
158 | inline iterator insert(T &&value) |
159 | { return q_hash.emplace(std::move(value), QHashDummyValue()); } |
160 | iterator find(const T &value) { return q_hash.find(value); } |
161 | const_iterator find(const T &value) const { return q_hash.find(value); } |
162 | inline const_iterator constFind(const T &value) const { return find(value); } |
163 | QSet<T> &unite(const QSet<T> &other); |
164 | QSet<T> &intersect(const QSet<T> &other); |
165 | bool intersects(const QSet<T> &other) const; |
166 | QSet<T> &subtract(const QSet<T> &other); |
167 | |
168 | // STL compatibility |
169 | typedef T key_type; |
170 | typedef T value_type; |
171 | typedef value_type *pointer; |
172 | typedef const value_type *const_pointer; |
173 | typedef value_type &reference; |
174 | typedef const value_type &const_reference; |
175 | typedef qptrdiff difference_type; |
176 | typedef qsizetype size_type; |
177 | |
178 | inline bool empty() const { return isEmpty(); } |
179 | |
180 | iterator insert(const_iterator, const T &value) { return insert(value); } |
181 | |
182 | // comfort |
183 | inline QSet<T> &operator<<(const T &value) { insert(value); return *this; } |
184 | inline QSet<T> &operator|=(const QSet<T> &other) { unite(other); return *this; } |
185 | inline QSet<T> &operator|=(const T &value) { insert(value); return *this; } |
186 | inline QSet<T> &operator&=(const QSet<T> &other) { intersect(other); return *this; } |
187 | inline QSet<T> &operator&=(const T &value) |
188 | { QSet<T> result; if (contains(value)) result.insert(value); return (*this = result); } |
189 | inline QSet<T> &operator+=(const QSet<T> &other) { unite(other); return *this; } |
190 | inline QSet<T> &operator+=(const T &value) { insert(value); return *this; } |
191 | inline QSet<T> &operator-=(const QSet<T> &other) { subtract(other); return *this; } |
192 | inline QSet<T> &operator-=(const T &value) { remove(value); return *this; } |
193 | |
194 | friend QSet operator|(const QSet &lhs, const QSet &rhs) { return QSet(lhs) |= rhs; } |
195 | friend QSet operator|(QSet &&lhs, const QSet &rhs) { lhs |= rhs; return std::move(lhs); } |
196 | |
197 | friend QSet operator&(const QSet &lhs, const QSet &rhs) { return QSet(lhs) &= rhs; } |
198 | friend QSet operator&(QSet &&lhs, const QSet &rhs) { lhs &= rhs; return std::move(lhs); } |
199 | |
200 | friend QSet operator+(const QSet &lhs, const QSet &rhs) { return QSet(lhs) += rhs; } |
201 | friend QSet operator+(QSet &&lhs, const QSet &rhs) { lhs += rhs; return std::move(lhs); } |
202 | |
203 | friend QSet operator-(const QSet &lhs, const QSet &rhs) { return QSet(lhs) -= rhs; } |
204 | friend QSet operator-(QSet &&lhs, const QSet &rhs) { lhs -= rhs; return std::move(lhs); } |
205 | |
206 | QList<T> values() const; |
207 | |
208 | private: |
209 | static inline QSet intersected_helper(const QSet &lhs, const QSet &rhs); |
210 | |
211 | Hash q_hash; |
212 | }; |
213 | |
214 | template <typename InputIterator, |
215 | typename ValueType = typename std::iterator_traits<InputIterator>::value_type, |
216 | QtPrivate::IfIsInputIterator<InputIterator> = true> |
217 | QSet(InputIterator, InputIterator) -> QSet<ValueType>; |
218 | |
219 | template <typename T> |
220 | size_t qHash(const QSet<T> &key, size_t seed = 0) |
221 | noexcept(noexcept(qHashRangeCommutative(key.begin(), key.end(), seed))) |
222 | { |
223 | return qHashRangeCommutative(key.begin(), key.end(), seed); |
224 | } |
225 | |
226 | // inline function implementations |
227 | |
228 | template <class T> |
229 | Q_INLINE_TEMPLATE void QSet<T>::reserve(qsizetype asize) { q_hash.reserve(asize); } |
230 | |
231 | template <class T> |
232 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::unite(const QSet<T> &other) |
233 | { |
234 | if (!q_hash.isSharedWith(other.q_hash)) { |
235 | for (const T &e : other) |
236 | insert(e); |
237 | } |
238 | return *this; |
239 | } |
240 | |
241 | template <class T> |
242 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::intersect(const QSet<T> &other) |
243 | { |
244 | if (q_hash.isSharedWith(other.q_hash)) { |
245 | // nothing to do |
246 | } else if (isEmpty() || other.isEmpty()) { |
247 | // any set intersected with the empty set is the empty set |
248 | clear(); |
249 | } else if (q_hash.isDetached()) { |
250 | // do it in-place: |
251 | removeIf([&other] (const T &e) { return !other.contains(e); }); |
252 | } else { |
253 | // don't detach *this just to remove some items; create a new set |
254 | *this = intersected_helper(lhs: *this, rhs: other); |
255 | } |
256 | return *this; |
257 | } |
258 | |
259 | template <class T> |
260 | // static |
261 | auto QSet<T>::intersected_helper(const QSet &lhs, const QSet &rhs) -> QSet |
262 | { |
263 | QSet r; |
264 | |
265 | const auto l_size = lhs.size(); |
266 | const auto r_size = rhs.size(); |
267 | r.reserve((std::min)(l_size, r_size)); |
268 | |
269 | // Iterate the smaller of the two sets, but always take from lhs, for |
270 | // consistency with insert(): |
271 | |
272 | if (l_size <= r_size) { |
273 | // lhs is not larger |
274 | for (const auto &e : lhs) { |
275 | if (rhs.contains(e)) |
276 | r.insert(e); |
277 | } |
278 | } else { |
279 | // rhs is smaller |
280 | for (const auto &e : rhs) { |
281 | if (const auto it = lhs.find(e); it != lhs.end()) |
282 | r.insert(*it); |
283 | } |
284 | } |
285 | |
286 | return r; |
287 | } |
288 | |
289 | template <class T> |
290 | Q_INLINE_TEMPLATE bool QSet<T>::intersects(const QSet<T> &other) const |
291 | { |
292 | const bool otherIsBigger = other.size() > size(); |
293 | const QSet &smallestSet = otherIsBigger ? *this : other; |
294 | const QSet &biggestSet = otherIsBigger ? other : *this; |
295 | typename QSet::const_iterator i = smallestSet.cbegin(); |
296 | typename QSet::const_iterator e = smallestSet.cend(); |
297 | |
298 | while (i != e) { |
299 | if (biggestSet.contains(*i)) |
300 | return true; |
301 | ++i; |
302 | } |
303 | |
304 | return false; |
305 | } |
306 | |
307 | template <class T> |
308 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::subtract(const QSet<T> &other) |
309 | { |
310 | if (q_hash.isSharedWith(other.q_hash)) { |
311 | clear(); |
312 | } else { |
313 | for (const auto &e : other) |
314 | remove(value: e); |
315 | } |
316 | return *this; |
317 | } |
318 | |
319 | template <class T> |
320 | Q_INLINE_TEMPLATE bool QSet<T>::contains(const QSet<T> &other) const |
321 | { |
322 | typename QSet<T>::const_iterator i = other.constBegin(); |
323 | while (i != other.constEnd()) { |
324 | if (!contains(*i)) |
325 | return false; |
326 | ++i; |
327 | } |
328 | return true; |
329 | } |
330 | |
331 | template <typename T> |
332 | Q_OUTOFLINE_TEMPLATE QList<T> QSet<T>::values() const |
333 | { |
334 | QList<T> result; |
335 | result.reserve(size()); |
336 | typename QSet<T>::const_iterator i = constBegin(); |
337 | while (i != constEnd()) { |
338 | result.append(*i); |
339 | ++i; |
340 | } |
341 | return result; |
342 | } |
343 | |
344 | Q_DECLARE_SEQUENTIAL_ITERATOR(Set) |
345 | |
346 | #if !defined(QT_NO_JAVA_STYLE_ITERATORS) |
347 | template <typename T> |
348 | class QMutableSetIterator |
349 | { |
350 | typedef typename QSet<T>::iterator iterator; |
351 | QSet<T> *c; |
352 | iterator i, n; |
353 | inline bool item_exists() const { return c->constEnd() != n; } |
354 | |
355 | public: |
356 | inline QMutableSetIterator(QSet<T> &container) |
357 | : c(&container) |
358 | { i = c->begin(); n = c->end(); } |
359 | inline QMutableSetIterator &operator=(QSet<T> &container) |
360 | { c = &container; i = c->begin(); n = c->end(); return *this; } |
361 | inline void toFront() { i = c->begin(); n = c->end(); } |
362 | inline void toBack() { i = c->end(); n = i; } |
363 | inline bool hasNext() const { return c->constEnd() != i; } |
364 | inline const T &next() { n = i++; return *n; } |
365 | inline const T &peekNext() const { return *i; } |
366 | inline void remove() |
367 | { if (c->constEnd() != n) { i = c->erase(n); n = c->end(); } } |
368 | inline const T &value() const { Q_ASSERT(item_exists()); return *n; } |
369 | inline bool findNext(const T &t) |
370 | { while (c->constEnd() != (n = i)) if (*i++ == t) return true; return false; } |
371 | }; |
372 | #endif // QT_NO_JAVA_STYLE_ITERATORS |
373 | |
374 | template <typename T, typename Predicate> |
375 | qsizetype erase_if(QSet<T> &set, Predicate pred) |
376 | { |
377 | return QtPrivate::qset_erase_if(set, pred); |
378 | } |
379 | |
380 | QT_END_NAMESPACE |
381 | |
382 | #endif // QSET_H |
383 |
Definitions
- QSet
- QSet
- QSet
- QSet
- swap
- operator==
- operator!=
- size
- isEmpty
- capacity
- squeeze
- detach
- isDetached
- clear
- remove
- removeIf
- contains
- iterator
- iterator
- iterator
- iterator
- operator=
- operator*
- operator->
- operator==
- operator!=
- operator==
- operator!=
- operator++
- operator++
- const_iterator
- const_iterator
- const_iterator
- const_iterator
- const_iterator
- operator=
- operator*
- operator->
- operator==
- operator!=
- operator++
- operator++
- begin
- begin
- cbegin
- constBegin
- end
- end
- cend
- constEnd
- erase
- count
- insert
- insert
- find
- find
- constFind
- empty
- insert
- operator<<
- operator|=
- operator|=
- operator&=
- operator&=
- operator+=
- operator+=
- operator-=
- operator-=
- operator|
- operator|
- operator&
- operator&
- operator+
- operator+
- operator-
- operator-
- qHash
- reserve
- unite
- intersect
- intersected_helper
- intersects
- subtract
- contains
- values
Start learning QML with our Intro Training
Find out more