blob: 339726e4ea869026d47c6146ef862269a61487d7 [file] [log] [blame]
Dominik Laskowski0bacf272020-10-22 14:08:27 -07001/*
2 * Copyright 2020 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#pragma once
18
Dominik Laskowski04667b72021-12-15 13:14:54 -080019#include <ftl/details/array_traits.h>
Dominik Laskowski5444fc82020-11-24 13:41:10 -080020#include <ftl/static_vector.h>
Dominik Laskowski0bacf272020-10-22 14:08:27 -070021
22#include <algorithm>
23#include <iterator>
24#include <type_traits>
25#include <utility>
26#include <variant>
27#include <vector>
28
29namespace android::ftl {
30
31template <typename>
Dominik Laskowski5444fc82020-11-24 13:41:10 -080032struct is_small_vector;
Dominik Laskowski0bacf272020-10-22 14:08:27 -070033
34// ftl::StaticVector that promotes to std::vector when full. SmallVector is a drop-in replacement
35// for std::vector with statically allocated storage for N elements, whose goal is to improve run
36// time by avoiding heap allocation and increasing probability of cache hits. The standard API is
37// augmented by an unstable_erase operation that does not preserve order, and a replace operation
38// that destructively emplaces.
39//
Dominik Laskowski206996f2022-01-20 13:21:57 -080040// Unlike std::vector, T does not require copy/move assignment, so may be an object with const data
41// members, or be const itself.
42//
Dominik Laskowski0bacf272020-10-22 14:08:27 -070043// SmallVector<T, 0> is a specialization that thinly wraps std::vector.
44//
45// Example usage:
46//
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080047// ftl::SmallVector<char, 3> vector;
48// assert(vector.empty());
49// assert(!vector.dynamic());
Dominik Laskowski0bacf272020-10-22 14:08:27 -070050//
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080051// vector = {'a', 'b', 'c'};
52// assert(vector.size() == 3u);
53// assert(!vector.dynamic());
Dominik Laskowski0bacf272020-10-22 14:08:27 -070054//
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080055// vector.push_back('d');
56// assert(vector.dynamic());
Dominik Laskowski0bacf272020-10-22 14:08:27 -070057//
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080058// vector.unstable_erase(vector.begin());
59// assert(vector == (ftl::SmallVector{'d', 'b', 'c'}));
Dominik Laskowski0bacf272020-10-22 14:08:27 -070060//
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080061// vector.pop_back();
62// assert(vector.back() == 'b');
63// assert(vector.dynamic());
Dominik Laskowski0bacf272020-10-22 14:08:27 -070064//
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080065// const char array[] = "hi";
66// vector = ftl::SmallVector(array);
67// assert(vector == (ftl::SmallVector{'h', 'i', '\0'}));
68// assert(!vector.dynamic());
Dominik Laskowski0bacf272020-10-22 14:08:27 -070069//
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080070// ftl::SmallVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?');
71// assert(strings.size() == 3u);
72// assert(!strings.dynamic());
Dominik Laskowskiccd50a42020-10-30 19:56:38 -070073//
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080074// assert(strings[0] == "abc");
75// assert(strings[1] == "123");
76// assert(strings[2] == "???");
Dominik Laskowskiccd50a42020-10-30 19:56:38 -070077//
Dominik Laskowski5444fc82020-11-24 13:41:10 -080078template <typename T, std::size_t N>
Dominik Laskowski04667b72021-12-15 13:14:54 -080079class SmallVector final : details::ArrayTraits<T>, details::ArrayComparators<SmallVector> {
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080080 using Static = StaticVector<T, N>;
81 using Dynamic = SmallVector<T, 0>;
Dominik Laskowski0bacf272020-10-22 14:08:27 -070082
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080083 // TODO: Replace with std::remove_cvref_t in C++20.
84 template <typename U>
85 using remove_cvref_t = std::remove_cv_t<std::remove_reference_t<U>>;
Dominik Laskowski0bacf272020-10-22 14:08:27 -070086
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080087 public:
88 FTL_ARRAY_TRAIT(T, value_type);
89 FTL_ARRAY_TRAIT(T, size_type);
90 FTL_ARRAY_TRAIT(T, difference_type);
Dominik Laskowski0bacf272020-10-22 14:08:27 -070091
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080092 FTL_ARRAY_TRAIT(T, pointer);
93 FTL_ARRAY_TRAIT(T, reference);
94 FTL_ARRAY_TRAIT(T, iterator);
95 FTL_ARRAY_TRAIT(T, reverse_iterator);
Dominik Laskowski0bacf272020-10-22 14:08:27 -070096
Dominik Laskowskie21dbed2020-12-04 20:51:43 -080097 FTL_ARRAY_TRAIT(T, const_pointer);
98 FTL_ARRAY_TRAIT(T, const_reference);
99 FTL_ARRAY_TRAIT(T, const_iterator);
100 FTL_ARRAY_TRAIT(T, const_reverse_iterator);
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700101
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800102 // Creates an empty vector.
103 SmallVector() = default;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700104
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800105 // Constructs at most N elements. See StaticVector for underlying constructors.
106 template <typename Arg, typename... Args,
107 typename = std::enable_if_t<!is_small_vector<remove_cvref_t<Arg>>{}>>
108 SmallVector(Arg&& arg, Args&&... args)
109 : vector_(std::in_place_type<Static>, std::forward<Arg>(arg), std::forward<Args>(args)...) {}
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700110
Dominik Laskowski206996f2022-01-20 13:21:57 -0800111 // Copies or moves elements from a smaller convertible vector.
112 template <typename U, std::size_t M, typename = std::enable_if_t<(M > 0)>>
113 SmallVector(SmallVector<U, M> other) : vector_(convert(std::move(other))) {}
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700114
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800115 void swap(SmallVector& other) { vector_.swap(other.vector_); }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700116
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800117 // Returns whether the vector is backed by static or dynamic storage.
118 bool dynamic() const { return std::holds_alternative<Dynamic>(vector_); }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700119
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800120 // Avoid std::visit as it generates a dispatch table.
121#define DISPATCH(T, F, ...) \
122 T F() __VA_ARGS__ { \
123 return dynamic() ? std::get<Dynamic>(vector_).F() : std::get<Static>(vector_).F(); \
124 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700125
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800126 DISPATCH(size_type, max_size, const)
127 DISPATCH(size_type, size, const)
128 DISPATCH(bool, empty, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700129
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800130 // noexcept to suppress warning about zero variadic macro arguments.
131 DISPATCH(iterator, begin, noexcept)
132 DISPATCH(const_iterator, begin, const)
133 DISPATCH(const_iterator, cbegin, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700134
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800135 DISPATCH(iterator, end, noexcept)
136 DISPATCH(const_iterator, end, const)
137 DISPATCH(const_iterator, cend, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700138
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800139 DISPATCH(reverse_iterator, rbegin, noexcept)
140 DISPATCH(const_reverse_iterator, rbegin, const)
141 DISPATCH(const_reverse_iterator, crbegin, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700142
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800143 DISPATCH(reverse_iterator, rend, noexcept)
144 DISPATCH(const_reverse_iterator, rend, const)
145 DISPATCH(const_reverse_iterator, crend, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700146
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800147 DISPATCH(iterator, last, noexcept)
148 DISPATCH(const_iterator, last, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700149
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800150 DISPATCH(reference, front, noexcept)
151 DISPATCH(const_reference, front, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700152
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800153 DISPATCH(reference, back, noexcept)
154 DISPATCH(const_reference, back, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700155
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800156 reference operator[](size_type i) {
157 return dynamic() ? std::get<Dynamic>(vector_)[i] : std::get<Static>(vector_)[i];
158 }
159
160 const_reference operator[](size_type i) const { return const_cast<SmallVector&>(*this)[i]; }
161
162 // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
163 // replacing at end() is erroneous.
164 //
165 // The element is emplaced via move constructor, so type T does not need to define copy/move
166 // assignment, e.g. its data members may be const.
167 //
168 // The arguments may directly or indirectly refer to the element being replaced.
169 //
170 // Iterators to the replaced element point to its replacement, and others remain valid.
171 //
172 template <typename... Args>
173 reference replace(const_iterator it, Args&&... args) {
174 if (dynamic()) {
175 return std::get<Dynamic>(vector_).replace(it, std::forward<Args>(args)...);
176 } else {
177 return std::get<Static>(vector_).replace(it, std::forward<Args>(args)...);
178 }
179 }
180
181 // Appends an element, and returns a reference to it.
182 //
183 // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
184 // Otherwise, only the end() iterator is invalidated.
185 //
186 template <typename... Args>
187 reference emplace_back(Args&&... args) {
188 constexpr auto kInsertStatic = &Static::template emplace_back<Args...>;
189 constexpr auto kInsertDynamic = &Dynamic::template emplace_back<Args...>;
190 return *insert<kInsertStatic, kInsertDynamic>(std::forward<Args>(args)...);
191 }
192
193 // Appends an element.
194 //
195 // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
196 // Otherwise, only the end() iterator is invalidated.
197 //
198 void push_back(const value_type& v) {
199 constexpr auto kInsertStatic =
200 static_cast<bool (Static::*)(const value_type&)>(&Static::push_back);
201 constexpr auto kInsertDynamic =
202 static_cast<bool (Dynamic::*)(const value_type&)>(&Dynamic::push_back);
203 insert<kInsertStatic, kInsertDynamic>(v);
204 }
205
206 void push_back(value_type&& v) {
207 constexpr auto kInsertStatic = static_cast<bool (Static::*)(value_type &&)>(&Static::push_back);
208 constexpr auto kInsertDynamic =
209 static_cast<bool (Dynamic::*)(value_type &&)>(&Dynamic::push_back);
210 insert<kInsertStatic, kInsertDynamic>(std::move(v));
211 }
212
213 // Removes the last element. The vector must not be empty, or the call is erroneous.
214 //
215 // The last() and end() iterators are invalidated.
216 //
Dominik Laskowski44828ce2021-09-13 11:00:22 -0700217 DISPATCH(void, pop_back, noexcept)
218
219 // Removes all elements.
220 //
221 // All iterators are invalidated.
222 //
223 DISPATCH(void, clear, noexcept)
224
225#undef DISPATCH
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800226
227 // Erases an element, but does not preserve order. Rather than shifting subsequent elements,
228 // this moves the last element to the slot of the erased element.
229 //
230 // The last() and end() iterators, as well as those to the erased element, are invalidated.
231 //
232 void unstable_erase(iterator it) {
233 if (dynamic()) {
234 std::get<Dynamic>(vector_).unstable_erase(it);
235 } else {
236 std::get<Static>(vector_).unstable_erase(it);
237 }
238 }
239
Dominik Laskowski206996f2022-01-20 13:21:57 -0800240 // Extracts the elements as std::vector.
241 std::vector<T> promote() && {
242 if (dynamic()) {
243 return std::get<Dynamic>(std::move(vector_)).promote();
244 } else {
245 return {std::make_move_iterator(begin()), std::make_move_iterator(end())};
246 }
247 }
248
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800249 private:
Dominik Laskowski206996f2022-01-20 13:21:57 -0800250 template <typename, std::size_t>
251 friend class SmallVector;
252
253 template <typename U, std::size_t M>
254 static std::variant<Static, Dynamic> convert(SmallVector<U, M>&& other) {
255 using Other = SmallVector<U, M>;
256
257 if (other.dynamic()) {
258 return std::get<typename Other::Dynamic>(std::move(other.vector_));
259 } else {
260 return std::get<typename Other::Static>(std::move(other.vector_));
261 }
262 }
263
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800264 template <auto InsertStatic, auto InsertDynamic, typename... Args>
265 auto insert(Args&&... args) {
266 if (Dynamic* const vector = std::get_if<Dynamic>(&vector_)) {
267 return (vector->*InsertDynamic)(std::forward<Args>(args)...);
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700268 }
269
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800270 auto& vector = std::get<Static>(vector_);
271 if (vector.full()) {
272 return (promote(vector).*InsertDynamic)(std::forward<Args>(args)...);
273 } else {
274 return (vector.*InsertStatic)(std::forward<Args>(args)...);
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700275 }
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800276 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700277
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800278 Dynamic& promote(Static& static_vector) {
279 assert(static_vector.full());
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700280
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800281 // Allocate double capacity to reduce probability of reallocation.
282 Dynamic vector;
283 vector.reserve(Static::max_size() * 2);
284 std::move(static_vector.begin(), static_vector.end(), std::back_inserter(vector));
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700285
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800286 return vector_.template emplace<Dynamic>(std::move(vector));
287 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700288
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800289 std::variant<Static, Dynamic> vector_;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700290};
291
292// Partial specialization without static storage.
293template <typename T>
Dominik Laskowski04667b72021-12-15 13:14:54 -0800294class SmallVector<T, 0> final : details::ArrayTraits<T>,
Dominik Laskowski206996f2022-01-20 13:21:57 -0800295 details::ArrayComparators<SmallVector>,
Dominik Laskowski04667b72021-12-15 13:14:54 -0800296 details::ArrayIterators<SmallVector<T, 0>, T>,
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700297 std::vector<T> {
Dominik Laskowski206996f2022-01-20 13:21:57 -0800298 using details::ArrayTraits<T>::replace_at;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700299
Dominik Laskowski04667b72021-12-15 13:14:54 -0800300 using Iter = details::ArrayIterators<SmallVector, T>;
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800301 using Impl = std::vector<T>;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700302
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800303 friend Iter;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700304
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800305 public:
306 FTL_ARRAY_TRAIT(T, value_type);
307 FTL_ARRAY_TRAIT(T, size_type);
308 FTL_ARRAY_TRAIT(T, difference_type);
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700309
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800310 FTL_ARRAY_TRAIT(T, pointer);
311 FTL_ARRAY_TRAIT(T, reference);
312 FTL_ARRAY_TRAIT(T, iterator);
313 FTL_ARRAY_TRAIT(T, reverse_iterator);
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700314
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800315 FTL_ARRAY_TRAIT(T, const_pointer);
316 FTL_ARRAY_TRAIT(T, const_reference);
317 FTL_ARRAY_TRAIT(T, const_iterator);
318 FTL_ARRAY_TRAIT(T, const_reverse_iterator);
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700319
Dominik Laskowski206996f2022-01-20 13:21:57 -0800320 // See std::vector for underlying constructors.
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800321 using Impl::Impl;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700322
Dominik Laskowski206996f2022-01-20 13:21:57 -0800323 // Copies and moves a vector, respectively.
324 SmallVector(const SmallVector&) = default;
325 SmallVector(SmallVector&&) = default;
326
327 // Constructs elements in place. See StaticVector for underlying constructor.
328 template <typename U, std::size_t... Sizes, typename... Types>
329 SmallVector(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& list)
330 : SmallVector(SmallVector<T, sizeof...(Sizes)>(std::move(list))) {}
331
332 // Copies or moves elements from a convertible vector.
333 template <typename U, std::size_t M>
334 SmallVector(SmallVector<U, M> other) : Impl(convert(std::move(other))) {}
335
336 SmallVector& operator=(SmallVector other) {
337 // Define copy/move assignment in terms of copy/move construction.
338 swap(other);
339 return *this;
340 }
341
342 void swap(SmallVector& other) { Impl::swap(other); }
343
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800344 using Impl::empty;
345 using Impl::max_size;
346 using Impl::size;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700347
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800348 using Impl::reserve;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700349
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800350 // std::vector iterators are not necessarily raw pointers.
351 iterator begin() { return Impl::data(); }
352 iterator end() { return Impl::data() + size(); }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700353
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800354 using Iter::begin;
355 using Iter::end;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700356
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800357 using Iter::cbegin;
358 using Iter::cend;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700359
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800360 using Iter::rbegin;
361 using Iter::rend;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700362
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800363 using Iter::crbegin;
364 using Iter::crend;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700365
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800366 using Iter::last;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700367
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800368 using Iter::back;
369 using Iter::front;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700370
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800371 using Iter::operator[];
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700372
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800373 template <typename... Args>
374 reference replace(const_iterator it, Args&&... args) {
Dominik Laskowski206996f2022-01-20 13:21:57 -0800375 return replace_at(it, std::forward<Args>(args)...);
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800376 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700377
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800378 template <typename... Args>
379 iterator emplace_back(Args&&... args) {
380 return &Impl::emplace_back(std::forward<Args>(args)...);
381 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700382
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800383 bool push_back(const value_type& v) {
384 Impl::push_back(v);
385 return true;
386 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700387
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800388 bool push_back(value_type&& v) {
389 Impl::push_back(std::move(v));
390 return true;
391 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700392
Dominik Laskowski44828ce2021-09-13 11:00:22 -0700393 using Impl::clear;
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800394 using Impl::pop_back;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700395
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800396 void unstable_erase(iterator it) {
Dominik Laskowskidda9bba2021-02-03 18:56:00 -0800397 if (it != last()) replace(it, std::move(back()));
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800398 pop_back();
399 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700400
Dominik Laskowski206996f2022-01-20 13:21:57 -0800401 std::vector<T> promote() && { return std::move(*this); }
402
403 private:
404 template <typename U, std::size_t M>
405 static Impl convert(SmallVector<U, M>&& other) {
406 if constexpr (std::is_constructible_v<Impl, std::vector<U>&&>) {
407 return std::move(other).promote();
408 } else {
409 SmallVector vector(other.size());
410
411 // Consistently with StaticVector, T only requires copy/move construction from U, rather than
412 // copy/move assignment.
413 auto it = vector.begin();
414 for (auto& element : other) {
415 vector.replace(it++, std::move(element));
416 }
417
418 return vector;
419 }
420 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700421};
422
423template <typename>
Dominik Laskowski5444fc82020-11-24 13:41:10 -0800424struct is_small_vector : std::false_type {};
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700425
Dominik Laskowski5444fc82020-11-24 13:41:10 -0800426template <typename T, std::size_t N>
427struct is_small_vector<SmallVector<T, N>> : std::true_type {};
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700428
429// Deduction guide for array constructor.
Dominik Laskowski5444fc82020-11-24 13:41:10 -0800430template <typename T, std::size_t N>
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700431SmallVector(T (&)[N]) -> SmallVector<std::remove_cv_t<T>, N>;
432
433// Deduction guide for variadic constructor.
434template <typename T, typename... Us, typename V = std::decay_t<T>,
435 typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>>
436SmallVector(T&&, Us&&...) -> SmallVector<V, 1 + sizeof...(Us)>;
437
438// Deduction guide for in-place constructor.
Dominik Laskowski5444fc82020-11-24 13:41:10 -0800439template <typename T, std::size_t... Sizes, typename... Types>
Dominik Laskowskiccd50a42020-10-30 19:56:38 -0700440SmallVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&)
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800441 -> SmallVector<T, sizeof...(Sizes)>;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700442
443// Deduction guide for StaticVector conversion.
Dominik Laskowski5444fc82020-11-24 13:41:10 -0800444template <typename T, std::size_t N>
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700445SmallVector(StaticVector<T, N>&&) -> SmallVector<T, N>;
446
Dominik Laskowski5444fc82020-11-24 13:41:10 -0800447template <typename T, std::size_t N>
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700448inline void swap(SmallVector<T, N>& lhs, SmallVector<T, N>& rhs) {
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800449 lhs.swap(rhs);
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700450}
451
Dominik Laskowskie21dbed2020-12-04 20:51:43 -0800452} // namespace android::ftl