inlined_vector.h
Go to the documentation of this file.
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 <cassert>
40 #include <cstddef>
41 #include <cstdlib>
42 #include <cstring>
43 #include <initializer_list>
44 #include <iterator>
45 #include <memory>
46 #include <type_traits>
47 #include <utility>
48 
51 #include "absl/base/optimization.h"
52 #include "absl/base/port.h"
54 #include "absl/memory/memory.h"
55 
56 namespace absl {
57 // -----------------------------------------------------------------------------
58 // InlinedVector
59 // -----------------------------------------------------------------------------
60 //
61 // An `absl::InlinedVector` is designed to be a drop-in replacement for
62 // `std::vector` for use cases where the vector's size is sufficiently small
63 // that it can be inlined. If the inlined vector does grow beyond its estimated
64 // capacity, it will trigger an initial allocation on the heap, and will behave
65 // as a `std:vector`. The API of the `absl::InlinedVector` within this file is
66 // designed to cover the same API footprint as covered by `std::vector`.
67 template <typename T, size_t N, typename A = std::allocator<T>>
69  static_assert(
70  N > 0, "InlinedVector cannot be instantiated with `0` inlined elements.");
71 
74 
75  template <typename Iterator>
78 
79  template <typename Iterator>
82 
84 
85  public:
87  using value_type = typename Storage::value_type;
88  using pointer = typename Storage::pointer;
90  using reference = typename Storage::reference;
92  using size_type = typename Storage::size_type;
94  using iterator = typename Storage::iterator;
98 
99  // ---------------------------------------------------------------------------
100  // InlinedVector Constructors and Destructor
101  // ---------------------------------------------------------------------------
102 
103  // Creates an empty inlined vector with a default initialized allocator.
104  InlinedVector() noexcept(noexcept(allocator_type()))
105  : storage_(allocator_type()) {}
106 
107  // Creates an empty inlined vector with a specified allocator.
108  explicit InlinedVector(const allocator_type& alloc) noexcept
109  : storage_(alloc) {}
110 
111  // Creates an inlined vector with `n` copies of `value_type()`.
114  : storage_(alloc) {
115  InitAssign(n);
116  }
117 
118  // Creates an inlined vector with `n` copies of `v`.
121  : storage_(alloc) {
122  InitAssign(n, v);
123  }
124 
125  // Creates an inlined vector of copies of the values in `list`.
126  InlinedVector(std::initializer_list<value_type> list,
128  : storage_(alloc) {
129  AppendForwardRange(list.begin(), list.end());
130  }
131 
132  // Creates an inlined vector with elements constructed from the provided
133  // forward iterator range [`first`, `last`).
134  //
135  // NOTE: The `enable_if` prevents ambiguous interpretation between a call to
136  // this constructor with two integral arguments and a call to the above
137  // `InlinedVector(size_type, const_reference)` constructor.
138  template <typename ForwardIterator,
140  InlinedVector(ForwardIterator first, ForwardIterator last,
142  : storage_(alloc) {
143  AppendForwardRange(first, last);
144  }
145 
146  // Creates an inlined vector with elements constructed from the provided input
147  // iterator range [`first`, `last`).
148  template <typename InputIterator,
150  InlinedVector(InputIterator first, InputIterator last,
152  : storage_(alloc) {
153  std::copy(first, last, std::back_inserter(*this));
154  }
155 
156  // Creates a copy of an `other` inlined vector using `other`'s allocator.
158  : InlinedVector(other, *other.storage_.GetAllocPtr()) {}
159 
160  // Creates a copy of an `other` inlined vector using a specified allocator.
162  : storage_(alloc) {
163  reserve(other.size());
164  if (storage_.GetIsAllocated()) {
165  UninitializedCopy(other.begin(), other.end(),
167  storage_.SetAllocatedSize(other.size());
168  } else {
169  UninitializedCopy(other.begin(), other.end(), storage_.GetInlinedData());
170  storage_.SetInlinedSize(other.size());
171  }
172  }
173 
174  // Creates an inlined vector by moving in the contents of an `other` inlined
175  // vector without performing any allocations. If `other` contains allocated
176  // memory, the newly-created instance will take ownership of that memory
177  // (leaving `other` empty). However, if `other` does not contain allocated
178  // memory (i.e. is inlined), the new inlined vector will perform element-wise
179  // move construction of `other`'s elements.
180  //
181  // NOTE: since no allocation is performed for the inlined vector in either
182  // case, the `noexcept(...)` specification depends on whether moving the
183  // underlying objects can throw. We assume:
184  // a) Move constructors should only throw due to allocation failure.
185  // b) If `value_type`'s move constructor allocates, it uses the same
186  // allocation function as the `InlinedVector`'s allocator. Thus, the move
187  // constructor is non-throwing if the allocator is non-throwing or
188  // `value_type`'s move constructor is specified as `noexcept`.
189  InlinedVector(InlinedVector&& other) noexcept(
191  std::is_nothrow_move_constructible<value_type>::value)
192  : storage_(*other.storage_.GetAllocPtr()) {
193  if (other.storage_.GetIsAllocated()) {
194  // We can just steal the underlying buffer from the source.
195  // That leaves the source empty, so we clear its size.
196  storage_.SetAllocatedData(other.storage_.GetAllocatedData());
197  storage_.SetAllocatedCapacity(other.storage_.GetAllocatedCapacity());
198  storage_.SetAllocatedSize(other.size());
199  other.storage_.SetInlinedSize(0);
200  } else {
202  std::make_move_iterator(other.storage_.GetInlinedData()),
203  std::make_move_iterator(other.storage_.GetInlinedData() +
204  other.size()),
206  storage_.SetInlinedSize(other.size());
207  }
208  }
209 
210  // Creates an inlined vector by moving in the contents of an `other` inlined
211  // vector, performing allocations with the specified `alloc` allocator. If
212  // `other`'s allocator is not equal to `alloc` and `other` contains allocated
213  // memory, this move constructor will create a new allocation.
214  //
215  // NOTE: since allocation is performed in this case, this constructor can
216  // only be `noexcept` if the specified allocator is also `noexcept`. If this
217  // is the case, or if `other` contains allocated memory, this constructor
218  // performs element-wise move construction of its contents.
219  //
220  // Only in the case where `other`'s allocator is equal to `alloc` and `other`
221  // contains allocated memory will the newly created inlined vector take
222  // ownership of `other`'s allocated memory.
223  InlinedVector(InlinedVector&& other, const allocator_type& alloc) noexcept(
225  : storage_(alloc) {
226  if (other.storage_.GetIsAllocated()) {
227  if (*storage_.GetAllocPtr() == *other.storage_.GetAllocPtr()) {
228  // We can just steal the allocation from the source.
229  storage_.SetAllocatedSize(other.size());
230  storage_.SetAllocatedData(other.storage_.GetAllocatedData());
231  storage_.SetAllocatedCapacity(other.storage_.GetAllocatedCapacity());
232  other.storage_.SetInlinedSize(0);
233  } else {
234  // We need to use our own allocator
235  reserve(other.size());
236  UninitializedCopy(std::make_move_iterator(other.begin()),
237  std::make_move_iterator(other.end()),
239  storage_.SetAllocatedSize(other.size());
240  }
241  } else {
243  std::make_move_iterator(other.storage_.GetInlinedData()),
244  std::make_move_iterator(other.storage_.GetInlinedData() +
245  other.size()),
247  storage_.SetInlinedSize(other.size());
248  }
249  }
250 
252 
253  // ---------------------------------------------------------------------------
254  // InlinedVector Member Accessors
255  // ---------------------------------------------------------------------------
256 
257  // `InlinedVector::empty()`
258  //
259  // Checks if the inlined vector has no elements.
260  bool empty() const noexcept { return !size(); }
261 
262  // `InlinedVector::size()`
263  //
264  // Returns the number of elements in the inlined vector.
265  size_type size() const noexcept { return storage_.GetSize(); }
266 
267  // `InlinedVector::max_size()`
268  //
269  // Returns the maximum number of elements the vector can hold.
270  size_type max_size() const noexcept {
271  // One bit of the size storage is used to indicate whether the inlined
272  // vector is allocated. As a result, the maximum size of the container that
273  // we can express is half of the max for `size_type`.
274  return (std::numeric_limits<size_type>::max)() / 2;
275  }
276 
277  // `InlinedVector::capacity()`
278  //
279  // Returns the number of elements that can be stored in the inlined vector
280  // without requiring a reallocation of underlying memory.
281  //
282  // NOTE: For most inlined vectors, `capacity()` should equal the template
283  // parameter `N`. For inlined vectors which exceed this capacity, they
284  // will no longer be inlined and `capacity()` will equal its capacity on the
285  // allocated heap.
286  size_type capacity() const noexcept {
288  : static_cast<size_type>(N);
289  }
290 
291  // `InlinedVector::data()`
292  //
293  // Returns a `pointer` to elements of the inlined vector. This pointer can be
294  // used to access and modify the contained elements.
295  // Only results within the range [`0`, `size()`) are defined.
296  pointer data() noexcept {
299  }
300 
301  // Overload of `InlinedVector::data()` to return a `const_pointer` to elements
302  // of the inlined vector. This pointer can be used to access (but not modify)
303  // the contained elements.
304  const_pointer data() const noexcept {
307  }
308 
309  // `InlinedVector::operator[]()`
310  //
311  // Returns a `reference` to the `i`th element of the inlined vector using the
312  // array operator.
314  assert(i < size());
315  return data()[i];
316  }
317 
318  // Overload of `InlinedVector::operator[]()` to return a `const_reference` to
319  // the `i`th element of the inlined vector.
321  assert(i < size());
322  return data()[i];
323  }
324 
325  // `InlinedVector::at()`
326  //
327  // Returns a `reference` to the `i`th element of the inlined vector.
329  if (ABSL_PREDICT_FALSE(i >= size())) {
331  "`InlinedVector::at(size_type)` failed bounds check");
332  }
333  return data()[i];
334  }
335 
336  // Overload of `InlinedVector::at()` to return a `const_reference` to the
337  // `i`th element of the inlined vector.
339  if (ABSL_PREDICT_FALSE(i >= size())) {
341  "`InlinedVector::at(size_type) const` failed bounds check");
342  }
343  return data()[i];
344  }
345 
346  // `InlinedVector::front()`
347  //
348  // Returns a `reference` to the first element of the inlined vector.
350  assert(!empty());
351  return at(0);
352  }
353 
354  // Overload of `InlinedVector::front()` returns a `const_reference` to the
355  // first element of the inlined vector.
357  assert(!empty());
358  return at(0);
359  }
360 
361  // `InlinedVector::back()`
362  //
363  // Returns a `reference` to the last element of the inlined vector.
365  assert(!empty());
366  return at(size() - 1);
367  }
368 
369  // Overload of `InlinedVector::back()` to return a `const_reference` to the
370  // last element of the inlined vector.
372  assert(!empty());
373  return at(size() - 1);
374  }
375 
376  // `InlinedVector::begin()`
377  //
378  // Returns an `iterator` to the beginning of the inlined vector.
379  iterator begin() noexcept { return data(); }
380 
381  // Overload of `InlinedVector::begin()` to return a `const_iterator` to
382  // the beginning of the inlined vector.
383  const_iterator begin() const noexcept { return data(); }
384 
385  // `InlinedVector::end()`
386  //
387  // Returns an `iterator` to the end of the inlined vector.
388  iterator end() noexcept { return data() + size(); }
389 
390  // Overload of `InlinedVector::end()` to return a `const_iterator` to the
391  // end of the inlined vector.
392  const_iterator end() const noexcept { return data() + size(); }
393 
394  // `InlinedVector::cbegin()`
395  //
396  // Returns a `const_iterator` to the beginning of the inlined vector.
397  const_iterator cbegin() const noexcept { return begin(); }
398 
399  // `InlinedVector::cend()`
400  //
401  // Returns a `const_iterator` to the end of the inlined vector.
402  const_iterator cend() const noexcept { return end(); }
403 
404  // `InlinedVector::rbegin()`
405  //
406  // Returns a `reverse_iterator` from the end of the inlined vector.
407  reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
408 
409  // Overload of `InlinedVector::rbegin()` to return a
410  // `const_reverse_iterator` from the end of the inlined vector.
411  const_reverse_iterator rbegin() const noexcept {
412  return const_reverse_iterator(end());
413  }
414 
415  // `InlinedVector::rend()`
416  //
417  // Returns a `reverse_iterator` from the beginning of the inlined vector.
418  reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
419 
420  // Overload of `InlinedVector::rend()` to return a `const_reverse_iterator`
421  // from the beginning of the inlined vector.
422  const_reverse_iterator rend() const noexcept {
423  return const_reverse_iterator(begin());
424  }
425 
426  // `InlinedVector::crbegin()`
427  //
428  // Returns a `const_reverse_iterator` from the end of the inlined vector.
429  const_reverse_iterator crbegin() const noexcept { return rbegin(); }
430 
431  // `InlinedVector::crend()`
432  //
433  // Returns a `const_reverse_iterator` from the beginning of the inlined
434  // vector.
435  const_reverse_iterator crend() const noexcept { return rend(); }
436 
437  // `InlinedVector::get_allocator()`
438  //
439  // Returns a copy of the allocator of the inlined vector.
441 
442  // ---------------------------------------------------------------------------
443  // InlinedVector Member Mutators
444  // ---------------------------------------------------------------------------
445 
446  // `InlinedVector::operator=()`
447  //
448  // Replaces the contents of the inlined vector with copies of the elements in
449  // the provided `std::initializer_list`.
450  InlinedVector& operator=(std::initializer_list<value_type> list) {
451  assign(list.begin(), list.end());
452  return *this;
453  }
454 
455  // Overload of `InlinedVector::operator=()` to replace the contents of the
456  // inlined vector with the contents of `other`.
458  if (ABSL_PREDICT_TRUE(this != std::addressof(other))) {
459  const_pointer other_data = other.data();
460  assign(other_data, other_data + other.size());
461  }
462  return *this;
463  }
464 
465  // Overload of `InlinedVector::operator=()` to replace the contents of the
466  // inlined vector with the contents of `other`.
467  //
468  // NOTE: As a result of calling this overload, `other` may be empty or it's
469  // contents may be left in a moved-from state.
471  if (ABSL_PREDICT_FALSE(this == std::addressof(other))) return *this;
472 
473  if (other.storage_.GetIsAllocated()) {
474  clear();
475  storage_.SetAllocatedSize(other.size());
476  storage_.SetAllocatedData(other.storage_.GetAllocatedData());
477  storage_.SetAllocatedCapacity(other.storage_.GetAllocatedCapacity());
478  other.storage_.SetInlinedSize(0);
479  } else {
480  if (storage_.GetIsAllocated()) clear();
481  // Both are inlined now.
482  if (size() < other.size()) {
483  auto mid = std::make_move_iterator(other.begin() + size());
484  std::copy(std::make_move_iterator(other.begin()), mid, begin());
485  UninitializedCopy(mid, std::make_move_iterator(other.end()), end());
486  } else {
487  auto new_end = std::copy(std::make_move_iterator(other.begin()),
488  std::make_move_iterator(other.end()), begin());
489  Destroy(new_end, end());
490  }
491  storage_.SetInlinedSize(other.size());
492  }
493  return *this;
494  }
495 
496  // `InlinedVector::assign()`
497  //
498  // Replaces the contents of the inlined vector with `n` copies of `v`.
500  if (n <= size()) { // Possibly shrink
501  std::fill_n(begin(), n, v);
502  erase(begin() + n, end());
503  return;
504  }
505  // Grow
506  reserve(n);
507  std::fill_n(begin(), size(), v);
508  if (storage_.GetIsAllocated()) {
512  } else {
514  storage_.GetInlinedData() + n, v);
516  }
517  }
518 
519  // Overload of `InlinedVector::assign()` to replace the contents of the
520  // inlined vector with copies of the values in the provided
521  // `std::initializer_list`.
522  void assign(std::initializer_list<value_type> list) {
523  assign(list.begin(), list.end());
524  }
525 
526  // Overload of `InlinedVector::assign()` to replace the contents of the
527  // inlined vector with the forward iterator range [`first`, `last`).
528  template <typename ForwardIterator,
529  EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr>
530  void assign(ForwardIterator first, ForwardIterator last) {
531  auto length = std::distance(first, last);
532 
533  // Prefer reassignment to copy construction for elements.
534  if (static_cast<size_type>(length) <= size()) {
535  erase(std::copy(first, last, begin()), end());
536  return;
537  }
538 
539  reserve(length);
540  iterator out = begin();
541  for (; out != end(); ++first, ++out) *out = *first;
542  if (storage_.GetIsAllocated()) {
543  UninitializedCopy(first, last, out);
545  } else {
546  UninitializedCopy(first, last, out);
548  }
549  }
550 
551  // Overload of `InlinedVector::assign()` to replace the contents of the
552  // inlined vector with the input iterator range [`first`, `last`).
553  template <typename InputIterator,
554  DisableIfAtLeastForwardIterator<InputIterator>* = nullptr>
555  void assign(InputIterator first, InputIterator last) {
556  size_type assign_index = 0;
557  for (; (assign_index < size()) && (first != last);
558  static_cast<void>(++assign_index), static_cast<void>(++first)) {
559  *(data() + assign_index) = *first;
560  }
561  erase(data() + assign_index, data() + size());
562  std::copy(first, last, std::back_inserter(*this));
563  }
564 
565  // `InlinedVector::resize()`
566  //
567  // Resizes the inlined vector to contain `n` elements. If `n` is smaller than
568  // the inlined vector's current size, extra elements are destroyed. If `n` is
569  // larger than the initial size, new elements are value-initialized.
570  void resize(size_type n) {
571  size_type s = size();
572  if (n < s) {
573  erase(begin() + n, end());
574  return;
575  }
576  reserve(n);
577  assert(capacity() >= n);
578 
579  // Fill new space with elements constructed in-place.
580  if (storage_.GetIsAllocated()) {
584  } else {
588  }
589  }
590 
591  // Overload of `InlinedVector::resize()` to resize the inlined vector to
592  // contain `n` elements where, if `n` is larger than `size()`, the new values
593  // will be copy-constructed from `v`.
595  size_type s = size();
596  if (n < s) {
597  erase(begin() + n, end());
598  return;
599  }
600  reserve(n);
601  assert(capacity() >= n);
602 
603  // Fill new space with copies of `v`.
604  if (storage_.GetIsAllocated()) {
608  } else {
610  storage_.GetInlinedData() + n, v);
612  }
613  }
614 
615  // `InlinedVector::insert()`
616  //
617  // Copies `v` into `pos`, returning an `iterator` pointing to the newly
618  // inserted element.
620  return emplace(pos, v);
621  }
622 
623  // Overload of `InlinedVector::insert()` for moving `v` into `pos`, returning
624  // an iterator pointing to the newly inserted element.
626  return emplace(pos, std::move(v));
627  }
628 
629  // Overload of `InlinedVector::insert()` for inserting `n` contiguous copies
630  // of `v` starting at `pos`. Returns an `iterator` pointing to the first of
631  // the newly inserted elements.
633  return InsertWithCount(pos, n, v);
634  }
635 
636  // Overload of `InlinedVector::insert()` for copying the contents of the
637  // `std::initializer_list` into the vector starting at `pos`. Returns an
638  // `iterator` pointing to the first of the newly inserted elements.
639  iterator insert(const_iterator pos, std::initializer_list<value_type> list) {
640  return insert(pos, list.begin(), list.end());
641  }
642 
643  // Overload of `InlinedVector::insert()` for inserting elements constructed
644  // from the forward iterator range [`first`, `last`). Returns an `iterator`
645  // pointing to the first of the newly inserted elements.
646  //
647  // NOTE: The `enable_if` is intended to disambiguate the two three-argument
648  // overloads of `insert()`.
649  template <typename ForwardIterator,
650  EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr>
651  iterator insert(const_iterator pos, ForwardIterator first,
652  ForwardIterator last) {
653  return InsertWithForwardRange(pos, first, last);
654  }
655 
656  // Overload of `InlinedVector::insert()` for inserting elements constructed
657  // from the input iterator range [`first`, `last`). Returns an `iterator`
658  // pointing to the first of the newly inserted elements.
659  template <typename InputIterator,
660  DisableIfAtLeastForwardIterator<InputIterator>* = nullptr>
661  iterator insert(const_iterator pos, InputIterator first, InputIterator last) {
662  size_type initial_insert_index = std::distance(cbegin(), pos);
663  for (size_type insert_index = initial_insert_index; first != last;
664  static_cast<void>(++insert_index), static_cast<void>(++first)) {
665  insert(data() + insert_index, *first);
666  }
667  return iterator(data() + initial_insert_index);
668  }
669 
670  // `InlinedVector::emplace()`
671  //
672  // Constructs and inserts an object in the inlined vector at the given `pos`,
673  // returning an `iterator` pointing to the newly emplaced element.
674  template <typename... Args>
675  iterator emplace(const_iterator pos, Args&&... args) {
676  assert(pos >= begin());
677  assert(pos <= end());
678  if (ABSL_PREDICT_FALSE(pos == end())) {
679  emplace_back(std::forward<Args>(args)...);
680  return end() - 1;
681  }
682 
683  T new_t = T(std::forward<Args>(args)...);
684 
685  auto range = ShiftRight(pos, 1);
686  if (range.first == range.second) {
687  // constructing into uninitialized memory
688  Construct(range.first, std::move(new_t));
689  } else {
690  // assigning into moved-from object
691  *range.first = T(std::move(new_t));
692  }
693 
694  return range.first;
695  }
696 
697  // `InlinedVector::emplace_back()`
698  //
699  // Constructs and appends a new element to the end of the inlined vector,
700  // returning a `reference` to the emplaced element.
701  template <typename... Args>
702  reference emplace_back(Args&&... args) {
703  size_type s = size();
704  if (ABSL_PREDICT_FALSE(s == capacity())) {
705  return GrowAndEmplaceBack(std::forward<Args>(args)...);
706  }
707  pointer space;
708  if (storage_.GetIsAllocated()) {
709  storage_.SetAllocatedSize(s + 1);
710  space = storage_.GetAllocatedData();
711  } else {
712  storage_.SetInlinedSize(s + 1);
713  space = storage_.GetInlinedData();
714  }
715  return Construct(space + s, std::forward<Args>(args)...);
716  }
717 
718  // `InlinedVector::push_back()`
719  //
720  // Appends a copy of `v` to the end of the inlined vector.
721  void push_back(const_reference v) { static_cast<void>(emplace_back(v)); }
722 
723  // Overload of `InlinedVector::push_back()` for moving `v` into a newly
724  // appended element.
726  static_cast<void>(emplace_back(std::move(v)));
727  }
728 
729  // `InlinedVector::pop_back()`
730  //
731  // Destroys the element at the end of the inlined vector and shrinks the size
732  // by `1` (unless the inlined vector is empty, in which case this is a no-op).
733  void pop_back() noexcept {
734  assert(!empty());
735  size_type s = size();
736  if (storage_.GetIsAllocated()) {
738  storage_.GetAllocatedData() + s);
739  storage_.SetAllocatedSize(s - 1);
740  } else {
742  storage_.SetInlinedSize(s - 1);
743  }
744  }
745 
746  // `InlinedVector::erase()`
747  //
748  // Erases the element at `pos` of the inlined vector, returning an `iterator`
749  // pointing to the first element following the erased element.
750  //
751  // NOTE: May return the end iterator, which is not dereferencable.
753  assert(pos >= begin());
754  assert(pos < end());
755 
756  iterator position = const_cast<iterator>(pos);
757  std::move(position + 1, end(), position);
758  pop_back();
759  return position;
760  }
761 
762  // Overload of `InlinedVector::erase()` for erasing all elements in the
763  // range [`from`, `to`) in the inlined vector. Returns an `iterator` pointing
764  // to the first element following the range erased or the end iterator if `to`
765  // was the end iterator.
767  assert(begin() <= from);
768  assert(from <= to);
769  assert(to <= end());
770 
771  iterator range_start = const_cast<iterator>(from);
772  iterator range_end = const_cast<iterator>(to);
773 
774  size_type s = size();
775  ptrdiff_t erase_gap = std::distance(range_start, range_end);
776  if (erase_gap > 0) {
777  pointer space;
778  if (storage_.GetIsAllocated()) {
779  space = storage_.GetAllocatedData();
780  storage_.SetAllocatedSize(s - erase_gap);
781  } else {
782  space = storage_.GetInlinedData();
783  storage_.SetInlinedSize(s - erase_gap);
784  }
785  std::move(range_end, space + s, range_start);
786  Destroy(space + s - erase_gap, space + s);
787  }
788  return range_start;
789  }
790 
791  // `InlinedVector::clear()`
792  //
793  // Destroys all elements in the inlined vector, sets the size of `0` and
794  // deallocates the heap allocation if the inlined vector was allocated.
795  void clear() noexcept {
796  const bool is_allocated = storage_.GetIsAllocated();
797  pointer the_data =
798  is_allocated ? storage_.GetAllocatedData() : storage_.GetInlinedData();
800  storage_.GetSize());
802  if (is_allocated) {
803  AllocatorTraits::deallocate(*storage_.GetAllocPtr(), the_data,
805  }
806  }
807 
808  // `InlinedVector::reserve()`
809  //
810  // Enlarges the underlying representation of the inlined vector so it can hold
811  // at least `n` elements. This method does not change `size()` or the actual
812  // contents of the vector.
813  //
814  // NOTE: If `n` does not exceed `capacity()`, `reserve()` will have no
815  // effects. Otherwise, `reserve()` will reallocate, performing an n-time
816  // element-wise move of everything contained.
817  void reserve(size_type n) {
818  if (n > capacity()) {
819  // Make room for new elements
820  EnlargeBy(n - size());
821  }
822  }
823 
824  // `InlinedVector::shrink_to_fit()`
825  //
826  // Reduces memory usage by freeing unused memory. After this call, calls to
827  // `capacity()` will be equal to `max(N, size())`.
828  //
829  // If `size() <= N` and the elements are currently stored on the heap, they
830  // will be moved to the inlined storage and the heap memory will be
831  // deallocated.
832  //
833  // If `size() > N` and `size() < capacity()` the elements will be moved to a
834  // smaller heap allocation.
835  void shrink_to_fit() {
836  const auto s = size();
838  return;
839 
840  if (s <= N) {
841  // Move the elements to the inlined storage.
842  // We have to do this using a temporary, because `inlined_storage` and
843  // `allocation_storage` are in a union field.
844  auto temp = std::move(*this);
845  assign(std::make_move_iterator(temp.begin()),
846  std::make_move_iterator(temp.end()));
847  return;
848  }
849 
850  // Reallocate storage and move elements.
851  // We can't simply use the same approach as above, because `assign()` would
852  // call into `reserve()` internally and reserve larger capacity than we need
853  pointer new_data = AllocatorTraits::allocate(*storage_.GetAllocPtr(), s);
854  UninitializedCopy(std::make_move_iterator(storage_.GetAllocatedData()),
855  std::make_move_iterator(storage_.GetAllocatedData() + s),
856  new_data);
857  ResetAllocation(new_data, s, s);
858  }
859 
860  // `InlinedVector::swap()`
861  //
862  // Swaps the contents of this inlined vector with the contents of `other`.
863  void swap(InlinedVector& other) {
864  if (ABSL_PREDICT_FALSE(this == std::addressof(other))) return;
865 
866  SwapImpl(other);
867  }
868 
869  private:
870  template <typename H, typename TheT, size_t TheN, typename TheA>
872 
873  void ResetAllocation(pointer new_data, size_type new_capacity,
874  size_type new_size) {
875  if (storage_.GetIsAllocated()) {
878  assert(begin() == storage_.GetAllocatedData());
879  AllocatorTraits::deallocate(*storage_.GetAllocPtr(),
882  } else {
884  }
885 
886  storage_.SetAllocatedData(new_data);
887  storage_.SetAllocatedCapacity(new_capacity);
888  storage_.SetAllocatedSize(new_size);
889  }
890 
891  template <typename... Args>
892  reference Construct(pointer p, Args&&... args) {
894  *storage_.GetAllocPtr(), p, std::forward<Args>(args)...);
895  return *p;
896  }
897 
898  template <typename Iterator>
899  void UninitializedCopy(Iterator src, Iterator src_last, pointer dst) {
900  for (; src != src_last; ++dst, ++src) Construct(dst, *src);
901  }
902 
903  template <typename... Args>
904  void UninitializedFill(pointer dst, pointer dst_last, const Args&... args) {
905  for (; dst != dst_last; ++dst) Construct(dst, args...);
906  }
907 
908  // Destroy [`from`, `to`) in place.
910  for (pointer cur = from; cur != to; ++cur) {
912  cur);
913  }
914 #if !defined(NDEBUG)
915  // Overwrite unused memory with `0xab` so we can catch uninitialized usage.
916  // Cast to `void*` to tell the compiler that we don't care that we might be
917  // scribbling on a vtable pointer.
918  if (from != to) {
919  auto len = sizeof(value_type) * std::distance(from, to);
920  std::memset(reinterpret_cast<void*>(from), 0xab, len);
921  }
922 #endif // !defined(NDEBUG)
923  }
924 
925  // Enlarge the underlying representation so we can store `size_ + delta` elems
926  // in allocated space. The size is not changed, and any newly added memory is
927  // not initialized.
928  void EnlargeBy(size_type delta) {
929  const size_type s = size();
930  assert(s <= capacity());
931 
932  size_type target = (std::max)(static_cast<size_type>(N), s + delta);
933 
934  // Compute new capacity by repeatedly doubling current capacity
935  // TODO(psrc): Check and avoid overflow?
936  size_type new_capacity = capacity();
937  while (new_capacity < target) {
938  new_capacity <<= 1;
939  }
940 
941  pointer new_data =
942  AllocatorTraits::allocate(*storage_.GetAllocPtr(), new_capacity);
943 
944  UninitializedCopy(std::make_move_iterator(data()),
945  std::make_move_iterator(data() + s), new_data);
946 
947  ResetAllocation(new_data, new_capacity, s);
948  }
949 
950  // Shift all elements from `position` to `end()` by `n` places to the right.
951  // If the vector needs to be enlarged, memory will be allocated.
952  // Returns `iterator`s pointing to the start of the previously-initialized
953  // portion and the start of the uninitialized portion of the created gap.
954  // The number of initialized spots is `pair.second - pair.first`. The number
955  // of raw spots is `n - (pair.second - pair.first)`.
956  //
957  // Updates the size of the InlinedVector internally.
958  std::pair<iterator, iterator> ShiftRight(const_iterator position,
959  size_type n) {
960  iterator start_used = const_cast<iterator>(position);
961  iterator start_raw = const_cast<iterator>(position);
962  size_type s = size();
963  size_type required_size = s + n;
964 
965  if (required_size > capacity()) {
966  // Compute new capacity by repeatedly doubling current capacity
967  size_type new_capacity = capacity();
968  while (new_capacity < required_size) {
969  new_capacity <<= 1;
970  }
971  // Move everyone into the new allocation, leaving a gap of `n` for the
972  // requested shift.
973  pointer new_data =
974  AllocatorTraits::allocate(*storage_.GetAllocPtr(), new_capacity);
975  size_type index = position - begin();
976  UninitializedCopy(std::make_move_iterator(data()),
977  std::make_move_iterator(data() + index), new_data);
978  UninitializedCopy(std::make_move_iterator(data() + index),
979  std::make_move_iterator(data() + s),
980  new_data + index + n);
981  ResetAllocation(new_data, new_capacity, s);
982 
983  // New allocation means our iterator is invalid, so we'll recalculate.
984  // Since the entire gap is in new space, there's no used space to reuse.
985  start_raw = begin() + index;
986  start_used = start_raw;
987  } else {
988  // If we had enough space, it's a two-part move. Elements going into
989  // previously-unoccupied space need an `UninitializedCopy()`. Elements
990  // going into a previously-occupied space are just a `std::move()`.
991  iterator pos = const_cast<iterator>(position);
992  iterator raw_space = end();
993  size_type slots_in_used_space = raw_space - pos;
994  size_type new_elements_in_used_space = (std::min)(n, slots_in_used_space);
995  size_type new_elements_in_raw_space = n - new_elements_in_used_space;
996  size_type old_elements_in_used_space =
997  slots_in_used_space - new_elements_in_used_space;
998 
1000  std::make_move_iterator(pos + old_elements_in_used_space),
1001  std::make_move_iterator(raw_space),
1002  raw_space + new_elements_in_raw_space);
1003  std::move_backward(pos, pos + old_elements_in_used_space, raw_space);
1004 
1005  // If the gap is entirely in raw space, the used space starts where the
1006  // raw space starts, leaving no elements in used space. If the gap is
1007  // entirely in used space, the raw space starts at the end of the gap,
1008  // leaving all elements accounted for within the used space.
1009  start_used = pos;
1010  start_raw = pos + new_elements_in_used_space;
1011  }
1012  storage_.AddSize(n);
1013  return std::make_pair(start_used, start_raw);
1014  }
1015 
1016  template <typename... Args>
1017  reference GrowAndEmplaceBack(Args&&... args) {
1018  assert(size() == capacity());
1019  const size_type s = size();
1020 
1021  size_type new_capacity = 2 * capacity();
1022  pointer new_data =
1023  AllocatorTraits::allocate(*storage_.GetAllocPtr(), new_capacity);
1024 
1025  reference new_element =
1026  Construct(new_data + s, std::forward<Args>(args)...);
1027  UninitializedCopy(std::make_move_iterator(data()),
1028  std::make_move_iterator(data() + s), new_data);
1029 
1030  ResetAllocation(new_data, new_capacity, s + 1);
1031 
1032  return new_element;
1033  }
1034 
1036  if (n > static_cast<size_type>(N)) {
1037  pointer new_data = AllocatorTraits::allocate(*storage_.GetAllocPtr(), n);
1038  storage_.SetAllocatedData(new_data);
1043  } else {
1045  storage_.GetInlinedData() + n);
1047  }
1048  }
1049 
1051  if (n > static_cast<size_type>(N)) {
1052  pointer new_data = AllocatorTraits::allocate(*storage_.GetAllocPtr(), n);
1053  storage_.SetAllocatedData(new_data);
1056  storage_.GetAllocatedData() + n, v);
1058  } else {
1060  storage_.GetInlinedData() + n, v);
1062  }
1063  }
1064 
1065  template <typename ForwardIt>
1066  void AppendForwardRange(ForwardIt first, ForwardIt last) {
1068  ForwardIt>::value,
1069  "");
1070 
1071  auto length = std::distance(first, last);
1072  reserve(size() + length);
1073  if (storage_.GetIsAllocated()) {
1074  UninitializedCopy(first, last, storage_.GetAllocatedData() + size());
1076  } else {
1077  UninitializedCopy(first, last, storage_.GetInlinedData() + size());
1079  }
1080  }
1081 
1083  const_reference v) {
1084  assert(position >= begin() && position <= end());
1085  if (ABSL_PREDICT_FALSE(n == 0)) return const_cast<iterator>(position);
1086 
1087  value_type copy = v;
1088  std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
1089  std::fill(it_pair.first, it_pair.second, copy);
1090  UninitializedFill(it_pair.second, it_pair.first + n, copy);
1091 
1092  return it_pair.first;
1093  }
1094 
1095  template <typename ForwardIt>
1097  ForwardIt last) {
1099  ForwardIt>::value,
1100  "");
1101  assert(position >= begin() && position <= end());
1102 
1103  if (ABSL_PREDICT_FALSE(first == last))
1104  return const_cast<iterator>(position);
1105 
1106  auto n = std::distance(first, last);
1107  std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
1108  size_type used_spots = it_pair.second - it_pair.first;
1109  auto open_spot = std::next(first, used_spots);
1110  std::copy(first, open_spot, it_pair.first);
1111  UninitializedCopy(open_spot, last, it_pair.second);
1112  return it_pair.first;
1113  }
1114 
1115  void SwapImpl(InlinedVector& other) {
1116  using std::swap;
1117 
1118  bool is_allocated = storage_.GetIsAllocated();
1119  bool other_is_allocated = other.storage_.GetIsAllocated();
1120 
1121  if (is_allocated && other_is_allocated) {
1122  // Both out of line, so just swap the tag, allocation, and allocator.
1123  storage_.SwapSizeAndIsAllocated(std::addressof(other.storage_));
1124  storage_.SwapAllocatedSizeAndCapacity(std::addressof(other.storage_));
1126 
1127  return;
1128  }
1129 
1130  if (!is_allocated && !other_is_allocated) {
1131  // Both inlined: swap up to smaller size, then move remaining elements.
1132  InlinedVector* a = this;
1133  InlinedVector* b = std::addressof(other);
1134  if (size() < other.size()) {
1135  swap(a, b);
1136  }
1137 
1138  const size_type a_size = a->size();
1139  const size_type b_size = b->size();
1140  assert(a_size >= b_size);
1141  // `a` is larger. Swap the elements up to the smaller array size.
1142  std::swap_ranges(a->storage_.GetInlinedData(),
1143  a->storage_.GetInlinedData() + b_size,
1144  b->storage_.GetInlinedData());
1145 
1146  // Move the remaining elements:
1147  // [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b`
1148  b->UninitializedCopy(a->storage_.GetInlinedData() + b_size,
1149  a->storage_.GetInlinedData() + a_size,
1150  b->storage_.GetInlinedData() + b_size);
1151  a->Destroy(a->storage_.GetInlinedData() + b_size,
1152  a->storage_.GetInlinedData() + a_size);
1153 
1154  storage_.SwapSizeAndIsAllocated(std::addressof(other.storage_));
1156 
1157  assert(b->size() == a_size);
1158  assert(a->size() == b_size);
1159  return;
1160  }
1161 
1162  // One is out of line, one is inline.
1163  // We first move the elements from the inlined vector into the
1164  // inlined space in the other vector. We then put the other vector's
1165  // pointer/capacity into the originally inlined vector and swap
1166  // the tags.
1167  InlinedVector* a = this;
1168  InlinedVector* b = std::addressof(other);
1169  if (a->storage_.GetIsAllocated()) {
1170  swap(a, b);
1171  }
1172 
1173  assert(!a->storage_.GetIsAllocated());
1174  assert(b->storage_.GetIsAllocated());
1175 
1176  const size_type a_size = a->size();
1177  const size_type b_size = b->size();
1178  // In an optimized build, `b_size` would be unused.
1179  static_cast<void>(b_size);
1180 
1181  // Made Local copies of `size()`, these can now be swapped
1182  a->storage_.SwapSizeAndIsAllocated(std::addressof(b->storage_));
1183 
1184  // Copy out before `b`'s union gets clobbered by `inline_space`
1185  pointer b_data = b->storage_.GetAllocatedData();
1186  size_type b_capacity = b->storage_.GetAllocatedCapacity();
1187 
1189  a->storage_.GetInlinedData() + a_size,
1190  b->storage_.GetInlinedData());
1192  a->storage_.GetInlinedData() + a_size);
1193 
1194  a->storage_.SetAllocatedData(b_data);
1195  a->storage_.SetAllocatedCapacity(b_capacity);
1196 
1197  if (*a->storage_.GetAllocPtr() != *b->storage_.GetAllocPtr()) {
1199  }
1200 
1201  assert(b->size() == a_size);
1202  assert(a->size() == b_size);
1203  }
1204 
1206 };
1207 
1208 // -----------------------------------------------------------------------------
1209 // InlinedVector Non-Member Functions
1210 // -----------------------------------------------------------------------------
1211 
1212 // `swap()`
1213 //
1214 // Swaps the contents of two inlined vectors. This convenience function
1215 // simply calls `InlinedVector::swap()`.
1216 template <typename T, size_t N, typename A>
1218  absl::InlinedVector<T, N, A>& b) noexcept(noexcept(a.swap(b))) {
1219  a.swap(b);
1220 }
1221 
1222 // `operator==()`
1223 //
1224 // Tests the equivalency of the contents of two inlined vectors.
1225 template <typename T, size_t N, typename A>
1228  auto a_data = a.data();
1229  auto a_size = a.size();
1230  auto b_data = b.data();
1231  auto b_size = b.size();
1232  return absl::equal(a_data, a_data + a_size, b_data, b_data + b_size);
1233 }
1234 
1235 // `operator!=()`
1236 //
1237 // Tests the inequality of the contents of two inlined vectors.
1238 template <typename T, size_t N, typename A>
1241  return !(a == b);
1242 }
1243 
1244 // `operator<()`
1245 //
1246 // Tests whether the contents of one inlined vector are less than the contents
1247 // of another through a lexicographical comparison operation.
1248 template <typename T, size_t N, typename A>
1249 bool operator<(const absl::InlinedVector<T, N, A>& a,
1251  auto a_data = a.data();
1252  auto a_size = a.size();
1253  auto b_data = b.data();
1254  auto b_size = b.size();
1255  return std::lexicographical_compare(a_data, a_data + a_size, b_data,
1256  b_data + b_size);
1257 }
1258 
1259 // `operator>()`
1260 //
1261 // Tests whether the contents of one inlined vector are greater than the
1262 // contents of another through a lexicographical comparison operation.
1263 template <typename T, size_t N, typename A>
1266  return b < a;
1267 }
1268 
1269 // `operator<=()`
1270 //
1271 // Tests whether the contents of one inlined vector are less than or equal to
1272 // the contents of another through a lexicographical comparison operation.
1273 template <typename T, size_t N, typename A>
1274 bool operator<=(const absl::InlinedVector<T, N, A>& a,
1276  return !(b < a);
1277 }
1278 
1279 // `operator>=()`
1280 //
1281 // Tests whether the contents of one inlined vector are greater than or equal to
1282 // the contents of another through a lexicographical comparison operation.
1283 template <typename T, size_t N, typename A>
1286  return !(a < b);
1287 }
1288 
1289 // `AbslHashValue()`
1290 //
1291 // Provides `absl::Hash` support for `absl::InlinedVector`. You do not normally
1292 // call this function directly.
1293 template <typename H, typename TheT, size_t TheN, typename TheA>
1295  auto a_data = a.data();
1296  auto a_size = a.size();
1297  return H::combine(H::combine_contiguous(std::move(h), a_data, a_size),
1298  a_size);
1299 }
1300 
1301 } // namespace absl
1302 
1303 #endif // ABSL_CONTAINER_INLINED_VECTOR_H_
int v
Definition: variant_test.cc:81
iterator emplace(const_iterator pos, Args &&...args)
void Destroy(pointer from, pointer to)
pointer data() noexcept
const_reference operator[](size_type i) const
InlinedVector() noexcept(noexcept(allocator_type()))
const_iterator cend() const noexcept
const_reverse_iterator rend() const noexcept
iterator end() noexcept
void UninitializedCopy(Iterator src, Iterator src_last, pointer dst)
const_reverse_iterator crend() const noexcept
size_type max_size() const noexcept
InlinedVector(std::initializer_list< value_type > list, const allocator_type &alloc=allocator_type())
void EnlargeBy(size_type delta)
typename allocator_type::size_type size_type
iterator insert(const_iterator pos, std::initializer_list< value_type > list)
iterator insert(const_iterator pos, size_type n, const_reference v)
InlinedVector & operator=(InlinedVector &&other)
std::reverse_iterator< const_iterator > const_reverse_iterator
typename allocator_type::value_type && rvalue_reference
typename allocator_type::const_reference const_reference
iterator insert(const_iterator pos, InputIterator first, InputIterator last)
typename allocator_type::value_type value_type
iterator insert(const_iterator pos, ForwardIterator first, ForwardIterator last)
typename allocator_type::reference reference
void ThrowStdOutOfRange(const std::string &what_arg)
void InitAssign(size_type n, const_reference v)
InlinedVector(const InlinedVector &other, const allocator_type &alloc)
#define ABSL_PREDICT_FALSE(x)
Definition: optimization.h:177
reference operator[](size_type i)
allocator_type get_allocator() const
std::allocator_traits< allocator_type > AllocatorTraits
void assign(InputIterator first, InputIterator last)
InlinedVector & operator=(const InlinedVector &other)
const_reverse_iterator rbegin() const noexcept
int fill
void UninitializedFill(pointer dst, pointer dst_last, const Args &...args)
InlinedVector(InlinedVector &&other) noexcept(absl::allocator_is_nothrow< allocator_type >::value||std::is_nothrow_move_constructible< value_type >::value)
typename Storage::const_reverse_iterator const_reverse_iterator
friend H AbslHashValue(H h, const absl::InlinedVector< TheT, TheN, TheA > &a)
iterator InsertWithCount(const_iterator position, size_type n, const_reference v)
reference emplace_back(Args &&...args)
reference at(size_type i)
reference GrowAndEmplaceBack(Args &&...args)
void assign(ForwardIterator first, ForwardIterator last)
Definition: algorithm.h:29
void reserve(size_type n)
void ResetAllocation(pointer new_data, size_type new_capacity, size_type new_size)
InlinedVector(const InlinedVector &other)
bool operator>(const absl::InlinedVector< T, N, A > &a, const absl::InlinedVector< T, N, A > &b)
void AppendForwardRange(ForwardIt first, ForwardIt last)
typename std::enable_if< B, T >::type enable_if_t
Definition: type_traits.h:547
InlinedVector(ForwardIterator first, ForwardIterator last, const allocator_type &alloc=allocator_type())
static std::function< void(void *, Slot *)> destroy
void clear() noexcept
std::reverse_iterator< iterator > reverse_iterator
iterator insert(const_iterator pos, const_reference v)
InlinedVector(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
InlinedVector(size_type n, const_reference v, const allocator_type &alloc=allocator_type())
size_t to
bool operator==(const absl::InlinedVector< T, N, A > &a, const absl::InlinedVector< T, N, A > &b)
const_pointer data() const noexcept
AllocList * next[kMaxLevel]
iterator erase(const_iterator from, const_iterator to)
bool operator>=(const absl::InlinedVector< T, N, A > &a, const absl::InlinedVector< T, N, A > &b)
std::is_convertible< typename std::iterator_traits< Iterator >::iterator_category, std::forward_iterator_tag > IsAtLeastForwardIterator
std::pair< iterator, iterator > ShiftRight(const_iterator position, size_type n)
size_t value
void swap(InlinedVector &other)
void pop_back() noexcept
bool operator!=(const absl::InlinedVector< T, N, A > &a, const absl::InlinedVector< T, N, A > &b)
size_type capacity() const noexcept
reverse_iterator rbegin() noexcept
bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2, InputIter2 last2, Pred &&pred)
Definition: algorithm.h:99
size_type size() const noexcept
InlinedVector(size_type n, const allocator_type &alloc=allocator_type())
const_reference at(size_type i) const
reference Construct(pointer p, Args &&...args)
void swap(absl::InlinedVector< T, N, A > &a, absl::InlinedVector< T, N, A > &b) noexcept(noexcept(a.swap(b)))
static std::function< void(void *, Slot *, Slot)> construct
typename allocator_type::pointer pointer
void InitAssign(size_type n)
void resize(size_type n)
void DestroyElements(AllocatorType *alloc_ptr, ValueType *destroy_first, SizeType destroy_size)
InlinedVector(InlinedVector &&other, const allocator_type &alloc) noexcept(absl::allocator_is_nothrow< allocator_type >::value)
typename allocator_type::difference_type difference_type
void assign(size_type n, const_reference v)
void SwapImpl(InlinedVector &other)
typename allocator_type::const_pointer const_pointer
#define ABSL_PREDICT_TRUE(x)
Definition: optimization.h:178
void resize(size_type n, const_reference v)
const_iterator end() const noexcept
const_reverse_iterator crbegin() const noexcept
InlinedVector & operator=(std::initializer_list< value_type > list)
void assign(std::initializer_list< value_type > list)
absl::enable_if_t< !inlined_vector_internal::IsAtLeastForwardIterator< Iterator >::value > DisableIfAtLeastForwardIterator
InlinedVector(const allocator_type &alloc) noexcept
iterator InsertWithForwardRange(const_iterator position, ForwardIt first, ForwardIt last)
absl::enable_if_t< inlined_vector_internal::IsAtLeastForwardIterator< Iterator >::value > EnableIfAtLeastForwardIterator
iterator insert(const_iterator pos, rvalue_reference v)
const_iterator cbegin() const noexcept
uint64_t b
Definition: layout_test.cc:50
std::allocator< int > alloc
void push_back(rvalue_reference v)
iterator begin() noexcept
constexpr absl::remove_reference_t< T > && move(T &&t) noexcept
Definition: utility.h:219
char * out
Definition: mutex.h:1013
size_t from
const_reference back() const
const_reference front() const
bool empty() const noexcept
std::size_t length
Definition: test_util.cc:52
const_iterator begin() const noexcept
reverse_iterator rend() noexcept
void push_back(const_reference v)
iterator erase(const_iterator pos)


abseil_cpp
Author(s):
autogenerated on Tue Jun 18 2019 19:44:36