All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
smallVector.h
Go to the documentation of this file.
1//
2// Copyright 2019 Pixar
3//
4// Licensed under the terms set forth in the LICENSE.txt file available at
5// https://openusd.org/license.
6//
7#ifndef PXR_BASE_TF_SMALL_VECTOR_H
8#define PXR_BASE_TF_SMALL_VECTOR_H
9
12
13#include "pxr/pxr.h"
14
15#include "pxr/base/arch/defines.h"
16
17#include <algorithm>
18#include <cstddef>
19#include <cstdint>
20#include <cstdlib>
21#include <initializer_list>
22#include <iterator>
23#include <limits>
24#include <memory>
25#include <new>
26#include <type_traits>
27
28PXR_NAMESPACE_OPEN_SCOPE
29
30// Contains parts of the small vector implementation that do not depend on
31// *all* of TfSmallVector's template parameters.
32class TfSmallVectorBase
33{
34protected:
35 // We present the public size_type and difference_type as std::size_t and
36 // std::ptrdiff_t to match std::vector, but internally we store size &
37 // capacity as uint32_t.
38 using _SizeMemberType = std::uint32_t;
39
40 // Union type containing local storage or a pointer to heap storage.
41 template <size_t Size, size_t Align, size_t NumLocal>
42 union _DataUnion;
43
44 // Helper alias to produce the right _DataUnion instantiation for a given
45 // ValueType and NumLocal elements.
46 template <class ValueType, size_t NumLocal>
47 using _Data = _DataUnion<sizeof(ValueType), alignof(ValueType), NumLocal>;
48
49public:
50 using size_type = std::size_t;
51 using difference_type = std::ptrdiff_t;
52
53 // Returns the local capacity that may be used without increasing the size
54 // of the TfSmallVector. TfSmallVector<T, N> will never use more local
55 // capacity than is specified by N but clients that wish to maximize local
56 // occupancy in a generic way can compute N using this function.
57 template <typename U>
58 static constexpr size_type ComputeSerendipitousLocalCapacity() {
59 return (alignof(U) <= alignof(_Data<U, 0>))
60 ? sizeof(_Data<U, 0>) / sizeof(U)
61 : 0;
62 }
63
64protected:
65
66 // Enabler used to disambiguate the range-based constructor (begin, end)
67 // from the n-copies constructor (size_t n, value_type const &value)
68 // when the value_type is integral.
69 template<typename _ForwardIterator>
70 using _EnableIfForwardIterator =
71 std::enable_if_t<
72 std::is_convertible_v<
73 typename std::iterator_traits<
74 _ForwardIterator>::iterator_category,
75 std::forward_iterator_tag
76 >
77 >;
78
79 // Invoke std::uninitialized_copy that either moves or copies entries,
80 // depending on whether the type is move constructible or not.
81 template <typename Iterator>
82 static Iterator _UninitializedMove(
83 Iterator first, Iterator last, Iterator dest) {
84 return std::uninitialized_copy(
85 std::make_move_iterator(first),
86 std::make_move_iterator(last),
87 dest);
88 }
89
90 // Invokes either the move or copy constructor (via placement new),
91 // depending on whether U is move constructible or not.
92 template <typename U>
93 static void _MoveConstruct(U *p, U *src) {
94 new (p) U(std::move(*src));
95 }
96
97 // The data storage, which is a union of both the local storage, as well
98 // as a pointer, holding the address to the remote storage on the heap, if
99 // used.
100 template <size_t Size, size_t Align, size_t NumLocal>
101 union _DataUnion {
102 public:
103 // XXX: Could in principle assert in calls to GetLocalStorage() when
104 // HasLocal is false. Add dependency on tf/diagnostic.h?
105 static constexpr bool HasLocal = NumLocal != 0;
106
107 void *GetLocalStorage() {
108 return HasLocal ? _local : nullptr;
109 }
110 const void *GetLocalStorage() const {
111 return HasLocal ? _local : nullptr;
112 }
113
114 void *GetRemoteStorage() {
115 return _remote;
116 }
117 const void *GetRemoteStorage() const {
118 return _remote;
119 }
120
121 void SetRemoteStorage(void *p) {
122 _remote = p;
123 }
124 private:
125 // Pointer to heap storage.
126 void *_remote;
127 // Local storage -- min size is sizeof(_remote).
128 alignas(NumLocal == 0 ? std::alignment_of_v<void *> : Align)
129 char _local[std::max<size_t>(Size * NumLocal, sizeof(_remote))];
130 };
131};
132
155template <typename T, uint32_t N>
156class TfSmallVector : public TfSmallVectorBase
157{
158public:
159
166
169
170 typedef T value_type;
171 typedef T& reference;
172 typedef const T& const_reference;
173
175
178
179 using iterator = T*;
180 using const_iterator = const T*;
181 typedef std::reverse_iterator<iterator> reverse_iterator;
182 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
183
185
188 TfSmallVector() : _size(0), _capacity(N) {}
189
192 explicit TfSmallVector(size_type n) :
193 _capacity(N) {
194 _InitStorage(n);
195 value_type *d = data();
196 for (size_type i = 0; i < n; ++i) {
197 new (d + i) value_type();
198 }
199 }
200
203 TfSmallVector(size_type n, const value_type &v) :
204 _capacity(N) {
205 _InitStorage(n);
206 std::uninitialized_fill_n(data(), n, v);
207 }
208
211 enum DefaultInitTag { DefaultInit };
212 TfSmallVector(size_type n, DefaultInitTag) :
213 _capacity(N) {
214 _InitStorage(n);
215 value_type *d = data();
216 for (size_type i = 0; i < n; ++i) {
217 new (d + i) value_type;
218 }
219 }
220
223 TfSmallVector(const TfSmallVector &rhs) : _capacity(N) {
224 _InitStorage(rhs.size());
225 std::uninitialized_copy(rhs.begin(), rhs.end(), begin());
226 }
227
230 TfSmallVector(TfSmallVector &&rhs) : _size(0), _capacity(N) {
231 // If rhs can not be stored locally, take rhs's remote storage and
232 // reset rhs to empty.
233 if (rhs.size() > N) {
234 _SetRemoteStorage(rhs._GetRemoteStorage());
235 std::swap(_capacity, rhs._capacity);
236 }
237
238 // If rhs is stored locally, it's faster to simply move the entries
239 // into this vector's storage, destruct the entries at rhs, and swap
240 // sizes. Note that capacities will be the same in this case, so no
241 // need to swap those.
242 else {
243 _UninitializedMove(rhs.begin(), rhs.end(), begin());
244 rhs._Destruct();
245 }
246 std::swap(_size, rhs._size);
247 }
248
250 TfSmallVector(std::initializer_list<T> values)
251 : TfSmallVector(values.begin(), values.end()) {
252 }
253
256 template<typename ForwardIterator,
257 typename = _EnableIfForwardIterator<ForwardIterator>>
258 TfSmallVector(ForwardIterator first, ForwardIterator last) : _capacity(N)
259 {
260 _InitStorage(std::distance(first, last));
261 std::uninitialized_copy(first, last, begin());
262 }
263
267 _Destruct();
268 _FreeStorage();
269 }
270
274 if (this != &rhs) {
275 assign(rhs.begin(), rhs.end());
276 }
277 return *this;
278 }
279
283 if (this != &rhs) {
284 swap(rhs);
285 }
286 return *this;
287 }
288
291 TfSmallVector &operator=(std::initializer_list<T> ilist) {
292 assign(ilist.begin(), ilist.end());
293 return *this;
294 }
295
298 void swap(TfSmallVector &rhs) {
299 // Both this vector and rhs are stored locally.
300 if (_IsLocal() && rhs._IsLocal()) {
301 TfSmallVector *smaller = size() < rhs.size() ? this : &rhs;
302 TfSmallVector *larger = size() < rhs.size() ? &rhs : this;
303
304 // Swap all the entries up to the size of the smaller vector.
305 std::swap_ranges(smaller->begin(), smaller->end(), larger->begin());
306
307 // Move the tail end of the entries, and destruct them at the
308 // source vector.
309 for (size_type i = smaller->size(); i < larger->size(); ++i) {
310 _MoveConstruct(smaller->data() + i, &(*larger)[i]);
311 (*larger)[i].~value_type();
312 }
313
314 // Swap sizes. Capacities are already equal in this case.
315 std::swap(smaller->_size, larger->_size);
316 }
317
318 // Both this vector and rhs are stored remotely. Simply swap the
319 // pointers, as well as size and capacity.
320 else if (!_IsLocal() && !rhs._IsLocal()) {
321 value_type *tmp = _GetRemoteStorage();
322 _SetRemoteStorage(rhs._GetRemoteStorage());
323 rhs._SetRemoteStorage(tmp);
324
325 std::swap(_size, rhs._size);
326 std::swap(_capacity, rhs._capacity);
327 }
328
329 // Either this vector or rhs is stored remotely, whereas the other
330 // one is stored locally.
331 else {
332 TfSmallVector *remote = _IsLocal() ? &rhs : this;
333 TfSmallVector *local = _IsLocal() ? this : &rhs;
334
335 // Get a pointer to the remote storage. We'll be overwriting the
336 // pointer value below, so gotta retain it first.
337 value_type *remoteStorage = remote->_GetStorage();
338
339 // Move all the entries from the vector with the local storage, to
340 // the other vector's local storage. This will overwrite the pointer
341 // to the other vectors remote storage. Note that we will have to
342 // also destruct the elements at the source's local storage. The
343 // source will become the one with the remote storage, so those
344 // entries will be essentially freed.
345 for (size_type i = 0; i < local->size(); ++i) {
346 _MoveConstruct(remote->_GetLocalStorage() + i, &(*local)[i]);
347 (*local)[i].~value_type();
348 }
349
350 // Swap the remote storage into the vector which previously had the
351 // local storage. It's been properly cleaned up now.
352 local->_SetRemoteStorage(remoteStorage);
353
354 // Swap sizes and capacities. Easy peasy.
355 std::swap(remote->_size, local->_size);
356 std::swap(remote->_capacity, local->_capacity);
357 }
358
359 }
360
363 iterator insert(const_iterator it, value_type &&v) {
364 return _Insert(it, std::move(v));
365 }
366
369 iterator insert(const_iterator it, const value_type &v) {
370 return _Insert(it, v);
371 }
372
375 iterator erase(const_iterator it) {
376 return erase(it, it + 1);
377 }
378
381 iterator erase(const_iterator it, const_iterator last) {
382 value_type *p = const_cast<value_type *>(&*it);
383 value_type *q = const_cast<value_type *>(&*last);
384
385 // If we're not removing anything, bail out.
386 if (p == q) {
387 return iterator(p);
388 }
389
390 const size_type num = std::distance(p, q);
391
392 // Move entries starting at last, down a few slots to starting a it.
393 value_type *e = data() + size();
394 std::move(q, e, p);
395
396 // Destruct all the freed up slots at the end of the vector.
397 for (value_type *i = (e - num); i != e; ++i) {
398 i->~value_type();
399 }
400
401 // Bump down the size.
402 _size -= num;
403
404 // Return an iterator to the next entry.
405 return iterator(p);
406 }
407
410 void reserve(size_type newCapacity) {
411 // Only reserve storage if the new capacity would grow past the local
412 // storage, or the currently allocated storage. We'll grow to
413 // accommodate exactly newCapacity entries.
414 if (newCapacity > capacity()) {
415 _GrowStorage(newCapacity);
416 }
417 }
418
421 void resize(size_type newSize, const value_type &v = value_type()) {
422 // If the new size is smaller than the current size, let go of some
423 // entries at the tail.
424 if (newSize < size()) {
425 erase(const_iterator(data() + newSize),
426 const_iterator(data() + size()));
427 }
428
429 // Otherwise, lets grow and fill: Reserve some storage, fill the tail
430 // end with copies of v, and update the new size.
431 else if (newSize > size()) {
432 reserve(newSize);
433 std::uninitialized_fill(data() + size(), data() + newSize, v);
434 _size = newSize;
435 }
436 }
437
441 void clear() {
442 _Destruct();
443 _size = 0;
444 }
445
449 template<typename ForwardIterator,
450 typename = _EnableIfForwardIterator<ForwardIterator>>
451 void assign(ForwardIterator first, ForwardIterator last) {
452 clear();
453 const size_type newSize = std::distance(first, last);
454 reserve(newSize);
455 std::uninitialized_copy(first, last, begin());
456 _size = newSize;
457 }
458
461 void assign(std::initializer_list<T> ilist) {
462 assign(ilist.begin(), ilist.end());
463 }
464
467 template < typename... Args >
468 void emplace_back(Args&&... args) {
469 if (size() == capacity()) {
470 _GrowStorage(_NextCapacity());
471 }
472 new (data() + size()) value_type(std::forward<Args>(args)...);
473 _size += 1;
474 }
475
478 void push_back(const value_type &v) {
479 emplace_back(v);
480 }
481
484 void push_back(value_type &&v) {
485 emplace_back(std::move(v));
486 }
487
491 template <typename ForwardIterator>
492 void insert(iterator pos, ForwardIterator first, ForwardIterator last)
493 {
494 static_assert(
495 std::is_convertible<
496 typename std::iterator_traits<ForwardIterator>::iterator_category,
497 std::forward_iterator_tag>::value,
498 "Input Iterators not supported.");
499
500 // Check for the insert-at-end special case as the very first thing so
501 // that we give the compiler the best possible opportunity to
502 // eliminate the general case code.
503 const bool insertAtEnd = pos == end();
504
505 const long numNewElems = std::distance(first, last);
506 const size_type neededCapacity = size() + numNewElems;
507 const size_type nextCapacity =
508 std::max(_NextCapacity(), neededCapacity);
509
510 // Insertions at the end would be handled correctly by the code below
511 // without this special case. However, insert(end(), f, l) is an
512 // extremely common operation so we provide this fast path both to
513 // avoid unneeded work and to make it easier for the compiler to
514 // eliminate dead code when pos == end().
515 if (insertAtEnd) {
516 // The reallocation here is not a simple reserve. We want to grow
517 // the storage only when there are too many new elements but the
518 // desired size is based on the growth factor.
519 if (neededCapacity > capacity()) {
520 _GrowStorage(nextCapacity);
521 }
522 std::uninitialized_copy(first, last, end());
523 _size += numNewElems;
524 return;
525 }
526
527 if (neededCapacity > capacity()) {
528 // Because we need to realloc, we can do the insertion by copying
529 // each range, [begin(), pos), [first, last), [pos, end()), into
530 // the new storage.
531
532 const size_type posI = std::distance(begin(), pos);
533 value_type *newStorage = _Allocate(nextCapacity);
534
535 iterator newPrefixBegin = iterator(newStorage);
536 iterator newPos = newPrefixBegin + posI;
537 iterator newSuffixBegin = newPos + numNewElems;
538 _UninitializedMove(begin(), pos, newPrefixBegin);
539 std::uninitialized_copy(first, last, newPos);
540 _UninitializedMove(pos, end(), newSuffixBegin);
541
542 // Destroy old data and set up this new buffer.
543 _Destruct();
544 _FreeStorage();
545 _SetRemoteStorage(newStorage);
546 _capacity = nextCapacity;
547 }
548 else {
549 // Insert in-place requires handling four ranges.
550 //
551 // For both the range-to-move [pos, end()) and the range-to-insert
552 // [first, last), there are two subranges: the subrange to copy
553 // and the subrange to uinitialized_copy. Note that only three of
554 // these ranges may be non-empty: either there is a non-empty
555 // prefix of [pos, end()) that needs to be copied over existing
556 // elements or there is a non-empty suffix of [first, last) that
557 // needs to be placed in uninitialized storage.
558
559 const long numMoveElems = std::distance(pos, end());
560 const long numUninitMoves = std::min(numNewElems, numMoveElems);
561 const long numInitMoves = numMoveElems - numUninitMoves;
562 const long numUninitNews = numNewElems - numUninitMoves;
563 const long numInitNews = numNewElems - numUninitNews;
564
565 // Move our existing elements out of the way of new elements.
566 iterator umSrc = pos + numInitMoves;
567 iterator umDst = end() + numUninitNews;
568 _UninitializedMove(umSrc, end(), umDst);
569 std::copy_backward(pos, umSrc, umDst);
570
571 // Copy new elements into place.
572 for (long i=0; i<numInitNews; ++i, ++first, ++pos) {
573 *pos = *first;
574 }
575 std::uninitialized_copy(first, last, end());
576 }
577
578 _size += numNewElems;
579 }
580
583 void insert(iterator pos, std::initializer_list<T> ilist) {
584 insert(pos, ilist.begin(), ilist.end());
585 }
586
589 void pop_back() {
590 back().~value_type();
591 _size -= 1;
592 }
593
596 size_type size() const {
597 return _size;
598 }
599
602 static constexpr size_type max_size() {
603 return std::numeric_limits<_SizeMemberType>::max();
604 }
605
608 bool empty() const {
609 return size() == 0;
610 }
611
617 size_type capacity() const {
618 return _capacity;
619 }
620
625 static constexpr size_type internal_capacity() {
626 return N;
627 }
628
631
632 iterator begin() {
633 return iterator(_GetStorage());
634 }
635
636 const_iterator begin() const {
637 return const_iterator(_GetStorage());
638 }
639
640 const_iterator cbegin() const {
641 return begin();
642 }
643
645
648
649 iterator end() {
650 return iterator(_GetStorage() + size());
651 }
652
653 const_iterator end() const {
654 return const_iterator(_GetStorage() + size());
655 }
656
657 const_iterator cend() const {
658 return end();
659 }
660
662
665
666 reverse_iterator rbegin() {
667 return reverse_iterator(end());
668 }
669
670 const_reverse_iterator rbegin() const {
671 return const_reverse_iterator(end());
672 }
673
674 const_reverse_iterator crbegin() const {
675 return rbegin();
676 }
677
679
682
683 reverse_iterator rend() {
684 return reverse_iterator(begin());
685 }
686
687 const_reverse_iterator rend() const {
688 return const_reverse_iterator(begin());
689 }
690
691 const_reverse_iterator crend() const {
692 return rend();
693 }
694
696
699 reference front() {
700 return *begin();
701 }
702
705 const_reference front() const {
706 return *begin();
707 }
708
711 reference back() {
712 return data()[size() - 1];
713 }
714
717 const_reference back() const {
718 return data()[size() - 1];
719 }
720
723 reference operator[](size_type i) {
724 return data()[i];
725 }
726
729 const_reference operator[](size_type i) const {
730 return data()[i];
731 }
732
735 value_type *data() {
736 return _GetStorage();
737 }
738
741 const value_type *data() const {
742 return _GetStorage();
743 }
744
747 bool operator==(const TfSmallVector &rhs) const {
748 return size() == rhs.size() && std::equal(begin(), end(), rhs.begin());
749 }
750
753 bool operator!=(const TfSmallVector &rhs) const {
754 return !operator==(rhs);
755 }
756
757private:
758
759 // Raw data access.
760 value_type *_GetLocalStorage() {
761 return static_cast<value_type *>(_data.GetLocalStorage());
762 }
763 const value_type *_GetLocalStorage() const {
764 return static_cast<const value_type *>(_data.GetLocalStorage());
765 }
766
767 value_type *_GetRemoteStorage() {
768 return static_cast<value_type *>(_data.GetRemoteStorage());
769 }
770 const value_type *_GetRemoteStorage() const {
771 return static_cast<const value_type *>(_data.GetRemoteStorage());
772 }
773
774 void _SetRemoteStorage(value_type *p) {
775 _data.SetRemoteStorage(static_cast<void *>(p));
776 }
777
778 // Returns true if the local storage is used.
779 bool _IsLocal() const {
780 return _capacity <= N;
781 }
782
783 // Return a pointer to the storage, which is either local or remote
784 // depending on the current capacity.
785 value_type *_GetStorage() {
786 return _IsLocal() ? _GetLocalStorage() : _GetRemoteStorage();
787 }
788
789 // Return a const pointer to the storage, which is either local or remote
790 // depending on the current capacity.
791 const value_type *_GetStorage() const {
792 return _IsLocal() ? _GetLocalStorage() : _GetRemoteStorage();
793 }
794
795 // Free the remotely allocated storage.
796 void _FreeStorage() {
797 if (!_IsLocal()) {
798 free(_GetRemoteStorage());
799 }
800 }
801
802 // Destructs all the elements stored in this vector.
803 void _Destruct() {
804 value_type *b = data();
805 value_type *e = b + size();
806 for (value_type *p = b; p != e; ++p) {
807 p->~value_type();
808 }
809 }
810
811 // Allocate a buffer on the heap.
812 static value_type *_Allocate(size_type size) {
813 return static_cast<value_type *>(malloc(sizeof(value_type) * size));
814 }
815
816 // Initialize the vector with new storage, updating the capacity and size.
817 void _InitStorage(size_type size) {
818 if (size > capacity()) {
819 _SetRemoteStorage(_Allocate(size));
820 _capacity = size;
821 }
822#if defined(ARCH_COMPILER_GCC) && ARCH_COMPILER_GCC_MAJOR < 11
823 else if constexpr (!_data.HasLocal) {
824 // When there's no local storage and we're not allocating remote
825 // storage, initialize the remote storage pointer to avoid
826 // spurious compiler warnings about maybe-uninitialized values
827 // being used.
828
829 // This clause can be removed upon upgrade to gcc 11 as
830 // the new compiler no longer generates this warning in this case.
831 _data.SetRemoteStorage(nullptr);
832 }
833#endif
834 _size = size;
835 }
836
837 // Grow the storage to be able to accommodate newCapacity entries. This
838 // always allocates remote storage.
839 void _GrowStorage(const size_type newCapacity) {
840 value_type *newStorage = _Allocate(newCapacity);
841 _UninitializedMove(begin(), end(), iterator(newStorage));
842 _Destruct();
843 _FreeStorage();
844 _SetRemoteStorage(newStorage);
845 _capacity = newCapacity;
846 }
847
848 // Returns the next capacity to use for vector growth. The growth factor
849 // here is 1.5. A constant 1 is added so that we do not have to special
850 // case initial capacities of 0 and 1.
851 size_type _NextCapacity() const {
852 const size_type cap = capacity();
853 return cap + (cap / 2) + 1;
854 }
855
856 // Insert the value v at iterator it. We use this method that takes a
857 // universal reference to de-duplicate the logic required for the insert
858 // overloads, one taking an rvalue reference, and the other one taking a
859 // const reference. This way, we can take the most optimal code path (
860 // move, or copy without making redundant copies) based on whether v is
861 // a rvalue reference or const reference.
862 template < typename U >
863 iterator _Insert(const_iterator it, U &&v) {
864 value_type *newEntry;
865
866 // If the iterator points to the end, simply push back.
867 if (it == end()) {
868 push_back(std::forward<U>(v));
869 return end() - 1;
870 }
871
872 // Grow the remote storage, if we need to. This invalidates iterators,
873 // so special care must be taken in order to return a new, valid
874 // iterator.
875 else if (size() == capacity()) {
876 const size_type newCapacity = _NextCapacity();
877 value_type *newStorage = _Allocate(newCapacity);
878
879 value_type *i = const_cast<value_type *>(&*it);
880 value_type *curData = data();
881 newEntry = _UninitializedMove(curData, i, newStorage);
882
883 new (newEntry) value_type(std::forward<U>(v));
884
885 _UninitializedMove(i, curData + size(), newEntry + 1);
886
887 _Destruct();
888 _FreeStorage();
889
890 _SetRemoteStorage(newStorage);
891 _capacity = newCapacity;
892 }
893
894 // Our current capacity is big enough to allow us to simply shift
895 // elements up one slot and insert v at it.
896 else {
897 // Move all the elements after it up by one slot.
898 newEntry = const_cast<value_type *>(&*it);
899 value_type *last = const_cast<value_type *>(&back());
900 new (data() + size()) value_type(std::move(*last));
901 std::move_backward(newEntry, last, last + 1);
902
903 // Move v into the slot at the supplied iterator position.
904 newEntry->~value_type();
905 new (newEntry) value_type(std::forward<U>(v));
906 }
907
908 // Bump size and return an iterator to the newly inserted entry.
909 ++_size;
910 return iterator(newEntry);
911 }
912
913 // The vector storage, which is a union of the local storage and a pointer
914 // to the heap memory, if allocated.
915 _Data<value_type, N> _data;
916
917 // The current size of the vector, i.e. how many entries it contains.
918 _SizeMemberType _size;
919
920 // The current capacity of the vector, i.e. how big the currently allocated
921 // storage space is.
922 _SizeMemberType _capacity;
923};
924
926
927template < typename T, uint32_t N >
929{
930 a.swap(b);
931}
932
934
935PXR_NAMESPACE_CLOSE_SCOPE
936
937#endif
This is a small-vector class with local storage optimization, the local storage can be specified via ...
Definition: smallVector.h:157
void push_back(const value_type &v)
Copy an entry to the back of the vector,.
Definition: smallVector.h:478
void pop_back()
Remove the entry at the back of the vector.
Definition: smallVector.h:589
const_reference front() const
Returns the first element in the vector.
Definition: smallVector.h:705
reference operator[](size_type i)
Access the specified element.
Definition: smallVector.h:723
void assign(ForwardIterator first, ForwardIterator last)
Clears any previously held entries, and copies entries between [ first, last ) to this vector.
Definition: smallVector.h:451
void reserve(size_type newCapacity)
Reserve storage for newCapacity entries.
Definition: smallVector.h:410
iterator erase(const_iterator it)
Erase an entry at the given iterator.
Definition: smallVector.h:375
TfSmallVector(ForwardIterator first, ForwardIterator last)
Creates a new vector containing copies of the data between first and last.
Definition: smallVector.h:258
void assign(std::initializer_list< T > ilist)
Replace existing contents with the contents of ilist.
Definition: smallVector.h:461
TfSmallVector(std::initializer_list< T > values)
Construct a new vector from initializer list.
Definition: smallVector.h:250
~TfSmallVector()
Destructor.
Definition: smallVector.h:266
bool operator!=(const TfSmallVector &rhs) const
Lexicographically compares the elements in the vectors for inequality.
Definition: smallVector.h:753
size_type size() const
Returns the current size of the vector.
Definition: smallVector.h:596
const_reference back() const
Returns the last elements in the vector.
Definition: smallVector.h:717
iterator erase(const_iterator it, const_iterator last)
Erase entries between [ first, last ) from the vector.
Definition: smallVector.h:381
TfSmallVector & operator=(std::initializer_list< T > ilist)
Replace existing contents with the contents of ilist.
Definition: smallVector.h:291
TfSmallVector(size_type n)
Construct a vector holding n value-initialized elements.
Definition: smallVector.h:192
bool empty() const
Returns true if this vector is empty.
Definition: smallVector.h:608
reference front()
Returns the first element in the vector.
Definition: smallVector.h:699
static constexpr size_type max_size()
Returns the maximum size of this vector.
Definition: smallVector.h:602
TfSmallVector(size_type n, const value_type &v)
Construct a vector holding n copies of v.
Definition: smallVector.h:203
bool operator==(const TfSmallVector &rhs) const
Lexicographically compares the elements in the vectors for equality.
Definition: smallVector.h:747
void swap(TfSmallVector &rhs)
Swap two vector instances.
Definition: smallVector.h:298
void resize(size_type newSize, const value_type &v=value_type())
Resize the vector to newSize and insert copies of \v.
Definition: smallVector.h:421
const value_type * data() const
Direct access to the underlying array.
Definition: smallVector.h:741
DefaultInitTag
Construct a vector holding n default-initialized elements.
Definition: smallVector.h:211
TfSmallVector(const TfSmallVector &rhs)
Copy constructor.
Definition: smallVector.h:223
const_reference operator[](size_type i) const
Access the specified element.
Definition: smallVector.h:729
TfSmallVector & operator=(const TfSmallVector &rhs)
Assignment operator.
Definition: smallVector.h:273
static constexpr size_type internal_capacity()
Returns the local storage capacity.
Definition: smallVector.h:625
void insert(iterator pos, ForwardIterator first, ForwardIterator last)
Copy the range denoted by [first, last) into this vector before pos.
Definition: smallVector.h:492
void emplace_back(Args &&... args)
Emplace an entry at the back of the vector.
Definition: smallVector.h:468
void clear()
Clear the entries in the vector.
Definition: smallVector.h:441
iterator insert(const_iterator it, value_type &&v)
Insert an rvalue-reference entry at the given iterator position.
Definition: smallVector.h:363
TfSmallVector & operator=(TfSmallVector &&rhs)
Move assignment operator.
Definition: smallVector.h:282
size_type capacity() const
Returns the current capacity of this vector.
Definition: smallVector.h:617
TfSmallVector(TfSmallVector &&rhs)
Move constructor.
Definition: smallVector.h:230
void insert(iterator pos, std::initializer_list< T > ilist)
Insert elements from ilist starting at position pos.
Definition: smallVector.h:583
value_type * data()
Direct access to the underlying array.
Definition: smallVector.h:735
iterator insert(const_iterator it, const value_type &v)
Insert an entry at the given iterator.
Definition: smallVector.h:369
reference back()
Returns the last element in the vector.
Definition: smallVector.h:711
void push_back(value_type &&v)
Move an entry to the back of the vector.
Definition: smallVector.h:484