This document is for a version of USD that is under development. See this page for the current release.
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