LLVM 17.0.0git
SetVector.h
Go to the documentation of this file.
1//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements a set that has insertion order iteration
11/// characteristics. This is useful for keeping a set of things that need to be
12/// visited later but in a deterministic order (insertion order). The interface
13/// is purposefully minimal.
14///
15/// This file defines SetVector and SmallSetVector, which performs no
16/// allocations if the SetVector has less than a certain number of elements.
17///
18//===----------------------------------------------------------------------===//
19
20#ifndef LLVM_ADT_SETVECTOR_H
21#define LLVM_ADT_SETVECTOR_H
22
23#include "llvm/ADT/ArrayRef.h"
24#include "llvm/ADT/DenseSet.h"
25#include "llvm/ADT/STLExtras.h"
27#include <cassert>
28#include <iterator>
29#include <vector>
30
31namespace llvm {
32
33/// A vector that has set insertion semantics.
34///
35/// This adapter class provides a way to keep a set of things that also has the
36/// property of a deterministic iteration order. The order of iteration is the
37/// order of insertion.
38template <typename T, typename Vector = std::vector<T>,
39 typename Set = DenseSet<T>>
40class SetVector {
41public:
42 using value_type = T;
43 using key_type = T;
44 using reference = T&;
45 using const_reference = const T&;
46 using set_type = Set;
48 using iterator = typename vector_type::const_iterator;
49 using const_iterator = typename vector_type::const_iterator;
50 using reverse_iterator = typename vector_type::const_reverse_iterator;
51 using const_reverse_iterator = typename vector_type::const_reverse_iterator;
52 using size_type = typename vector_type::size_type;
53
54 /// Construct an empty SetVector
55 SetVector() = default;
56
57 /// Initialize a SetVector with a range of elements
58 template<typename It>
59 SetVector(It Start, It End) {
60 insert(Start, End);
61 }
62
63 ArrayRef<T> getArrayRef() const { return vector_; }
64
65 /// Clear the SetVector and return the underlying vector.
67 set_.clear();
68 return std::move(vector_);
69 }
70
71 /// Determine if the SetVector is empty or not.
72 bool empty() const {
73 return vector_.empty();
74 }
75
76 /// Determine the number of elements in the SetVector.
77 size_type size() const {
78 return vector_.size();
79 }
80
81 /// Get an iterator to the beginning of the SetVector.
83 return vector_.begin();
84 }
85
86 /// Get a const_iterator to the beginning of the SetVector.
88 return vector_.begin();
89 }
90
91 /// Get an iterator to the end of the SetVector.
93 return vector_.end();
94 }
95
96 /// Get a const_iterator to the end of the SetVector.
98 return vector_.end();
99 }
100
101 /// Get an reverse_iterator to the end of the SetVector.
103 return vector_.rbegin();
104 }
105
106 /// Get a const_reverse_iterator to the end of the SetVector.
108 return vector_.rbegin();
109 }
110
111 /// Get a reverse_iterator to the beginning of the SetVector.
113 return vector_.rend();
114 }
115
116 /// Get a const_reverse_iterator to the beginning of the SetVector.
118 return vector_.rend();
119 }
120
121 /// Return the first element of the SetVector.
122 const T &front() const {
123 assert(!empty() && "Cannot call front() on empty SetVector!");
124 return vector_.front();
125 }
126
127 /// Return the last element of the SetVector.
128 const T &back() const {
129 assert(!empty() && "Cannot call back() on empty SetVector!");
130 return vector_.back();
131 }
132
133 /// Index into the SetVector.
135 assert(n < vector_.size() && "SetVector access out of range!");
136 return vector_[n];
137 }
138
139 /// Insert a new element into the SetVector.
140 /// \returns true if the element was inserted into the SetVector.
141 bool insert(const value_type &X) {
142 bool result = set_.insert(X).second;
143 if (result)
144 vector_.push_back(X);
145 return result;
146 }
147
148 /// Insert a range of elements into the SetVector.
149 template<typename It>
150 void insert(It Start, It End) {
151 for (; Start != End; ++Start)
152 if (set_.insert(*Start).second)
153 vector_.push_back(*Start);
154 }
155
156 /// Remove an item from the set vector.
157 bool remove(const value_type& X) {
158 if (set_.erase(X)) {
159 typename vector_type::iterator I = find(vector_, X);
160 assert(I != vector_.end() && "Corrupted SetVector instances!");
161 vector_.erase(I);
162 return true;
163 }
164 return false;
165 }
166
167 /// Erase a single element from the set vector.
168 /// \returns an iterator pointing to the next element that followed the
169 /// element erased. This is the end of the SetVector if the last element is
170 /// erased.
172 const key_type &V = *I;
173 assert(set_.count(V) && "Corrupted SetVector instances!");
174 set_.erase(V);
175 return vector_.erase(I);
176 }
177
178 /// Remove items from the set vector based on a predicate function.
179 ///
180 /// This is intended to be equivalent to the following code, if we could
181 /// write it:
182 ///
183 /// \code
184 /// V.erase(remove_if(V, P), V.end());
185 /// \endcode
186 ///
187 /// However, SetVector doesn't expose non-const iterators, making any
188 /// algorithm like remove_if impossible to use.
189 ///
190 /// \returns true if any element is removed.
191 template <typename UnaryPredicate>
192 bool remove_if(UnaryPredicate P) {
193 typename vector_type::iterator I =
194 llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_));
195 if (I == vector_.end())
196 return false;
197 vector_.erase(I, vector_.end());
198 return true;
199 }
200
201 /// Check if the SetVector contains the given key.
202 bool contains(const key_type &key) const {
203 return set_.find(key) != set_.end();
204 }
205
206 /// Count the number of elements of a given key in the SetVector.
207 /// \returns 0 if the element is not in the SetVector, 1 if it is.
208 size_type count(const key_type &key) const {
209 return set_.count(key);
210 }
211
212 /// Completely clear the SetVector
213 void clear() {
214 set_.clear();
215 vector_.clear();
216 }
217
218 /// Remove the last element of the SetVector.
219 void pop_back() {
220 assert(!empty() && "Cannot remove an element from an empty SetVector!");
221 set_.erase(back());
222 vector_.pop_back();
223 }
224
225 [[nodiscard]] T pop_back_val() {
226 T Ret = back();
227 pop_back();
228 return Ret;
229 }
230
231 bool operator==(const SetVector &that) const {
232 return vector_ == that.vector_;
233 }
234
235 bool operator!=(const SetVector &that) const {
236 return vector_ != that.vector_;
237 }
238
239 /// Compute This := This u S, return whether 'This' changed.
240 /// TODO: We should be able to use set_union from SetOperations.h, but
241 /// SetVector interface is inconsistent with DenseSet.
242 template <class STy>
243 bool set_union(const STy &S) {
244 bool Changed = false;
245
246 for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
247 ++SI)
248 if (insert(*SI))
249 Changed = true;
250
251 return Changed;
252 }
253
254 /// Compute This := This - B
255 /// TODO: We should be able to use set_subtract from SetOperations.h, but
256 /// SetVector interface is inconsistent with DenseSet.
257 template <class STy>
258 void set_subtract(const STy &S) {
259 for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
260 ++SI)
261 remove(*SI);
262 }
263
265 set_.swap(RHS.set_);
266 vector_.swap(RHS.vector_);
267 }
268
269private:
270 /// A wrapper predicate designed for use with std::remove_if.
271 ///
272 /// This predicate wraps a predicate suitable for use with std::remove_if to
273 /// call set_.erase(x) on each element which is slated for removal.
274 template <typename UnaryPredicate>
275 class TestAndEraseFromSet {
276 UnaryPredicate P;
277 set_type &set_;
278
279 public:
280 TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
281 : P(std::move(P)), set_(set_) {}
282
283 template <typename ArgumentT>
284 bool operator()(const ArgumentT &Arg) {
285 if (P(Arg)) {
286 set_.erase(Arg);
287 return true;
288 }
289 return false;
290 }
291 };
292
293 set_type set_; ///< The set.
294 vector_type vector_; ///< The vector.
295};
296
297/// A SetVector that performs no allocations if smaller than
298/// a certain size.
299template <typename T, unsigned N>
301 : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {
302public:
303 SmallSetVector() = default;
304
305 /// Initialize a SmallSetVector with a range of elements
306 template<typename It>
307 SmallSetVector(It Start, It End) {
308 this->insert(Start, End);
309 }
310};
311
312} // end namespace llvm
313
314namespace std {
315
316/// Implement std::swap in terms of SetVector swap.
317template<typename T, typename V, typename S>
318inline void
320 LHS.swap(RHS);
321}
322
323/// Implement std::swap in terms of SmallSetVector swap.
324template<typename T, unsigned N>
325inline void
327 LHS.swap(RHS);
328}
329
330} // end namespace std
331
332#endif // LLVM_ADT_SETVECTOR_H
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
This file defines the DenseSet and SmallDenseSet classes.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
#define I(x, y, z)
Definition: MD5.cpp:58
#define T
#define P(N)
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
Value * RHS
Value * LHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A vector that has set insertion semantics.
Definition: SetVector.h:40
const_iterator end() const
Get a const_iterator to the end of the SetVector.
Definition: SetVector.h:97
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
typename vector_type::const_iterator const_iterator
Definition: SetVector.h:49
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:208
reverse_iterator rend()
Get a reverse_iterator to the beginning of the SetVector.
Definition: SetVector.h:112
iterator erase(const_iterator I)
Erase a single element from the set vector.
Definition: SetVector.h:171
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
Definition: SetVector.h:202
SetVector()=default
Construct an empty SetVector.
bool remove_if(UnaryPredicate P)
Remove items from the set vector based on a predicate function.
Definition: SetVector.h:192
Vector vector_type
Definition: SetVector.h:47
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:157
ArrayRef< T > getArrayRef() const
Definition: SetVector.h:63
reverse_iterator rbegin()
Get an reverse_iterator to the end of the SetVector.
Definition: SetVector.h:102
const_reference operator[](size_type n) const
Index into the SetVector.
Definition: SetVector.h:134
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
const_reverse_iterator rend() const
Get a const_reverse_iterator to the beginning of the SetVector.
Definition: SetVector.h:117
void pop_back()
Remove the last element of the SetVector.
Definition: SetVector.h:219
typename vector_type::const_reverse_iterator const_reverse_iterator
Definition: SetVector.h:51
const T & front() const
Return the first element of the SetVector.
Definition: SetVector.h:122
bool operator!=(const SetVector &that) const
Definition: SetVector.h:235
void clear()
Completely clear the SetVector.
Definition: SetVector.h:213
const_reverse_iterator rbegin() const
Get a const_reverse_iterator to the end of the SetVector.
Definition: SetVector.h:107
bool set_union(const STy &S)
Compute This := This u S, return whether 'This' changed.
Definition: SetVector.h:243
typename vector_type::size_type size_type
Definition: SetVector.h:52
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
Vector takeVector()
Clear the SetVector and return the underlying vector.
Definition: SetVector.h:66
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:128
typename vector_type::const_iterator iterator
Definition: SetVector.h:48
SetVector(It Start, It End)
Initialize a SetVector with a range of elements.
Definition: SetVector.h:59
const_iterator begin() const
Get a const_iterator to the beginning of the SetVector.
Definition: SetVector.h:87
typename vector_type::const_reverse_iterator reverse_iterator
Definition: SetVector.h:50
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
bool operator==(const SetVector &that) const
Definition: SetVector.h:231
void swap(SetVector< T, Vector, Set > &RHS)
Definition: SetVector.h:264
void insert(It Start, It End)
Insert a range of elements into the SetVector.
Definition: SetVector.h:150
void set_subtract(const STy &S)
Compute This := This - B TODO: We should be able to use set_subtract from SetOperations....
Definition: SetVector.h:258
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:301
SmallSetVector(It Start, It End)
Initialize a SmallSetVector with a range of elements.
Definition: SetVector.h:307
SmallSetVector()=default
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1755
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1774
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1862
Definition: BitVector.h:851
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853