1 | // Copyright 2019 The Abseil Authors. |
2 | // |
3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
4 | // you may not use this file except in compliance with the License. |
5 | // You may obtain a copy of the License at |
6 | // |
7 | // https://www.apache.org/licenses/LICENSE-2.0 |
8 | // |
9 | // Unless required by applicable law or agreed to in writing, software |
10 | // distributed under the License is distributed on an "AS IS" BASIS, |
11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | // See the License for the specific language governing permissions and |
13 | // limitations under the License. |
14 | // |
15 | // ----------------------------------------------------------------------------- |
16 | // File: inlined_vector.h |
17 | // ----------------------------------------------------------------------------- |
18 | // |
19 | // This header file contains the declaration and definition of an "inlined |
20 | // vector" which behaves in an equivalent fashion to a `std::vector`, except |
21 | // that storage for small sequences of the vector are provided inline without |
22 | // requiring any heap allocation. |
23 | // |
24 | // An `absl::InlinedVector<T, N>` specifies the default capacity `N` as one of |
25 | // its template parameters. Instances where `size() <= N` hold contained |
26 | // elements in inline space. Typically `N` is very small so that sequences that |
27 | // are expected to be short do not require allocations. |
28 | // |
29 | // An `absl::InlinedVector` does not usually require a specific allocator. If |
30 | // the inlined vector grows beyond its initial constraints, it will need to |
31 | // allocate (as any normal `std::vector` would). This is usually performed with |
32 | // the default allocator (defined as `std::allocator<T>`). Optionally, a custom |
33 | // allocator type may be specified as `A` in `absl::InlinedVector<T, N, A>`. |
34 | |
35 | #ifndef ABSL_CONTAINER_INLINED_VECTOR_H_ |
36 | #define ABSL_CONTAINER_INLINED_VECTOR_H_ |
37 | |
38 | #include <algorithm> |
39 | #include <cstddef> |
40 | #include <cstdlib> |
41 | #include <cstring> |
42 | #include <initializer_list> |
43 | #include <iterator> |
44 | #include <memory> |
45 | #include <type_traits> |
46 | #include <utility> |
47 | |
48 | #include "absl/algorithm/algorithm.h" |
49 | #include "absl/base/internal/throw_delegate.h" |
50 | #include "absl/base/macros.h" |
51 | #include "absl/base/optimization.h" |
52 | #include "absl/base/port.h" |
53 | #include "absl/container/internal/inlined_vector.h" |
54 | #include "absl/memory/memory.h" |
55 | |
56 | namespace absl { |
57 | ABSL_NAMESPACE_BEGIN |
58 | // ----------------------------------------------------------------------------- |
59 | // InlinedVector |
60 | // ----------------------------------------------------------------------------- |
61 | // |
62 | // An `absl::InlinedVector` is designed to be a drop-in replacement for |
63 | // `std::vector` for use cases where the vector's size is sufficiently small |
64 | // that it can be inlined. If the inlined vector does grow beyond its estimated |
65 | // capacity, it will trigger an initial allocation on the heap, and will behave |
66 | // as a `std::vector`. The API of the `absl::InlinedVector` within this file is |
67 | // designed to cover the same API footprint as covered by `std::vector`. |
68 | template <typename T, size_t N, typename A = std::allocator<T>> |
69 | class InlinedVector { |
70 | static_assert(N > 0, "`absl::InlinedVector` requires an inlined capacity." ); |
71 | |
72 | using Storage = inlined_vector_internal::Storage<T, N, A>; |
73 | |
74 | template <typename TheA> |
75 | using AllocatorTraits = inlined_vector_internal::AllocatorTraits<TheA>; |
76 | template <typename TheA> |
77 | using MoveIterator = inlined_vector_internal::MoveIterator<TheA>; |
78 | template <typename TheA> |
79 | using IsMemcpyOk = inlined_vector_internal::IsMemcpyOk<TheA>; |
80 | |
81 | template <typename TheA, typename Iterator> |
82 | using IteratorValueAdapter = |
83 | inlined_vector_internal::IteratorValueAdapter<TheA, Iterator>; |
84 | template <typename TheA> |
85 | using CopyValueAdapter = inlined_vector_internal::CopyValueAdapter<TheA>; |
86 | template <typename TheA> |
87 | using DefaultValueAdapter = |
88 | inlined_vector_internal::DefaultValueAdapter<TheA>; |
89 | |
90 | template <typename Iterator> |
91 | using EnableIfAtLeastForwardIterator = absl::enable_if_t< |
92 | inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value, int>; |
93 | template <typename Iterator> |
94 | using DisableIfAtLeastForwardIterator = absl::enable_if_t< |
95 | !inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value, int>; |
96 | |
97 | public: |
98 | using allocator_type = A; |
99 | using value_type = inlined_vector_internal::ValueType<A>; |
100 | using pointer = inlined_vector_internal::Pointer<A>; |
101 | using const_pointer = inlined_vector_internal::ConstPointer<A>; |
102 | using size_type = inlined_vector_internal::SizeType<A>; |
103 | using difference_type = inlined_vector_internal::DifferenceType<A>; |
104 | using reference = inlined_vector_internal::Reference<A>; |
105 | using const_reference = inlined_vector_internal::ConstReference<A>; |
106 | using iterator = inlined_vector_internal::Iterator<A>; |
107 | using const_iterator = inlined_vector_internal::ConstIterator<A>; |
108 | using reverse_iterator = inlined_vector_internal::ReverseIterator<A>; |
109 | using const_reverse_iterator = |
110 | inlined_vector_internal::ConstReverseIterator<A>; |
111 | |
112 | // --------------------------------------------------------------------------- |
113 | // InlinedVector Constructors and Destructor |
114 | // --------------------------------------------------------------------------- |
115 | |
116 | // Creates an empty inlined vector with a value-initialized allocator. |
117 | InlinedVector() noexcept(noexcept(allocator_type())) : storage_() {} |
118 | |
119 | // Creates an empty inlined vector with a copy of `allocator`. |
120 | explicit InlinedVector(const allocator_type& allocator) noexcept |
121 | : storage_(allocator) {} |
122 | |
123 | // Creates an inlined vector with `n` copies of `value_type()`. |
124 | explicit InlinedVector(size_type n, |
125 | const allocator_type& allocator = allocator_type()) |
126 | : storage_(allocator) { |
127 | storage_.Initialize(DefaultValueAdapter<A>(), n); |
128 | } |
129 | |
130 | // Creates an inlined vector with `n` copies of `v`. |
131 | InlinedVector(size_type n, const_reference v, |
132 | const allocator_type& allocator = allocator_type()) |
133 | : storage_(allocator) { |
134 | storage_.Initialize(CopyValueAdapter<A>(std::addressof(v)), n); |
135 | } |
136 | |
137 | // Creates an inlined vector with copies of the elements of `list`. |
138 | InlinedVector(std::initializer_list<value_type> list, |
139 | const allocator_type& allocator = allocator_type()) |
140 | : InlinedVector(list.begin(), list.end(), allocator) {} |
141 | |
142 | // Creates an inlined vector with elements constructed from the provided |
143 | // forward iterator range [`first`, `last`). |
144 | // |
145 | // NOTE: the `enable_if` prevents ambiguous interpretation between a call to |
146 | // this constructor with two integral arguments and a call to the above |
147 | // `InlinedVector(size_type, const_reference)` constructor. |
148 | template <typename ForwardIterator, |
149 | EnableIfAtLeastForwardIterator<ForwardIterator> = 0> |
150 | InlinedVector(ForwardIterator first, ForwardIterator last, |
151 | const allocator_type& allocator = allocator_type()) |
152 | : storage_(allocator) { |
153 | storage_.Initialize(IteratorValueAdapter<A, ForwardIterator>(first), |
154 | static_cast<size_t>(std::distance(first, last))); |
155 | } |
156 | |
157 | // Creates an inlined vector with elements constructed from the provided input |
158 | // iterator range [`first`, `last`). |
159 | template <typename InputIterator, |
160 | DisableIfAtLeastForwardIterator<InputIterator> = 0> |
161 | InlinedVector(InputIterator first, InputIterator last, |
162 | const allocator_type& allocator = allocator_type()) |
163 | : storage_(allocator) { |
164 | std::copy(first, last, std::back_inserter(*this)); |
165 | } |
166 | |
167 | // Creates an inlined vector by copying the contents of `other` using |
168 | // `other`'s allocator. |
169 | InlinedVector(const InlinedVector& other) |
170 | : InlinedVector(other, other.storage_.GetAllocator()) {} |
171 | |
172 | // Creates an inlined vector by copying the contents of `other` using the |
173 | // provided `allocator`. |
174 | InlinedVector(const InlinedVector& other, const allocator_type& allocator) |
175 | : storage_(allocator) { |
176 | if (other.empty()) { |
177 | // Empty; nothing to do. |
178 | } else if (IsMemcpyOk<A>::value && !other.storage_.GetIsAllocated()) { |
179 | // Memcpy-able and do not need allocation. |
180 | storage_.MemcpyFrom(other.storage_); |
181 | } else { |
182 | storage_.InitFrom(other.storage_); |
183 | } |
184 | } |
185 | |
186 | // Creates an inlined vector by moving in the contents of `other` without |
187 | // allocating. If `other` contains allocated memory, the newly-created inlined |
188 | // vector will take ownership of that memory. However, if `other` does not |
189 | // contain allocated memory, the newly-created inlined vector will perform |
190 | // element-wise move construction of the contents of `other`. |
191 | // |
192 | // NOTE: since no allocation is performed for the inlined vector in either |
193 | // case, the `noexcept(...)` specification depends on whether moving the |
194 | // underlying objects can throw. It is assumed assumed that... |
195 | // a) move constructors should only throw due to allocation failure. |
196 | // b) if `value_type`'s move constructor allocates, it uses the same |
197 | // allocation function as the inlined vector's allocator. |
198 | // Thus, the move constructor is non-throwing if the allocator is non-throwing |
199 | // or `value_type`'s move constructor is specified as `noexcept`. |
200 | InlinedVector(InlinedVector&& other) noexcept( |
201 | absl::allocator_is_nothrow<allocator_type>::value || |
202 | std::is_nothrow_move_constructible<value_type>::value) |
203 | : storage_(other.storage_.GetAllocator()) { |
204 | if (IsMemcpyOk<A>::value) { |
205 | storage_.MemcpyFrom(other.storage_); |
206 | |
207 | other.storage_.SetInlinedSize(0); |
208 | } else if (other.storage_.GetIsAllocated()) { |
209 | storage_.SetAllocation({other.storage_.GetAllocatedData(), |
210 | other.storage_.GetAllocatedCapacity()}); |
211 | storage_.SetAllocatedSize(other.storage_.GetSize()); |
212 | |
213 | other.storage_.SetInlinedSize(0); |
214 | } else { |
215 | IteratorValueAdapter<A, MoveIterator<A>> other_values( |
216 | MoveIterator<A>(other.storage_.GetInlinedData())); |
217 | |
218 | inlined_vector_internal::ConstructElements<A>( |
219 | storage_.GetAllocator(), storage_.GetInlinedData(), other_values, |
220 | other.storage_.GetSize()); |
221 | |
222 | storage_.SetInlinedSize(other.storage_.GetSize()); |
223 | } |
224 | } |
225 | |
226 | // Creates an inlined vector by moving in the contents of `other` with a copy |
227 | // of `allocator`. |
228 | // |
229 | // NOTE: if `other`'s allocator is not equal to `allocator`, even if `other` |
230 | // contains allocated memory, this move constructor will still allocate. Since |
231 | // allocation is performed, this constructor can only be `noexcept` if the |
232 | // specified allocator is also `noexcept`. |
233 | InlinedVector( |
234 | InlinedVector&& other, |
235 | const allocator_type& |
236 | allocator) noexcept(absl::allocator_is_nothrow<allocator_type>::value) |
237 | : storage_(allocator) { |
238 | if (IsMemcpyOk<A>::value) { |
239 | storage_.MemcpyFrom(other.storage_); |
240 | |
241 | other.storage_.SetInlinedSize(0); |
242 | } else if ((storage_.GetAllocator() == other.storage_.GetAllocator()) && |
243 | other.storage_.GetIsAllocated()) { |
244 | storage_.SetAllocation({other.storage_.GetAllocatedData(), |
245 | other.storage_.GetAllocatedCapacity()}); |
246 | storage_.SetAllocatedSize(other.storage_.GetSize()); |
247 | |
248 | other.storage_.SetInlinedSize(0); |
249 | } else { |
250 | storage_.Initialize(IteratorValueAdapter<A, MoveIterator<A>>( |
251 | MoveIterator<A>(other.data())), |
252 | other.size()); |
253 | } |
254 | } |
255 | |
256 | ~InlinedVector() {} |
257 | |
258 | // --------------------------------------------------------------------------- |
259 | // InlinedVector Member Accessors |
260 | // --------------------------------------------------------------------------- |
261 | |
262 | // `InlinedVector::empty()` |
263 | // |
264 | // Returns whether the inlined vector contains no elements. |
265 | bool empty() const noexcept { return !size(); } |
266 | |
267 | // `InlinedVector::size()` |
268 | // |
269 | // Returns the number of elements in the inlined vector. |
270 | size_type size() const noexcept { return storage_.GetSize(); } |
271 | |
272 | // `InlinedVector::max_size()` |
273 | // |
274 | // Returns the maximum number of elements the inlined vector can hold. |
275 | size_type max_size() const noexcept { |
276 | // One bit of the size storage is used to indicate whether the inlined |
277 | // vector contains allocated memory. As a result, the maximum size that the |
278 | // inlined vector can express is half of the max for `size_type`. |
279 | return (std::numeric_limits<size_type>::max)() / 2; |
280 | } |
281 | |
282 | // `InlinedVector::capacity()` |
283 | // |
284 | // Returns the number of elements that could be stored in the inlined vector |
285 | // without requiring a reallocation. |
286 | // |
287 | // NOTE: for most inlined vectors, `capacity()` should be equal to the |
288 | // template parameter `N`. For inlined vectors which exceed this capacity, |
289 | // they will no longer be inlined and `capacity()` will equal the capactity of |
290 | // the allocated memory. |
291 | size_type capacity() const noexcept { |
292 | return storage_.GetIsAllocated() ? storage_.GetAllocatedCapacity() |
293 | : storage_.GetInlinedCapacity(); |
294 | } |
295 | |
296 | // `InlinedVector::data()` |
297 | // |
298 | // Returns a `pointer` to the elements of the inlined vector. This pointer |
299 | // can be used to access and modify the contained elements. |
300 | // |
301 | // NOTE: only elements within [`data()`, `data() + size()`) are valid. |
302 | pointer data() noexcept { |
303 | return storage_.GetIsAllocated() ? storage_.GetAllocatedData() |
304 | : storage_.GetInlinedData(); |
305 | } |
306 | |
307 | // Overload of `InlinedVector::data()` that returns a `const_pointer` to the |
308 | // elements of the inlined vector. This pointer can be used to access but not |
309 | // modify the contained elements. |
310 | // |
311 | // NOTE: only elements within [`data()`, `data() + size()`) are valid. |
312 | const_pointer data() const noexcept { |
313 | return storage_.GetIsAllocated() ? storage_.GetAllocatedData() |
314 | : storage_.GetInlinedData(); |
315 | } |
316 | |
317 | // `InlinedVector::operator[](...)` |
318 | // |
319 | // Returns a `reference` to the `i`th element of the inlined vector. |
320 | reference operator[](size_type i) { |
321 | ABSL_HARDENING_ASSERT(i < size()); |
322 | return data()[i]; |
323 | } |
324 | |
325 | // Overload of `InlinedVector::operator[](...)` that returns a |
326 | // `const_reference` to the `i`th element of the inlined vector. |
327 | const_reference operator[](size_type i) const { |
328 | ABSL_HARDENING_ASSERT(i < size()); |
329 | return data()[i]; |
330 | } |
331 | |
332 | // `InlinedVector::at(...)` |
333 | // |
334 | // Returns a `reference` to the `i`th element of the inlined vector. |
335 | // |
336 | // NOTE: if `i` is not within the required range of `InlinedVector::at(...)`, |
337 | // in both debug and non-debug builds, `std::out_of_range` will be thrown. |
338 | reference at(size_type i) { |
339 | if (ABSL_PREDICT_FALSE(i >= size())) { |
340 | base_internal::ThrowStdOutOfRange( |
341 | "`InlinedVector::at(size_type)` failed bounds check" ); |
342 | } |
343 | return data()[i]; |
344 | } |
345 | |
346 | // Overload of `InlinedVector::at(...)` that returns a `const_reference` to |
347 | // the `i`th element of the inlined vector. |
348 | // |
349 | // NOTE: if `i` is not within the required range of `InlinedVector::at(...)`, |
350 | // in both debug and non-debug builds, `std::out_of_range` will be thrown. |
351 | const_reference at(size_type i) const { |
352 | if (ABSL_PREDICT_FALSE(i >= size())) { |
353 | base_internal::ThrowStdOutOfRange( |
354 | "`InlinedVector::at(size_type) const` failed bounds check" ); |
355 | } |
356 | return data()[i]; |
357 | } |
358 | |
359 | // `InlinedVector::front()` |
360 | // |
361 | // Returns a `reference` to the first element of the inlined vector. |
362 | reference front() { |
363 | ABSL_HARDENING_ASSERT(!empty()); |
364 | return data()[0]; |
365 | } |
366 | |
367 | // Overload of `InlinedVector::front()` that returns a `const_reference` to |
368 | // the first element of the inlined vector. |
369 | const_reference front() const { |
370 | ABSL_HARDENING_ASSERT(!empty()); |
371 | return data()[0]; |
372 | } |
373 | |
374 | // `InlinedVector::back()` |
375 | // |
376 | // Returns a `reference` to the last element of the inlined vector. |
377 | reference back() { |
378 | ABSL_HARDENING_ASSERT(!empty()); |
379 | return data()[size() - 1]; |
380 | } |
381 | |
382 | // Overload of `InlinedVector::back()` that returns a `const_reference` to the |
383 | // last element of the inlined vector. |
384 | const_reference back() const { |
385 | ABSL_HARDENING_ASSERT(!empty()); |
386 | return data()[size() - 1]; |
387 | } |
388 | |
389 | // `InlinedVector::begin()` |
390 | // |
391 | // Returns an `iterator` to the beginning of the inlined vector. |
392 | iterator begin() noexcept { return data(); } |
393 | |
394 | // Overload of `InlinedVector::begin()` that returns a `const_iterator` to |
395 | // the beginning of the inlined vector. |
396 | const_iterator begin() const noexcept { return data(); } |
397 | |
398 | // `InlinedVector::end()` |
399 | // |
400 | // Returns an `iterator` to the end of the inlined vector. |
401 | iterator end() noexcept { return data() + size(); } |
402 | |
403 | // Overload of `InlinedVector::end()` that returns a `const_iterator` to the |
404 | // end of the inlined vector. |
405 | const_iterator end() const noexcept { return data() + size(); } |
406 | |
407 | // `InlinedVector::cbegin()` |
408 | // |
409 | // Returns a `const_iterator` to the beginning of the inlined vector. |
410 | const_iterator cbegin() const noexcept { return begin(); } |
411 | |
412 | // `InlinedVector::cend()` |
413 | // |
414 | // Returns a `const_iterator` to the end of the inlined vector. |
415 | const_iterator cend() const noexcept { return end(); } |
416 | |
417 | // `InlinedVector::rbegin()` |
418 | // |
419 | // Returns a `reverse_iterator` from the end of the inlined vector. |
420 | reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } |
421 | |
422 | // Overload of `InlinedVector::rbegin()` that returns a |
423 | // `const_reverse_iterator` from the end of the inlined vector. |
424 | const_reverse_iterator rbegin() const noexcept { |
425 | return const_reverse_iterator(end()); |
426 | } |
427 | |
428 | // `InlinedVector::rend()` |
429 | // |
430 | // Returns a `reverse_iterator` from the beginning of the inlined vector. |
431 | reverse_iterator rend() noexcept { return reverse_iterator(begin()); } |
432 | |
433 | // Overload of `InlinedVector::rend()` that returns a `const_reverse_iterator` |
434 | // from the beginning of the inlined vector. |
435 | const_reverse_iterator rend() const noexcept { |
436 | return const_reverse_iterator(begin()); |
437 | } |
438 | |
439 | // `InlinedVector::crbegin()` |
440 | // |
441 | // Returns a `const_reverse_iterator` from the end of the inlined vector. |
442 | const_reverse_iterator crbegin() const noexcept { return rbegin(); } |
443 | |
444 | // `InlinedVector::crend()` |
445 | // |
446 | // Returns a `const_reverse_iterator` from the beginning of the inlined |
447 | // vector. |
448 | const_reverse_iterator crend() const noexcept { return rend(); } |
449 | |
450 | // `InlinedVector::get_allocator()` |
451 | // |
452 | // Returns a copy of the inlined vector's allocator. |
453 | allocator_type get_allocator() const { return storage_.GetAllocator(); } |
454 | |
455 | // --------------------------------------------------------------------------- |
456 | // InlinedVector Member Mutators |
457 | // --------------------------------------------------------------------------- |
458 | |
459 | // `InlinedVector::operator=(...)` |
460 | // |
461 | // Replaces the elements of the inlined vector with copies of the elements of |
462 | // `list`. |
463 | InlinedVector& operator=(std::initializer_list<value_type> list) { |
464 | assign(list.begin(), list.end()); |
465 | |
466 | return *this; |
467 | } |
468 | |
469 | // Overload of `InlinedVector::operator=(...)` that replaces the elements of |
470 | // the inlined vector with copies of the elements of `other`. |
471 | InlinedVector& operator=(const InlinedVector& other) { |
472 | if (ABSL_PREDICT_TRUE(this != std::addressof(other))) { |
473 | const_pointer other_data = other.data(); |
474 | assign(other_data, other_data + other.size()); |
475 | } |
476 | |
477 | return *this; |
478 | } |
479 | |
480 | // Overload of `InlinedVector::operator=(...)` that moves the elements of |
481 | // `other` into the inlined vector. |
482 | // |
483 | // NOTE: as a result of calling this overload, `other` is left in a valid but |
484 | // unspecified state. |
485 | InlinedVector& operator=(InlinedVector&& other) { |
486 | if (ABSL_PREDICT_TRUE(this != std::addressof(other))) { |
487 | if (IsMemcpyOk<A>::value || other.storage_.GetIsAllocated()) { |
488 | inlined_vector_internal::DestroyAdapter<A>::DestroyElements( |
489 | storage_.GetAllocator(), data(), size()); |
490 | storage_.DeallocateIfAllocated(); |
491 | storage_.MemcpyFrom(other.storage_); |
492 | |
493 | other.storage_.SetInlinedSize(0); |
494 | } else { |
495 | storage_.Assign(IteratorValueAdapter<A, MoveIterator<A>>( |
496 | MoveIterator<A>(other.storage_.GetInlinedData())), |
497 | other.size()); |
498 | } |
499 | } |
500 | |
501 | return *this; |
502 | } |
503 | |
504 | // `InlinedVector::assign(...)` |
505 | // |
506 | // Replaces the contents of the inlined vector with `n` copies of `v`. |
507 | void assign(size_type n, const_reference v) { |
508 | storage_.Assign(CopyValueAdapter<A>(std::addressof(v)), n); |
509 | } |
510 | |
511 | // Overload of `InlinedVector::assign(...)` that replaces the contents of the |
512 | // inlined vector with copies of the elements of `list`. |
513 | void assign(std::initializer_list<value_type> list) { |
514 | assign(list.begin(), list.end()); |
515 | } |
516 | |
517 | // Overload of `InlinedVector::assign(...)` to replace the contents of the |
518 | // inlined vector with the range [`first`, `last`). |
519 | // |
520 | // NOTE: this overload is for iterators that are "forward" category or better. |
521 | template <typename ForwardIterator, |
522 | EnableIfAtLeastForwardIterator<ForwardIterator> = 0> |
523 | void assign(ForwardIterator first, ForwardIterator last) { |
524 | storage_.Assign(IteratorValueAdapter<A, ForwardIterator>(first), |
525 | static_cast<size_t>(std::distance(first, last))); |
526 | } |
527 | |
528 | // Overload of `InlinedVector::assign(...)` to replace the contents of the |
529 | // inlined vector with the range [`first`, `last`). |
530 | // |
531 | // NOTE: this overload is for iterators that are "input" category. |
532 | template <typename InputIterator, |
533 | DisableIfAtLeastForwardIterator<InputIterator> = 0> |
534 | void assign(InputIterator first, InputIterator last) { |
535 | size_type i = 0; |
536 | for (; i < size() && first != last; ++i, static_cast<void>(++first)) { |
537 | data()[i] = *first; |
538 | } |
539 | |
540 | erase(data() + i, data() + size()); |
541 | std::copy(first, last, std::back_inserter(*this)); |
542 | } |
543 | |
544 | // `InlinedVector::resize(...)` |
545 | // |
546 | // Resizes the inlined vector to contain `n` elements. |
547 | // |
548 | // NOTE: If `n` is smaller than `size()`, extra elements are destroyed. If `n` |
549 | // is larger than `size()`, new elements are value-initialized. |
550 | void resize(size_type n) { |
551 | ABSL_HARDENING_ASSERT(n <= max_size()); |
552 | storage_.Resize(DefaultValueAdapter<A>(), n); |
553 | } |
554 | |
555 | // Overload of `InlinedVector::resize(...)` that resizes the inlined vector to |
556 | // contain `n` elements. |
557 | // |
558 | // NOTE: if `n` is smaller than `size()`, extra elements are destroyed. If `n` |
559 | // is larger than `size()`, new elements are copied-constructed from `v`. |
560 | void resize(size_type n, const_reference v) { |
561 | ABSL_HARDENING_ASSERT(n <= max_size()); |
562 | storage_.Resize(CopyValueAdapter<A>(std::addressof(v)), n); |
563 | } |
564 | |
565 | // `InlinedVector::insert(...)` |
566 | // |
567 | // Inserts a copy of `v` at `pos`, returning an `iterator` to the newly |
568 | // inserted element. |
569 | iterator insert(const_iterator pos, const_reference v) { |
570 | return emplace(pos, v); |
571 | } |
572 | |
573 | // Overload of `InlinedVector::insert(...)` that inserts `v` at `pos` using |
574 | // move semantics, returning an `iterator` to the newly inserted element. |
575 | iterator insert(const_iterator pos, value_type&& v) { |
576 | return emplace(pos, std::move(v)); |
577 | } |
578 | |
579 | // Overload of `InlinedVector::insert(...)` that inserts `n` contiguous copies |
580 | // of `v` starting at `pos`, returning an `iterator` pointing to the first of |
581 | // the newly inserted elements. |
582 | iterator insert(const_iterator pos, size_type n, const_reference v) { |
583 | ABSL_HARDENING_ASSERT(pos >= begin()); |
584 | ABSL_HARDENING_ASSERT(pos <= end()); |
585 | |
586 | if (ABSL_PREDICT_TRUE(n != 0)) { |
587 | value_type dealias = v; |
588 | // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102329#c2 |
589 | // It appears that GCC thinks that since `pos` is a const pointer and may |
590 | // point to uninitialized memory at this point, a warning should be |
591 | // issued. But `pos` is actually only used to compute an array index to |
592 | // write to. |
593 | #if !defined(__clang__) && defined(__GNUC__) |
594 | #pragma GCC diagnostic push |
595 | #pragma GCC diagnostic ignored "-Wmaybe-uninitialized" |
596 | #endif |
597 | return storage_.Insert(pos, CopyValueAdapter<A>(std::addressof(dealias)), |
598 | n); |
599 | #if !defined(__clang__) && defined(__GNUC__) |
600 | #pragma GCC diagnostic pop |
601 | #endif |
602 | } else { |
603 | return const_cast<iterator>(pos); |
604 | } |
605 | } |
606 | |
607 | // Overload of `InlinedVector::insert(...)` that inserts copies of the |
608 | // elements of `list` starting at `pos`, returning an `iterator` pointing to |
609 | // the first of the newly inserted elements. |
610 | iterator insert(const_iterator pos, std::initializer_list<value_type> list) { |
611 | return insert(pos, list.begin(), list.end()); |
612 | } |
613 | |
614 | // Overload of `InlinedVector::insert(...)` that inserts the range [`first`, |
615 | // `last`) starting at `pos`, returning an `iterator` pointing to the first |
616 | // of the newly inserted elements. |
617 | // |
618 | // NOTE: this overload is for iterators that are "forward" category or better. |
619 | template <typename ForwardIterator, |
620 | EnableIfAtLeastForwardIterator<ForwardIterator> = 0> |
621 | iterator insert(const_iterator pos, ForwardIterator first, |
622 | ForwardIterator last) { |
623 | ABSL_HARDENING_ASSERT(pos >= begin()); |
624 | ABSL_HARDENING_ASSERT(pos <= end()); |
625 | |
626 | if (ABSL_PREDICT_TRUE(first != last)) { |
627 | return storage_.Insert(pos, |
628 | IteratorValueAdapter<A, ForwardIterator>(first), |
629 | std::distance(first, last)); |
630 | } else { |
631 | return const_cast<iterator>(pos); |
632 | } |
633 | } |
634 | |
635 | // Overload of `InlinedVector::insert(...)` that inserts the range [`first`, |
636 | // `last`) starting at `pos`, returning an `iterator` pointing to the first |
637 | // of the newly inserted elements. |
638 | // |
639 | // NOTE: this overload is for iterators that are "input" category. |
640 | template <typename InputIterator, |
641 | DisableIfAtLeastForwardIterator<InputIterator> = 0> |
642 | iterator insert(const_iterator pos, InputIterator first, InputIterator last) { |
643 | ABSL_HARDENING_ASSERT(pos >= begin()); |
644 | ABSL_HARDENING_ASSERT(pos <= end()); |
645 | |
646 | size_type index = std::distance(cbegin(), pos); |
647 | for (size_type i = index; first != last; ++i, static_cast<void>(++first)) { |
648 | insert(data() + i, *first); |
649 | } |
650 | |
651 | return iterator(data() + index); |
652 | } |
653 | |
654 | // `InlinedVector::emplace(...)` |
655 | // |
656 | // Constructs and inserts an element using `args...` in the inlined vector at |
657 | // `pos`, returning an `iterator` pointing to the newly emplaced element. |
658 | template <typename... Args> |
659 | iterator emplace(const_iterator pos, Args&&... args) { |
660 | ABSL_HARDENING_ASSERT(pos >= begin()); |
661 | ABSL_HARDENING_ASSERT(pos <= end()); |
662 | |
663 | value_type dealias(std::forward<Args>(args)...); |
664 | return storage_.Insert(pos, |
665 | IteratorValueAdapter<A, MoveIterator<A>>( |
666 | MoveIterator<A>(std::addressof(dealias))), |
667 | 1); |
668 | } |
669 | |
670 | // `InlinedVector::emplace_back(...)` |
671 | // |
672 | // Constructs and inserts an element using `args...` in the inlined vector at |
673 | // `end()`, returning a `reference` to the newly emplaced element. |
674 | template <typename... Args> |
675 | reference emplace_back(Args&&... args) { |
676 | return storage_.EmplaceBack(std::forward<Args>(args)...); |
677 | } |
678 | |
679 | // `InlinedVector::push_back(...)` |
680 | // |
681 | // Inserts a copy of `v` in the inlined vector at `end()`. |
682 | void push_back(const_reference v) { static_cast<void>(emplace_back(v)); } |
683 | |
684 | // Overload of `InlinedVector::push_back(...)` for inserting `v` at `end()` |
685 | // using move semantics. |
686 | void push_back(value_type&& v) { |
687 | static_cast<void>(emplace_back(std::move(v))); |
688 | } |
689 | |
690 | // `InlinedVector::pop_back()` |
691 | // |
692 | // Destroys the element at `back()`, reducing the size by `1`. |
693 | void pop_back() noexcept { |
694 | ABSL_HARDENING_ASSERT(!empty()); |
695 | |
696 | AllocatorTraits<A>::destroy(storage_.GetAllocator(), data() + (size() - 1)); |
697 | storage_.SubtractSize(1); |
698 | } |
699 | |
700 | // `InlinedVector::erase(...)` |
701 | // |
702 | // Erases the element at `pos`, returning an `iterator` pointing to where the |
703 | // erased element was located. |
704 | // |
705 | // NOTE: may return `end()`, which is not dereferencable. |
706 | iterator erase(const_iterator pos) { |
707 | ABSL_HARDENING_ASSERT(pos >= begin()); |
708 | ABSL_HARDENING_ASSERT(pos < end()); |
709 | |
710 | return storage_.Erase(pos, pos + 1); |
711 | } |
712 | |
713 | // Overload of `InlinedVector::erase(...)` that erases every element in the |
714 | // range [`from`, `to`), returning an `iterator` pointing to where the first |
715 | // erased element was located. |
716 | // |
717 | // NOTE: may return `end()`, which is not dereferencable. |
718 | iterator erase(const_iterator from, const_iterator to) { |
719 | ABSL_HARDENING_ASSERT(from >= begin()); |
720 | ABSL_HARDENING_ASSERT(from <= to); |
721 | ABSL_HARDENING_ASSERT(to <= end()); |
722 | |
723 | if (ABSL_PREDICT_TRUE(from != to)) { |
724 | return storage_.Erase(from, to); |
725 | } else { |
726 | return const_cast<iterator>(from); |
727 | } |
728 | } |
729 | |
730 | // `InlinedVector::clear()` |
731 | // |
732 | // Destroys all elements in the inlined vector, setting the size to `0` and |
733 | // deallocating any held memory. |
734 | void clear() noexcept { |
735 | inlined_vector_internal::DestroyAdapter<A>::DestroyElements( |
736 | storage_.GetAllocator(), data(), size()); |
737 | storage_.DeallocateIfAllocated(); |
738 | |
739 | storage_.SetInlinedSize(0); |
740 | } |
741 | |
742 | // `InlinedVector::reserve(...)` |
743 | // |
744 | // Ensures that there is enough room for at least `n` elements. |
745 | void reserve(size_type n) { storage_.Reserve(n); } |
746 | |
747 | // `InlinedVector::shrink_to_fit()` |
748 | // |
749 | // Attempts to reduce memory usage by moving elements to (or keeping elements |
750 | // in) the smallest available buffer sufficient for containing `size()` |
751 | // elements. |
752 | // |
753 | // If `size()` is sufficiently small, the elements will be moved into (or kept |
754 | // in) the inlined space. |
755 | void shrink_to_fit() { |
756 | if (storage_.GetIsAllocated()) { |
757 | storage_.ShrinkToFit(); |
758 | } |
759 | } |
760 | |
761 | // `InlinedVector::swap(...)` |
762 | // |
763 | // Swaps the contents of the inlined vector with `other`. |
764 | void swap(InlinedVector& other) { |
765 | if (ABSL_PREDICT_TRUE(this != std::addressof(other))) { |
766 | storage_.Swap(std::addressof(other.storage_)); |
767 | } |
768 | } |
769 | |
770 | private: |
771 | template <typename H, typename TheT, size_t TheN, typename TheA> |
772 | friend H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a); |
773 | |
774 | Storage storage_; |
775 | }; |
776 | |
777 | // ----------------------------------------------------------------------------- |
778 | // InlinedVector Non-Member Functions |
779 | // ----------------------------------------------------------------------------- |
780 | |
781 | // `swap(...)` |
782 | // |
783 | // Swaps the contents of two inlined vectors. |
784 | template <typename T, size_t N, typename A> |
785 | void swap(absl::InlinedVector<T, N, A>& a, |
786 | absl::InlinedVector<T, N, A>& b) noexcept(noexcept(a.swap(b))) { |
787 | a.swap(b); |
788 | } |
789 | |
790 | // `operator==(...)` |
791 | // |
792 | // Tests for value-equality of two inlined vectors. |
793 | template <typename T, size_t N, typename A> |
794 | bool operator==(const absl::InlinedVector<T, N, A>& a, |
795 | const absl::InlinedVector<T, N, A>& b) { |
796 | auto a_data = a.data(); |
797 | auto b_data = b.data(); |
798 | return absl::equal(a_data, a_data + a.size(), b_data, b_data + b.size()); |
799 | } |
800 | |
801 | // `operator!=(...)` |
802 | // |
803 | // Tests for value-inequality of two inlined vectors. |
804 | template <typename T, size_t N, typename A> |
805 | bool operator!=(const absl::InlinedVector<T, N, A>& a, |
806 | const absl::InlinedVector<T, N, A>& b) { |
807 | return !(a == b); |
808 | } |
809 | |
810 | // `operator<(...)` |
811 | // |
812 | // Tests whether the value of an inlined vector is less than the value of |
813 | // another inlined vector using a lexicographical comparison algorithm. |
814 | template <typename T, size_t N, typename A> |
815 | bool operator<(const absl::InlinedVector<T, N, A>& a, |
816 | const absl::InlinedVector<T, N, A>& b) { |
817 | auto a_data = a.data(); |
818 | auto b_data = b.data(); |
819 | return std::lexicographical_compare(a_data, a_data + a.size(), b_data, |
820 | b_data + b.size()); |
821 | } |
822 | |
823 | // `operator>(...)` |
824 | // |
825 | // Tests whether the value of an inlined vector is greater than the value of |
826 | // another inlined vector using a lexicographical comparison algorithm. |
827 | template <typename T, size_t N, typename A> |
828 | bool operator>(const absl::InlinedVector<T, N, A>& a, |
829 | const absl::InlinedVector<T, N, A>& b) { |
830 | return b < a; |
831 | } |
832 | |
833 | // `operator<=(...)` |
834 | // |
835 | // Tests whether the value of an inlined vector is less than or equal to the |
836 | // value of another inlined vector using a lexicographical comparison algorithm. |
837 | template <typename T, size_t N, typename A> |
838 | bool operator<=(const absl::InlinedVector<T, N, A>& a, |
839 | const absl::InlinedVector<T, N, A>& b) { |
840 | return !(b < a); |
841 | } |
842 | |
843 | // `operator>=(...)` |
844 | // |
845 | // Tests whether the value of an inlined vector is greater than or equal to the |
846 | // value of another inlined vector using a lexicographical comparison algorithm. |
847 | template <typename T, size_t N, typename A> |
848 | bool operator>=(const absl::InlinedVector<T, N, A>& a, |
849 | const absl::InlinedVector<T, N, A>& b) { |
850 | return !(a < b); |
851 | } |
852 | |
853 | // `AbslHashValue(...)` |
854 | // |
855 | // Provides `absl::Hash` support for `absl::InlinedVector`. It is uncommon to |
856 | // call this directly. |
857 | template <typename H, typename T, size_t N, typename A> |
858 | H AbslHashValue(H h, const absl::InlinedVector<T, N, A>& a) { |
859 | auto size = a.size(); |
860 | return H::combine(H::combine_contiguous(std::move(h), a.data(), size), size); |
861 | } |
862 | |
863 | ABSL_NAMESPACE_END |
864 | } // namespace absl |
865 | |
866 | #endif // ABSL_CONTAINER_INLINED_VECTOR_H_ |
867 | |