LLVM  12.0.0git
SmallVector.h
Go to the documentation of this file.
1 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the SmallVector class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ADT_SMALLVECTOR_H
14 #define LLVM_ADT_SMALLVECTOR_H
15 
17 #include "llvm/Support/Compiler.h"
20 #include "llvm/Support/MemAlloc.h"
22 #include <algorithm>
23 #include <cassert>
24 #include <cstddef>
25 #include <cstdlib>
26 #include <cstring>
27 #include <initializer_list>
28 #include <iterator>
29 #include <limits>
30 #include <memory>
31 #include <new>
32 #include <type_traits>
33 #include <utility>
34 
35 namespace llvm {
36 
37 /// This is all the stuff common to all SmallVectors.
38 ///
39 /// The template parameter specifies the type which should be used to hold the
40 /// Size and Capacity of the SmallVector, so it can be adjusted.
41 /// Using 32 bit size is desirable to shrink the size of the SmallVector.
42 /// Using 64 bit size is desirable for cases like SmallVector<char>, where a
43 /// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
44 /// buffering bitcode output - which can exceed 4GB.
45 template <class Size_T> class SmallVectorBase {
46 protected:
47  void *BeginX;
48  Size_T Size = 0, Capacity;
49 
50  /// The maximum value of the Size_T used.
51  static constexpr size_t SizeTypeMax() {
53  }
54 
55  SmallVectorBase() = delete;
56  SmallVectorBase(void *FirstEl, size_t TotalCapacity)
57  : BeginX(FirstEl), Capacity(TotalCapacity) {}
58 
59  /// This is an implementation of the grow() method which only works
60  /// on POD-like data types and is out of line to reduce code duplication.
61  /// This function will report a fatal error if it cannot increase capacity.
62  void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
63 
64  /// Report that MinSize doesn't fit into this vector's size type. Throws
65  /// std::length_error or calls report_fatal_error.
66  LLVM_ATTRIBUTE_NORETURN static void report_size_overflow(size_t MinSize);
67  /// Report that this vector is already at maximum capacity. Throws
68  /// std::length_error or calls report_fatal_error.
70 
71 public:
72  size_t size() const { return Size; }
73  size_t capacity() const { return Capacity; }
74 
75  LLVM_NODISCARD bool empty() const { return !Size; }
76 
77  /// Set the array size to \p N, which the current array must have enough
78  /// capacity for.
79  ///
80  /// This does not construct or destroy any elements in the vector.
81  ///
82  /// Clients can use this in conjunction with capacity() to write past the end
83  /// of the buffer when they know that more elements are available, and only
84  /// update the size later. This avoids the cost of value initializing elements
85  /// which will only be overwritten.
86  void set_size(size_t N) {
87  assert(N <= capacity());
88  Size = N;
89  }
90 };
91 
92 template <class T>
93 using SmallVectorSizeType =
94  typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
96 
97 /// Figure out the offset of the first element.
98 template <class T, typename = void> struct SmallVectorAlignmentAndSize {
99  alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(
101  alignas(T) char FirstEl[sizeof(T)];
102 };
103 
104 /// This is the part of SmallVectorTemplateBase which does not depend on whether
105 /// the type T is a POD. The extra dummy template argument is used by ArrayRef
106 /// to avoid unnecessarily requiring T to be complete.
107 template <typename T, typename = void>
109  : public SmallVectorBase<SmallVectorSizeType<T>> {
111 
112  /// Find the address of the first element. For this pointer math to be valid
113  /// with small-size of 0 for T with lots of alignment, it's important that
114  /// SmallVectorStorage is properly-aligned even for small-size of 0.
115  void *getFirstEl() const {
116  return const_cast<void *>(reinterpret_cast<const void *>(
117  reinterpret_cast<const char *>(this) +
119  }
120  // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
121 
122 protected:
123  SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
124 
125  void grow_pod(size_t MinSize, size_t TSize) {
126  Base::grow_pod(getFirstEl(), MinSize, TSize);
127  }
128 
129  /// Return true if this is a smallvector which has not had dynamic
130  /// memory allocated for it.
131  bool isSmall() const { return this->BeginX == getFirstEl(); }
132 
133  /// Put this vector in a state of being small.
134  void resetToSmall() {
135  this->BeginX = getFirstEl();
136  this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
137  }
138 
139  /// Return true unless Elt will be invalidated by resizing the vector to
140  /// NewSize.
141  bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
142  // Past the end.
143  if (LLVM_LIKELY(Elt < this->begin() || Elt >= this->end()))
144  return true;
145 
146  // Return false if Elt will be destroyed by shrinking.
147  if (NewSize <= this->size())
148  return Elt < this->begin() + NewSize;
149 
150  // Return false if we need to grow.
151  return NewSize <= this->capacity();
152  }
153 
154  /// Check whether Elt will be invalidated by resizing the vector to NewSize.
155  void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
156  assert(isSafeToReferenceAfterResize(Elt, NewSize) &&
157  "Attempting to reference an element of the vector in an operation "
158  "that invalidates it");
159  }
160 
161  /// Check whether Elt will be invalidated by increasing the size of the
162  /// vector by N.
163  void assertSafeToAdd(const void *Elt, size_t N = 1) {
164  this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
165  }
166 
167  /// Check whether any part of the range will be invalidated by clearing.
168  void assertSafeToReferenceAfterClear(const T *From, const T *To) {
169  if (From == To)
170  return;
171  this->assertSafeToReferenceAfterResize(From, 0);
172  this->assertSafeToReferenceAfterResize(To - 1, 0);
173  }
174  template <
175  class ItTy,
176  std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
177  bool> = false>
179 
180  /// Check whether any part of the range will be invalidated by growing.
181  void assertSafeToAddRange(const T *From, const T *To) {
182  if (From == To)
183  return;
184  this->assertSafeToAdd(From, To - From);
185  this->assertSafeToAdd(To - 1, To - From);
186  }
187  template <
188  class ItTy,
189  std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
190  bool> = false>
192 
193  /// Check whether any argument will be invalidated by growing for
194  /// emplace_back.
195  template <class ArgType1, class... ArgTypes>
196  void assertSafeToEmplace(ArgType1 &Arg1, ArgTypes &... Args) {
197  this->assertSafeToAdd(&Arg1);
198  this->assertSafeToEmplace(Args...);
199  }
201 
202 public:
203  using size_type = size_t;
205  using value_type = T;
206  using iterator = T *;
207  using const_iterator = const T *;
208 
209  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
210  using reverse_iterator = std::reverse_iterator<iterator>;
211 
212  using reference = T &;
213  using const_reference = const T &;
214  using pointer = T *;
215  using const_pointer = const T *;
216 
217  using Base::capacity;
218  using Base::empty;
219  using Base::size;
220 
221  // forward iterator creation methods.
222  iterator begin() { return (iterator)this->BeginX; }
223  const_iterator begin() const { return (const_iterator)this->BeginX; }
224  iterator end() { return begin() + size(); }
225  const_iterator end() const { return begin() + size(); }
226 
227  // reverse iterator creation methods.
232 
233  size_type size_in_bytes() const { return size() * sizeof(T); }
234  size_type max_size() const {
235  return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
236  }
237 
238  size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
239 
240  /// Return a pointer to the vector's buffer, even if empty().
241  pointer data() { return pointer(begin()); }
242  /// Return a pointer to the vector's buffer, even if empty().
243  const_pointer data() const { return const_pointer(begin()); }
244 
246  assert(idx < size());
247  return begin()[idx];
248  }
250  assert(idx < size());
251  return begin()[idx];
252  }
253 
255  assert(!empty());
256  return begin()[0];
257  }
259  assert(!empty());
260  return begin()[0];
261  }
262 
264  assert(!empty());
265  return end()[-1];
266  }
268  assert(!empty());
269  return end()[-1];
270  }
271 };
272 
273 /// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
274 /// method implementations that are designed to work with non-trivial T's.
275 ///
276 /// We approximate is_trivially_copyable with trivial move/copy construction and
277 /// trivial destruction. While the standard doesn't specify that you're allowed
278 /// copy these types with memcpy, there is no way for the type to observe this.
279 /// This catches the important case of std::pair<POD, POD>, which is not
280 /// trivially assignable.
281 template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
283  std::is_trivially_destructible<T>::value>
285 protected:
287 
288  static void destroy_range(T *S, T *E) {
289  while (S != E) {
290  --E;
291  E->~T();
292  }
293  }
294 
295  /// Move the range [I, E) into the uninitialized memory starting with "Dest",
296  /// constructing elements as needed.
297  template<typename It1, typename It2>
298  static void uninitialized_move(It1 I, It1 E, It2 Dest) {
299  std::uninitialized_copy(std::make_move_iterator(I),
300  std::make_move_iterator(E), Dest);
301  }
302 
303  /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
304  /// constructing elements as needed.
305  template<typename It1, typename It2>
306  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
307  std::uninitialized_copy(I, E, Dest);
308  }
309 
310  /// Grow the allocated memory (without initializing new elements), doubling
311  /// the size of the allocated memory. Guarantees space for at least one more
312  /// element, or MinSize more elements if specified.
313  void grow(size_t MinSize = 0);
314 
315 public:
316  void push_back(const T &Elt) {
317  this->assertSafeToAdd(&Elt);
318  if (LLVM_UNLIKELY(this->size() >= this->capacity()))
319  this->grow();
320  ::new ((void*) this->end()) T(Elt);
321  this->set_size(this->size() + 1);
322  }
323 
324  void push_back(T &&Elt) {
325  this->assertSafeToAdd(&Elt);
326  if (LLVM_UNLIKELY(this->size() >= this->capacity()))
327  this->grow();
328  ::new ((void*) this->end()) T(::std::move(Elt));
329  this->set_size(this->size() + 1);
330  }
331 
332  void pop_back() {
333  this->set_size(this->size() - 1);
334  this->end()->~T();
335  }
336 };
337 
338 // Define this out-of-line to dissuade the C++ compiler from inlining it.
339 template <typename T, bool TriviallyCopyable>
341  // Ensure we can fit the new capacity.
342  // This is only going to be applicable when the capacity is 32 bit.
343  if (MinSize > this->SizeTypeMax())
344  this->report_size_overflow(MinSize);
345 
346  // Ensure we can meet the guarantee of space for at least one more element.
347  // The above check alone will not catch the case where grow is called with a
348  // default MinSize of 0, but the current capacity cannot be increased.
349  // This is only going to be applicable when the capacity is 32 bit.
350  if (this->capacity() == this->SizeTypeMax())
352 
353  // Always grow, even from zero.
354  size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
355  NewCapacity = std::min(std::max(NewCapacity, MinSize), this->SizeTypeMax());
356  T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
357 
358  // Move the elements over.
359  this->uninitialized_move(this->begin(), this->end(), NewElts);
360 
361  // Destroy the original elements.
362  destroy_range(this->begin(), this->end());
363 
364  // If this wasn't grown from the inline copy, deallocate the old space.
365  if (!this->isSmall())
366  free(this->begin());
367 
368  this->BeginX = NewElts;
369  this->Capacity = NewCapacity;
370 }
371 
372 /// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
373 /// method implementations that are designed to work with trivially copyable
374 /// T's. This allows using memcpy in place of copy/move construction and
375 /// skipping destruction.
376 template <typename T>
378 protected:
380 
381  // No need to do a destroy loop for POD's.
382  static void destroy_range(T *, T *) {}
383 
384  /// Move the range [I, E) onto the uninitialized memory
385  /// starting with "Dest", constructing elements into it as needed.
386  template<typename It1, typename It2>
387  static void uninitialized_move(It1 I, It1 E, It2 Dest) {
388  // Just do a copy.
389  uninitialized_copy(I, E, Dest);
390  }
391 
392  /// Copy the range [I, E) onto the uninitialized memory
393  /// starting with "Dest", constructing elements into it as needed.
394  template<typename It1, typename It2>
395  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
396  // Arbitrary iterator types; just use the basic implementation.
397  std::uninitialized_copy(I, E, Dest);
398  }
399 
400  /// Copy the range [I, E) onto the uninitialized memory
401  /// starting with "Dest", constructing elements into it as needed.
402  template <typename T1, typename T2>
403  static void uninitialized_copy(
404  T1 *I, T1 *E, T2 *Dest,
405  std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
406  T2>::value> * = nullptr) {
407  // Use memcpy for PODs iterated by pointers (which includes SmallVector
408  // iterators): std::uninitialized_copy optimizes to memmove, but we can
409  // use memcpy here. Note that I and E are iterators and thus might be
410  // invalid for memcpy if they are equal.
411  if (I != E)
412  memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
413  }
414 
415  /// Double the size of the allocated memory, guaranteeing space for at
416  /// least one more element or MinSize if specified.
417  void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
418 
419 public:
420  void push_back(const T &Elt) {
421  this->assertSafeToAdd(&Elt);
422  if (LLVM_UNLIKELY(this->size() >= this->capacity()))
423  this->grow();
424  memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
425  this->set_size(this->size() + 1);
426  }
427 
428  void pop_back() { this->set_size(this->size() - 1); }
429 };
430 
431 /// This class consists of common code factored out of the SmallVector class to
432 /// reduce code duplication based on the SmallVector 'N' template parameter.
433 template <typename T>
434 class SmallVectorImpl : public SmallVectorTemplateBase<T> {
436 
437 public:
438  using iterator = typename SuperClass::iterator;
442 
443 protected:
444  // Default ctor - Initialize to empty.
445  explicit SmallVectorImpl(unsigned N)
446  : SmallVectorTemplateBase<T>(N) {}
447 
448 public:
449  SmallVectorImpl(const SmallVectorImpl &) = delete;
450 
452  // Subclass has already destructed this vector's elements.
453  // If this wasn't grown from the inline copy, deallocate the old space.
454  if (!this->isSmall())
455  free(this->begin());
456  }
457 
458  void clear() {
459  this->destroy_range(this->begin(), this->end());
460  this->Size = 0;
461  }
462 
464  if (N < this->size()) {
465  this->destroy_range(this->begin()+N, this->end());
466  this->set_size(N);
467  } else if (N > this->size()) {
468  if (this->capacity() < N)
469  this->grow(N);
470  for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
471  new (&*I) T();
472  this->set_size(N);
473  }
474  }
475 
476  void resize(size_type N, const T &NV) {
477  if (N == this->size())
478  return;
479 
480  if (N < this->size()) {
481  this->destroy_range(this->begin()+N, this->end());
482  this->set_size(N);
483  return;
484  }
485 
486  this->assertSafeToReferenceAfterResize(&NV, N);
487  if (this->capacity() < N)
488  this->grow(N);
489  std::uninitialized_fill(this->end(), this->begin() + N, NV);
490  this->set_size(N);
491  }
492 
494  if (this->capacity() < N)
495  this->grow(N);
496  }
497 
498  void pop_back_n(size_type NumItems) {
499  assert(this->size() >= NumItems);
500  this->destroy_range(this->end() - NumItems, this->end());
501  this->set_size(this->size() - NumItems);
502  }
503 
505  T Result = ::std::move(this->back());
506  this->pop_back();
507  return Result;
508  }
509 
510  void swap(SmallVectorImpl &RHS);
511 
512  /// Add the specified range to the end of the SmallVector.
513  template <typename in_iter,
514  typename = std::enable_if_t<std::is_convertible<
515  typename std::iterator_traits<in_iter>::iterator_category,
516  std::input_iterator_tag>::value>>
517  void append(in_iter in_start, in_iter in_end) {
518  this->assertSafeToAddRange(in_start, in_end);
519  size_type NumInputs = std::distance(in_start, in_end);
520  if (NumInputs > this->capacity() - this->size())
521  this->grow(this->size()+NumInputs);
522 
523  this->uninitialized_copy(in_start, in_end, this->end());
524  this->set_size(this->size() + NumInputs);
525  }
526 
527  /// Append \p NumInputs copies of \p Elt to the end.
528  void append(size_type NumInputs, const T &Elt) {
529  this->assertSafeToAdd(&Elt, NumInputs);
530  if (NumInputs > this->capacity() - this->size())
531  this->grow(this->size()+NumInputs);
532 
533  std::uninitialized_fill_n(this->end(), NumInputs, Elt);
534  this->set_size(this->size() + NumInputs);
535  }
536 
537  void append(std::initializer_list<T> IL) {
538  append(IL.begin(), IL.end());
539  }
540 
541  // FIXME: Consider assigning over existing elements, rather than clearing &
542  // re-initializing them - for all assign(...) variants.
543 
544  void assign(size_type NumElts, const T &Elt) {
545  this->assertSafeToReferenceAfterResize(&Elt, 0);
546  clear();
547  if (this->capacity() < NumElts)
548  this->grow(NumElts);
549  this->set_size(NumElts);
550  std::uninitialized_fill(this->begin(), this->end(), Elt);
551  }
552 
553  template <typename in_iter,
554  typename = std::enable_if_t<std::is_convertible<
555  typename std::iterator_traits<in_iter>::iterator_category,
556  std::input_iterator_tag>::value>>
557  void assign(in_iter in_start, in_iter in_end) {
558  this->assertSafeToReferenceAfterClear(in_start, in_end);
559  clear();
560  append(in_start, in_end);
561  }
562 
563  void assign(std::initializer_list<T> IL) {
564  clear();
565  append(IL);
566  }
567 
569  // Just cast away constness because this is a non-const member function.
570  iterator I = const_cast<iterator>(CI);
571 
572  assert(I >= this->begin() && "Iterator to erase is out of bounds.");
573  assert(I < this->end() && "Erasing at past-the-end iterator.");
574 
575  iterator N = I;
576  // Shift all elts down one.
577  std::move(I+1, this->end(), I);
578  // Drop the last elt.
579  this->pop_back();
580  return(N);
581  }
582 
584  // Just cast away constness because this is a non-const member function.
585  iterator S = const_cast<iterator>(CS);
586  iterator E = const_cast<iterator>(CE);
587 
588  assert(S >= this->begin() && "Range to erase is out of bounds.");
589  assert(S <= E && "Trying to erase invalid range.");
590  assert(E <= this->end() && "Trying to erase past the end.");
591 
592  iterator N = S;
593  // Shift all elts down.
594  iterator I = std::move(E, this->end(), S);
595  // Drop the last elts.
596  this->destroy_range(I, this->end());
597  this->set_size(I - this->begin());
598  return(N);
599  }
600 
601 private:
602  template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
603  if (I == this->end()) { // Important special case for empty vector.
604  this->push_back(::std::forward<ArgType>(Elt));
605  return this->end()-1;
606  }
607 
608  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
609  assert(I <= this->end() && "Inserting past the end of the vector.");
610 
611  // Check that adding an element won't invalidate Elt.
612  this->assertSafeToAdd(&Elt);
613 
614  if (this->size() >= this->capacity()) {
615  size_t EltNo = I-this->begin();
616  this->grow();
617  I = this->begin()+EltNo;
618  }
619 
620  ::new ((void*) this->end()) T(::std::move(this->back()));
621  // Push everything else over.
622  std::move_backward(I, this->end()-1, this->end());
623  this->set_size(this->size() + 1);
624 
625  // If we just moved the element we're inserting, be sure to update
626  // the reference.
627  std::remove_reference_t<ArgType> *EltPtr = &Elt;
628  if (I <= EltPtr && EltPtr < this->end())
629  ++EltPtr;
630 
631  *I = ::std::forward<ArgType>(*EltPtr);
632  return I;
633  }
634 
635 public:
636  iterator insert(iterator I, T &&Elt) {
637  return insert_one_impl(I, std::move(Elt));
638  }
639 
640  iterator insert(iterator I, const T &Elt) { return insert_one_impl(I, Elt); }
641 
642  iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
643  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
644  size_t InsertElt = I - this->begin();
645 
646  if (I == this->end()) { // Important special case for empty vector.
647  append(NumToInsert, Elt);
648  return this->begin()+InsertElt;
649  }
650 
651  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
652  assert(I <= this->end() && "Inserting past the end of the vector.");
653 
654  // Check that adding NumToInsert elements won't invalidate Elt.
655  this->assertSafeToAdd(&Elt, NumToInsert);
656 
657  // Ensure there is enough space.
658  reserve(this->size() + NumToInsert);
659 
660  // Uninvalidate the iterator.
661  I = this->begin()+InsertElt;
662 
663  // If there are more elements between the insertion point and the end of the
664  // range than there are being inserted, we can use a simple approach to
665  // insertion. Since we already reserved space, we know that this won't
666  // reallocate the vector.
667  if (size_t(this->end()-I) >= NumToInsert) {
668  T *OldEnd = this->end();
669  append(std::move_iterator<iterator>(this->end() - NumToInsert),
670  std::move_iterator<iterator>(this->end()));
671 
672  // Copy the existing elements that get replaced.
673  std::move_backward(I, OldEnd-NumToInsert, OldEnd);
674 
675  std::fill_n(I, NumToInsert, Elt);
676  return I;
677  }
678 
679  // Otherwise, we're inserting more elements than exist already, and we're
680  // not inserting at the end.
681 
682  // Move over the elements that we're about to overwrite.
683  T *OldEnd = this->end();
684  this->set_size(this->size() + NumToInsert);
685  size_t NumOverwritten = OldEnd-I;
686  this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
687 
688  // Replace the overwritten part.
689  std::fill_n(I, NumOverwritten, Elt);
690 
691  // Insert the non-overwritten middle part.
692  std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
693  return I;
694  }
695 
696  template <typename ItTy,
697  typename = std::enable_if_t<std::is_convertible<
698  typename std::iterator_traits<ItTy>::iterator_category,
699  std::input_iterator_tag>::value>>
701  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
702  size_t InsertElt = I - this->begin();
703 
704  if (I == this->end()) { // Important special case for empty vector.
705  append(From, To);
706  return this->begin()+InsertElt;
707  }
708 
709  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
710  assert(I <= this->end() && "Inserting past the end of the vector.");
711 
712  // Check that the reserve that follows doesn't invalidate the iterators.
713  this->assertSafeToAddRange(From, To);
714 
715  size_t NumToInsert = std::distance(From, To);
716 
717  // Ensure there is enough space.
718  reserve(this->size() + NumToInsert);
719 
720  // Uninvalidate the iterator.
721  I = this->begin()+InsertElt;
722 
723  // If there are more elements between the insertion point and the end of the
724  // range than there are being inserted, we can use a simple approach to
725  // insertion. Since we already reserved space, we know that this won't
726  // reallocate the vector.
727  if (size_t(this->end()-I) >= NumToInsert) {
728  T *OldEnd = this->end();
729  append(std::move_iterator<iterator>(this->end() - NumToInsert),
730  std::move_iterator<iterator>(this->end()));
731 
732  // Copy the existing elements that get replaced.
733  std::move_backward(I, OldEnd-NumToInsert, OldEnd);
734 
735  std::copy(From, To, I);
736  return I;
737  }
738 
739  // Otherwise, we're inserting more elements than exist already, and we're
740  // not inserting at the end.
741 
742  // Move over the elements that we're about to overwrite.
743  T *OldEnd = this->end();
744  this->set_size(this->size() + NumToInsert);
745  size_t NumOverwritten = OldEnd-I;
746  this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
747 
748  // Replace the overwritten part.
749  for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
750  *J = *From;
751  ++J; ++From;
752  }
753 
754  // Insert the non-overwritten middle part.
755  this->uninitialized_copy(From, To, OldEnd);
756  return I;
757  }
758 
759  void insert(iterator I, std::initializer_list<T> IL) {
760  insert(I, IL.begin(), IL.end());
761  }
762 
763  template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
764  this->assertSafeToEmplace(Args...);
765  if (LLVM_UNLIKELY(this->size() >= this->capacity()))
766  this->grow();
767  ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
768  this->set_size(this->size() + 1);
769  return this->back();
770  }
771 
773 
775 
776  bool operator==(const SmallVectorImpl &RHS) const {
777  if (this->size() != RHS.size()) return false;
778  return std::equal(this->begin(), this->end(), RHS.begin());
779  }
780  bool operator!=(const SmallVectorImpl &RHS) const {
781  return !(*this == RHS);
782  }
783 
784  bool operator<(const SmallVectorImpl &RHS) const {
785  return std::lexicographical_compare(this->begin(), this->end(),
786  RHS.begin(), RHS.end());
787  }
788 };
789 
790 template <typename T>
792  if (this == &RHS) return;
793 
794  // We can only avoid copying elements if neither vector is small.
795  if (!this->isSmall() && !RHS.isSmall()) {
796  std::swap(this->BeginX, RHS.BeginX);
797  std::swap(this->Size, RHS.Size);
798  std::swap(this->Capacity, RHS.Capacity);
799  return;
800  }
801  if (RHS.size() > this->capacity())
802  this->grow(RHS.size());
803  if (this->size() > RHS.capacity())
804  RHS.grow(this->size());
805 
806  // Swap the shared elements.
807  size_t NumShared = this->size();
808  if (NumShared > RHS.size()) NumShared = RHS.size();
809  for (size_type i = 0; i != NumShared; ++i)
810  std::swap((*this)[i], RHS[i]);
811 
812  // Copy over the extra elts.
813  if (this->size() > RHS.size()) {
814  size_t EltDiff = this->size() - RHS.size();
815  this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
816  RHS.set_size(RHS.size() + EltDiff);
817  this->destroy_range(this->begin()+NumShared, this->end());
818  this->set_size(NumShared);
819  } else if (RHS.size() > this->size()) {
820  size_t EltDiff = RHS.size() - this->size();
821  this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
822  this->set_size(this->size() + EltDiff);
823  this->destroy_range(RHS.begin()+NumShared, RHS.end());
824  RHS.set_size(NumShared);
825  }
826 }
827 
828 template <typename T>
831  // Avoid self-assignment.
832  if (this == &RHS) return *this;
833 
834  // If we already have sufficient space, assign the common elements, then
835  // destroy any excess.
836  size_t RHSSize = RHS.size();
837  size_t CurSize = this->size();
838  if (CurSize >= RHSSize) {
839  // Assign common elements.
840  iterator NewEnd;
841  if (RHSSize)
842  NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
843  else
844  NewEnd = this->begin();
845 
846  // Destroy excess elements.
847  this->destroy_range(NewEnd, this->end());
848 
849  // Trim.
850  this->set_size(RHSSize);
851  return *this;
852  }
853 
854  // If we have to grow to have enough elements, destroy the current elements.
855  // This allows us to avoid copying them during the grow.
856  // FIXME: don't do this if they're efficiently moveable.
857  if (this->capacity() < RHSSize) {
858  // Destroy current elements.
859  this->destroy_range(this->begin(), this->end());
860  this->set_size(0);
861  CurSize = 0;
862  this->grow(RHSSize);
863  } else if (CurSize) {
864  // Otherwise, use assignment for the already-constructed elements.
865  std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
866  }
867 
868  // Copy construct the new elements in place.
869  this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
870  this->begin()+CurSize);
871 
872  // Set end.
873  this->set_size(RHSSize);
874  return *this;
875 }
876 
877 template <typename T>
879  // Avoid self-assignment.
880  if (this == &RHS) return *this;
881 
882  // If the RHS isn't small, clear this vector and then steal its buffer.
883  if (!RHS.isSmall()) {
884  this->destroy_range(this->begin(), this->end());
885  if (!this->isSmall()) free(this->begin());
886  this->BeginX = RHS.BeginX;
887  this->Size = RHS.Size;
888  this->Capacity = RHS.Capacity;
889  RHS.resetToSmall();
890  return *this;
891  }
892 
893  // If we already have sufficient space, assign the common elements, then
894  // destroy any excess.
895  size_t RHSSize = RHS.size();
896  size_t CurSize = this->size();
897  if (CurSize >= RHSSize) {
898  // Assign common elements.
899  iterator NewEnd = this->begin();
900  if (RHSSize)
901  NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
902 
903  // Destroy excess elements and trim the bounds.
904  this->destroy_range(NewEnd, this->end());
905  this->set_size(RHSSize);
906 
907  // Clear the RHS.
908  RHS.clear();
909 
910  return *this;
911  }
912 
913  // If we have to grow to have enough elements, destroy the current elements.
914  // This allows us to avoid copying them during the grow.
915  // FIXME: this may not actually make any sense if we can efficiently move
916  // elements.
917  if (this->capacity() < RHSSize) {
918  // Destroy current elements.
919  this->destroy_range(this->begin(), this->end());
920  this->set_size(0);
921  CurSize = 0;
922  this->grow(RHSSize);
923  } else if (CurSize) {
924  // Otherwise, use assignment for the already-constructed elements.
925  std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
926  }
927 
928  // Move-construct the new elements in place.
929  this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
930  this->begin()+CurSize);
931 
932  // Set end.
933  this->set_size(RHSSize);
934 
935  RHS.clear();
936  return *this;
937 }
938 
939 /// Storage for the SmallVector elements. This is specialized for the N=0 case
940 /// to avoid allocating unnecessary storage.
941 template <typename T, unsigned N>
943  alignas(T) char InlineElts[N * sizeof(T)];
944 };
945 
946 /// We need the storage to be properly aligned even for small-size of 0 so that
947 /// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
948 /// well-defined.
949 template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
950 
951 /// This is a 'vector' (really, a variable-sized array), optimized
952 /// for the case when the array is small. It contains some number of elements
953 /// in-place, which allows it to avoid heap allocation when the actual number of
954 /// elements is below that threshold. This allows normal "small" cases to be
955 /// fast without losing generality for large inputs.
956 ///
957 /// Note that this does not attempt to be exception safe.
958 ///
959 template <typename T, unsigned N>
961  SmallVectorStorage<T, N> {
962 public:
964 
966  // Destroy the constructed elements in the vector.
967  this->destroy_range(this->begin(), this->end());
968  }
969 
970  explicit SmallVector(size_t Size, const T &Value = T())
971  : SmallVectorImpl<T>(N) {
972  this->assign(Size, Value);
973  }
974 
975  template <typename ItTy,
976  typename = std::enable_if_t<std::is_convertible<
977  typename std::iterator_traits<ItTy>::iterator_category,
978  std::input_iterator_tag>::value>>
980  this->append(S, E);
981  }
982 
983  template <typename RangeTy>
985  : SmallVectorImpl<T>(N) {
986  this->append(R.begin(), R.end());
987  }
988 
989  SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
990  this->assign(IL);
991  }
992 
994  if (!RHS.empty())
996  }
997 
1000  return *this;
1001  }
1002 
1004  if (!RHS.empty())
1006  }
1007 
1009  if (!RHS.empty())
1011  }
1012 
1015  return *this;
1016  }
1017 
1020  return *this;
1021  }
1022 
1023  SmallVector &operator=(std::initializer_list<T> IL) {
1024  this->assign(IL);
1025  return *this;
1026  }
1027 };
1028 
1029 template <typename T, unsigned N>
1030 inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
1031  return X.capacity_in_bytes();
1032 }
1033 
1034 /// Given a range of type R, iterate the entire range and return a
1035 /// SmallVector with elements of the vector. This is useful, for example,
1036 /// when you want to iterate a range and then sort the results.
1037 template <unsigned Size, typename R>
1038 SmallVector<typename std::remove_const<typename std::remove_reference<
1039  decltype(*std::begin(std::declval<R &>()))>::type>::type,
1040  Size>
1041 to_vector(R &&Range) {
1042  return {std::begin(Range), std::end(Range)};
1043 }
1044 
1045 } // end namespace llvm
1046 
1047 namespace std {
1048 
1049  /// Implement std::swap in terms of SmallVector swap.
1050  template<typename T>
1051  inline void
1053  LHS.swap(RHS);
1054  }
1055 
1056  /// Implement std::swap in terms of SmallVector swap.
1057  template<typename T, unsigned N>
1058  inline void
1060  LHS.swap(RHS);
1061  }
1062 
1063 } // end namespace std
1064 
1065 #endif // LLVM_ADT_SMALLVECTOR_H
static void destroy_range(T *S, T *E)
Definition: SmallVector.h:288
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: SmallVector.h:209
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:763
static void uninitialized_copy(It1 I, It1 E, It2 Dest)
Copy the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements into ...
Definition: SmallVector.h:395
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
SmallVector & operator=(const SmallVector &RHS)
Definition: SmallVector.h:998
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
DiagnosticInfoOptimizationBase::Argument NV
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:439
void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize)
Check whether Elt will be invalidated by resizing the vector to NewSize.
Definition: SmallVector.h:155
bool operator!=(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:780
static LLVM_ATTRIBUTE_NORETURN void report_at_maximum_capacity()
Report that this vector is already at maximum capacity.
Definition: SmallVector.cpp:61
This class represents lattice values for constants.
Definition: AllocatorList.h:23
const_iterator begin() const
Definition: SmallVector.h:223
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:219
const_pointer data() const
Return a pointer to the vector&#39;s buffer, even if empty().
Definition: SmallVector.h:243
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:218
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:75
void push_back(const T &Elt)
Definition: SmallVector.h:316
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
bool isSmall() const
Return true if this is a smallvector which has not had dynamic memory allocated for it...
Definition: SmallVector.h:131
void assign(in_iter in_start, in_iter in_end)
Definition: SmallVector.h:557
SmallVector(ItTy S, ItTy E)
Definition: SmallVector.h:979
iterator insert(iterator I, const T &Elt)
Definition: SmallVector.h:640
iterator insert(iterator I, size_type NumToInsert, const T &Elt)
Definition: SmallVector.h:642
static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest, std::enable_if_t< std::is_same< typename std::remove_const< T1 >::type, T2 >::value > *=nullptr)
Copy the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements into ...
Definition: SmallVector.h:403
bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize)
Return true unless Elt will be invalidated by resizing the vector to NewSize.
Definition: SmallVector.h:141
void append(size_type NumInputs, const T &Elt)
Append NumInputs copies of Elt to the end.
Definition: SmallVector.h:528
void set_size(size_t N)
Set the array size to N, which the current array must have enough capacity for.
Definition: SmallVector.h:86
void reserve(size_type N)
Definition: SmallVector.h:493
const_reverse_iterator rend() const
Definition: SmallVector.h:231
SmallVectorBase(void *FirstEl, size_t TotalCapacity)
Definition: SmallVector.h:56
typename SuperClass::size_type size_type
Definition: SmallVector.h:441
void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")
Append to path.
Definition: Path.cpp:454
Definition: BitVector.h:941
size_t capacity_in_bytes(const BitVector &X)
Definition: BitVector.h:918
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
void resize(size_type N, const T &NV)
Definition: SmallVector.h:476
This file defines counterparts of C library allocation functions defined in the namespace &#39;std&#39;...
void grow_pod(size_t MinSize, size_t TSize)
Definition: SmallVector.h:125
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:544
An implementation of std::is_trivially_move_constructible since we have users with STLs that don&#39;t ye...
Definition: type_traits.h:109
SmallVector(SmallVectorImpl< T > &&RHS)
Definition: SmallVector.h:1008
void assertSafeToAddRange(ItTy, ItTy)
Definition: SmallVector.h:191
SmallVector(SmallVector &&RHS)
Definition: SmallVector.h:1003
SmallVector< typename std::remove_const< typename std::remove_reference< decltype(*std::begin(std::declval< R & >)))>::type >::type, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
Definition: SmallVector.h:1041
void assertSafeToReferenceAfterClear(ItTy, ItTy)
Definition: SmallVector.h:178
#define LLVM_GSL_OWNER
LLVM_GSL_OWNER - Apply this to owning classes like SmallVector to enable lifetime warnings...
Definition: Compiler.h:297
const_reference front() const
Definition: SmallVector.h:258
SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put method implementations that...
Definition: SmallVector.h:284
void grow(size_t MinSize=0)
Grow the allocated memory (without initializing new elements), doubling the size of the allocated mem...
Definition: SmallVector.h:340
void swap(SmallVectorImpl &RHS)
Definition: SmallVector.h:791
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::reverse_iterator< iterator > reverse_iterator
Definition: SmallVector.h:210
reference operator[](size_type idx)
Definition: SmallVector.h:245
#define offsetof(TYPE, MEMBER)
SmallVectorImpl(unsigned N)
Definition: SmallVector.h:445
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:339
void assertSafeToReferenceAfterClear(const T *From, const T *To)
Check whether any part of the range will be invalidated by clearing.
Definition: SmallVector.h:168
const_reverse_iterator rbegin() const
Definition: SmallVector.h:229
void assign(std::initializer_list< T > IL)
Definition: SmallVector.h:563
SmallVector & operator=(SmallVectorImpl< T > &&RHS)
Definition: SmallVector.h:1018
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:684
iterator erase(const_iterator CI)
Definition: SmallVector.h:568
void swap(llvm::SmallVector< T, N > &LHS, llvm::SmallVector< T, N > &RHS)
Implement std::swap in terms of SmallVector swap.
Definition: SmallVector.h:1059
SmallVector(const iterator_range< RangeTy > &R)
Definition: SmallVector.h:984
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:263
typename SuperClass::reference reference
Definition: SmallVector.h:440
void grow_pod(void *FirstEl, size_t MinSize, size_t TSize)
This is an implementation of the grow() method which only works on POD-like data types and is out of ...
Definition: SmallVector.cpp:74
const_reference back() const
Definition: SmallVector.h:267
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_malloc(size_t Sz)
Definition: MemAlloc.h:25
static void uninitialized_copy(It1 I, It1 E, It2 Dest)
Copy the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements as ne...
Definition: SmallVector.h:306
BlockVerifier::State From
static constexpr size_t SizeTypeMax()
The maximum value of the Size_T used.
Definition: SmallVector.h:51
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:960
void grow(size_t MinSize=0)
Double the size of the allocated memory, guaranteeing space for at least one more element or MinSize ...
Definition: SmallVector.h:417
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:504
#define LLVM_ATTRIBUTE_NORETURN
Definition: Compiler.h:249
static void uninitialized_move(It1 I, It1 E, It2 Dest)
Move the range [I, E) into the uninitialized memory starting with "Dest", constructing elements as ne...
Definition: SmallVector.h:298
SmallVector & operator=(SmallVector &&RHS)
Definition: SmallVector.h:1013
SmallVector(std::initializer_list< T > IL)
Definition: SmallVector.h:989
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:944
bool operator<(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:784
A range adaptor for a pair of iterators.
void assertSafeToAdd(const void *Elt, size_t N=1)
Check whether Elt will be invalidated by increasing the size of the vector by N.
Definition: SmallVector.h:163
void append(std::initializer_list< T > IL)
Definition: SmallVector.h:537
SmallVectorImpl & operator=(const SmallVectorImpl &RHS)
Definition: SmallVector.h:830
typename SuperClass::iterator iterator
Definition: SmallVector.h:438
const_reference operator[](size_type idx) const
Definition: SmallVector.h:249
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:231
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:636
void insert(iterator I, std::initializer_list< T > IL)
Definition: SmallVector.h:759
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:517
iterator erase(const_iterator CS, const_iterator CE)
Definition: SmallVector.h:583
SmallVectorTemplateBase(size_t Size)
Definition: SmallVector.h:286
basic Basic Alias true
This is the part of SmallVectorTemplateBase which does not depend on whether the type T is a POD...
Definition: SmallVector.h:108
size_type size_in_bytes() const
Definition: SmallVector.h:233
pointer data()
Return a pointer to the vector&#39;s buffer, even if empty().
Definition: SmallVector.h:241
#define I(x, y, z)
Definition: MD5.cpp:59
#define N
This is all the stuff common to all SmallVectors.
Definition: SmallVector.h:45
void assertSafeToAddRange(const T *From, const T *To)
Check whether any part of the range will be invalidated by growing.
Definition: SmallVector.h:181
size_t size() const
Definition: SmallVector.h:72
SmallVectorTemplateCommon(size_t Size)
Definition: SmallVector.h:123
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:160
size_t capacity() const
Definition: SmallVector.h:73
SmallVector(const SmallVector &RHS)
Definition: SmallVector.h:993
Root & operator=(Root &&)=delete
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1479
typename std::conditional< sizeof(T)< 4 &&sizeof(void *) >=8, uint64_t, uint32_t >::type SmallVectorSizeType
Definition: SmallVector.h:95
LLVM Value Representation.
Definition: Value.h:75
iterator insert(iterator I, ItTy From, ItTy To)
Definition: SmallVector.h:700
static void uninitialized_move(It1 I, It1 E, It2 Dest)
Move the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements into ...
Definition: SmallVector.h:387
IteratorT begin() const
SmallVector & operator=(std::initializer_list< T > IL)
Definition: SmallVector.h:1023
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1556
const_iterator end() const
Definition: SmallVector.h:225
Storage for the SmallVector elements.
Definition: SmallVector.h:942
bool operator==(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:776
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1549
static LLVM_ATTRIBUTE_NORETURN void report_size_overflow(size_t MinSize)
Report that MinSize doesn&#39;t fit into this vector&#39;s size type.
Definition: SmallVector.cpp:49
IteratorT end() const
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
#define T1
void resetToSmall()
Put this vector in a state of being small.
Definition: SmallVector.h:134
SmallVector(size_t Size, const T &Value=T())
Definition: SmallVector.h:970
void pop_back_n(size_type NumItems)
Definition: SmallVector.h:498
void assertSafeToEmplace(ArgType1 &Arg1, ArgTypes &... Args)
Check whether any argument will be invalidated by growing for emplace_back.
Definition: SmallVector.h:196
void resize(size_type N)
Definition: SmallVector.h:463
Figure out the offset of the first element.
Definition: SmallVector.h:98