1 //
2 // Copyright 2018 The ANGLE Project Authors. All rights reserved.
3 // Use of this source code is governed by a BSD-style license that can be
4 // found in the LICENSE file.
5 //
6 // FastVector.h:
7 // A vector class with a initial fixed size and variable growth.
8 // Based on FixedVector.
9 //
10
11 #ifndef COMMON_FASTVECTOR_H_
12 #define COMMON_FASTVECTOR_H_
13
14 #include "bitset_utils.h"
15 #include "common/debug.h"
16
17 #include <algorithm>
18 #include <array>
19 #include <initializer_list>
20 #include <iterator>
21
22 namespace angle
23 {
24
25 template <class Iter>
26 class WrapIter
27 {
28 public:
29 typedef Iter iterator_type;
30 typedef typename std::iterator_traits<iterator_type>::value_type value_type;
31 typedef typename std::iterator_traits<iterator_type>::difference_type difference_type;
32 typedef typename std::iterator_traits<iterator_type>::pointer pointer;
33 typedef typename std::iterator_traits<iterator_type>::reference reference;
34 typedef typename std::iterator_traits<iterator_type>::iterator_category iterator_category;
35
WrapIter()36 WrapIter() : mIter() {}
37 WrapIter(const WrapIter &x) = default;
38 WrapIter &operator=(const WrapIter &x) = default;
WrapIter(const Iter & iter)39 WrapIter(const Iter &iter) : mIter(iter) {}
40 ~WrapIter() = default;
41
42 bool operator==(const WrapIter &x) const { return mIter == x.mIter; }
43 bool operator!=(const WrapIter &x) const { return mIter != x.mIter; }
44 bool operator<(const WrapIter &x) const { return mIter < x.mIter; }
45 bool operator<=(const WrapIter &x) const { return mIter <= x.mIter; }
46 bool operator>(const WrapIter &x) const { return mIter > x.mIter; }
47 bool operator>=(const WrapIter &x) const { return mIter >= x.mIter; }
48
49 WrapIter &operator++()
50 {
51 mIter++;
52 return *this;
53 }
54
55 WrapIter operator++(int)
56 {
57 WrapIter tmp(mIter);
58 mIter++;
59 return tmp;
60 }
61
62 WrapIter operator+(difference_type n)
63 {
64 WrapIter tmp(mIter);
65 tmp.mIter += n;
66 return tmp;
67 }
68
69 WrapIter operator-(difference_type n)
70 {
71 WrapIter tmp(mIter);
72 tmp.mIter -= n;
73 return tmp;
74 }
75
76 difference_type operator-(const WrapIter &x) const { return mIter - x.mIter; }
77
78 iterator_type operator->() const { return mIter; }
79
80 reference operator*() const { return *mIter; }
81
82 private:
83 iterator_type mIter;
84 };
85
86 template <class T, size_t N, class Storage = std::array<T, N>>
87 class FastVector final
88 {
89 public:
90 using value_type = typename Storage::value_type;
91 using size_type = typename Storage::size_type;
92 using reference = typename Storage::reference;
93 using const_reference = typename Storage::const_reference;
94 using pointer = typename Storage::pointer;
95 using const_pointer = typename Storage::const_pointer;
96 using iterator = WrapIter<T *>;
97 using const_iterator = WrapIter<const T *>;
98
99 // This class does not call destructors when resizing down (for performance reasons).
100 static_assert(std::is_trivially_destructible_v<value_type>);
101
102 FastVector();
103 FastVector(size_type count, const value_type &value);
104 FastVector(size_type count);
105
106 FastVector(const FastVector<T, N, Storage> &other);
107 FastVector(FastVector<T, N, Storage> &&other);
108 FastVector(std::initializer_list<value_type> init);
109
110 template <class InputIt, std::enable_if_t<!std::is_integral<InputIt>::value, bool> = true>
111 FastVector(InputIt first, InputIt last);
112
113 FastVector<T, N, Storage> &operator=(const FastVector<T, N, Storage> &other);
114 FastVector<T, N, Storage> &operator=(FastVector<T, N, Storage> &&other);
115 FastVector<T, N, Storage> &operator=(std::initializer_list<value_type> init);
116
117 ~FastVector();
118
119 reference at(size_type pos);
120 const_reference at(size_type pos) const;
121
122 reference operator[](size_type pos);
123 const_reference operator[](size_type pos) const;
124
125 pointer data();
126 const_pointer data() const;
127
128 iterator begin();
129 const_iterator begin() const;
130
131 iterator end();
132 const_iterator end() const;
133
134 bool empty() const;
135 size_type size() const;
136
137 void clear();
138
139 void push_back(const value_type &value);
140 void push_back(value_type &&value);
141
142 template <typename... Args>
143 void emplace_back(Args &&...args);
144
145 void pop_back();
146
147 reference front();
148 const_reference front() const;
149
150 reference back();
151 const_reference back() const;
152
153 void swap(FastVector<T, N, Storage> &other);
154
155 void resize(size_type count);
156 void resize(size_type count, const value_type &value);
157
158 // Only for use with non trivially constructible types.
159 // When increasing size, new elements may have previous values. Use with caution in cases when
160 // initialization of new elements is not required (will be explicitly initialized later), or
161 // is never resizing down (not possible to reuse previous values).
162 void resize_maybe_value_reuse(size_type count);
163 // Only for use with non trivially constructible types.
164 // No new elements added, so this function is safe to use. Generates ASSERT() if try resize up.
165 void resize_down(size_type count);
166
167 void reserve(size_type count);
168
169 // Specialty function that removes a known element and might shuffle the list.
170 void remove_and_permute(const value_type &element);
171 void remove_and_permute(iterator pos);
172
173 private:
174 void assign_from_initializer_list(std::initializer_list<value_type> init);
175 void ensure_capacity(size_t capacity);
176 bool uses_fixed_storage() const;
177 void resize_impl(size_type count);
178
179 Storage mFixedStorage;
180 pointer mData = mFixedStorage.data();
181 size_type mSize = 0;
182 size_type mReservedSize = N;
183 };
184
185 template <class T, size_t N, class StorageN, size_t M, class StorageM>
186 bool operator==(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
187 {
188 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
189 }
190
191 template <class T, size_t N, class StorageN, size_t M, class StorageM>
192 bool operator!=(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
193 {
194 return !(a == b);
195 }
196
197 template <class T, size_t N, class Storage>
uses_fixed_storage()198 ANGLE_INLINE bool FastVector<T, N, Storage>::uses_fixed_storage() const
199 {
200 return mData == mFixedStorage.data();
201 }
202
203 template <class T, size_t N, class Storage>
FastVector()204 FastVector<T, N, Storage>::FastVector()
205 {}
206
207 template <class T, size_t N, class Storage>
FastVector(size_type count,const value_type & value)208 FastVector<T, N, Storage>::FastVector(size_type count, const value_type &value)
209 {
210 ensure_capacity(count);
211 mSize = count;
212 std::fill(begin(), end(), value);
213 }
214
215 template <class T, size_t N, class Storage>
FastVector(size_type count)216 FastVector<T, N, Storage>::FastVector(size_type count)
217 {
218 ensure_capacity(count);
219 mSize = count;
220 }
221
222 template <class T, size_t N, class Storage>
FastVector(const FastVector<T,N,Storage> & other)223 FastVector<T, N, Storage>::FastVector(const FastVector<T, N, Storage> &other)
224 : FastVector(other.begin(), other.end())
225 {}
226
227 template <class T, size_t N, class Storage>
FastVector(FastVector<T,N,Storage> && other)228 FastVector<T, N, Storage>::FastVector(FastVector<T, N, Storage> &&other) : FastVector()
229 {
230 swap(other);
231 }
232
233 template <class T, size_t N, class Storage>
FastVector(std::initializer_list<value_type> init)234 FastVector<T, N, Storage>::FastVector(std::initializer_list<value_type> init)
235 {
236 assign_from_initializer_list(init);
237 }
238
239 template <class T, size_t N, class Storage>
240 template <class InputIt, std::enable_if_t<!std::is_integral<InputIt>::value, bool>>
FastVector(InputIt first,InputIt last)241 FastVector<T, N, Storage>::FastVector(InputIt first, InputIt last)
242 {
243 size_t newSize = last - first;
244 ensure_capacity(newSize);
245 mSize = newSize;
246 std::copy(first, last, begin());
247 }
248
249 template <class T, size_t N, class Storage>
250 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
251 const FastVector<T, N, Storage> &other)
252 {
253 ensure_capacity(other.mSize);
254 mSize = other.mSize;
255 std::copy(other.begin(), other.end(), begin());
256 return *this;
257 }
258
259 template <class T, size_t N, class Storage>
260 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(FastVector<T, N, Storage> &&other)
261 {
262 swap(other);
263 return *this;
264 }
265
266 template <class T, size_t N, class Storage>
267 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
268 std::initializer_list<value_type> init)
269 {
270 assign_from_initializer_list(init);
271 return *this;
272 }
273
274 template <class T, size_t N, class Storage>
~FastVector()275 FastVector<T, N, Storage>::~FastVector()
276 {
277 clear();
278 if (!uses_fixed_storage())
279 {
280 delete[] mData;
281 }
282 }
283
284 template <class T, size_t N, class Storage>
at(size_type pos)285 typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::at(size_type pos)
286 {
287 ASSERT(pos < mSize);
288 return mData[pos];
289 }
290
291 template <class T, size_t N, class Storage>
at(size_type pos)292 typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::at(
293 size_type pos) const
294 {
295 ASSERT(pos < mSize);
296 return mData[pos];
297 }
298
299 template <class T, size_t N, class Storage>
300 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::operator[](
301 size_type pos)
302 {
303 ASSERT(pos < mSize);
304 return mData[pos];
305 }
306
307 template <class T, size_t N, class Storage>
308 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference
309 FastVector<T, N, Storage>::operator[](size_type pos) const
310 {
311 ASSERT(pos < mSize);
312 return mData[pos];
313 }
314
315 template <class T, size_t N, class Storage>
316 ANGLE_INLINE typename FastVector<T, N, Storage>::const_pointer
data()317 angle::FastVector<T, N, Storage>::data() const
318 {
319 return mData;
320 }
321
322 template <class T, size_t N, class Storage>
data()323 ANGLE_INLINE typename FastVector<T, N, Storage>::pointer angle::FastVector<T, N, Storage>::data()
324 {
325 return mData;
326 }
327
328 template <class T, size_t N, class Storage>
begin()329 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::begin()
330 {
331 return mData;
332 }
333
334 template <class T, size_t N, class Storage>
begin()335 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::begin()
336 const
337 {
338 return mData;
339 }
340
341 template <class T, size_t N, class Storage>
end()342 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::end()
343 {
344 return mData + mSize;
345 }
346
347 template <class T, size_t N, class Storage>
end()348 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::end()
349 const
350 {
351 return mData + mSize;
352 }
353
354 template <class T, size_t N, class Storage>
empty()355 ANGLE_INLINE bool FastVector<T, N, Storage>::empty() const
356 {
357 return mSize == 0;
358 }
359
360 template <class T, size_t N, class Storage>
size()361 ANGLE_INLINE typename FastVector<T, N, Storage>::size_type FastVector<T, N, Storage>::size() const
362 {
363 return mSize;
364 }
365
366 template <class T, size_t N, class Storage>
clear()367 void FastVector<T, N, Storage>::clear()
368 {
369 resize_impl(0);
370 }
371
372 template <class T, size_t N, class Storage>
push_back(const value_type & value)373 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(const value_type &value)
374 {
375 if (mSize == mReservedSize)
376 ensure_capacity(mSize + 1);
377 mData[mSize++] = value;
378 }
379
380 template <class T, size_t N, class Storage>
push_back(value_type && value)381 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(value_type &&value)
382 {
383 emplace_back(std::move(value));
384 }
385
386 template <class T, size_t N, class Storage>
387 template <typename... Args>
emplace_back(Args &&...args)388 ANGLE_INLINE void FastVector<T, N, Storage>::emplace_back(Args &&...args)
389 {
390 if (mSize == mReservedSize)
391 ensure_capacity(mSize + 1);
392 mData[mSize++] = std::move(T(std::forward<Args>(args)...));
393 }
394
395 template <class T, size_t N, class Storage>
pop_back()396 ANGLE_INLINE void FastVector<T, N, Storage>::pop_back()
397 {
398 ASSERT(mSize > 0);
399 mSize--;
400 }
401
402 template <class T, size_t N, class Storage>
front()403 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::front()
404 {
405 ASSERT(mSize > 0);
406 return mData[0];
407 }
408
409 template <class T, size_t N, class Storage>
front()410 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::front()
411 const
412 {
413 ASSERT(mSize > 0);
414 return mData[0];
415 }
416
417 template <class T, size_t N, class Storage>
back()418 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::back()
419 {
420 ASSERT(mSize > 0);
421 return mData[mSize - 1];
422 }
423
424 template <class T, size_t N, class Storage>
back()425 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::back()
426 const
427 {
428 ASSERT(mSize > 0);
429 return mData[mSize - 1];
430 }
431
432 template <class T, size_t N, class Storage>
swap(FastVector<T,N,Storage> & other)433 void FastVector<T, N, Storage>::swap(FastVector<T, N, Storage> &other)
434 {
435 std::swap(mSize, other.mSize);
436
437 pointer tempData = other.mData;
438 if (uses_fixed_storage())
439 other.mData = other.mFixedStorage.data();
440 else
441 other.mData = mData;
442 if (tempData == other.mFixedStorage.data())
443 mData = mFixedStorage.data();
444 else
445 mData = tempData;
446 std::swap(mReservedSize, other.mReservedSize);
447
448 if (uses_fixed_storage() || other.uses_fixed_storage())
449 std::swap(mFixedStorage, other.mFixedStorage);
450 }
451
452 template <class T, size_t N, class Storage>
resize(size_type count)453 ANGLE_INLINE void FastVector<T, N, Storage>::resize(size_type count)
454 {
455 // Trivially constructible types will have undefined values when created therefore reusing
456 // previous values after resize should not be a problem..
457 static_assert(std::is_trivially_constructible_v<value_type>,
458 "For non trivially constructible types please use: resize(count, value), "
459 "resize_maybe_value_reuse(count), or resize_down(count) methods.");
460 resize_impl(count);
461 }
462
463 template <class T, size_t N, class Storage>
resize_maybe_value_reuse(size_type count)464 ANGLE_INLINE void FastVector<T, N, Storage>::resize_maybe_value_reuse(size_type count)
465 {
466 static_assert(!std::is_trivially_constructible_v<value_type>,
467 "This is a special method for non trivially constructible types. "
468 "Please use regular resize(count) method.");
469 resize_impl(count);
470 }
471
472 template <class T, size_t N, class Storage>
resize_down(size_type count)473 ANGLE_INLINE void FastVector<T, N, Storage>::resize_down(size_type count)
474 {
475 static_assert(!std::is_trivially_constructible_v<value_type>,
476 "This is a special method for non trivially constructible types. "
477 "Please use regular resize(count) method.");
478 ASSERT(count <= mSize);
479 resize_impl(count);
480 }
481
482 template <class T, size_t N, class Storage>
resize_impl(size_type count)483 void FastVector<T, N, Storage>::resize_impl(size_type count)
484 {
485 if (count > mSize)
486 {
487 ensure_capacity(count);
488 }
489 mSize = count;
490 }
491
492 template <class T, size_t N, class Storage>
resize(size_type count,const value_type & value)493 void FastVector<T, N, Storage>::resize(size_type count, const value_type &value)
494 {
495 if (count > mSize)
496 {
497 ensure_capacity(count);
498 std::fill(mData + mSize, mData + count, value);
499 }
500 mSize = count;
501 }
502
503 template <class T, size_t N, class Storage>
reserve(size_type count)504 void FastVector<T, N, Storage>::reserve(size_type count)
505 {
506 ensure_capacity(count);
507 }
508
509 template <class T, size_t N, class Storage>
assign_from_initializer_list(std::initializer_list<value_type> init)510 void FastVector<T, N, Storage>::assign_from_initializer_list(std::initializer_list<value_type> init)
511 {
512 ensure_capacity(init.size());
513 mSize = init.size();
514 size_t index = 0;
515 for (auto &value : init)
516 {
517 mData[index++] = value;
518 }
519 }
520
521 template <class T, size_t N, class Storage>
remove_and_permute(const value_type & element)522 ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(const value_type &element)
523 {
524 size_t len = mSize - 1;
525 for (size_t index = 0; index < len; ++index)
526 {
527 if (mData[index] == element)
528 {
529 mData[index] = std::move(mData[len]);
530 break;
531 }
532 }
533 pop_back();
534 }
535
536 template <class T, size_t N, class Storage>
remove_and_permute(iterator pos)537 ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(iterator pos)
538 {
539 ASSERT(pos >= begin());
540 ASSERT(pos < end());
541 size_t len = mSize - 1;
542 *pos = std::move(mData[len]);
543 pop_back();
544 }
545
546 template <class T, size_t N, class Storage>
ensure_capacity(size_t capacity)547 void FastVector<T, N, Storage>::ensure_capacity(size_t capacity)
548 {
549 // We have a minimum capacity of N.
550 if (mReservedSize < capacity)
551 {
552 ASSERT(capacity > N);
553 size_type newSize = std::max(mReservedSize, N);
554 while (newSize < capacity)
555 {
556 newSize *= 2;
557 }
558
559 pointer newData = new value_type[newSize];
560
561 if (mSize > 0)
562 {
563 std::move(begin(), end(), newData);
564 }
565
566 if (!uses_fixed_storage())
567 {
568 delete[] mData;
569 }
570
571 mData = newData;
572 mReservedSize = newSize;
573 }
574 }
575
576 template <class Value, size_t N, class Storage = FastVector<Value, N>>
577 class FastMap final
578 {
579 public:
580 using value_type = typename Storage::value_type;
581 using size_type = typename Storage::size_type;
582 using reference = typename Storage::reference;
583 using const_reference = typename Storage::const_reference;
584 using pointer = typename Storage::pointer;
585 using const_pointer = typename Storage::const_pointer;
586 using iterator = typename Storage::iterator;
587 using const_iterator = typename Storage::const_iterator;
588
FastMap()589 FastMap() {}
~FastMap()590 ~FastMap() {}
591
592 Value &operator[](uint32_t key)
593 {
594 if (mData.size() <= key)
595 {
596 mData.resize(key + 1, {});
597 }
598 return at(key);
599 }
600
601 const Value &operator[](uint32_t key) const { return at(key); }
602
at(uint32_t key)603 Value &at(uint32_t key)
604 {
605 ASSERT(key < mData.size());
606 return mData[key];
607 }
608
at(uint32_t key)609 const Value &at(uint32_t key) const
610 {
611 ASSERT(key < mData.size());
612 return mData[key];
613 }
614
clear()615 void clear() { mData.clear(); }
616
empty()617 bool empty() const { return mData.empty(); }
size()618 size_t size() const { return mData.size(); }
619
data()620 const Value *data() const { return mData.data(); }
621
622 bool operator==(const FastMap<Value, N> &other) const
623 {
624 return (size() == other.size()) &&
625 (memcmp(data(), other.data(), size() * sizeof(Value)) == 0);
626 }
627
begin()628 iterator begin() { return mData.begin(); }
begin()629 const_iterator begin() const { return mData.begin(); }
630
end()631 iterator end() { return mData.end(); }
end()632 const_iterator end() const { return mData.end(); }
633
634 private:
635 FastVector<Value, N> mData;
636 };
637
638 template <class Key, class Value, size_t N>
639 class FlatUnorderedMap final
640 {
641 public:
642 using Pair = std::pair<Key, Value>;
643 using Storage = FastVector<Pair, N>;
644 using iterator = typename Storage::iterator;
645 using const_iterator = typename Storage::const_iterator;
646
647 FlatUnorderedMap() = default;
648 ~FlatUnorderedMap() = default;
649
begin()650 iterator begin() { return mData.begin(); }
begin()651 const_iterator begin() const { return mData.begin(); }
end()652 iterator end() { return mData.end(); }
end()653 const_iterator end() const { return mData.end(); }
654
find(const Key & key)655 iterator find(const Key &key)
656 {
657 for (auto it = mData.begin(); it != mData.end(); ++it)
658 {
659 if (it->first == key)
660 {
661 return it;
662 }
663 }
664 return mData.end();
665 }
666
find(const Key & key)667 const_iterator find(const Key &key) const
668 {
669 for (auto it = mData.begin(); it != mData.end(); ++it)
670 {
671 if (it->first == key)
672 {
673 return it;
674 }
675 }
676 return mData.end();
677 }
678
679 Value &operator[](const Key &key)
680 {
681 iterator it = find(key);
682 if (it != end())
683 {
684 return it->second;
685 }
686
687 mData.push_back(Pair(key, {}));
688 return mData.back().second;
689 }
690
insert(Pair pair)691 void insert(Pair pair)
692 {
693 ASSERT(!contains(pair.first));
694 mData.push_back(std::move(pair));
695 }
696
insert(const Key & key,Value value)697 void insert(const Key &key, Value value) { insert(Pair(key, value)); }
698
erase(iterator pos)699 void erase(iterator pos) { mData.remove_and_permute(pos); }
700
contains(const Key & key)701 bool contains(const Key &key) const { return find(key) != end(); }
702
clear()703 void clear() { mData.clear(); }
704
get(const Key & key,Value * value)705 bool get(const Key &key, Value *value) const
706 {
707 auto it = find(key);
708 if (it != end())
709 {
710 *value = it->second;
711 return true;
712 }
713 return false;
714 }
715
empty()716 bool empty() const { return mData.empty(); }
size()717 size_t size() const { return mData.size(); }
718
719 private:
720 FastVector<Pair, N> mData;
721 };
722
723 template <class T, size_t N>
724 class FlatUnorderedSet final
725 {
726 public:
727 using Storage = FastVector<T, N>;
728 using iterator = typename Storage::iterator;
729 using const_iterator = typename Storage::const_iterator;
730
731 FlatUnorderedSet() = default;
732 ~FlatUnorderedSet() = default;
733
begin()734 iterator begin() { return mData.begin(); }
begin()735 const_iterator begin() const { return mData.begin(); }
end()736 iterator end() { return mData.end(); }
end()737 const_iterator end() const { return mData.end(); }
738
find(const T & value)739 iterator find(const T &value)
740 {
741 for (auto it = mData.begin(); it != mData.end(); ++it)
742 {
743 if (*it == value)
744 {
745 return it;
746 }
747 }
748 return mData.end();
749 }
750
find(const T & value)751 const_iterator find(const T &value) const
752 {
753 for (auto it = mData.begin(); it != mData.end(); ++it)
754 {
755 if (*it == value)
756 {
757 return it;
758 }
759 }
760 return mData.end();
761 }
762
empty()763 bool empty() const { return mData.empty(); }
764
insert(const T & value)765 void insert(const T &value)
766 {
767 ASSERT(!contains(value));
768 mData.push_back(value);
769 }
770
erase(const T & value)771 void erase(const T &value)
772 {
773 ASSERT(contains(value));
774 mData.remove_and_permute(value);
775 }
776
remove(const T & value)777 void remove(const T &value) { erase(value); }
778
contains(const T & value)779 bool contains(const T &value) const { return find(value) != end(); }
780
clear()781 void clear() { mData.clear(); }
782
783 bool operator==(const FlatUnorderedSet<T, N> &other) const { return mData == other.mData; }
784
785 private:
786 Storage mData;
787 };
788 } // namespace angle
789
790 #endif // COMMON_FASTVECTOR_H_
791