MRPT  2.0.4
vector_with_small_size_optimization.h
Go to the documentation of this file.
1 /* +------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | https://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2020, Individual contributors, see AUTHORS file |
6  | See: https://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See: https://www.mrpt.org/License |
8  +------------------------------------------------------------------------+ */
9 #pragma once
10 
11 #include <mrpt/core/aligned_allocator.h> // aligned_allocator_cpp11
12 #include <array>
13 #include <cstddef> // size_t
14 #include <type_traits> // conditional_t, ...
15 #include <vector>
16 
17 namespace mrpt::containers
18 {
19 namespace internal
20 {
22 {
23  operator const bool&() const { return b; }
24  operator bool&() { return b; }
25 
26  bool b;
27 };
28 } // namespace internal
29 
30 /** Container that transparently and dynamically switches between a std::array
31  * and std::vector. Used to avoid heap allocations with small vectors.
32  *
33  * \note In `#include <mrpt/containers/vector_with_small_size_optimization.h>`
34  * \ingroup mrpt_containers_grp
35  */
36 template <typename VAL, size_t small_size, size_t alignment = 16>
38 {
39  private:
40  using T = std::conditional_t<
41  std::is_same_v<VAL, bool>, internal::UnspecializedBool, VAL>;
43  using self_t =
45  using large_vec = std::vector<T, ALLOC>;
46  using small_array = std::array<T, small_size>;
47 
48  /** @name Data
49  * @{ */
51  alignas(alignment) small_array m_a;
52  bool m_is_small = true;
53  size_t m_size = 0;
54  /** @} */
55 
56  public:
57  using value_type = T;
58  using reference = T&;
59  using const_reference = const T&;
60  using difference_type = typename large_vec::difference_type;
61  using size_type = typename large_vec::size_type;
62 
65 
67  : m_is_small(n <= small_size), m_size(n)
68  {
69  if (!m_is_small) m_v.resize(n);
70  }
71 
74  {
75  *this = o;
76  }
78  {
79  *this = o;
80  }
83  {
84  m_size = o.m_size;
86  if (m_size > small_size)
87  m_v = o.m_v;
88  else if (m_size > 0)
89  m_a = o.m_a;
90  return *this;
91  }
94  {
95  m_size = o.m_size;
96  m_is_small = o.m_is_small;
97  if (m_size > small_size)
98  m_v = std::move(o.m_v);
99  else if (m_size > 0)
100  m_a = std::move(o.m_a);
101  return *this;
102  }
103 
104  template <typename TYPE, typename POINTER, typename REFERENCE>
106  {
107  using STORAGE = std::conditional_t<
108  std::is_same_v<POINTER, bool*>, internal::UnspecializedBool*,
109  std::conditional_t<
110  std::is_same_v<POINTER, const bool*>,
111  const internal::UnspecializedBool*, POINTER>>;
113 
114  public:
115  using value_type = TYPE;
116  using reference = REFERENCE;
117  using pointer = POINTER;
118  using iterator_category = std::random_access_iterator_tag;
119  using difference_type = typename large_vec::difference_type;
120  iteratorImpl() = default;
121  iteratorImpl(STORAGE ptr) : m_ptr(ptr) {}
122  self operator++()
123  {
124  self i = *this;
125  m_ptr++;
126  return i;
127  }
128  self operator--()
129  {
130  self i = *this;
131  m_ptr--;
132  return i;
133  }
134  self operator++(int)
135  {
136  m_ptr++;
137  return *this;
138  }
139  self operator--(int)
140  {
141  m_ptr--;
142  return *this;
143  }
145  {
146  self i = *this;
147  i.m_ptr += n;
148  return i;
149  }
151  {
152  self i = *this;
153  i.m_ptr -= n;
154  return i;
155  }
157  {
158  m_ptr += n;
159  return *this;
160  }
162  {
163  m_ptr -= n;
164  return *this;
165  }
166  difference_type operator-(const self& o) const
167  {
168  return m_ptr - o.m_ptr;
169  }
170  REFERENCE operator*() { return *m_ptr; }
171  const REFERENCE operator*() const { return *m_ptr; }
172  POINTER operator->() { return m_ptr; }
173  const POINTER operator->() const { return m_ptr; }
174  bool operator==(const self& o) { return m_ptr == o.m_ptr; }
175  bool operator!=(const self& o) { return m_ptr != o.m_ptr; }
176 
177  private:
178  STORAGE m_ptr{nullptr};
179  };
180 
181  using iterator = iteratorImpl<VAL, VAL*, VAL&>;
182  using const_iterator = iteratorImpl<VAL, const VAL*, const VAL&>;
183 
185  {
186  if (m_size)
187  {
188  if (m_is_small && n > small_size)
189  {
190  m_v.assign(m_a.begin(), m_a.begin() + m_size);
191  }
192  else if (!m_is_small && n <= small_size)
193  {
194  std::copy(m_v.begin(), m_v.begin() + n, m_a.begin());
195  }
196  }
197  m_size = n;
198  m_is_small = (n <= small_size);
199  if (!m_is_small)
200  {
201  m_v.resize(m_size);
202  }
203  }
204 
205  void fill(const T& v)
206  {
207  if (m_is_small)
208  m_a.fill(v);
209  else
210  m_v.assign(m_v.size(), v);
211  }
212 
213  size_t size() const { return m_size; }
214  bool empty() const { return m_size == 0; }
215 
216  reference operator[](size_type n) { return m_is_small ? m_a[n] : m_v[n]; }
217 
219  {
220  return m_is_small ? m_a[n] : m_v[n];
221  }
222 
224  {
225  return m_is_small ? m_a[m_size - 1] : m_v.back();
226  }
227  reference back() { return m_is_small ? m_a[m_size - 1] : m_v.back(); }
228 
230  {
231  return m_is_small ? m_a.front() : m_v.front();
232  }
233  reference front() { return m_is_small ? m_a.front() : m_v.front(); }
234 
235  void swap(self_t& x)
236  {
237  if (m_is_small && x.m_is_small)
238  {
239  m_a.swap(x.m_a);
240  }
241  else if (!m_is_small && !x.m_is_small)
242  {
243  m_v.swap(x.m_v);
244  }
245  else if (!m_is_small && x.m_is_small)
246  {
247  std::copy(x.m_a.begin(), x.m_a.begin() + x.m_size, m_a.begin());
248  x.m_v.swap(m_v);
249  }
250  else
251  {
252  m_v.swap(x.m_v);
253  std::copy(m_a.begin(), m_a.begin() + m_size, x.m_a.begin());
254  }
255  std::swap(m_size, x.m_size);
256  std::swap(m_is_small, x.m_is_small);
257  }
258 
259  iterator begin() noexcept { return m_is_small ? m_a.data() : m_v.data(); }
260  const_iterator begin() const noexcept
261  {
262  return m_is_small ? m_a.data() : m_v.data();
263  }
264 
265  iterator end() noexcept
266  {
267  return m_is_small ? m_a.data() + m_size : m_v.data() + m_size;
268  }
269  const_iterator end() const noexcept
270  {
271  return m_is_small ? m_a.data() + m_size : m_v.data() + m_size;
272  }
273 };
274 
275 } // namespace mrpt::containers
mrpt::containers::vector_with_small_size_optimization< NUMTYPE, small_size, MRPT_MAX_STATIC_ALIGN_BYTES >::difference_type
typename large_vec::difference_type difference_type
Definition: vector_with_small_size_optimization.h:60
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::reference
REFERENCE reference
Definition: vector_with_small_size_optimization.h:116
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::iteratorImpl
iteratorImpl()=default
mrpt::containers::internal::UnspecializedBool
Definition: vector_with_small_size_optimization.h:21
aligned_allocator.h
mrpt::containers::vector_with_small_size_optimization::vector_with_small_size_optimization
vector_with_small_size_optimization(vector_with_small_size_optimization &&o)
Definition: vector_with_small_size_optimization.h:77
mrpt::aligned_allocator_cpp11
Aligned allocator that is compatible with C++11.
Definition: aligned_allocator.h:37
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator*
REFERENCE operator*()
Definition: vector_with_small_size_optimization.h:170
mrpt::containers::vector_with_small_size_optimization< NUMTYPE, small_size, MRPT_MAX_STATIC_ALIGN_BYTES >::small_array
std::array< T, small_size > small_array
Definition: vector_with_small_size_optimization.h:46
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::difference_type
typename large_vec::difference_type difference_type
Definition: vector_with_small_size_optimization.h:119
mrpt::containers::vector_with_small_size_optimization::end
iterator end() noexcept
Definition: vector_with_small_size_optimization.h:265
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator*
const REFERENCE operator*() const
Definition: vector_with_small_size_optimization.h:171
mrpt::containers::vector_with_small_size_optimization::m_size
size_t m_size
Definition: vector_with_small_size_optimization.h:53
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator--
self operator--()
Definition: vector_with_small_size_optimization.h:128
mrpt::containers::vector_with_small_size_optimization::resize
void resize(size_type n)
Definition: vector_with_small_size_optimization.h:184
mrpt::containers::vector_with_small_size_optimization::iteratorImpl
Definition: vector_with_small_size_optimization.h:105
mrpt::containers::vector_with_small_size_optimization::m_a
small_array m_a
Definition: vector_with_small_size_optimization.h:51
mrpt::containers::vector_with_small_size_optimization::front
const_reference front() const
Definition: vector_with_small_size_optimization.h:229
mrpt::containers::vector_with_small_size_optimization::vector_with_small_size_optimization
vector_with_small_size_optimization()=default
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator++
self operator++(int)
Definition: vector_with_small_size_optimization.h:134
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator-
difference_type operator-(const self &o) const
Definition: vector_with_small_size_optimization.h:166
mrpt::containers::vector_with_small_size_optimization::operator[]
const_reference operator[](size_type n) const
Definition: vector_with_small_size_optimization.h:218
mrpt::containers::vector_with_small_size_optimization::empty
bool empty() const
Definition: vector_with_small_size_optimization.h:214
mrpt::containers::vector_with_small_size_optimization::operator=
vector_with_small_size_optimization & operator=(const vector_with_small_size_optimization &o)
Definition: vector_with_small_size_optimization.h:81
mrpt::containers::vector_with_small_size_optimization< NUMTYPE, small_size, MRPT_MAX_STATIC_ALIGN_BYTES >::value_type
T value_type
Definition: vector_with_small_size_optimization.h:57
mrpt::containers::vector_with_small_size_optimization::m_is_small
bool m_is_small
Definition: vector_with_small_size_optimization.h:52
mrpt::containers::vector_with_small_size_optimization::size
size_t size() const
Definition: vector_with_small_size_optimization.h:213
mrpt::containers::vector_with_small_size_optimization::vector_with_small_size_optimization
vector_with_small_size_optimization(size_t n)
Definition: vector_with_small_size_optimization.h:66
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator-
self operator-(difference_type n)
Definition: vector_with_small_size_optimization.h:150
mrpt::containers::vector_with_small_size_optimization< NUMTYPE, small_size, MRPT_MAX_STATIC_ALIGN_BYTES >::iterator
iteratorImpl< NUMTYPE, NUMTYPE *, NUMTYPE & > iterator
Definition: vector_with_small_size_optimization.h:181
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator->
const POINTER operator->() const
Definition: vector_with_small_size_optimization.h:173
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator!=
bool operator!=(const self &o)
Definition: vector_with_small_size_optimization.h:175
mrpt::containers::vector_with_small_size_optimization::operator[]
reference operator[](size_type n)
Definition: vector_with_small_size_optimization.h:216
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator+
self operator+(difference_type n)
Definition: vector_with_small_size_optimization.h:144
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::iterator_category
std::random_access_iterator_tag iterator_category
Definition: vector_with_small_size_optimization.h:118
mrpt::containers::vector_with_small_size_optimization::fill
void fill(const T &v)
Definition: vector_with_small_size_optimization.h:205
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator-=
self operator-=(difference_type n)
Definition: vector_with_small_size_optimization.h:161
mrpt::containers::vector_with_small_size_optimization::begin
const_iterator begin() const noexcept
Definition: vector_with_small_size_optimization.h:260
mrpt::containers::vector_with_small_size_optimization::vector_with_small_size_optimization
vector_with_small_size_optimization(const vector_with_small_size_optimization &o)
Definition: vector_with_small_size_optimization.h:72
mrpt::containers::vector_with_small_size_optimization::m_v
large_vec m_v
Definition: vector_with_small_size_optimization.h:50
mrpt::containers::vector_with_small_size_optimization::begin
iterator begin() noexcept
Definition: vector_with_small_size_optimization.h:259
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::STORAGE
std::conditional_t< std::is_same_v< POINTER, bool * >, internal::UnspecializedBool *, std::conditional_t< std::is_same_v< POINTER, const bool * >, const internal::UnspecializedBool *, POINTER > > STORAGE
Definition: vector_with_small_size_optimization.h:111
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator->
POINTER operator->()
Definition: vector_with_small_size_optimization.h:172
mrpt::containers::vector_with_small_size_optimization< NUMTYPE, small_size, MRPT_MAX_STATIC_ALIGN_BYTES >::const_iterator
iteratorImpl< NUMTYPE, const NUMTYPE *, const NUMTYPE & > const_iterator
Definition: vector_with_small_size_optimization.h:182
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator++
self operator++()
Definition: vector_with_small_size_optimization.h:122
mrpt::containers::vector_with_small_size_optimization::operator=
vector_with_small_size_optimization & operator=(vector_with_small_size_optimization &&o)
Definition: vector_with_small_size_optimization.h:92
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator--
self operator--(int)
Definition: vector_with_small_size_optimization.h:139
mrpt::containers::vector_with_small_size_optimization< NUMTYPE, small_size, MRPT_MAX_STATIC_ALIGN_BYTES >::const_reference
const T & const_reference
Definition: vector_with_small_size_optimization.h:59
mrpt::containers::vector_with_small_size_optimization< NUMTYPE, small_size, MRPT_MAX_STATIC_ALIGN_BYTES >::size_type
typename large_vec::size_type size_type
Definition: vector_with_small_size_optimization.h:61
mrpt::containers::vector_with_small_size_optimization::end
const_iterator end() const noexcept
Definition: vector_with_small_size_optimization.h:269
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::m_ptr
STORAGE m_ptr
Definition: vector_with_small_size_optimization.h:178
mrpt::containers::vector_with_small_size_optimization::back
const_reference back() const
Definition: vector_with_small_size_optimization.h:223
mrpt::containers::vector_with_small_size_optimization
Container that transparently and dynamically switches between a std::array and std::vector.
Definition: vector_with_small_size_optimization.h:37
mrpt::containers::vector_with_small_size_optimization::front
reference front()
Definition: vector_with_small_size_optimization.h:233
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::value_type
TYPE value_type
Definition: vector_with_small_size_optimization.h:115
mrpt::containers::internal::UnspecializedBool::b
bool b
Definition: vector_with_small_size_optimization.h:26
mrpt::containers::vector_with_small_size_optimization::back
reference back()
Definition: vector_with_small_size_optimization.h:227
mrpt::containers::vector_with_small_size_optimization::~vector_with_small_size_optimization
~vector_with_small_size_optimization()=default
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::pointer
POINTER pointer
Definition: vector_with_small_size_optimization.h:117
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator==
bool operator==(const self &o)
Definition: vector_with_small_size_optimization.h:174
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::iteratorImpl
iteratorImpl(STORAGE ptr)
Definition: vector_with_small_size_optimization.h:121
mrpt::containers::vector_with_small_size_optimization::T
std::conditional_t< std::is_same_v< VAL, bool >, internal::UnspecializedBool, VAL > T
Definition: vector_with_small_size_optimization.h:41
mrpt::containers::vector_with_small_size_optimization< NUMTYPE, small_size, MRPT_MAX_STATIC_ALIGN_BYTES >::reference
T & reference
Definition: vector_with_small_size_optimization.h:58
mrpt::containers::vector_with_small_size_optimization< NUMTYPE, small_size, MRPT_MAX_STATIC_ALIGN_BYTES >::large_vec
std::vector< T, ALLOC > large_vec
Definition: vector_with_small_size_optimization.h:45
mrpt::containers::vector_with_small_size_optimization::iteratorImpl::operator+=
self operator+=(difference_type n)
Definition: vector_with_small_size_optimization.h:156
mrpt::containers
Definition: bimap.h:14
mrpt::containers::vector_with_small_size_optimization::swap
void swap(self_t &x)
Definition: vector_with_small_size_optimization.h:235



Page generated by Doxygen 1.8.17 for MRPT 2.0.4 at Sun Jul 19 17:54:30 UTC 2020