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 | inline bool remove(const T &value) { return q_hash.remove(value) != 0; } |
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 | Hash q_hash; |
210 | }; |
211 | |
212 | template <typename InputIterator, |
213 | typename ValueType = typename std::iterator_traits<InputIterator>::value_type, |
214 | QtPrivate::IfIsInputIterator<InputIterator> = true> |
215 | QSet(InputIterator, InputIterator) -> QSet<ValueType>; |
216 | |
217 | template <typename T> |
218 | size_t qHash(const QSet<T> &key, size_t seed = 0) |
219 | noexcept(noexcept(qHashRangeCommutative(key.begin(), key.end(), seed))) |
220 | { |
221 | return qHashRangeCommutative(key.begin(), key.end(), seed); |
222 | } |
223 | |
224 | // inline function implementations |
225 | |
226 | template <class T> |
227 | Q_INLINE_TEMPLATE void QSet<T>::reserve(qsizetype asize) { q_hash.reserve(asize); } |
228 | |
229 | template <class T> |
230 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::unite(const QSet<T> &other) |
231 | { |
232 | if (q_hash.isSharedWith(other.q_hash)) |
233 | return *this; |
234 | QSet<T> tmp = other; |
235 | if (size() < other.size()) |
236 | swap(other&: tmp); |
237 | for (const auto &e : std::as_const(tmp)) |
238 | insert(e); |
239 | return *this; |
240 | } |
241 | |
242 | template <class T> |
243 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::intersect(const QSet<T> &other) |
244 | { |
245 | QSet<T> copy1; |
246 | QSet<T> copy2; |
247 | if (size() <= other.size()) { |
248 | copy1 = *this; |
249 | copy2 = other; |
250 | } else { |
251 | copy1 = other; |
252 | copy2 = *this; |
253 | *this = copy1; |
254 | } |
255 | for (const auto &e : std::as_const(copy1)) { |
256 | if (!copy2.contains(e)) |
257 | remove(value: e); |
258 | } |
259 | return *this; |
260 | } |
261 | |
262 | template <class T> |
263 | Q_INLINE_TEMPLATE bool QSet<T>::intersects(const QSet<T> &other) const |
264 | { |
265 | const bool otherIsBigger = other.size() > size(); |
266 | const QSet &smallestSet = otherIsBigger ? *this : other; |
267 | const QSet &biggestSet = otherIsBigger ? other : *this; |
268 | typename QSet::const_iterator i = smallestSet.cbegin(); |
269 | typename QSet::const_iterator e = smallestSet.cend(); |
270 | |
271 | while (i != e) { |
272 | if (biggestSet.contains(*i)) |
273 | return true; |
274 | ++i; |
275 | } |
276 | |
277 | return false; |
278 | } |
279 | |
280 | template <class T> |
281 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::subtract(const QSet<T> &other) |
282 | { |
283 | if (q_hash.isSharedWith(other.q_hash)) { |
284 | clear(); |
285 | } else { |
286 | for (const auto &e : other) |
287 | remove(value: e); |
288 | } |
289 | return *this; |
290 | } |
291 | |
292 | template <class T> |
293 | Q_INLINE_TEMPLATE bool QSet<T>::contains(const QSet<T> &other) const |
294 | { |
295 | typename QSet<T>::const_iterator i = other.constBegin(); |
296 | while (i != other.constEnd()) { |
297 | if (!contains(*i)) |
298 | return false; |
299 | ++i; |
300 | } |
301 | return true; |
302 | } |
303 | |
304 | template <typename T> |
305 | Q_OUTOFLINE_TEMPLATE QList<T> QSet<T>::values() const |
306 | { |
307 | QList<T> result; |
308 | result.reserve(size()); |
309 | typename QSet<T>::const_iterator i = constBegin(); |
310 | while (i != constEnd()) { |
311 | result.append(*i); |
312 | ++i; |
313 | } |
314 | return result; |
315 | } |
316 | |
317 | Q_DECLARE_SEQUENTIAL_ITERATOR(Set) |
318 | |
319 | #if !defined(QT_NO_JAVA_STYLE_ITERATORS) |
320 | template <typename T> |
321 | class QMutableSetIterator |
322 | { |
323 | typedef typename QSet<T>::iterator iterator; |
324 | QSet<T> *c; |
325 | iterator i, n; |
326 | inline bool item_exists() const { return c->constEnd() != n; } |
327 | |
328 | public: |
329 | inline QMutableSetIterator(QSet<T> &container) |
330 | : c(&container) |
331 | { i = c->begin(); n = c->end(); } |
332 | inline QMutableSetIterator &operator=(QSet<T> &container) |
333 | { c = &container; i = c->begin(); n = c->end(); return *this; } |
334 | inline void toFront() { i = c->begin(); n = c->end(); } |
335 | inline void toBack() { i = c->end(); n = i; } |
336 | inline bool hasNext() const { return c->constEnd() != i; } |
337 | inline const T &next() { n = i++; return *n; } |
338 | inline const T &peekNext() const { return *i; } |
339 | inline void remove() |
340 | { if (c->constEnd() != n) { i = c->erase(n); n = c->end(); } } |
341 | inline const T &value() const { Q_ASSERT(item_exists()); return *n; } |
342 | inline bool findNext(const T &t) |
343 | { while (c->constEnd() != (n = i)) if (*i++ == t) return true; return false; } |
344 | }; |
345 | #endif // QT_NO_JAVA_STYLE_ITERATORS |
346 | |
347 | template <typename T, typename Predicate> |
348 | qsizetype erase_if(QSet<T> &set, Predicate pred) |
349 | { |
350 | return QtPrivate::qset_erase_if(set, pred); |
351 | } |
352 | |
353 | QT_END_NAMESPACE |
354 | |
355 | #endif // QSET_H |
356 |
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
- intersects
- subtract
- contains
- values
Learn to use CMake with our Intro Training
Find out more