General Utility Library for C++14  2.8
SmallVector.h
Go to the documentation of this file.
1 
23 #ifndef GUL14_SMALLVECTOR_H_
24 #define GUL14_SMALLVECTOR_H_
25 
26 #include <algorithm>
27 #include <array>
28 #include <initializer_list>
29 #include <iterator>
30 #include <limits>
31 #include <memory>
32 #include <stdexcept>
33 #include <type_traits>
34 #include "gul14/internal.h"
35 #include "gul14/cat.h"
36 
37 namespace gul14 {
38 
261 template <typename ElementT, size_t in_capacity>
263 {
264 public:
266  using ValueType = ElementT;
270  using SizeType = uint32_t;
274  using DifferenceType = std::ptrdiff_t;
282  using ConstReference = const ValueType&;
286  using Iterator = ValueType*;
290  using ConstIterator = const ValueType*;
294  using ReverseIterator = std::reverse_iterator<Iterator>;
298  using ConstReverseIterator = std::reverse_iterator<ConstIterator>;
301 
310  SmallVector() noexcept = default;
311 
318  explicit SmallVector(SizeType num_elements)
319  {
320  static_assert(std::is_default_constructible<ValueType>::value,
321  "SmallVector: Element type is not default-constructible");
322 
323  reserve(num_elements);
324  for (SizeType i = 0u; i != num_elements; ++i)
325  ::new(static_cast<void*>(data() + i)) ValueType{};
326  size_ = num_elements;
327  }
328 
336  SmallVector(SizeType num_elements, const ValueType& value)
337  {
338  fill_empty_vector_with_copied_value(num_elements, value);
339  }
340 
357  template<class InputIterator,
358  typename = std::enable_if_t<not std::is_integral<InputIterator>::value>>
359  SmallVector(InputIterator first, InputIterator last)
360  {
361  fill_empty_vector_with_copied_range(first, last);
362  }
363 
372  SmallVector(const SmallVector& other)
373  noexcept(std::is_nothrow_copy_constructible<ValueType>::value)
374  {
375  static_assert(std::is_copy_constructible<ValueType>::value == true,
376  "SmallVector: Element type is not copy-constructible");
377  fill_empty_vector_with_copied_range(other.cbegin(), other.cend());
378  }
379 
396  noexcept(std::is_nothrow_move_constructible<ValueType>::value)
397  {
398  move_or_copy_all_elements_from(std::move(other));
399  }
400 
408  SmallVector(std::initializer_list<ValueType> init)
409  {
410  fill_empty_vector_with_copied_range(init.begin(), init.end());
411  }
412 
415  {
416  clear();
417 
418  if (is_storage_allocated())
419  delete[] data_ptr_;
420  }
421 
429  void assign(SizeType num_elements, const ValueType& value)
430  {
431  clear();
432  fill_empty_vector_with_copied_value(num_elements, value);
433  }
434 
454  template<class InputIterator,
455  typename = std::enable_if_t<not std::is_integral<InputIterator>::value>>
456  void assign(InputIterator first, InputIterator last)
457  {
458  clear();
459  fill_empty_vector_with_copied_range(first, last);
460  }
461 
469  void assign(std::initializer_list<ValueType> init)
470  {
471  const auto num_elements = static_cast<SizeType>(init.size());
472 
473  clear();
474  reserve(num_elements);
475  std::uninitialized_copy(init.begin(), init.end(), data());
476  size_ = num_elements;
477  }
478 
483  constexpr Reference at(SizeType idx)
484  {
485  if (idx >= size_)
486  throw std::out_of_range(cat("Index out of range: ", idx, " >= ", size_));
487  return *(data() + idx);
488  }
489 
491  constexpr ConstReference at(SizeType idx) const
492  {
493  if (idx >= size_)
494  throw std::out_of_range(cat("Index out of range: ", idx, " >= ", size_));
495  return *(data() + idx);
496  }
497 
502  constexpr Reference back() noexcept
503  {
504  return *(data_end() - 1);
505  }
506 
511  constexpr ConstReference back() const noexcept
512  {
513  return *(data_end() - 1);
514  }
515 
520  constexpr Iterator begin() noexcept
521  {
522  return data();
523  }
524 
529  constexpr ConstIterator begin() const noexcept
530  {
531  return data();
532  }
533 
538  constexpr SizeType capacity() const noexcept { return capacity_; }
539 
544  constexpr ConstIterator cbegin() const noexcept
545  {
546  return begin();
547  }
548 
553  constexpr ConstIterator cend() const noexcept
554  {
555  return end();
556  }
557 
562  void clear() noexcept
563  {
564  destroy_range(data(), data_end());
565  size_ = 0;
566  }
567 
575  {
576  return std::make_reverse_iterator(end());
577  }
578 
586  {
587  return std::make_reverse_iterator(begin());
588  }
589 
594  constexpr ValueType* data() noexcept
595  {
596  return reinterpret_cast<ValueType*>(data_ptr_);
597  }
598 
603  constexpr const ValueType* data() const noexcept
604  {
605  return reinterpret_cast<const ValueType*>(data_ptr_);
606  }
607 
633  template <typename... ArgumentTypes>
634  Iterator emplace(ConstIterator pos, ArgumentTypes&&... arguments)
635  {
636  if (pos == cend())
637  {
638  emplace_back(std::forward<ArgumentTypes>(arguments)...);
639  return data_end() - 1;
640  }
641 
642  ValueType v(std::forward<ArgumentTypes>(arguments)...);
643 
644  return insert_single_value(pos, std::move(v));
645  }
646 
664  template <typename... ArgumentTypes>
665  Reference emplace_back(ArgumentTypes&&... arguments)
666  {
667  if (size_ == capacity_)
668  grow();
669 
670  ::new(static_cast<void*>(data_end()))
671  ValueType(std::forward<ArgumentTypes>(arguments)...);
672 
673  ++size_;
674 
675  return back();
676  }
677 
679  constexpr bool empty() const noexcept { return size_ == 0u; }
680 
685  constexpr Iterator end() noexcept
686  {
687  return data_end();
688  }
689 
694  constexpr ConstIterator end() const noexcept
695  {
696  return data_end();
697  }
698 
711  {
712  return erase(pos, pos + 1);
713  }
714 
729  {
730  auto range_begin = const_cast<Iterator>(first);
731  auto range_end = const_cast<Iterator>(last);
732  auto num_elements = range_end - range_begin;
733 
734  std::move(range_end, end(), range_begin);
735  destroy_range(end() - num_elements, end());
736 
737  size_ -= static_cast<SizeType>(num_elements);
738 
739  return range_begin;
740  }
741 
746  constexpr Reference front() noexcept
747  {
748  return *data();
749  }
750 
755  constexpr ConstReference front() const noexcept
756  {
757  return *data();
758  }
759 
764  constexpr SizeType inner_capacity() const noexcept { return in_capacity; }
765 
776  {
777  return insert_single_value(pos, value);
778  }
779 
790  {
791  return insert_single_value(pos, std::move(value));
792  }
793 
803  Iterator insert(ConstIterator pos, SizeType num_elements, const ValueType& value)
804  {
805  const auto idx = static_cast<SizeType>(pos - begin());
806  if (num_elements < 1)
807  return begin() + idx;
808 
809  const SizeType num_assignable = make_space_at_idx_for_n_elements(idx, num_elements);
810  Iterator insert_pos = begin() + idx;
811 
812  // Copy-assign to moved-from elements
813  std::fill_n(insert_pos, num_assignable, value);
814 
815  // Copy the remaining values into uninitialized cells
816  copy_value_into_uninitialized_cells(size_, num_elements - num_assignable, value);
817 
818  size_ += num_elements;
819 
820  return insert_pos;
821  }
822 
842  template<class InputIterator,
843  typename = std::enable_if_t<not std::is_integral<InputIterator>::value>>
844  Iterator insert(ConstIterator pos, InputIterator first, InputIterator last)
845  {
846  const auto idx = static_cast<SizeType>(pos - begin());
847  const auto num_elements = static_cast<SizeType>(std::distance(first, last));
848  if (num_elements < 1)
849  return begin() + idx;
850 
851  const SizeType num_assignable = make_space_at_idx_for_n_elements(idx, num_elements);
852  Iterator insert_pos = begin() + idx;
853 
854  // Copy-assign to moved-from elements
855  std::copy_n(first, num_assignable, insert_pos);
856 
857  // Copy the remaining values into uninitialized cells
858  copy_range_into_uninitialized_cells(size_, first + num_assignable, last);
859 
860  size_ += num_elements;
861 
862  return insert_pos;
863  }
864 
878  Iterator insert(ConstIterator pos, std::initializer_list<ValueType> init)
879  {
880  return insert(pos, init.begin(), init.end());
881  }
882 
889  constexpr SizeType max_size() const noexcept
890  {
891  return std::numeric_limits<SizeType>::max();
892  }
893 
902  noexcept(std::is_nothrow_copy_assignable<ValueType>::value)
903  {
904  if (&other != this)
905  {
906  clear();
907  reserve(other.size());
908  std::uninitialized_copy(other.cbegin(), other.cend(), data());
909  size_ = other.size();
910  }
911 
912  return *this;
913  }
914 
929  noexcept(std::is_nothrow_move_constructible<ValueType>::value)
930  {
931  if (&other != this)
932  {
933  clear();
934  if (is_storage_allocated())
935  delete[] data_ptr_;
936  move_or_copy_all_elements_from(std::move(other));
937  }
938 
939  return *this;
940  }
941 
946  SmallVector& operator=(std::initializer_list<ValueType> init)
947  {
948  assign(init);
949  return *this;
950  }
951 
959  friend bool operator==(const SmallVector& lhs, const SmallVector& rhs)
960  {
961  return std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend());
962  }
963 
971  friend bool operator!=(const SmallVector& lhs, const SmallVector& rhs)
972  {
973  return not (lhs == rhs);
974  }
975 
978  {
979  return *(data() + idx);
980  }
981 
983  constexpr ConstReference operator[](SizeType idx) const
984  {
985  return *(data() + idx);
986  }
987 
992  void pop_back()
993  {
994  --size_;
995  auto p = data_end();
996  p->~ValueType();
997  }
998 
1008  void push_back(const ValueType& value)
1009  {
1010  if (size_ == capacity_)
1011  grow();
1012 
1013  ::new(static_cast<void*>(data_end())) ValueType(value);
1014 
1015  ++size_;
1016  }
1017 
1026  void push_back(ValueType&& value)
1027  {
1028  if (size_ == capacity_)
1029  grow();
1030 
1031  ::new(static_cast<void*>(data_end())) ValueType(std::move(value));
1032 
1033  ++size_;
1034  }
1035 
1043  {
1044  return std::make_reverse_iterator(end());
1045  }
1046 
1053  {
1054  return std::make_reverse_iterator(begin());
1055  }
1056 
1065  void reserve(SizeType new_capacity)
1066  {
1067  if (new_capacity <= capacity_)
1068  return;
1069 
1070  auto new_data = std::make_unique<AlignedStorage[]>(new_capacity);
1071 
1072  const auto d_end = data_end();
1073 
1074  uninitialized_move_or_copy(data(), d_end, reinterpret_cast<ValueType*>(new_data.get()));
1075  destroy_range(data(), d_end);
1076 
1077  if (is_storage_allocated())
1078  delete[] data_ptr_;
1079 
1080  data_ptr_ = new_data.release();
1081  capacity_ = new_capacity;
1082  }
1083 
1099  void resize(SizeType num_elements)
1100  {
1101  static_assert(std::is_default_constructible<ValueType>::value,
1102  "SmallVector: For using resize(), element type must be default-constructible");
1103 
1104  if (num_elements < size_)
1105  {
1106  destroy_range(data() + num_elements, data_end());
1107  }
1108  else if (num_elements > size_)
1109  {
1110  reserve(num_elements);
1111  fill_uninitialized_cells_with_default_constructed_elements(size_,
1112  num_elements - size_);
1113  }
1114 
1115  size_ = num_elements;
1116  }
1117 
1129  void resize(SizeType num_elements, const ValueType& element)
1130  {
1131  if (num_elements < size_)
1132  {
1133  destroy_range(data() + num_elements, data_end());
1134  }
1135  else if (num_elements > size_)
1136  {
1137  reserve(num_elements);
1138  copy_value_into_uninitialized_cells(size_, num_elements - size_, element);
1139  }
1140 
1141  size_ = num_elements;
1142  }
1143 
1149  {
1150  const SizeType new_capacity = std::max(inner_capacity(), size_);
1151 
1152  // No shrinking required?
1153  if (new_capacity == capacity_)
1154  return;
1155 
1156  AlignedStorage* new_data;
1157  auto new_memory = std::unique_ptr<AlignedStorage[]>{};
1158 
1159  if (new_capacity == inner_capacity()) {
1160  new_data = internal_array_.data();
1161  } else {
1162  new_memory = std::make_unique<AlignedStorage[]>(new_capacity);
1163  new_data = new_memory.get();
1164  }
1165 
1166  const auto d_end = data_end();
1167 
1168  uninitialized_move_or_copy(data(), d_end, reinterpret_cast<ValueType*>(new_data));
1169  destroy_range(data(), d_end);
1170 
1171  if (is_storage_allocated())
1172  delete[] data_ptr_;
1173 
1174  data_ptr_ = new_memory ? new_memory.release() : new_data;
1175  capacity_ = new_capacity;
1176  }
1177 
1179  constexpr SizeType size() const noexcept { return size_; }
1180 
1188  void swap(SmallVector& other)
1189  {
1190  if (is_storage_allocated())
1191  {
1192  if (other.is_storage_allocated())
1193  swap_heap_with_heap(*this, other);
1194  else
1195  swap_heap_with_internal(*this, other);
1196  }
1197  else
1198  {
1199  if (other.is_storage_allocated())
1200  swap_heap_with_internal(other, *this);
1201  else
1202  swap_internal_with_internal(*this, other);
1203  }
1204  }
1205 
1206 private:
1207  using AlignedStorage =
1208  typename std::aligned_storage<sizeof(ValueType), alignof(ValueType)>::type;
1209 
1214  std::array<AlignedStorage, in_capacity> internal_array_;
1215 
1217  AlignedStorage* data_ptr_{ internal_array_.data() };
1218 
1221  SizeType capacity_{ in_capacity };
1223  SizeType size_{ 0u };
1224 
1237  template<class InputIterator>
1238  void copy_range_into_uninitialized_cells(SizeType pos, InputIterator first,
1239  InputIterator last)
1240  {
1241  auto data_ptr = data() + pos;
1242 
1243  try
1244  {
1245  for (auto it = first; it != last; ++it)
1246  {
1247  ::new(static_cast<void*>(data_ptr)) ValueType{ *it };
1248  ++data_ptr;
1249  }
1250  }
1251  catch (...)
1252  {
1253  for (auto p = data() + pos; p != data_ptr; ++p)
1254  p->~ValueType();
1255 
1256  throw;
1257  }
1258  }
1259 
1266  void copy_value_into_uninitialized_cells(SizeType pos, SizeType num_elements,
1267  const ValueType& value)
1268  {
1269  const auto start_ptr = data() + pos;
1270  const auto end_ptr = start_ptr + num_elements;
1271  for (auto p = start_ptr; p != end_ptr; ++p)
1272  ::new(static_cast<void*>(p)) ValueType(value);
1273  }
1274 
1276  constexpr ValueType* data_end() noexcept
1277  {
1278  return reinterpret_cast<ValueType*>(data_ptr_) + size_;
1279  }
1280 
1282  constexpr const ValueType* data_end() const noexcept
1283  {
1284  return reinterpret_cast<const ValueType*>(data_ptr_) + size_;
1285  }
1286 
1295  static void destroy_range(Iterator it_start, Iterator it_end) noexcept
1296  {
1297  for (auto it = it_start; it != it_end; ++it)
1298  it->~ValueType();
1299  }
1300 
1315  template<typename InputIterator>
1316  void fill_empty_vector_with_copied_range(InputIterator first, InputIterator last)
1317  {
1318  const auto num_elements = static_cast<SizeType>(std::distance(first, last));
1319 
1320  reserve(num_elements);
1321  copy_range_into_uninitialized_cells(0u, first, last);
1322  size_ = num_elements;
1323  }
1324 
1333  void fill_empty_vector_with_copied_value(SizeType num_elements, const ValueType& value)
1334  {
1335  reserve(num_elements);
1336  copy_value_into_uninitialized_cells(0u, num_elements, value);
1337  size_ = num_elements;
1338  }
1339 
1348  void fill_uninitialized_cells_with_default_constructed_elements(SizeType pos,
1349  SizeType num_elements)
1350  {
1351  const auto start_ptr = data() + pos;
1352  const auto end_ptr = start_ptr + num_elements;
1353  auto ptr = start_ptr;
1354 
1355  try
1356  {
1357  for (; ptr != end_ptr; ++ptr)
1358  ::new(static_cast<void*>(ptr)) ValueType{};
1359  }
1360  catch (...)
1361  {
1362  destroy_range(start_ptr, ptr);
1363  throw;
1364  }
1365  }
1366 
1376  void grow()
1377  {
1378  const auto remaining_space = std::numeric_limits<SizeType>::max() - capacity_;
1379 
1380  if (remaining_space == 0u)
1381  throw std::length_error("Max. capacity reached");
1382 
1383  SizeType increase = capacity_ / 2u;
1384  if (increase > remaining_space)
1385  increase = remaining_space;
1386  else if (increase == 0u)
1387  increase = 1u;
1388 
1389  reserve(capacity_ + increase);
1390  }
1391 
1393  template <typename T>
1394  Iterator insert_single_value(ConstIterator pos, T&& value)
1395  {
1396  if (pos == end())
1397  {
1398  push_back(std::forward<T>(value));
1399  return begin() + size_ - 1;
1400  }
1401 
1402  const auto idx = static_cast<SizeType>(pos - begin());
1403 
1404  if (size_ == capacity_)
1405  grow();
1406 
1407  Iterator insert_pos = begin() + idx;
1408 
1409  auto data_ptr = data();
1410 
1411  // Construct new back() element by moving from the old back()
1412  ::new(static_cast<void*>(data_ptr + size_)) ValueType(std::move(*(data_ptr + size_ - 1)));
1413 
1414  std::move_backward(insert_pos, data_ptr + size_ - 1, data_ptr + size_);
1415  ++size_;
1416 
1417  *insert_pos = std::forward<T>(value);
1418 
1419  return insert_pos;
1420  }
1421 
1423  bool is_storage_allocated() const noexcept
1424  {
1425  return capacity_ > inner_capacity();
1426  }
1427 
1438  SizeType make_space_at_idx_for_n_elements(SizeType idx, SizeType num_elements)
1439  {
1440  const auto new_size = size_ + num_elements;
1441 
1442  if (new_size > capacity_)
1443  reserve(new_size);
1444 
1445  auto data_ptr = data();
1446 
1447  // We have a total number of elements that need to be shifted backwards,
1448  // of which some need to be move-initialized at the end of the vector
1449  // and some simply need to be moved from one element to another.
1450  const SizeType num_shifted = size_ - idx;
1451  const SizeType num_move_initialized = std::min(num_shifted, num_elements);
1452  const SizeType num_moved = num_shifted - num_move_initialized;
1453 
1454  // Move-initialize elements in uninitialized space at the back of the container
1455  const auto from_ptr = data_ptr + size_ - num_move_initialized;
1456  const auto to_ptr = from_ptr + num_elements;
1457  for (SizeType i = 0; i != num_move_initialized; ++i)
1458  ::new(static_cast<void*>(to_ptr + i)) ValueType(std::move(*(from_ptr + i)));
1459 
1460  // Move elements backwards within old vector size
1461  std::move_backward(data_ptr + idx, data_ptr + idx + num_moved, to_ptr);
1462 
1463  return num_move_initialized;
1464  }
1465 
1484  void move_or_copy_all_elements_from(SmallVector&& other)
1485  noexcept(std::is_nothrow_move_constructible<ValueType>::value)
1486  {
1487  // Can we simply steal the complete allocated storage?
1488  if (other.is_storage_allocated())
1489  {
1490  data_ptr_ = other.data_ptr_; other.data_ptr_ = other.internal_array_.data();
1491  capacity_ = other.capacity_; other.capacity_ = other.inner_capacity();
1492  size_ = other.size_; other.size_ = 0u;
1493  }
1494  else // otherwise fall back to moving (or at least copying) all elements
1495  {
1496  data_ptr_ = internal_array_.data();
1497  capacity_ = in_capacity;
1498  uninitialized_move_or_copy(other.begin(), other.end(), data());
1499  size_ = other.size();
1500  other.clear();
1501  }
1502  }
1503 
1509  static void swap_heap_with_heap(SmallVector &a, SmallVector &b) noexcept
1510  {
1511  std::swap(a.data_ptr_, b.data_ptr_);
1512  std::swap(a.capacity_, b.capacity_);
1513  std::swap(a.size_, b.size_);
1514  }
1515 
1522  static void swap_heap_with_internal(SmallVector &a, SmallVector &b)
1523  {
1524  uninitialized_move_or_copy(b.begin(), b.end(),
1525  reinterpret_cast<ValueType*>(a.internal_array_.data()));
1526  destroy_range(b.begin(), b.end());
1527 
1528  b.data_ptr_ = a.data_ptr_;
1529  a.data_ptr_ = a.internal_array_.data();
1530 
1531  std::swap(a.capacity_, b.capacity_);
1532  std::swap(a.size_, b.size_);
1533  }
1534 
1540  static void swap_internal_with_internal(SmallVector &a, SmallVector &b)
1541  {
1542  if (a.size_ <= b.size_)
1543  {
1544  for (SmallVector::SizeType i = 0; i != a.size_; ++i)
1545  std::swap(a.data()[i], b.data()[i]);
1546 
1547  uninitialized_move_or_copy(b.begin() + a.size_, b.end(), a.begin() + a.size_);
1548  destroy_range(b.begin() + a.size_, b.end());
1549  }
1550  else
1551  {
1552  for (SizeType i = 0; i != b.size_; ++i)
1553  std::swap(a.data()[i], b.data()[i]);
1554 
1555  uninitialized_move_or_copy(a.begin() + b.size_, a.end(), b.begin() + b.size_);
1556  destroy_range(a.begin() + b.size_, a.end());
1557  }
1558 
1559  std::swap(a.size_, b.size_);
1560  }
1561 
1566  template <typename T>
1567  static typename std::enable_if_t<not std::is_nothrow_move_constructible<T>::value>
1568  uninitialized_move(T* src_begin, T* src_end, T* dest_begin)
1569  {
1570  auto src = src_begin;
1571  auto dest = dest_begin;
1572 
1573  try
1574  {
1575  while (src != src_end)
1576  {
1577  ::new (static_cast<void*>(dest)) ValueType(std::move(*src));
1578  ++src;
1579  ++dest;
1580  }
1581  }
1582  catch (...)
1583  {
1584  for (auto p = dest_begin; p != dest; ++p)
1585  p->~ValueType();
1586 
1587  throw;
1588  }
1589  }
1590 
1595  template <typename T>
1596  static typename std::enable_if_t<std::is_nothrow_move_constructible<T>::value>
1597  uninitialized_move(T* src_begin, T* src_end, T* dest_begin) noexcept
1598  {
1599  auto src = src_begin;
1600  auto dest = dest_begin;
1601 
1602  while (src != src_end)
1603  {
1604  ::new (static_cast<void*>(dest)) ValueType(std::move(*src));
1605  ++src;
1606  ++dest;
1607  }
1608  }
1609 
1612  template <typename T>
1613  static typename std::enable_if_t<std::is_nothrow_move_constructible<T>::value>
1614  uninitialized_move_or_copy(T* src_begin, T* src_end, T* dest_begin) noexcept
1615  {
1616  uninitialized_move(src_begin, src_end, dest_begin);
1617  }
1618 
1621  template <typename T>
1622  static typename std::enable_if_t<not std::is_nothrow_move_constructible<T>::value and
1623  std::is_copy_constructible<T>::value>
1624  uninitialized_move_or_copy(T* src_begin, T* src_end, T* dest_begin)
1625  {
1626  std::uninitialized_copy(src_begin, src_end, dest_begin);
1627  }
1628 
1631  template <typename T>
1632  static typename std::enable_if_t<not std::is_nothrow_move_constructible<T>::value
1633  and not std::is_copy_constructible<T>::value>
1634  uninitialized_move_or_copy(T* src_begin, T* src_end, T* dest_begin)
1635  {
1636  uninitialized_move(src_begin, src_end, dest_begin);
1637  }
1638 };
1639 
1640 
1648 template<typename ElementT, size_t in_capacity>
1650 {
1651  a.swap(b);
1652 }
1653 
1654 } // namespace gul14
1655 
1656 #endif
1657 
1658 // vi:ts=4:sw=4:sts=4:et
Declaration of the overload set for cat() and of the associated class ConvertingStringView.
A resizable container with contiguous storage that can hold a specified number of elements without al...
Definition: SmallVector.h:263
constexpr SizeType capacity() const noexcept
Return the number of elements that can currently be stored in this vector without having to allocate ...
Definition: SmallVector.h:538
constexpr ConstReference back() const noexcept
Return a const reference to the last element in the vector.
Definition: SmallVector.h:511
Iterator iterator
Iterator to an element.
Definition: SmallVector.h:288
SmallVector & operator=(SmallVector &&other) noexcept(std::is_nothrow_move_constructible< ValueType >::value)
Move assignment operator: Assign all of the elements from another vector to this one using move seman...
Definition: SmallVector.h:928
Iterator erase(ConstIterator pos)
Erase a single element from the vector, moving elements behind it forward.
Definition: SmallVector.h:710
SmallVector & operator=(const SmallVector &other) noexcept(std::is_nothrow_copy_assignable< ValueType >::value)
Copy assignment operator: Copy all elements from another SmallVector after clearing all previous cont...
Definition: SmallVector.h:901
constexpr ConstReference front() const noexcept
Return a const reference to the first element in the vector.
Definition: SmallVector.h:755
ReverseIterator rbegin() noexcept
Return a reverse iterator to the first element of the reversed vector (which is the last element of t...
Definition: SmallVector.h:1042
friend bool operator!=(const SmallVector &lhs, const SmallVector &rhs)
Inequality operator: Return true if both vectors have a different size() or at least one different el...
Definition: SmallVector.h:971
void resize(SizeType num_elements)
Change the number of elements in the container.
Definition: SmallVector.h:1099
constexpr Iterator begin() noexcept
Return an iterator to the first element of the vector.
Definition: SmallVector.h:520
Reference emplace_back(ArgumentTypes &&... arguments)
Construct an additional element at the end of the buffer.
Definition: SmallVector.h:665
Iterator insert(ConstIterator pos, SizeType num_elements, const ValueType &value)
Insert a number of copies of the given value before the indicated position.
Definition: SmallVector.h:803
ReverseIterator reverse_iterator
Iterator to an element in reversed container.
Definition: SmallVector.h:296
void pop_back()
Remove the last element from the vector.
Definition: SmallVector.h:992
SmallVector & operator=(std::initializer_list< ValueType > init)
Assign the elements of an initializer list to this vector after clearing all previous contents.
Definition: SmallVector.h:946
uint32_t SizeType
Unsigned integer type for indexing, number of elements, capacity.
Definition: SmallVector.h:270
constexpr const ValueType * data() const noexcept
Return a pointer to the contiguous data storage of the vector.
Definition: SmallVector.h:603
constexpr Reference at(SizeType idx)
Return a reference to the element at the specified index with bounds-checking.
Definition: SmallVector.h:483
const ValueType & ConstReference
Reference to a const element.
Definition: SmallVector.h:282
Iterator insert(ConstIterator pos, InputIterator first, InputIterator last)
Insert a range of values before the indicated position.
Definition: SmallVector.h:844
void assign(SizeType num_elements, const ValueType &value)
Fill the vector with a certain number of copies of the given value after clearing all previous conten...
Definition: SmallVector.h:429
constexpr Reference back() noexcept
Return a reference to the last element in the vector.
Definition: SmallVector.h:502
friend bool operator==(const SmallVector &lhs, const SmallVector &rhs)
Equality operator: Return true if both vectors have the same size() and the same elements.
Definition: SmallVector.h:959
constexpr SizeType max_size() const noexcept
Return the maximum number of elements that this vector can theoretically hold.
Definition: SmallVector.h:889
Iterator insert(ConstIterator pos, std::initializer_list< ValueType > init)
Insert elements from an initializer list before the indicated position.
Definition: SmallVector.h:878
void reserve(SizeType new_capacity)
Increase the capacity of the vector to the specified size.
Definition: SmallVector.h:1065
~SmallVector()
Destructor: Destroys all stored elements and frees all allocated memory.
Definition: SmallVector.h:414
ValueType * Iterator
Iterator to an element.
Definition: SmallVector.h:286
void swap(SmallVector &other)
Exchange the contents of this SmallVector with those of another one.
Definition: SmallVector.h:1188
ReverseIterator rend() noexcept
Return a reverse iterator pointing past the last element of the reversed vector.
Definition: SmallVector.h:1052
Iterator erase(ConstIterator first, ConstIterator last)
Erase a range of elements from the vector, moving elements behind the range forward.
Definition: SmallVector.h:728
Iterator emplace(ConstIterator pos, ArgumentTypes &&... arguments)
Construct an additional element at an arbitrary position in the vector.
Definition: SmallVector.h:634
DifferenceType difference_type
Signed integer type for the difference of two iterators.
Definition: SmallVector.h:276
ConstIterator const_iterator
Iterator to a const element.
Definition: SmallVector.h:292
void assign(std::initializer_list< ValueType > init)
Assign the elements of an initializer list to this vector after clearing all previous contents.
Definition: SmallVector.h:469
constexpr ValueType * data() noexcept
Return a pointer to the contiguous data storage of the vector.
Definition: SmallVector.h:594
ElementT ValueType
Type of the elements in the underlying container.
Definition: SmallVector.h:266
constexpr ConstReference at(SizeType idx) const
Return a const reference to the element at the specified index.
Definition: SmallVector.h:491
constexpr Iterator end() noexcept
Return an iterator pointing past the last element of the vector.
Definition: SmallVector.h:685
SizeType size_type
Unsigned integer type for indexing, number of elements, capacity.
Definition: SmallVector.h:272
constexpr bool empty() const noexcept
Determine if the vector is empty.
Definition: SmallVector.h:679
constexpr ConstIterator cend() const noexcept
Return a const iterator pointing past the last element of the vector.
Definition: SmallVector.h:553
ValueType value_type
Type of the elements in the underlying container.
Definition: SmallVector.h:268
Iterator insert(ConstIterator pos, const ValueType &value)
Insert a single element before the indicated position.
Definition: SmallVector.h:775
ConstReference const_reference
Reference to a const element.
Definition: SmallVector.h:284
std::reverse_iterator< ConstIterator > ConstReverseIterator
Iterator to a const element in reversed container.
Definition: SmallVector.h:298
const ValueType * ConstIterator
Iterator to a const element.
Definition: SmallVector.h:290
SmallVector() noexcept=default
Construct an empty SmallVector.
SmallVector(SizeType num_elements, const ValueType &value)
Construct a SmallVector that is filled with a certain number of copies of the given value.
Definition: SmallVector.h:336
SmallVector(InputIterator first, InputIterator last)
Construct a SmallVector that is filled with copies of elements from the given range.
Definition: SmallVector.h:359
void resize(SizeType num_elements, const ValueType &element)
Change the number of elements in the container.
Definition: SmallVector.h:1129
ValueType & Reference
Reference to an element.
Definition: SmallVector.h:278
constexpr SizeType inner_capacity() const noexcept
Return the number of elements this SmallVector can hold internally without having to allocate storage...
Definition: SmallVector.h:764
Reference reference
Reference to an element.
Definition: SmallVector.h:280
SmallVector(std::initializer_list< ValueType > init)
Construct a SmallVector that is filled with copies of the elements from a given initializer list.
Definition: SmallVector.h:408
void shrink_to_fit()
Reduce the capacity as far as possible while retaining all stored elements.
Definition: SmallVector.h:1148
constexpr ConstIterator end() const noexcept
Return a const iterator pointing past the last element of the vector.
Definition: SmallVector.h:694
constexpr ConstIterator begin() const noexcept
Return a const iterator to the first element of the vector.
Definition: SmallVector.h:529
void push_back(ValueType &&value)
Move one element to the end of the buffer.
Definition: SmallVector.h:1026
constexpr ConstIterator cbegin() const noexcept
Return a const iterator to the first element of the vector.
Definition: SmallVector.h:544
ConstReverseIterator crbegin() noexcept
Return a const reverse iterator to the first element of the reversed vector (which is the last elemen...
Definition: SmallVector.h:574
Iterator insert(ConstIterator pos, ValueType &&value)
Insert a single element before the indicated position.
Definition: SmallVector.h:789
std::reverse_iterator< Iterator > ReverseIterator
Iterator to an element in reversed container.
Definition: SmallVector.h:294
void assign(InputIterator first, InputIterator last)
Fill the vector with copies of elements from the given range.
Definition: SmallVector.h:456
constexpr Reference operator[](SizeType idx)
Return a reference to the element at the specified index.
Definition: SmallVector.h:977
void clear() noexcept
Erase all elements from the container without changing its capacity.
Definition: SmallVector.h:562
constexpr Reference front() noexcept
Return a reference to the first element in the vector.
Definition: SmallVector.h:746
constexpr ConstReference operator[](SizeType idx) const
Return a const reference to the element at the specified index.
Definition: SmallVector.h:983
std::ptrdiff_t DifferenceType
Signed integer type for the difference of two iterators.
Definition: SmallVector.h:274
ConstReverseIterator const_reverse_iterator
Iterator to a const element in reversed container.
Definition: SmallVector.h:300
SmallVector(SmallVector &&other) noexcept(std::is_nothrow_move_constructible< ValueType >::value)
Move constructor: Create a SmallVector from the contents of another one with the same inner capacity ...
Definition: SmallVector.h:395
ConstReverseIterator crend() noexcept
Return a const reverse iterator pointing past the last element of the reversed vector.
Definition: SmallVector.h:585
void push_back(const ValueType &value)
Copy one element to the end of the buffer.
Definition: SmallVector.h:1008
constexpr SizeType size() const noexcept
Return the number of elements that are currently stored.
Definition: SmallVector.h:1179
SmallVector(const SmallVector &other) noexcept(std::is_nothrow_copy_constructible< ValueType >::value)
Create a copy of another SmallVector with the same inner capacity.
Definition: SmallVector.h:372
Definition of macros used internally by GUL.
Namespace gul14 contains all functions and classes of the General Utility Library.
Definition: doxygen.h:26
void swap(SmallVector< ElementT, in_capacity > &a, SmallVector< ElementT, in_capacity > &b)
Exchange the contents of one SmallVector with those of another one.
Definition: SmallVector.h:1649
std::string cat()
Efficiently concatenate an arbitrary number of strings and numbers.
Definition: cat.h:90