14 #ifndef WPIUTIL_WPI_SMALLSET_H
15 #define WPIUTIL_WPI_SMALLSET_H
17 #include "wpi/SmallPtrSet.h"
18 #include "wpi/SmallVector.h"
19 #include "wpi/Compiler.h"
20 #include "wpi/iterator.h"
21 #include "wpi/type_traits.h"
26 #include <type_traits>
33 template <
typename T,
unsigned N,
typename C>
36 std::forward_iterator_tag, T> {
38 using SetIterTy =
typename std::set<T, C>::const_iterator;
39 using VecIterTy =
typename SmallVector<T, N>::const_iterator;
67 VecIter = Other.VecIter;
71 new (&SetIter) SetIterTy(Other.SetIter);
76 VecIter = std::move(Other.VecIter);
80 new (&SetIter) SetIterTy(std::move(Other.SetIter));
89 isSmall = Other.isSmall;
91 VecIter = Other.VecIter;
93 new (&SetIter) SetIterTy(Other.SetIter);
101 SetIter.~SetIterTy();
103 isSmall = Other.isSmall;
105 VecIter = std::move(Other.VecIter);
107 new (&SetIter) SetIterTy(std::move(Other.SetIter));
112 if (isSmall != RHS.isSmall)
115 return VecIter == RHS.VecIter;
116 return SetIter == RHS.SetIter;
127 const T &operator*()
const {
return isSmall ? *VecIter : *SetIter; }
134 template <
typename T,
unsigned N,
typename C = std::less<T>>
142 using VIterator =
typename SmallVector<T, N>::const_iterator;
143 using mutable_iterator =
typename SmallVector<T, N>::iterator;
148 static_assert(N <= 32,
"N should be small");
151 using size_type = size_t;
156 LLVM_NODISCARD
bool empty()
const {
157 return Vector.empty() && Set.empty();
160 size_type size()
const {
161 return isSmall() ? Vector.size() : Set.size();
168 return vfind(V) == Vector.end() ? 0 : 1;
181 std::pair<std::nullopt_t, bool>
insert(
const T &V) {
183 return std::make_pair(std::nullopt, Set.insert(V).second);
185 VIterator I = vfind(V);
186 if (I != Vector.end())
187 return std::make_pair(std::nullopt,
false);
188 if (Vector.size() < N) {
190 return std::make_pair(std::nullopt,
true);
194 while (!Vector.empty()) {
195 Set.insert(Vector.back());
199 return std::make_pair(std::nullopt,
true);
202 template <
typename IterT>
203 void insert(IterT I, IterT E) {
208 bool erase(
const T &V) {
211 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
224 const_iterator begin()
const {
226 return {Vector.begin()};
227 return {Set.begin()};
230 const_iterator end()
const {
232 return {Vector.end()};
237 bool isSmall()
const {
return Set.empty(); }
239 VIterator vfind(
const T &V)
const {
240 for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
249 template <
typename Po
inteeType,
unsigned N>
254 #endif // LLVM_ADT_SMALLSET_H