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
56namespace absl {
57ABSL_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`.
68template <typename T, size_t N, typename A = std::allocator<T>>
69class 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.
784template <typename T, size_t N, typename A>
785void 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.
793template <typename T, size_t N, typename A>
794bool 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.
804template <typename T, size_t N, typename A>
805bool 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.
814template <typename T, size_t N, typename A>
815bool 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.
827template <typename T, size_t N, typename A>
828bool 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.
837template <typename T, size_t N, typename A>
838bool 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.
847template <typename T, size_t N, typename A>
848bool 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.
857template <typename H, typename T, size_t N, typename A>
858H 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
863ABSL_NAMESPACE_END
864} // namespace absl
865
866#endif // ABSL_CONTAINER_INLINED_VECTOR_H_
867