Blender V5.3
unique_ptr_vector.h
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2011-2022 Blender Foundation
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#pragma once
6
7#include <cassert>
8#include <utility>
9
10#include "util/algorithm.h"
12#include "util/set.h"
13#include "util/unique_ptr.h"
14#include "util/vector.h"
15
17
18/* Convenient vector of unique_ptr.
19 * - Indexing and iterators return the pointer value directly.
20 * - Utility functions for erase by swapping elements, for nodes.
21 */
22template<typename T> class unique_ptr_vector {
23 protected:
25
26 public:
27 T *operator[](const size_t i) const
28 {
29 return data[i].get();
30 }
31
32 unique_ptr<T> steal(const size_t i)
33 {
34 unique_ptr<T> local;
35 swap(data[i], local);
36 return local;
37 }
38
39 T *back() const
40 {
41 return data.back().get();
42 }
43
45 {
46 data.push_back(std::move(value));
47 }
48
49 void replace(const size_t i, unique_ptr<T> &&value)
50 {
51 data[i] = std::move(value);
52 }
53
54 void resize(const size_t new_size)
55 {
56 data.resize(new_size);
57 }
58
59 bool empty() const
60 {
61 return data.empty();
62 }
63
64 size_t size() const
65 {
66 return data.size();
67 }
68
69 void clear()
70 {
71 data.clear();
72 }
73
75 {
76 data.free_memory();
77 }
78
79 void erase_by_swap(const size_t index)
80 {
81 swap(data[index], data[data.size() - 1]);
82 data.resize(data.size() - 1);
83 }
84
85 void erase(const T *value)
86 {
87 const size_t size = data.size();
88 for (size_t i = 0; i < size; i++) {
89 if (data[i].get() == value) {
90 data.erase(data.begin() + i);
91 return;
92 }
93 }
94
95 assert(0);
96 }
97
98 /* Slightly faster erase swapping with other element instead of moving many,
99 * but will change element order. */
100 void erase_by_swap(const T *value)
101 {
102 const size_t size = data.size();
103 for (size_t i = 0; i < size; i++) {
104 if (data[i].get() == value) {
105 erase_by_swap(i);
106 return;
107 }
108 }
109
110 assert(0);
111 }
112
113 void erase_in_set(const set<T *> &values)
114 {
115 size_t new_size = data.size();
116
117 for (size_t i = 0; i < new_size; i++) {
118 T *value = data[i].get();
119 if (values.find(value) != values.end()) {
120 swap(data[i], data[new_size - 1]);
121 i -= 1;
122 new_size -= 1;
123 }
124 }
125
126 data.resize(new_size);
127 }
128
129 /* Remove trailing null entries. */
130 void trim()
131 {
132 while (!data.empty() && !data.back()) {
133 data.pop_back();
134 }
135 }
136
137 /* Basic iterators for range based for loop. */
138 struct ConstIterator : public random_access_iterator_mixin<ConstIterator> {
139 private:
140 using It = typename vector<unique_ptr<T>>::const_iterator;
141 It it_;
142
143 public:
144 using value_type = const T *;
145 using pointer = const T **;
148
149 ConstIterator(It it) : it_(it) {}
150
151 const T *operator*() const
152 {
153 return it_->get();
154 }
155
156 const It &iter_prop() const
157 {
158 return it_;
159 }
160 };
161
163 {
164 return ConstIterator{data.begin()};
165 }
167 {
168 return ConstIterator{data.end()};
169 }
170
171 struct Iterator : public random_access_iterator_mixin<Iterator> {
172 private:
173 using It = typename vector<unique_ptr<T>>::iterator;
174 It it_;
175
176 public:
177 using value_type = T *;
178 using pointer = T **;
181
182 Iterator(It it) : it_(it) {}
183
184 T *operator*() const
185 {
186 return it_->get();
187 }
188
189 const It &iter_prop() const
190 {
191 return it_;
192 }
193 };
195 {
196 return Iterator{data.begin()};
197 }
199 {
200 return Iterator{data.end()};
201 }
202
203 /* Iterator over vector with index. */
204 template<typename UniqueVectorU, typename U> struct EnumerateT {
205 UniqueVectorU &vec;
206
207 struct Iterator {
208 size_t index;
209 UniqueVectorU &vec;
210
211 bool operator!=(const Iterator &other) const
212 {
213 return index != other.index;
214 }
215
217 {
218 index++;
219 }
220
221 std::pair<size_t, U *> operator*() const
222 {
223 return std::make_pair(index, vec[index]);
224 }
225 };
226
227 Iterator begin()
228 {
229 return Iterator{0, vec};
230 }
231 Iterator end()
232 {
233 return Iterator{vec.size(), vec};
234 }
235 };
236
239
241 {
242 return Enumerate{*this};
243 }
244
246 {
247 return ConstEnumerate{*this};
248 }
249
250 /* Cast to read-only regular vector for easier interop.
251 * Assumes unique_ptr is zero overhead. */
252 operator const vector<T *> &()
253 {
254 static_assert(sizeof(unique_ptr<T>) == sizeof(T *));
255 return reinterpret_cast<vector<T *> &>(*this);
256 }
257
258 /* For sorting unique_ptr instead of pointer. */
259 template<typename Compare> void stable_sort(Compare compare)
260 {
261 auto compare_unique_ptr = [compare](const unique_ptr<T> &a, const unique_ptr<T> &b) {
262 return compare(a.get(), b.get());
263 };
264
265 std::stable_sort(data.begin(), data.end(), compare_unique_ptr);
266 }
267};
268
ConstIterator begin() const
void push_back(unique_ptr< T > &&value)
void erase_by_swap(const size_t index)
vector< unique_ptr< T > > data
void erase(const T *value)
ConstIterator end() const
EnumerateT< const unique_ptr_vector< T >, const T > ConstEnumerate
unique_ptr< T > steal(const size_t i)
T * operator[](const size_t i) const
size_t size() const
EnumerateT< unique_ptr_vector< T >, T > Enumerate
ConstEnumerate enumerate() const
void replace(const size_t i, unique_ptr< T > &&value)
void stable_sort(Compare compare)
void erase_in_set(const set< T * > &values)
void erase_by_swap(const T *value)
void resize(const size_t new_size)
#define CCL_NAMESPACE_END
#define assert(assertion)
#define index(i)
#define T
#define swap(a, b)
Definition sort.cc:61
bool operator!=(const Iterator &other) const
std::pair< size_t, U * > operator*() const