General Utility Library for C++14  2.7
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 
807  const SizeType num_assignable = make_space_at_idx_for_n_elements(idx, num_elements);
808  Iterator insert_pos = begin() + idx;
809 
810  // Copy-assign to moved-from elements
811  std::fill_n(insert_pos, num_assignable, value);
812 
813  // Copy the remaining values into uninitialized cells
814  copy_value_into_uninitialized_cells(size_, num_elements - num_assignable, value);
815 
816  size_ += num_elements;
817 
818  return insert_pos;
819  }
820 
840  template<class InputIterator,
841  typename = std::enable_if_t<not std::is_integral<InputIterator>::value>>
842  Iterator insert(ConstIterator pos, InputIterator first, InputIterator last)
843  {
844  const auto idx = static_cast<SizeType>(pos - begin());
845  const auto num_elements = static_cast<SizeType>(std::distance(first, last));
846 
847  const SizeType num_assignable = make_space_at_idx_for_n_elements(idx, num_elements);
848  Iterator insert_pos = begin() + idx;
849 
850  // Copy-assign to moved-from elements
851  std::copy_n(first, num_assignable, insert_pos);
852 
853  // Copy the remaining values into uninitialized cells
854  copy_range_into_uninitialized_cells(size_, first + num_assignable, last);
855 
856  size_ += num_elements;
857 
858  return insert_pos;
859  }
860 
874  Iterator insert(ConstIterator pos, std::initializer_list<ValueType> init)
875  {
876  return insert(pos, init.begin(), init.end());
877  }
878 
885  constexpr SizeType max_size() const noexcept
886  {
887  return std::numeric_limits<SizeType>::max();
888  }
889 
898  noexcept(std::is_nothrow_copy_assignable<ValueType>::value)
899  {
900  if (&other != this)
901  {
902  clear();
903  reserve(other.size());
904  std::uninitialized_copy(other.cbegin(), other.cend(), data());
905  size_ = other.size();
906  }
907 
908  return *this;
909  }
910 
925  noexcept(std::is_nothrow_move_constructible<ValueType>::value)
926  {
927  if (&other != this)
928  {
929  clear();
930  if (is_storage_allocated())
931  delete[] data_ptr_;
932  move_or_copy_all_elements_from(std::move(other));
933  }
934 
935  return *this;
936  }
937 
942  SmallVector& operator=(std::initializer_list<ValueType> init)
943  {
944  assign(init);
945  return *this;
946  }
947 
955  friend bool operator==(const SmallVector& lhs, const SmallVector& rhs)
956  {
957  return std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend());
958  }
959 
967  friend bool operator!=(const SmallVector& lhs, const SmallVector& rhs)
968  {
969  return not (lhs == rhs);
970  }
971 
974  {
975  return *(data() + idx);
976  }
977 
979  constexpr ConstReference operator[](SizeType idx) const
980  {
981  return *(data() + idx);
982  }
983 
988  void pop_back()
989  {
990  --size_;
991  auto p = data_end();
992  p->~ValueType();
993  }
994 
1004  void push_back(const ValueType& value)
1005  {
1006  if (size_ == capacity_)
1007  grow();
1008 
1009  ::new(static_cast<void*>(data_end())) ValueType(value);
1010 
1011  ++size_;
1012  }
1013 
1022  void push_back(ValueType&& value)
1023  {
1024  if (size_ == capacity_)
1025  grow();
1026 
1027  ::new(static_cast<void*>(data_end())) ValueType(std::move(value));
1028 
1029  ++size_;
1030  }
1031 
1039  {
1040  return std::make_reverse_iterator(end());
1041  }
1042 
1049  {
1050  return std::make_reverse_iterator(begin());
1051  }
1052 
1061  void reserve(SizeType new_capacity)
1062  {
1063  if (new_capacity <= capacity_)
1064  return;
1065 
1066  auto new_data = std::make_unique<AlignedStorage[]>(new_capacity);
1067 
1068  const auto d_end = data_end();
1069 
1070  uninitialized_move_or_copy(data(), d_end, reinterpret_cast<ValueType*>(new_data.get()));
1071  destroy_range(data(), d_end);
1072 
1073  if (is_storage_allocated())
1074  delete[] data_ptr_;
1075 
1076  data_ptr_ = new_data.release();
1077  capacity_ = new_capacity;
1078  }
1079 
1095  void resize(SizeType num_elements)
1096  {
1097  static_assert(std::is_default_constructible<ValueType>::value,
1098  "SmallVector: For using resize(), element type must be default-constructible");
1099 
1100  if (num_elements < size_)
1101  {
1102  destroy_range(data() + num_elements, data_end());
1103  }
1104  else if (num_elements > size_)
1105  {
1106  reserve(num_elements);
1107  fill_uninitialized_cells_with_default_constructed_elements(size_,
1108  num_elements - size_);
1109  }
1110 
1111  size_ = num_elements;
1112  }
1113 
1125  void resize(SizeType num_elements, const ValueType& element)
1126  {
1127  if (num_elements < size_)
1128  {
1129  destroy_range(data() + num_elements, data_end());
1130  }
1131  else if (num_elements > size_)
1132  {
1133  reserve(num_elements);
1134  copy_value_into_uninitialized_cells(size_, num_elements - size_, element);
1135  }
1136 
1137  size_ = num_elements;
1138  }
1139 
1145  {
1146  const SizeType new_capacity = std::max(inner_capacity(), size_);
1147 
1148  // No shrinking required?
1149  if (new_capacity == capacity_)
1150  return;
1151 
1152  AlignedStorage* new_data;
1153  auto new_memory = std::unique_ptr<AlignedStorage[]>{};
1154 
1155  if (new_capacity == inner_capacity()) {
1156  new_data = internal_array_.data();
1157  } else {
1158  new_memory = std::make_unique<AlignedStorage[]>(new_capacity);
1159  new_data = new_memory.get();
1160  }
1161 
1162  const auto d_end = data_end();
1163 
1164  uninitialized_move_or_copy(data(), d_end, reinterpret_cast<ValueType*>(new_data));
1165  destroy_range(data(), d_end);
1166 
1167  if (is_storage_allocated())
1168  delete[] data_ptr_;
1169 
1170  data_ptr_ = new_memory ? new_memory.release() : new_data;
1171  capacity_ = new_capacity;
1172  }
1173 
1175  constexpr SizeType size() const noexcept { return size_; }
1176 
1184  void swap(SmallVector& other)
1185  {
1186  if (is_storage_allocated())
1187  {
1188  if (other.is_storage_allocated())
1189  swap_heap_with_heap(*this, other);
1190  else
1191  swap_heap_with_internal(*this, other);
1192  }
1193  else
1194  {
1195  if (other.is_storage_allocated())
1196  swap_heap_with_internal(other, *this);
1197  else
1198  swap_internal_with_internal(*this, other);
1199  }
1200  }
1201 
1202 private:
1203  using AlignedStorage =
1204  typename std::aligned_storage<sizeof(ValueType), alignof(ValueType)>::type;
1205 
1210  std::array<AlignedStorage, in_capacity> internal_array_;
1211 
1213  AlignedStorage* data_ptr_{ internal_array_.data() };
1214 
1217  SizeType capacity_{ in_capacity };
1219  SizeType size_{ 0u };
1220 
1233  template<class InputIterator>
1234  void copy_range_into_uninitialized_cells(SizeType pos, InputIterator first,
1235  InputIterator last)
1236  {
1237  auto data_ptr = data() + pos;
1238 
1239  try
1240  {
1241  for (auto it = first; it != last; ++it)
1242  {
1243  ::new(static_cast<void*>(data_ptr)) ValueType{ *it };
1244  ++data_ptr;
1245  }
1246  }
1247  catch (...)
1248  {
1249  for (auto p = data() + pos; p != data_ptr; ++p)
1250  p->~ValueType();
1251 
1252  throw;
1253  }
1254  }
1255 
1262  void copy_value_into_uninitialized_cells(SizeType pos, SizeType num_elements,
1263  const ValueType& value)
1264  {
1265  const auto start_ptr = data() + pos;
1266  const auto end_ptr = start_ptr + num_elements;
1267  for (auto p = start_ptr; p != end_ptr; ++p)
1268  ::new(static_cast<void*>(p)) ValueType(value);
1269  }
1270 
1272  constexpr ValueType* data_end() noexcept
1273  {
1274  return reinterpret_cast<ValueType*>(data_ptr_) + size_;
1275  }
1276 
1278  constexpr const ValueType* data_end() const noexcept
1279  {
1280  return reinterpret_cast<const ValueType*>(data_ptr_) + size_;
1281  }
1282 
1291  static void destroy_range(Iterator it_start, Iterator it_end) noexcept
1292  {
1293  for (auto it = it_start; it != it_end; ++it)
1294  it->~ValueType();
1295  }
1296 
1311  template<typename InputIterator>
1312  void fill_empty_vector_with_copied_range(InputIterator first, InputIterator last)
1313  {
1314  const auto num_elements = static_cast<SizeType>(std::distance(first, last));
1315 
1316  reserve(num_elements);
1317  copy_range_into_uninitialized_cells(0u, first, last);
1318  size_ = num_elements;
1319  }
1320 
1329  void fill_empty_vector_with_copied_value(SizeType num_elements, const ValueType& value)
1330  {
1331  reserve(num_elements);
1332  copy_value_into_uninitialized_cells(0u, num_elements, value);
1333  size_ = num_elements;
1334  }
1335 
1344  void fill_uninitialized_cells_with_default_constructed_elements(SizeType pos,
1345  SizeType num_elements)
1346  {
1347  const auto start_ptr = data() + pos;
1348  const auto end_ptr = start_ptr + num_elements;
1349  auto ptr = start_ptr;
1350 
1351  try
1352  {
1353  for (; ptr != end_ptr; ++ptr)
1354  ::new(static_cast<void*>(ptr)) ValueType{};
1355  }
1356  catch (...)
1357  {
1358  destroy_range(start_ptr, ptr);
1359  throw;
1360  }
1361  }
1362 
1372  void grow()
1373  {
1374  const auto remaining_space = std::numeric_limits<SizeType>::max() - capacity_;
1375 
1376  if (remaining_space == 0u)
1377  throw std::length_error("Max. capacity reached");
1378 
1379  SizeType increase = capacity_ / 2u;
1380  if (increase > remaining_space)
1381  increase = remaining_space;
1382  else if (increase == 0u)
1383  increase = 1u;
1384 
1385  reserve(capacity_ + increase);
1386  }
1387 
1389  template <typename T>
1390  Iterator insert_single_value(ConstIterator pos, T&& value)
1391  {
1392  if (pos == end())
1393  {
1394  push_back(std::forward<T>(value));
1395  return begin() + size_ - 1;
1396  }
1397 
1398  const auto idx = static_cast<SizeType>(pos - begin());
1399 
1400  if (size_ == capacity_)
1401  grow();
1402 
1403  Iterator insert_pos = begin() + idx;
1404 
1405  auto data_ptr = data();
1406 
1407  // Construct new back() element by moving from the old back()
1408  ::new(static_cast<void*>(data_ptr + size_)) ValueType(std::move(*(data_ptr + size_ - 1)));
1409 
1410  std::move_backward(insert_pos, data_ptr + size_ - 1, data_ptr + size_);
1411  ++size_;
1412 
1413  *insert_pos = std::forward<T>(value);
1414 
1415  return insert_pos;
1416  }
1417 
1419  bool is_storage_allocated() const noexcept
1420  {
1421  return capacity_ > inner_capacity();
1422  }
1423 
1434  SizeType make_space_at_idx_for_n_elements(SizeType idx, SizeType num_elements)
1435  {
1436  const auto new_size = size_ + num_elements;
1437 
1438  if (new_size > capacity_)
1439  reserve(new_size);
1440 
1441  auto data_ptr = data();
1442 
1443  // We have a total number of elements that need to be shifted backwards,
1444  // of which some need to be move-initialized at the end of the vector
1445  // and some simply need to be moved from one element to another.
1446  const SizeType num_shifted = size_ - idx;
1447  const SizeType num_move_initialized = std::min(num_shifted, num_elements);
1448  const SizeType num_moved = num_shifted - num_move_initialized;
1449 
1450  // Move-initialize elements in uninitialized space at the back of the container
1451  const auto from_ptr = data_ptr + size_ - num_move_initialized;
1452  const auto to_ptr = from_ptr + num_elements;
1453  for (SizeType i = 0; i != num_move_initialized; ++i)
1454  ::new(static_cast<void*>(to_ptr + i)) ValueType(std::move(*(from_ptr + i)));
1455 
1456  // Move elements backwards within old vector size
1457  std::move_backward(data_ptr + idx, data_ptr + idx + num_moved, to_ptr);
1458 
1459  return num_move_initialized;
1460  }
1461 
1480  void move_or_copy_all_elements_from(SmallVector&& other)
1481  noexcept(std::is_nothrow_move_constructible<ValueType>::value)
1482  {
1483  // Can we simply steal the complete allocated storage?
1484  if (other.is_storage_allocated())
1485  {
1486  data_ptr_ = other.data_ptr_; other.data_ptr_ = other.internal_array_.data();
1487  capacity_ = other.capacity_; other.capacity_ = other.inner_capacity();
1488  size_ = other.size_; other.size_ = 0u;
1489  }
1490  else // otherwise fall back to moving (or at least copying) all elements
1491  {
1492  data_ptr_ = internal_array_.data();
1493  capacity_ = in_capacity;
1494  uninitialized_move_or_copy(other.begin(), other.end(), data());
1495  size_ = other.size();
1496  other.clear();
1497  }
1498  }
1499 
1505  static void swap_heap_with_heap(SmallVector &a, SmallVector &b) noexcept
1506  {
1507  std::swap(a.data_ptr_, b.data_ptr_);
1508  std::swap(a.capacity_, b.capacity_);
1509  std::swap(a.size_, b.size_);
1510  }
1511 
1518  static void swap_heap_with_internal(SmallVector &a, SmallVector &b)
1519  {
1520  uninitialized_move_or_copy(b.begin(), b.end(),
1521  reinterpret_cast<ValueType*>(a.internal_array_.data()));
1522  destroy_range(b.begin(), b.end());
1523 
1524  b.data_ptr_ = a.data_ptr_;
1525  a.data_ptr_ = a.internal_array_.data();
1526 
1527  std::swap(a.capacity_, b.capacity_);
1528  std::swap(a.size_, b.size_);
1529  }
1530 
1536  static void swap_internal_with_internal(SmallVector &a, SmallVector &b)
1537  {
1538  if (a.size_ <= b.size_)
1539  {
1540  for (SmallVector::SizeType i = 0; i != a.size_; ++i)
1541  std::swap(a.data()[i], b.data()[i]);
1542 
1543  uninitialized_move_or_copy(b.begin() + a.size_, b.end(), a.begin() + a.size_);
1544  destroy_range(b.begin() + a.size_, b.end());
1545  }
1546  else
1547  {
1548  for (SizeType i = 0; i != b.size_; ++i)
1549  std::swap(a.data()[i], b.data()[i]);
1550 
1551  uninitialized_move_or_copy(a.begin() + b.size_, a.end(), b.begin() + b.size_);
1552  destroy_range(a.begin() + b.size_, a.end());
1553  }
1554 
1555  std::swap(a.size_, b.size_);
1556  }
1557 
1562  template <typename T>
1563  static typename std::enable_if_t<not std::is_nothrow_move_constructible<T>::value>
1564  uninitialized_move(T* src_begin, T* src_end, T* dest_begin)
1565  {
1566  auto src = src_begin;
1567  auto dest = dest_begin;
1568 
1569  try
1570  {
1571  while (src != src_end)
1572  {
1573  ::new (static_cast<void*>(dest)) ValueType(std::move(*src));
1574  ++src;
1575  ++dest;
1576  }
1577  }
1578  catch (...)
1579  {
1580  for (auto p = dest_begin; p != dest; ++p)
1581  p->~ValueType();
1582 
1583  throw;
1584  }
1585  }
1586 
1591  template <typename T>
1592  static typename std::enable_if_t<std::is_nothrow_move_constructible<T>::value>
1593  uninitialized_move(T* src_begin, T* src_end, T* dest_begin) noexcept
1594  {
1595  auto src = src_begin;
1596  auto dest = dest_begin;
1597 
1598  while (src != src_end)
1599  {
1600  ::new (static_cast<void*>(dest)) ValueType(std::move(*src));
1601  ++src;
1602  ++dest;
1603  }
1604  }
1605 
1608  template <typename T>
1609  static typename std::enable_if_t<std::is_nothrow_move_constructible<T>::value>
1610  uninitialized_move_or_copy(T* src_begin, T* src_end, T* dest_begin) noexcept
1611  {
1612  uninitialized_move(src_begin, src_end, dest_begin);
1613  }
1614 
1617  template <typename T>
1618  static typename std::enable_if_t<not std::is_nothrow_move_constructible<T>::value and
1619  std::is_copy_constructible<T>::value>
1620  uninitialized_move_or_copy(T* src_begin, T* src_end, T* dest_begin)
1621  {
1622  std::uninitialized_copy(src_begin, src_end, dest_begin);
1623  }
1624 
1627  template <typename T>
1628  static typename std::enable_if_t<not std::is_nothrow_move_constructible<T>::value
1629  and not std::is_copy_constructible<T>::value>
1630  uninitialized_move_or_copy(T* src_begin, T* src_end, T* dest_begin)
1631  {
1632  uninitialized_move(src_begin, src_end, dest_begin);
1633  }
1634 };
1635 
1636 
1644 template<typename ElementT, size_t in_capacity>
1646 {
1647  a.swap(b);
1648 }
1649 
1650 } // namespace gul14
1651 
1652 #endif
1653 
1654 // vi:ts=4:sw=4:sts=4:et
gul14::SmallVector::crbegin
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
gul14::SmallVector::ConstReference
const ValueType & ConstReference
Reference to a const element.
Definition: SmallVector.h:282
gul14::SmallVector::clear
void clear() noexcept
Erase all elements from the container without changing its capacity.
Definition: SmallVector.h:562
gul14::SmallVector::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
gul14::SmallVector::SmallVector
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
gul14::SmallVector::ConstReverseIterator
std::reverse_iterator< ConstIterator > ConstReverseIterator
Iterator to a const element in reversed container.
Definition: SmallVector.h:298
gul14::SmallVector::insert
Iterator insert(ConstIterator pos, ValueType &&value)
Insert a single element before the indicated position.
Definition: SmallVector.h:789
gul14::swap
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:1645
gul14::SmallVector::max_size
constexpr SizeType max_size() const noexcept
Return the maximum number of elements that this vector can theoretically hold.
Definition: SmallVector.h:885
gul14::SmallVector::ReverseIterator
std::reverse_iterator< Iterator > ReverseIterator
Iterator to an element in reversed container.
Definition: SmallVector.h:294
gul14::SmallVector::resize
void resize(SizeType num_elements)
Change the number of elements in the container.
Definition: SmallVector.h:1095
gul14::SmallVector::assign
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
gul14::SmallVector::rbegin
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:1038
gul14::SmallVector::push_back
void push_back(ValueType &&value)
Move one element to the end of the buffer.
Definition: SmallVector.h:1022
gul14::SmallVector::Reference
ValueType & Reference
Reference to an element.
Definition: SmallVector.h:278
gul14::SmallVector::operator==
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:955
gul14::SmallVector::erase
Iterator erase(ConstIterator pos)
Erase a single element from the vector, moving elements behind it forward.
Definition: SmallVector.h:710
gul14::SmallVector::size_type
SizeType size_type
Unsigned integer type for indexing, number of elements, capacity.
Definition: SmallVector.h:272
gul14::SmallVector::difference_type
DifferenceType difference_type
Signed integer type for the difference of two iterators.
Definition: SmallVector.h:276
gul14::SmallVector::reserve
void reserve(SizeType new_capacity)
Increase the capacity of the vector to the specified size.
Definition: SmallVector.h:1061
gul14::SmallVector::ValueType
ElementT ValueType
Type of the elements in the underlying container.
Definition: SmallVector.h:266
gul14::SmallVector::SmallVector
SmallVector(InputIterator first, InputIterator last)
Construct a SmallVector that is filled with copies of elements from the given range.
Definition: SmallVector.h:359
gul14::SmallVector::operator[]
constexpr ConstReference operator[](SizeType idx) const
Return a const reference to the element at the specified index.
Definition: SmallVector.h:979
gul14::SmallVector::erase
Iterator erase(ConstIterator first, ConstIterator last)
Erase a range of elements from the vector, moving elements behind the range forward.
Definition: SmallVector.h:728
gul14::SmallVector::back
constexpr Reference back() noexcept
Return a reference to the last element in the vector.
Definition: SmallVector.h:502
gul14::SmallVector::resize
void resize(SizeType num_elements, const ValueType &element)
Change the number of elements in the container.
Definition: SmallVector.h:1125
gul14::SmallVector::operator=
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:897
gul14::SmallVector::operator[]
constexpr Reference operator[](SizeType idx)
Return a reference to the element at the specified index.
Definition: SmallVector.h:973
gul14::SmallVector::back
constexpr ConstReference back() const noexcept
Return a const reference to the last element in the vector.
Definition: SmallVector.h:511
gul14::SmallVector::reference
Reference reference
Reference to an element.
Definition: SmallVector.h:280
gul14::SmallVector::inner_capacity
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
gul14::SmallVector::~SmallVector
~SmallVector()
Destructor: Destroys all stored elements and frees all allocated memory.
Definition: SmallVector.h:414
gul14::SmallVector::operator=
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:924
gul14::SmallVector::Iterator
ValueType * Iterator
Iterator to an element.
Definition: SmallVector.h:286
gul14::cat
std::string cat()
Efficiently concatenate an arbitrary number of strings and numbers.
Definition: cat.h:90
cat.h
Declaration of the overload set for cat() and of the associated class ConvertingStringView.
gul14::SmallVector::empty
constexpr bool empty() const noexcept
Determine if the vector is empty.
Definition: SmallVector.h:679
gul14::SmallVector::SmallVector
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
gul14::SmallVector::value_type
ValueType value_type
Type of the elements in the underlying container.
Definition: SmallVector.h:268
gul14::SmallVector::const_reverse_iterator
ConstReverseIterator const_reverse_iterator
Iterator to a const element in reversed container.
Definition: SmallVector.h:300
gul14::SmallVector::const_reference
ConstReference const_reference
Reference to a const element.
Definition: SmallVector.h:284
gul14::SmallVector::begin
constexpr Iterator begin() noexcept
Return an iterator to the first element of the vector.
Definition: SmallVector.h:520
gul14::SmallVector::size
constexpr SizeType size() const noexcept
Return the number of elements that are currently stored.
Definition: SmallVector.h:1175
gul14::SmallVector
A resizable container with contiguous storage that can hold a specified number of elements without al...
Definition: SmallVector.h:262
gul14::SmallVector::end
constexpr Iterator end() noexcept
Return an iterator pointing past the last element of the vector.
Definition: SmallVector.h:685
gul14::SmallVector::push_back
void push_back(const ValueType &value)
Copy one element to the end of the buffer.
Definition: SmallVector.h:1004
gul14::SmallVector::reverse_iterator
ReverseIterator reverse_iterator
Iterator to an element in reversed container.
Definition: SmallVector.h:296
gul14::SmallVector::data
constexpr ValueType * data() noexcept
Return a pointer to the contiguous data storage of the vector.
Definition: SmallVector.h:594
gul14::SmallVector::assign
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
gul14::SmallVector::swap
void swap(SmallVector &other)
Exchange the contents of this SmallVector with those of another one.
Definition: SmallVector.h:1184
gul14::SmallVector::SmallVector
SmallVector() noexcept=default
Construct an empty SmallVector.
gul14::SmallVector::emplace_back
Reference emplace_back(ArgumentTypes &&... arguments)
Construct an additional element at the end of the buffer.
Definition: SmallVector.h:665
gul14::SmallVector::at
constexpr Reference at(SizeType idx)
Return a reference to the element at the specified index with bounds-checking.
Definition: SmallVector.h:483
gul14::SmallVector::rend
ReverseIterator rend() noexcept
Return a reverse iterator pointing past the last element of the reversed vector.
Definition: SmallVector.h:1048
gul14::SmallVector::shrink_to_fit
void shrink_to_fit()
Reduce the capacity as far as possible while retaining all stored elements.
Definition: SmallVector.h:1144
gul14::SmallVector::emplace
Iterator emplace(ConstIterator pos, ArgumentTypes &&... arguments)
Construct an additional element at an arbitrary position in the vector.
Definition: SmallVector.h:634
gul14::SmallVector::cbegin
constexpr ConstIterator cbegin() const noexcept
Return a const iterator to the first element of the vector.
Definition: SmallVector.h:544
internal.h
Definition of macros used internally by GUL.
gul14::SmallVector::pop_back
void pop_back()
Remove the last element from the vector.
Definition: SmallVector.h:988
gul14::SmallVector::assign
void assign(InputIterator first, InputIterator last)
Fill the vector with copies of elements from the given range.
Definition: SmallVector.h:456
gul14::SmallVector::front
constexpr ConstReference front() const noexcept
Return a const reference to the first element in the vector.
Definition: SmallVector.h:755
gul14::SmallVector::operator=
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:942
gul14::SmallVector::capacity
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
gul14::SmallVector::begin
constexpr ConstIterator begin() const noexcept
Return a const iterator to the first element of the vector.
Definition: SmallVector.h:529
gul14
Namespace gul14 contains all functions and classes of the General Utility Library.
Definition: doxygen.h:26
gul14::SmallVector::end
constexpr ConstIterator end() const noexcept
Return a const iterator pointing past the last element of the vector.
Definition: SmallVector.h:694
gul14::SmallVector::insert
Iterator insert(ConstIterator pos, InputIterator first, InputIterator last)
Insert a range of values before the indicated position.
Definition: SmallVector.h:842
gul14::SmallVector::insert
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
gul14::SmallVector::insert
Iterator insert(ConstIterator pos, const ValueType &value)
Insert a single element before the indicated position.
Definition: SmallVector.h:775
gul14::SmallVector::SmallVector
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
gul14::SmallVector::front
constexpr Reference front() noexcept
Return a reference to the first element in the vector.
Definition: SmallVector.h:746
gul14::SmallVector::SizeType
uint32_t SizeType
Unsigned integer type for indexing, number of elements, capacity.
Definition: SmallVector.h:270
gul14::SmallVector::data
constexpr const ValueType * data() const noexcept
Return a pointer to the contiguous data storage of the vector.
Definition: SmallVector.h:603
gul14::SmallVector::at
constexpr ConstReference at(SizeType idx) const
Return a const reference to the element at the specified index.
Definition: SmallVector.h:491
gul14::SmallVector::DifferenceType
std::ptrdiff_t DifferenceType
Signed integer type for the difference of two iterators.
Definition: SmallVector.h:274
gul14::SmallVector::ConstIterator
const ValueType * ConstIterator
Iterator to a const element.
Definition: SmallVector.h:290
gul14::SmallVector::operator!=
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:967
gul14::SmallVector::iterator
Iterator iterator
Iterator to an element.
Definition: SmallVector.h:288
gul14::SmallVector::const_iterator
ConstIterator const_iterator
Iterator to a const element.
Definition: SmallVector.h:292
gul14::SmallVector::cend
constexpr ConstIterator cend() const noexcept
Return a const iterator pointing past the last element of the vector.
Definition: SmallVector.h:553
gul14::SmallVector::crend
ConstReverseIterator crend() noexcept
Return a const reverse iterator pointing past the last element of the reversed vector.
Definition: SmallVector.h:585
gul14::SmallVector::insert
Iterator insert(ConstIterator pos, std::initializer_list< ValueType > init)
Insert elements from an initializer list before the indicated position.
Definition: SmallVector.h:874