Bitcoin ABC  0.24.7
P2P Digital Currency
prevector.h
Go to the documentation of this file.
1 // Copyright (c) 2015-2016 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #ifndef BITCOIN_PREVECTOR_H
6 #define BITCOIN_PREVECTOR_H
7 
8 #include <algorithm>
9 #include <cassert>
10 #include <cstddef>
11 #include <cstdint>
12 #include <cstdlib>
13 #include <cstring>
14 #include <type_traits>
15 #include <utility>
16 
36 template <unsigned int N, typename T, typename Size = uint32_t,
37  typename Diff = int32_t>
38 class prevector {
39 public:
40  typedef Size size_type;
41  typedef Diff difference_type;
42  typedef T value_type;
44  typedef const value_type &const_reference;
45  typedef value_type *pointer;
46  typedef const value_type *const_pointer;
47 
48  class iterator {
49  T *ptr;
50 
51  public:
52  typedef Diff difference_type;
53  typedef T value_type;
54  typedef T *pointer;
55  typedef T &reference;
56  typedef std::random_access_iterator_tag iterator_category;
57  iterator() : ptr(nullptr) {}
58  iterator(T *ptr_) : ptr(ptr_) {}
59  T &operator*() const { return *ptr; }
60  T *operator->() const { return ptr; }
61  T &operator[](size_type pos) { return ptr[pos]; }
62  const T &operator[](size_type pos) const { return ptr[pos]; }
64  ptr++;
65  return *this;
66  }
68  ptr--;
69  return *this;
70  }
72  iterator copy(*this);
73  ++(*this);
74  return copy;
75  }
77  iterator copy(*this);
78  --(*this);
79  return copy;
80  }
82  return (&(*a) - &(*b));
83  }
84  iterator operator+(size_type n) { return iterator(ptr + n); }
86  ptr += n;
87  return *this;
88  }
89  iterator operator-(size_type n) { return iterator(ptr - n); }
91  ptr -= n;
92  return *this;
93  }
94  bool operator==(iterator x) const { return ptr == x.ptr; }
95  bool operator!=(iterator x) const { return ptr != x.ptr; }
96  bool operator>=(iterator x) const { return ptr >= x.ptr; }
97  bool operator<=(iterator x) const { return ptr <= x.ptr; }
98  bool operator>(iterator x) const { return ptr > x.ptr; }
99  bool operator<(iterator x) const { return ptr < x.ptr; }
100  };
101 
103  T *ptr;
104 
105  public:
106  typedef Diff difference_type;
107  typedef T value_type;
108  typedef T *pointer;
109  typedef T &reference;
110  typedef std::bidirectional_iterator_tag iterator_category;
111  reverse_iterator() : ptr(nullptr) {}
112  reverse_iterator(T *ptr_) : ptr(ptr_) {}
113  T &operator*() { return *ptr; }
114  const T &operator*() const { return *ptr; }
115  T *operator->() { return ptr; }
116  const T *operator->() const { return ptr; }
118  ptr++;
119  return *this;
120  }
122  ptr--;
123  return *this;
124  }
126  reverse_iterator copy(*this);
127  ++(*this);
128  return copy;
129  }
131  reverse_iterator copy(*this);
132  --(*this);
133  return copy;
134  }
135  bool operator==(reverse_iterator x) const { return ptr == x.ptr; }
136  bool operator!=(reverse_iterator x) const { return ptr != x.ptr; }
137  };
138 
140  const T *ptr;
141 
142  public:
143  typedef Diff difference_type;
144  typedef const T value_type;
145  typedef const T *pointer;
146  typedef const T &reference;
147  typedef std::random_access_iterator_tag iterator_category;
148  const_iterator() : ptr(nullptr) {}
149  const_iterator(const T *ptr_) : ptr(ptr_) {}
150  const_iterator(iterator x) : ptr(&(*x)) {}
151  const T &operator*() const { return *ptr; }
152  const T *operator->() const { return ptr; }
153  const T &operator[](size_type pos) const { return ptr[pos]; }
155  ptr++;
156  return *this;
157  }
159  ptr--;
160  return *this;
161  }
163  const_iterator copy(*this);
164  ++(*this);
165  return copy;
166  }
168  const_iterator copy(*this);
169  --(*this);
170  return copy;
171  }
173  return (&(*a) - &(*b));
174  }
176  return const_iterator(ptr + n);
177  }
179  ptr += n;
180  return *this;
181  }
183  return const_iterator(ptr - n);
184  }
186  ptr -= n;
187  return *this;
188  }
189  bool operator==(const_iterator x) const { return ptr == x.ptr; }
190  bool operator!=(const_iterator x) const { return ptr != x.ptr; }
191  bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
192  bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
193  bool operator>(const_iterator x) const { return ptr > x.ptr; }
194  bool operator<(const_iterator x) const { return ptr < x.ptr; }
195  };
196 
198  const T *ptr;
199 
200  public:
201  typedef Diff difference_type;
202  typedef const T value_type;
203  typedef const T *pointer;
204  typedef const T &reference;
205  typedef std::bidirectional_iterator_tag iterator_category;
206  const_reverse_iterator() : ptr(nullptr) {}
207  const_reverse_iterator(const T *ptr_) : ptr(ptr_) {}
209  const T &operator*() const { return *ptr; }
210  const T *operator->() const { return ptr; }
212  ptr++;
213  return *this;
214  }
216  ptr--;
217  return *this;
218  }
220  const_reverse_iterator copy(*this);
221  ++(*this);
222  return copy;
223  }
225  const_reverse_iterator copy(*this);
226  --(*this);
227  return copy;
228  }
229  bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; }
230  bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; }
231  };
232 
233 private:
234 #pragma pack(push, 1)
236  char direct[sizeof(T) * N];
237  struct {
238  char *indirect;
241  };
242 #pragma pack(pop)
243  alignas(char *) direct_or_indirect _union = {};
245 
246  static_assert(alignof(char *) % alignof(size_type) == 0 &&
247  sizeof(char *) % alignof(size_type) == 0,
248  "size_type cannot have more restrictive alignment "
249  "requirement than pointer");
250  static_assert(alignof(char *) % alignof(T) == 0,
251  "value_type T cannot have more restrictive alignment "
252  "requirement than pointer");
253 
255  return reinterpret_cast<T *>(_union.direct) + pos;
256  }
257  const T *direct_ptr(difference_type pos) const {
258  return reinterpret_cast<const T *>(_union.direct) + pos;
259  }
261  return reinterpret_cast<T *>(_union.indirect_contents.indirect) + pos;
262  }
263  const T *indirect_ptr(difference_type pos) const {
264  return reinterpret_cast<const T *>(_union.indirect_contents.indirect) +
265  pos;
266  }
267  bool is_direct() const { return _size <= N; }
268 
269  void change_capacity(size_type new_capacity) {
270  if (new_capacity <= N) {
271  if (!is_direct()) {
272  T *indirect = indirect_ptr(0);
273  T *src = indirect;
274  T *dst = direct_ptr(0);
275  memcpy(dst, src, size() * sizeof(T));
276  free(indirect);
277  _size -= N + 1;
278  }
279  } else {
280  if (!is_direct()) {
281  // FIXME: Because malloc/realloc here won't call new_handler if
282  // allocation fails, assert success. These should instead use an
283  // allocator or new/delete so that handlers are called as
284  // necessary, but performance would be slightly degraded by
285  // doing so.
286  _union.indirect_contents.indirect = static_cast<char *>(
288  ((size_t)sizeof(T)) * new_capacity));
290  _union.indirect_contents.capacity = new_capacity;
291  } else {
292  char *new_indirect = static_cast<char *>(
293  malloc(((size_t)sizeof(T)) * new_capacity));
294  assert(new_indirect);
295  T *src = direct_ptr(0);
296  T *dst = reinterpret_cast<T *>(new_indirect);
297  memcpy(dst, src, size() * sizeof(T));
298  _union.indirect_contents.indirect = new_indirect;
299  _union.indirect_contents.capacity = new_capacity;
300  _size += N + 1;
301  }
302  }
303  }
304 
306  return is_direct() ? direct_ptr(pos) : indirect_ptr(pos);
307  }
308  const T *item_ptr(difference_type pos) const {
309  return is_direct() ? direct_ptr(pos) : indirect_ptr(pos);
310  }
311 
312  void fill(T *dst, ptrdiff_t count, const T &value = T{}) {
313  std::fill_n(dst, count, value);
314  }
315 
316  template <typename InputIterator>
317  void fill(T *dst, InputIterator first, InputIterator last) {
318  while (first != last) {
319  new (static_cast<void *>(dst)) T(*first);
320  ++dst;
321  ++first;
322  }
323  }
324 
325 public:
326  void assign(size_type n, const T &val) {
327  clear();
328  if (capacity() < n) {
329  change_capacity(n);
330  }
331  _size += n;
332  fill(item_ptr(0), n, val);
333  }
334 
335  template <typename InputIterator>
336  void assign(InputIterator first, InputIterator last) {
337  size_type n = last - first;
338  clear();
339  if (capacity() < n) {
340  change_capacity(n);
341  }
342  _size += n;
343  fill(item_ptr(0), first, last);
344  }
345 
347 
348  explicit prevector(size_type n) { resize(n); }
349 
350  explicit prevector(size_type n, const T &val) {
351  change_capacity(n);
352  _size += n;
353  fill(item_ptr(0), n, val);
354  }
355 
356  template <typename InputIterator>
357  prevector(InputIterator first, InputIterator last) {
358  size_type n = last - first;
359  change_capacity(n);
360  _size += n;
361  fill(item_ptr(0), first, last);
362  }
363 
365  size_type n = other.size();
366  change_capacity(n);
367  _size += n;
368  fill(item_ptr(0), other.begin(), other.end());
369  }
370 
372 
374  if (&other == this) {
375  return *this;
376  }
377  assign(other.begin(), other.end());
378  return *this;
379  }
380 
382  swap(other);
383  return *this;
384  }
385 
386  size_type size() const { return is_direct() ? _size : _size - N - 1; }
387 
388  bool empty() const { return size() == 0; }
389 
390  iterator begin() { return iterator(item_ptr(0)); }
391  const_iterator begin() const { return const_iterator(item_ptr(0)); }
392  iterator end() { return iterator(item_ptr(size())); }
393  const_iterator end() const { return const_iterator(item_ptr(size())); }
394 
395  reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
396  const_reverse_iterator rbegin() const {
397  return const_reverse_iterator(item_ptr(size() - 1));
398  }
399  reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
400  const_reverse_iterator rend() const {
401  return const_reverse_iterator(item_ptr(-1));
402  }
403 
404  size_t capacity() const {
405  if (is_direct()) {
406  return N;
407  } else {
409  }
410  }
411 
412  T &operator[](size_type pos) { return *item_ptr(pos); }
413 
414  const T &operator[](size_type pos) const { return *item_ptr(pos); }
415 
416  void resize(size_type new_size) {
417  size_type cur_size = size();
418  if (cur_size == new_size) {
419  return;
420  }
421  if (cur_size > new_size) {
422  erase(item_ptr(new_size), end());
423  return;
424  }
425  if (new_size > capacity()) {
426  change_capacity(new_size);
427  }
428  ptrdiff_t increase = new_size - cur_size;
429  fill(item_ptr(cur_size), increase);
430  _size += increase;
431  }
432 
433  void reserve(size_type new_capacity) {
434  if (new_capacity > capacity()) {
435  change_capacity(new_capacity);
436  }
437  }
438 
440 
441  void clear() { resize(0); }
442 
443  iterator insert(iterator pos, const T &value) {
444  size_type p = pos - begin();
445  size_type new_size = size() + 1;
446  if (capacity() < new_size) {
447  change_capacity(new_size + (new_size >> 1));
448  }
449  T *ptr = item_ptr(p);
450  memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
451  _size++;
452  new (static_cast<void *>(ptr)) T(value);
453  return iterator(ptr);
454  }
455 
456  void insert(iterator pos, size_type count, const T &value) {
457  size_type p = pos - begin();
458  size_type new_size = size() + count;
459  if (capacity() < new_size) {
460  change_capacity(new_size + (new_size >> 1));
461  }
462  T *ptr = item_ptr(p);
463  memmove(ptr + count, ptr, (size() - p) * sizeof(T));
464  _size += count;
465  fill(item_ptr(p), count, value);
466  }
467 
468  template <typename InputIterator>
469  void insert(iterator pos, InputIterator first, InputIterator last) {
470  size_type p = pos - begin();
471  difference_type count = last - first;
472  size_type new_size = size() + count;
473  if (capacity() < new_size) {
474  change_capacity(new_size + (new_size >> 1));
475  }
476  T *ptr = item_ptr(p);
477  memmove(ptr + count, ptr, (size() - p) * sizeof(T));
478  _size += count;
479  fill(ptr, first, last);
480  }
481 
482  inline void resize_uninitialized(size_type new_size) {
483  // resize_uninitialized changes the size of the prevector but does not
484  // initialize it. If size < new_size, the added elements must be
485  // initialized explicitly.
486  if (capacity() < new_size) {
487  change_capacity(new_size);
488  _size += new_size - size();
489  return;
490  }
491  if (new_size < size()) {
492  erase(item_ptr(new_size), end());
493  } else {
494  _size += new_size - size();
495  }
496  }
497 
498  iterator erase(iterator pos) { return erase(pos, pos + 1); }
499 
500  iterator erase(iterator first, iterator last) {
501  // Erase is not allowed to the change the object's capacity. That means
502  // that when starting with an indirectly allocated prevector with
503  // size and capacity > N, the result may be a still indirectly allocated
504  // prevector with size <= N and capacity > N. A shrink_to_fit() call is
505  // necessary to switch to the (more efficient) directly allocated
506  // representation (with capacity N and size <= N).
507  iterator p = first;
508  char *endp = (char *)&(*end());
509  if (!std::is_trivially_destructible<T>::value) {
510  while (p != last) {
511  (*p).~T();
512  _size--;
513  ++p;
514  }
515  } else {
516  _size -= last - p;
517  }
518  memmove(&(*first), &(*last), endp - ((char *)(&(*last))));
519  return first;
520  }
521 
522  template <typename... Args> void emplace_back(Args &&... args) {
523  size_type new_size = size() + 1;
524  if (capacity() < new_size) {
525  change_capacity(new_size + (new_size >> 1));
526  }
527  new (item_ptr(size())) T(std::forward<Args>(args)...);
528  _size++;
529  }
530 
531  void push_back(const T &value) { emplace_back(value); }
532 
533  void pop_back() { erase(end() - 1, end()); }
534 
535  T &front() { return *item_ptr(0); }
536 
537  const T &front() const { return *item_ptr(0); }
538 
539  T &back() { return *item_ptr(size() - 1); }
540 
541  const T &back() const { return *item_ptr(size() - 1); }
542 
544  std::swap(_union, other._union);
545  std::swap(_size, other._size);
546  }
547 
549  if (!std::is_trivially_destructible<T>::value) {
550  clear();
551  }
552  if (!is_direct()) {
555  }
556  }
557 
558  bool operator==(const prevector<N, T, Size, Diff> &other) const {
559  if (other.size() != size()) {
560  return false;
561  }
562  const_iterator b1 = begin();
563  const_iterator b2 = other.begin();
564  const_iterator e1 = end();
565  while (b1 != e1) {
566  if ((*b1) != (*b2)) {
567  return false;
568  }
569  ++b1;
570  ++b2;
571  }
572  return true;
573  }
574 
575  bool operator!=(const prevector<N, T, Size, Diff> &other) const {
576  return !(*this == other);
577  }
578 
579  bool operator<(const prevector<N, T, Size, Diff> &other) const {
580  if (size() < other.size()) {
581  return true;
582  }
583  if (size() > other.size()) {
584  return false;
585  }
586  const_iterator b1 = begin();
587  const_iterator b2 = other.begin();
588  const_iterator e1 = end();
589  while (b1 != e1) {
590  if ((*b1) < (*b2)) {
591  return true;
592  }
593  if ((*b2) < (*b1)) {
594  return false;
595  }
596  ++b1;
597  ++b2;
598  }
599  return false;
600  }
601 
602  size_t allocated_memory() const {
603  if (is_direct()) {
604  return 0;
605  } else {
606  return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
607  }
608  }
609 
610  value_type *data() { return item_ptr(0); }
611 
612  const value_type *data() const { return item_ptr(0); }
613 };
614 
615 #endif // BITCOIN_PREVECTOR_H
prevector::reference
value_type & reference
Definition: prevector.h:43
prevector::rend
reverse_iterator rend()
Definition: prevector.h:399
prevector::iterator::iterator
iterator()
Definition: prevector.h:57
prevector::insert
iterator insert(iterator pos, const T &value)
Definition: prevector.h:443
prevector::iterator::operator--
iterator operator--(int)
Definition: prevector.h:76
prevector::const_iterator::iterator_category
std::random_access_iterator_tag iterator_category
Definition: prevector.h:147
count
static int count
Definition: tests.c:41
prevector::insert
void insert(iterator pos, size_type count, const T &value)
Definition: prevector.h:456
prevector::const_iterator::operator>
bool operator>(const_iterator x) const
Definition: prevector.h:193
prevector::iterator::operator-
difference_type friend operator-(iterator a, iterator b)
Definition: prevector.h:81
prevector::size_type
Size size_type
Definition: prevector.h:40
prevector::const_pointer
const typedef value_type * const_pointer
Definition: prevector.h:46
prevector::const_iterator
Definition: prevector.h:139
prevector::iterator::operator[]
const T & operator[](size_type pos) const
Definition: prevector.h:62
prevector::iterator::operator-=
iterator & operator-=(size_type n)
Definition: prevector.h:90
prevector::prevector
prevector(size_type n)
Definition: prevector.h:348
prevector::reverse_iterator::operator++
reverse_iterator operator++(int)
Definition: prevector.h:125
prevector::indirect_ptr
T * indirect_ptr(difference_type pos)
Definition: prevector.h:260
prevector::iterator::operator==
bool operator==(iterator x) const
Definition: prevector.h:94
prevector::iterator::operator+=
iterator & operator+=(size_type n)
Definition: prevector.h:85
prevector::const_iterator::operator++
const_iterator & operator++()
Definition: prevector.h:154
prevector::erase
iterator erase(iterator pos)
Definition: prevector.h:498
prevector::const_reverse_iterator
Definition: prevector.h:197
prevector::prevector
prevector(prevector< N, T, Size, Diff > &&other)
Definition: prevector.h:371
prevector::const_reverse_iterator::operator->
const T * operator->() const
Definition: prevector.h:210
prevector::pop_back
void pop_back()
Definition: prevector.h:533
prevector::fill
void fill(T *dst, InputIterator first, InputIterator last)
Definition: prevector.h:317
prevector::back
const T & back() const
Definition: prevector.h:541
prevector::const_iterator::operator+=
const_iterator & operator+=(size_type n)
Definition: prevector.h:178
prevector::clear
void clear()
Definition: prevector.h:441
prevector::reverse_iterator::operator++
reverse_iterator & operator++()
Definition: prevector.h:121
prevector::reverse_iterator::reverse_iterator
reverse_iterator(T *ptr_)
Definition: prevector.h:112
prevector::operator[]
const T & operator[](size_type pos) const
Definition: prevector.h:414
prevector::const_iterator::operator!=
bool operator!=(const_iterator x) const
Definition: prevector.h:190
prevector::front
const T & front() const
Definition: prevector.h:537
prevector::const_reverse_iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: prevector.h:205
prevector::reverse_iterator::operator*
const T & operator*() const
Definition: prevector.h:114
prevector::const_iterator::operator<
bool operator<(const_iterator x) const
Definition: prevector.h:194
prevector::iterator::operator<=
bool operator<=(iterator x) const
Definition: prevector.h:97
prevector::change_capacity
void change_capacity(size_type new_capacity)
Definition: prevector.h:269
prevector::reverse_iterator::operator==
bool operator==(reverse_iterator x) const
Definition: prevector.h:135
prevector::const_reverse_iterator::operator!=
bool operator!=(const_reverse_iterator x) const
Definition: prevector.h:230
prevector::const_iterator::operator>=
bool operator>=(const_iterator x) const
Definition: prevector.h:191
prevector::const_iterator::ptr
const T * ptr
Definition: prevector.h:140
prevector::indirect_ptr
const T * indirect_ptr(difference_type pos) const
Definition: prevector.h:263
prevector::direct_ptr
const T * direct_ptr(difference_type pos) const
Definition: prevector.h:257
prevector::iterator::pointer
T * pointer
Definition: prevector.h:54
prevector::reverse_iterator::operator->
T * operator->()
Definition: prevector.h:115
prevector::iterator::operator+
iterator operator+(size_type n)
Definition: prevector.h:84
prevector::iterator::operator[]
T & operator[](size_type pos)
Definition: prevector.h:61
prevector::prevector
prevector(const prevector< N, T, Size, Diff > &other)
Definition: prevector.h:364
prevector::reverse_iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: prevector.h:110
prevector::const_iterator::difference_type
Diff difference_type
Definition: prevector.h:143
prevector::iterator::operator-
iterator operator-(size_type n)
Definition: prevector.h:89
prevector::fill
void fill(T *dst, ptrdiff_t count, const T &value=T{})
Definition: prevector.h:312
prevector::item_ptr
const T * item_ptr(difference_type pos) const
Definition: prevector.h:308
prevector::const_iterator::pointer
const typedef T * pointer
Definition: prevector.h:145
prevector::reverse_iterator::operator!=
bool operator!=(reverse_iterator x) const
Definition: prevector.h:136
prevector::end
iterator end()
Definition: prevector.h:392
prevector::iterator::value_type
T value_type
Definition: prevector.h:53
prevector::~prevector
~prevector()
Definition: prevector.h:548
prevector::reverse_iterator::difference_type
Diff difference_type
Definition: prevector.h:106
prevector::reverse_iterator::value_type
T value_type
Definition: prevector.h:107
prevector::push_back
void push_back(const T &value)
Definition: prevector.h:531
prevector::const_iterator::operator-=
const_iterator & operator-=(size_type n)
Definition: prevector.h:185
prevector::const_iterator::operator--
const_iterator & operator--()
Definition: prevector.h:158
prevector::operator!=
bool operator!=(const prevector< N, T, Size, Diff > &other) const
Definition: prevector.h:575
prevector::iterator::iterator_category
std::random_access_iterator_tag iterator_category
Definition: prevector.h:56
prevector::end
const_iterator end() const
Definition: prevector.h:393
prevector::rend
const_reverse_iterator rend() const
Definition: prevector.h:400
prevector::_union
direct_or_indirect _union
Definition: prevector.h:243
prevector::const_reference
const typedef value_type & const_reference
Definition: prevector.h:44
prevector::direct_or_indirect
Definition: prevector.h:235
prevector::const_iterator::operator->
const T * operator->() const
Definition: prevector.h:152
prevector::iterator::operator++
iterator & operator++()
Definition: prevector.h:63
prevector::reverse_iterator::operator*
T & operator*()
Definition: prevector.h:113
prevector::erase
iterator erase(iterator first, iterator last)
Definition: prevector.h:500
prevector::reverse_iterator::operator--
reverse_iterator operator--(int)
Definition: prevector.h:130
prevector::const_iterator::operator-
difference_type friend operator-(const_iterator a, const_iterator b)
Definition: prevector.h:172
prevector::difference_type
Diff difference_type
Definition: prevector.h:41
prevector::const_reverse_iterator::operator*
const T & operator*() const
Definition: prevector.h:209
prevector::iterator::operator*
T & operator*() const
Definition: prevector.h:59
prevector::back
T & back()
Definition: prevector.h:539
prevector::rbegin
reverse_iterator rbegin()
Definition: prevector.h:395
prevector::const_iterator::operator--
const_iterator operator--(int)
Definition: prevector.h:167
prevector::emplace_back
void emplace_back(Args &&... args)
Definition: prevector.h:522
prevector::operator[]
T & operator[](size_type pos)
Definition: prevector.h:412
prevector::swap
void swap(prevector< N, T, Size, Diff > &other)
Definition: prevector.h:543
prevector::const_reverse_iterator::ptr
const T * ptr
Definition: prevector.h:198
prevector::reverse_iterator::operator--
reverse_iterator & operator--()
Definition: prevector.h:117
prevector::direct_or_indirect::indirect_contents
struct prevector::direct_or_indirect::@2 indirect_contents
prevector::rbegin
const_reverse_iterator rbegin() const
Definition: prevector.h:396
prevector::iterator::iterator
iterator(T *ptr_)
Definition: prevector.h:58
prevector::const_iterator::operator+
const_iterator operator+(size_type n)
Definition: prevector.h:175
prevector::operator=
prevector & operator=(const prevector< N, T, Size, Diff > &other)
Definition: prevector.h:373
prevector::const_reverse_iterator::value_type
const typedef T value_type
Definition: prevector.h:202
prevector::const_reverse_iterator::operator--
const_reverse_iterator & operator--()
Definition: prevector.h:211
prevector::direct_or_indirect::capacity
size_type capacity
Definition: prevector.h:239
prevector::iterator::operator++
iterator operator++(int)
Definition: prevector.h:71
prevector::const_iterator::const_iterator
const_iterator()
Definition: prevector.h:148
prevector::prevector
prevector()
Definition: prevector.h:346
prevector::insert
void insert(iterator pos, InputIterator first, InputIterator last)
Definition: prevector.h:469
prevector::direct_or_indirect::direct
char direct[sizeof(T) *N]
Definition: prevector.h:236
prevector::iterator::operator>=
bool operator>=(iterator x) const
Definition: prevector.h:96
prevector::const_reverse_iterator::operator==
bool operator==(const_reverse_iterator x) const
Definition: prevector.h:229
prevector::direct_or_indirect::indirect
char * indirect
Definition: prevector.h:238
prevector::data
const value_type * data() const
Definition: prevector.h:612
prevector::assign
void assign(InputIterator first, InputIterator last)
Definition: prevector.h:336
prevector::reverse_iterator::operator->
const T * operator->() const
Definition: prevector.h:116
prevector::const_iterator::value_type
const typedef T value_type
Definition: prevector.h:144
prevector::reserve
void reserve(size_type new_capacity)
Definition: prevector.h:433
prevector::const_reverse_iterator::const_reverse_iterator
const_reverse_iterator()
Definition: prevector.h:206
prevector::iterator::ptr
T * ptr
Definition: prevector.h:49
prevector::resize
void resize(size_type new_size)
Definition: prevector.h:416
prevector
Implements a drop-in replacement for std::vector<T> which stores up to N elements directly (without h...
Definition: prevector.h:38
prevector::assign
void assign(size_type n, const T &val)
Definition: prevector.h:326
prevector::const_reverse_iterator::operator--
const_reverse_iterator operator--(int)
Definition: prevector.h:224
prevector::const_iterator::operator[]
const T & operator[](size_type pos) const
Definition: prevector.h:153
prevector::item_ptr
T * item_ptr(difference_type pos)
Definition: prevector.h:305
prevector::reverse_iterator::pointer
T * pointer
Definition: prevector.h:108
prevector::capacity
size_t capacity() const
Definition: prevector.h:404
prevector::iterator::difference_type
Diff difference_type
Definition: prevector.h:52
prevector::shrink_to_fit
void shrink_to_fit()
Definition: prevector.h:439
prevector::const_iterator::operator*
const T & operator*() const
Definition: prevector.h:151
prevector::reverse_iterator::reference
T & reference
Definition: prevector.h:109
prevector::reverse_iterator
Definition: prevector.h:102
prevector::iterator::operator!=
bool operator!=(iterator x) const
Definition: prevector.h:95
prevector::allocated_memory
size_t allocated_memory() const
Definition: prevector.h:602
prevector::iterator::operator>
bool operator>(iterator x) const
Definition: prevector.h:98
prevector::data
value_type * data()
Definition: prevector.h:610
prevector::const_reverse_iterator::reference
const typedef T & reference
Definition: prevector.h:204
prevector::const_reverse_iterator::const_reverse_iterator
const_reverse_iterator(reverse_iterator x)
Definition: prevector.h:208
prevector::iterator::operator--
iterator & operator--()
Definition: prevector.h:67
prevector::operator==
bool operator==(const prevector< N, T, Size, Diff > &other) const
Definition: prevector.h:558
prevector::value_type
T value_type
Definition: prevector.h:42
prevector::size
size_type size() const
Definition: prevector.h:386
prevector::const_reverse_iterator::operator++
const_reverse_iterator operator++(int)
Definition: prevector.h:219
prevector::begin
iterator begin()
Definition: prevector.h:390
prevector::const_iterator::reference
const typedef T & reference
Definition: prevector.h:146
prevector::resize_uninitialized
void resize_uninitialized(size_type new_size)
Definition: prevector.h:482
prevector::const_reverse_iterator::difference_type
Diff difference_type
Definition: prevector.h:201
prevector::prevector
prevector(InputIterator first, InputIterator last)
Definition: prevector.h:357
prevector::const_reverse_iterator::const_reverse_iterator
const_reverse_iterator(const T *ptr_)
Definition: prevector.h:207
prevector::const_reverse_iterator::operator++
const_reverse_iterator & operator++()
Definition: prevector.h:215
prevector::const_iterator::operator==
bool operator==(const_iterator x) const
Definition: prevector.h:189
prevector::operator<
bool operator<(const prevector< N, T, Size, Diff > &other) const
Definition: prevector.h:579
prevector::prevector
prevector(size_type n, const T &val)
Definition: prevector.h:350
prevector::empty
bool empty() const
Definition: prevector.h:388
prevector::front
T & front()
Definition: prevector.h:535
prevector::reverse_iterator::ptr
T * ptr
Definition: prevector.h:103
prevector::const_iterator::const_iterator
const_iterator(const T *ptr_)
Definition: prevector.h:149
prevector::const_iterator::operator-
const_iterator operator-(size_type n)
Definition: prevector.h:182
prevector::reverse_iterator::reverse_iterator
reverse_iterator()
Definition: prevector.h:111
prevector::_size
size_type _size
Definition: prevector.h:244
prevector::is_direct
bool is_direct() const
Definition: prevector.h:267
prevector::pointer
value_type * pointer
Definition: prevector.h:45
prevector::const_iterator::operator++
const_iterator operator++(int)
Definition: prevector.h:162
prevector::iterator
Definition: prevector.h:48
prevector::iterator::operator->
T * operator->() const
Definition: prevector.h:60
prevector::const_iterator::const_iterator
const_iterator(iterator x)
Definition: prevector.h:150
prevector::operator=
prevector & operator=(prevector< N, T, Size, Diff > &&other)
Definition: prevector.h:381
prevector::const_iterator::operator<=
bool operator<=(const_iterator x) const
Definition: prevector.h:192
prevector::iterator::operator<
bool operator<(iterator x) const
Definition: prevector.h:99
prevector::begin
const_iterator begin() const
Definition: prevector.h:391
prevector::const_reverse_iterator::pointer
const typedef T * pointer
Definition: prevector.h:203
prevector::direct_ptr
T * direct_ptr(difference_type pos)
Definition: prevector.h:254
prevector::iterator::reference
T & reference
Definition: prevector.h:55