23 #ifndef GUL14_SMALLVECTOR_H_
24 #define GUL14_SMALLVECTOR_H_
28 #include <initializer_list>
33 #include <type_traits>
261 template <
typename ElementT,
size_t in_capacity>
320 static_assert(std::is_default_constructible<ValueType>::value,
321 "SmallVector: Element type is not default-constructible");
324 for (
SizeType i = 0u; i != num_elements; ++i)
326 size_ = num_elements;
338 fill_empty_vector_with_copied_value(num_elements, value);
357 template<
class InputIterator,
358 typename = std::enable_if_t<not std::is_integral<InputIterator>::value>>
361 fill_empty_vector_with_copied_range(first, last);
373 noexcept(std::is_nothrow_copy_constructible<ValueType>::value)
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());
396 noexcept(std::is_nothrow_move_constructible<ValueType>::value)
398 move_or_copy_all_elements_from(std::move(other));
410 fill_empty_vector_with_copied_range(init.begin(), init.end());
418 if (is_storage_allocated())
432 fill_empty_vector_with_copied_value(num_elements, value);
454 template<
class InputIterator,
455 typename = std::enable_if_t<not std::is_integral<InputIterator>::value>>
456 void assign(InputIterator first, InputIterator last)
459 fill_empty_vector_with_copied_range(first, last);
469 void assign(std::initializer_list<ValueType> init)
471 const auto num_elements =
static_cast<SizeType>(init.size());
475 std::uninitialized_copy(init.begin(), init.end(),
data());
476 size_ = num_elements;
486 throw std::out_of_range(
cat(
"Index out of range: ", idx,
" >= ", size_));
487 return *(
data() + idx);
494 throw std::out_of_range(
cat(
"Index out of range: ", idx,
" >= ", size_));
495 return *(
data() + idx);
504 return *(data_end() - 1);
513 return *(data_end() - 1);
564 destroy_range(
data(), data_end());
576 return std::make_reverse_iterator(
end());
587 return std::make_reverse_iterator(
begin());
596 return reinterpret_cast<ValueType*
>(data_ptr_);
605 return reinterpret_cast<const ValueType*
>(data_ptr_);
633 template <
typename... ArgumentTypes>
638 emplace_back(std::forward<ArgumentTypes>(arguments)...);
639 return data_end() - 1;
642 ValueType v(std::forward<ArgumentTypes>(arguments)...);
644 return insert_single_value(pos, std::move(v));
664 template <
typename... ArgumentTypes>
667 if (size_ == capacity_)
670 ::new(
static_cast<void*
>(data_end()))
671 ValueType(std::forward<ArgumentTypes>(arguments)...);
679 constexpr
bool empty() const noexcept {
return size_ == 0u; }
712 return erase(pos, pos + 1);
730 auto range_begin =
const_cast<Iterator>(first);
731 auto range_end =
const_cast<Iterator>(last);
732 auto num_elements = range_end - range_begin;
734 std::move(range_end,
end(), range_begin);
735 destroy_range(
end() - num_elements,
end());
737 size_ -=
static_cast<SizeType>(num_elements);
777 return insert_single_value(pos, value);
791 return insert_single_value(pos, std::move(value));
806 if (num_elements < 1)
807 return begin() + idx;
809 const SizeType num_assignable = make_space_at_idx_for_n_elements(idx, num_elements);
813 std::fill_n(insert_pos, num_assignable, value);
816 copy_value_into_uninitialized_cells(size_, num_elements - num_assignable, value);
818 size_ += num_elements;
842 template<
class InputIterator,
843 typename = std::enable_if_t<not std::is_integral<InputIterator>::value>>
847 const auto num_elements =
static_cast<SizeType>(std::distance(first, last));
848 if (num_elements < 1)
849 return begin() + idx;
851 const SizeType num_assignable = make_space_at_idx_for_n_elements(idx, num_elements);
855 std::copy_n(first, num_assignable, insert_pos);
858 copy_range_into_uninitialized_cells(size_, first + num_assignable, last);
860 size_ += num_elements;
880 return insert(pos, init.begin(), init.end());
891 return std::numeric_limits<SizeType>::max();
902 noexcept(std::is_nothrow_copy_assignable<ValueType>::value)
908 std::uninitialized_copy(other.cbegin(), other.cend(),
data());
909 size_ = other.size();
929 noexcept(std::is_nothrow_move_constructible<ValueType>::value)
934 if (is_storage_allocated())
936 move_or_copy_all_elements_from(std::move(other));
973 return not (lhs == rhs);
979 return *(
data() + idx);
985 return *(
data() + idx);
1010 if (size_ == capacity_)
1013 ::new(
static_cast<void*
>(data_end()))
ValueType(value);
1028 if (size_ == capacity_)
1031 ::new(
static_cast<void*
>(data_end()))
ValueType(std::move(value));
1044 return std::make_reverse_iterator(
end());
1054 return std::make_reverse_iterator(
begin());
1067 if (new_capacity <= capacity_)
1070 auto new_data = std::make_unique<AlignedStorage[]>(new_capacity);
1072 const auto d_end = data_end();
1074 uninitialized_move_or_copy(
data(), d_end,
reinterpret_cast<ValueType*
>(new_data.get()));
1075 destroy_range(
data(), d_end);
1077 if (is_storage_allocated())
1080 data_ptr_ = new_data.release();
1081 capacity_ = new_capacity;
1101 static_assert(std::is_default_constructible<ValueType>::value,
1102 "SmallVector: For using resize(), element type must be default-constructible");
1104 if (num_elements < size_)
1106 destroy_range(
data() + num_elements, data_end());
1108 else if (num_elements > size_)
1111 fill_uninitialized_cells_with_default_constructed_elements(size_,
1112 num_elements - size_);
1115 size_ = num_elements;
1131 if (num_elements < size_)
1133 destroy_range(
data() + num_elements, data_end());
1135 else if (num_elements > size_)
1138 copy_value_into_uninitialized_cells(size_, num_elements - size_, element);
1141 size_ = num_elements;
1153 if (new_capacity == capacity_)
1156 AlignedStorage* new_data;
1157 auto new_memory = std::unique_ptr<AlignedStorage[]>{};
1160 new_data = internal_array_.data();
1162 new_memory = std::make_unique<AlignedStorage[]>(new_capacity);
1163 new_data = new_memory.get();
1166 const auto d_end = data_end();
1168 uninitialized_move_or_copy(
data(), d_end,
reinterpret_cast<ValueType*
>(new_data));
1169 destroy_range(
data(), d_end);
1171 if (is_storage_allocated())
1174 data_ptr_ = new_memory ? new_memory.release() : new_data;
1175 capacity_ = new_capacity;
1190 if (is_storage_allocated())
1192 if (other.is_storage_allocated())
1193 swap_heap_with_heap(*
this, other);
1195 swap_heap_with_internal(*
this, other);
1199 if (other.is_storage_allocated())
1200 swap_heap_with_internal(other, *
this);
1202 swap_internal_with_internal(*
this, other);
1207 using AlignedStorage =
1214 std::array<AlignedStorage, in_capacity> internal_array_;
1217 AlignedStorage* data_ptr_{ internal_array_.data() };
1237 template<
class InputIterator>
1238 void copy_range_into_uninitialized_cells(
SizeType pos, InputIterator first,
1241 auto data_ptr =
data() + pos;
1245 for (
auto it = first; it != last; ++it)
1247 ::new(
static_cast<void*
>(data_ptr))
ValueType{ *it };
1253 for (
auto p =
data() + pos; p != data_ptr; ++p)
1266 void copy_value_into_uninitialized_cells(
SizeType pos,
SizeType num_elements,
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);
1276 constexpr
ValueType* data_end() noexcept
1278 return reinterpret_cast<ValueType*
>(data_ptr_) + size_;
1282 constexpr
const ValueType* data_end() const noexcept
1284 return reinterpret_cast<const ValueType*
>(data_ptr_) + size_;
1297 for (
auto it = it_start; it != it_end; ++it)
1315 template<
typename InputIterator>
1316 void fill_empty_vector_with_copied_range(InputIterator first, InputIterator last)
1318 const auto num_elements =
static_cast<SizeType>(std::distance(first, last));
1321 copy_range_into_uninitialized_cells(0u, first, last);
1322 size_ = num_elements;
1333 void fill_empty_vector_with_copied_value(
SizeType num_elements,
const ValueType& value)
1336 copy_value_into_uninitialized_cells(0u, num_elements, value);
1337 size_ = num_elements;
1348 void fill_uninitialized_cells_with_default_constructed_elements(
SizeType pos,
1351 const auto start_ptr =
data() + pos;
1352 const auto end_ptr = start_ptr + num_elements;
1353 auto ptr = start_ptr;
1357 for (; ptr != end_ptr; ++ptr)
1358 ::
new(
static_cast<void*
>(ptr))
ValueType{};
1362 destroy_range(start_ptr, ptr);
1378 const auto remaining_space = std::numeric_limits<SizeType>::max() - capacity_;
1380 if (remaining_space == 0u)
1381 throw std::length_error(
"Max. capacity reached");
1383 SizeType increase = capacity_ / 2u;
1384 if (increase > remaining_space)
1385 increase = remaining_space;
1386 else if (increase == 0u)
1389 reserve(capacity_ + increase);
1393 template <
typename T>
1399 return begin() + size_ - 1;
1404 if (size_ == capacity_)
1409 auto data_ptr =
data();
1412 ::new(
static_cast<void*
>(data_ptr + size_))
ValueType(std::move(*(data_ptr + size_ - 1)));
1414 std::move_backward(insert_pos, data_ptr + size_ - 1, data_ptr + size_);
1417 *insert_pos = std::forward<T>(value);
1423 bool is_storage_allocated() const noexcept
1440 const auto new_size = size_ + num_elements;
1442 if (new_size > capacity_)
1445 auto data_ptr =
data();
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;
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)));
1461 std::move_backward(data_ptr + idx, data_ptr + idx + num_moved, to_ptr);
1463 return num_move_initialized;
1484 void move_or_copy_all_elements_from(
SmallVector&& other)
1485 noexcept(std::is_nothrow_move_constructible<ValueType>::value)
1488 if (other.is_storage_allocated())
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;
1496 data_ptr_ = internal_array_.data();
1497 capacity_ = in_capacity;
1498 uninitialized_move_or_copy(other.begin(), other.end(),
data());
1499 size_ = other.size();
1524 uninitialized_move_or_copy(b.begin(), b.end(),
1525 reinterpret_cast<ValueType*
>(a.internal_array_.data()));
1526 destroy_range(b.begin(), b.end());
1528 b.data_ptr_ = a.data_ptr_;
1529 a.data_ptr_ = a.internal_array_.data();
1542 if (a.size_ <= b.size_)
1547 uninitialized_move_or_copy(b.begin() + a.size_, b.end(), a.begin() + a.size_);
1548 destroy_range(b.begin() + a.size_, b.end());
1552 for (
SizeType i = 0; i != b.size_; ++i)
1555 uninitialized_move_or_copy(a.begin() + b.size_, a.end(), b.begin() + b.size_);
1556 destroy_range(a.begin() + b.size_, a.end());
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)
1570 auto src = src_begin;
1571 auto dest = dest_begin;
1575 while (src != src_end)
1577 ::new (
static_cast<void*
>(dest))
ValueType(std::move(*src));
1584 for (
auto p = dest_begin; p != dest; ++p)
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
1599 auto src = src_begin;
1600 auto dest = dest_begin;
1602 while (src != src_end)
1604 ::new (
static_cast<void*
>(dest))
ValueType(std::move(*src));
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
1616 uninitialized_move(src_begin, src_end, dest_begin);
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)
1626 std::uninitialized_copy(src_begin, src_end, dest_begin);
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)
1636 uninitialized_move(src_begin, src_end, dest_begin);
1648 template<
typename ElementT,
size_t in_capacity>
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