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