StormByte 3.0.0
C++26 foundation of the StormByte suite
Loading...
Searching...
No Matches
vector.txx
Go to the documentation of this file.
1/*
2 * Copyright (C) 2024-2026 David C. Manuelda (StormBytePP)
3 *
4 * This is the base for StormByte Suite libraries.
5 *
6 * StormByte original source is dual-licensed:
7 *
8 * 1. GNU Lesser General Public License v3.0 (or later)
9 * You may redistribute and/or modify this file under the terms of the
10 * GNU Lesser General Public License as published by the Free Software
11 * Foundation, either version 3 of the License, or (at your option)
12 * any later version.
13 *
14 * 2. Commercial license
15 * Alternatively, this file may be used under the terms of a commercial
16 * license agreement with the copyright holder
17 * (David C. Manuelda <StormByte@gmail.com>).
18 *
19 * Both licenses apply only to original StormByte source in this repository.
20 * They do not cover other StormByte modules or any third-party material
21 * shipped with this repository (including everything under thirdparty/),
22 * which remains under its own license.
23 *
24 * Neither license grants any patent rights. Any patent licenses required
25 * to use this software or third-party components must be obtained separately
26 * from the patent holders.
27 *
28 * StormByte is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 * GNU Lesser General Public License for more details.
32 *
33 * You should have received a copy of the GNU Lesser General Public License
34 * version 3 along with StormByte. If not, see
35 * <https://www.gnu.org/licenses/lgpl-3.0.html>.
36 *
37 * SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-StormByte-Commercial
38 */
39
40#pragma once
41
42#include <algorithm>
43#include <cstring>
44#include <iterator>
45#include <memory>
46#include <new>
47#include <utility>
48
49namespace StormByte {
50 namespace Safe {
51 template<Type::SafeValue T>
52 Vector<T>::Vector() noexcept: m_data(nullptr), m_size(0), m_capacity(0) {}
53
54 template<Type::SafeValue T>
55 Vector<T>::Vector(size_type count): m_data(nullptr), m_size(0), m_capacity(0) {
56 resize(count);
57 }
58
59 template<Type::SafeValue T>
60 Vector<T>::Vector(size_type count, const T& value): m_data(nullptr), m_size(0), m_capacity(0) {
61 assign(count, value);
62 }
63
64 template<Type::SafeValue T>
65 template<std::input_iterator InputIt>
66 Vector<T>::Vector(InputIt first, InputIt last): m_data(nullptr), m_size(0), m_capacity(0) {
67 assign(first, last);
68 }
69
70 template<Type::SafeValue T>
71 Vector<T>::Vector(std::initializer_list<T> values): m_data(nullptr), m_size(0), m_capacity(0) {
72 assign(values);
73 }
74
75 template<Type::SafeValue T>
76 Vector<T>::Vector(const std::vector<T>& values): m_data(nullptr), m_size(0), m_capacity(0) {
77 reserve(values.size());
78 for (const T& value : values)
79 push_back(value);
80 }
81
82 template<Type::SafeValue T>
83 Vector<T>::Vector(const Vector& other): m_data(nullptr), m_size(0), m_capacity(0) {
84 reserve(other.m_size);
85 if constexpr (Type::TriviallyCopyable<T> && Type::TriviallyCopyConstructible<T>) {
86 if (other.m_size != 0)
87 std::memcpy(m_data, other.m_data, static_cast<std::size_t>(other.m_size) * sizeof(T));
88 m_size = other.m_size;
89 }
90 else {
91 for (const T& value : other)
92 push_back(value);
93 }
94 }
95
96 template<Type::SafeValue T>
97 Vector<T>::Vector(Vector&& other) noexcept: m_data(other.m_data), m_size(other.m_size), m_capacity(other.m_capacity) {
98 other.m_data = nullptr;
99 other.m_size = 0;
100 other.m_capacity = 0;
101 }
102
103 template<Type::SafeValue T>
104 Vector<T>::~Vector() noexcept {
105 Release(m_data, m_size);
106 }
107
108 template<Type::SafeValue T>
109 Vector<T>& Vector<T>::operator=(const Vector& other) {
110 if (this == &other)
111 return *this;
112 Vector copy(other);
113 swap(copy);
114 return *this;
115 }
116
117 template<Type::SafeValue T>
118 Vector<T>& Vector<T>::operator=(Vector&& other) noexcept {
119 if (this == &other)
120 return *this;
121 Release(m_data, m_size);
122 m_data = other.m_data;
123 m_size = other.m_size;
124 m_capacity = other.m_capacity;
125 other.m_data = nullptr;
126 other.m_size = 0;
127 other.m_capacity = 0;
128 return *this;
129 }
130
131 template<Type::SafeValue T>
132 Vector<T>& Vector<T>::operator=(std::initializer_list<T> values) {
133 assign(values);
134 return *this;
135 }
136
137 template<Type::SafeValue T>
138 Vector<T>& Vector<T>::operator=(const std::vector<T>& values) {
139 Vector copy(values);
140 swap(copy);
141 return *this;
142 }
143
144 template<Type::SafeValue T>
145 Vector<T>::iterator Vector<T>::begin() noexcept {
146 return m_data;
147 }
148
149 template<Type::SafeValue T>
150 Vector<T>::iterator Vector<T>::end() noexcept {
151 return m_data + m_size;
152 }
153
154 template<Type::SafeValue T>
155 Vector<T>::const_iterator Vector<T>::begin() const noexcept {
156 return m_data;
157 }
158
159 template<Type::SafeValue T>
160 Vector<T>::const_iterator Vector<T>::end() const noexcept {
161 return m_data + m_size;
162 }
163
164 template<Type::SafeValue T>
165 Vector<T>::const_iterator Vector<T>::cbegin() const noexcept {
166 return begin();
167 }
168
169 template<Type::SafeValue T>
170 Vector<T>::const_iterator Vector<T>::cend() const noexcept {
171 return end();
172 }
173
174 template<Type::SafeValue T>
175 bool Vector<T>::empty() const noexcept {
176 return m_size == 0;
177 }
178
179 template<Type::SafeValue T>
180 Vector<T>::size_type Vector<T>::size() const noexcept {
181 return m_size;
182 }
183
184 template<Type::SafeValue T>
185 Vector<T>::size_type Vector<T>::capacity() const noexcept {
186 return m_capacity;
187 }
188
189 template<Type::SafeValue T>
190 Vector<T>::pointer Vector<T>::data() noexcept {
191 return m_data;
192 }
193
194 template<Type::SafeValue T>
195 Vector<T>::const_pointer Vector<T>::data() const noexcept {
196 return m_data;
197 }
198
199 template<Type::SafeValue T>
200 void Vector<T>::reserve(size_type count) {
201 if (count <= m_capacity)
202 return;
203 T* block = Allocate(count);
204 for (size_type index = 0; index < m_size; ++index) {
205 new (block + index) T(std::move(m_data[index]));
206 m_data[index].~T();
207 }
208 Heap::Free(m_data);
209 m_data = block;
210 m_capacity = count;
211 }
212
213 template<Type::SafeValue T>
214 void Vector<T>::shrink_to_fit() {
215 if (m_size == m_capacity)
216 return;
217 Vector copy(*this);
218 swap(copy);
219 }
220
221 template<Type::SafeValue T>
222 void Vector<T>::clear() noexcept {
223 for (size_type index = 0; index < m_size; ++index)
224 m_data[index].~T();
225 m_size = 0;
226 }
227
228 template<Type::SafeValue T>
229 void Vector<T>::swap(Vector& other) noexcept {
230 using std::swap;
231 swap(m_data, other.m_data);
232 swap(m_size, other.m_size);
233 swap(m_capacity, other.m_capacity);
234 }
235
236 template<Type::SafeValue T>
237 Vector<T>::reference Vector<T>::operator[](size_type index) noexcept {
238 return m_data[index];
239 }
240
241 template<Type::SafeValue T>
242 Vector<T>::const_reference Vector<T>::operator[](size_type index) const noexcept {
243 return m_data[index];
244 }
245
246 template<Type::SafeValue T>
247 Vector<T>::reference Vector<T>::at(size_type index) {
248 if (index >= m_size)
249 ThrowVectorOutOfBounds(index);
250 return m_data[index];
251 }
252
253 template<Type::SafeValue T>
254 Vector<T>::const_reference Vector<T>::at(size_type index) const {
255 if (index >= m_size)
256 ThrowVectorOutOfBounds(index);
257 return m_data[index];
258 }
259
260 template<Type::SafeValue T>
261 Vector<T>::reference Vector<T>::front() {
262 if (m_size == 0)
263 ThrowVectorOutOfBounds();
264 return m_data[0];
265 }
266
267 template<Type::SafeValue T>
268 Vector<T>::const_reference Vector<T>::front() const {
269 if (m_size == 0)
270 ThrowVectorOutOfBounds();
271 return m_data[0];
272 }
273
274 template<Type::SafeValue T>
275 Vector<T>::reference Vector<T>::back() {
276 if (m_size == 0)
277 ThrowVectorOutOfBounds();
278 return m_data[m_size - 1];
279 }
280
281 template<Type::SafeValue T>
282 Vector<T>::const_reference Vector<T>::back() const {
283 if (m_size == 0)
284 ThrowVectorOutOfBounds();
285 return m_data[m_size - 1];
286 }
287
288 template<Type::SafeValue T>
289 void Vector<T>::push_back(const T& value) {
290 if (m_size == m_capacity)
291 Grow();
292 new (m_data + m_size) T(value);
293 ++m_size;
294 }
295
296 template<Type::SafeValue T>
297 void Vector<T>::push_back(T&& value) {
298 if (m_size == m_capacity)
299 Grow();
300 new (m_data + m_size) T(std::move(value));
301 ++m_size;
302 }
303
304 template<Type::SafeValue T>
305 template<std::ranges::input_range R>
306 void Vector<T>::append_range(R&& range) {
307 if constexpr (std::ranges::sized_range<R>)
308 reserve(m_size + static_cast<size_type>(std::ranges::size(range)));
309 for (auto&& value : range)
310 push_back(static_cast<T>(std::forward<decltype(value)>(value)));
311 }
312
313 template<Type::SafeValue T>
314 void Vector<T>::pop_back() {
315 if (m_size == 0)
316 ThrowVectorOutOfBounds();
317 --m_size;
318 m_data[m_size].~T();
319 }
320
321 template<Type::SafeValue T>
322 template<class... Args>
323 Vector<T>::reference Vector<T>::emplace_back(Args&&... args) {
324 if (m_size == m_capacity)
325 Grow();
326 new (m_data + m_size) T(std::forward<Args>(args)...);
327 ++m_size;
328 return m_data[m_size - 1];
329 }
330
331 template<Type::SafeValue T>
332 Vector<T>::iterator Vector<T>::insert(const_iterator position, const T& value) {
333 return insert(position, 1, value);
334 }
335
336 template<Type::SafeValue T>
337 Vector<T>::iterator Vector<T>::insert(const_iterator position, T&& value) {
338 const size_type index = static_cast<size_type>(position - m_data);
339 if (m_size == m_capacity)
340 Grow();
341 for (size_type cursor = m_size; cursor > index; --cursor) {
342 new (m_data + cursor) T(std::move(m_data[cursor - 1]));
343 m_data[cursor - 1].~T();
344 }
345 new (m_data + index) T(std::move(value));
346 ++m_size;
347 return m_data + index;
348 }
349
350 template<Type::SafeValue T>
351 Vector<T>::iterator Vector<T>::insert(const_iterator position, size_type count, const T& value) {
352 const size_type index = static_cast<size_type>(position - m_data);
353 if (count == 0)
354 return m_data + index;
355 if (m_size + count > m_capacity)
356 reserve(m_capacity * 2 > m_size + count ? m_capacity * 2 : m_size + count);
357 for (size_type cursor = m_size; cursor > index; --cursor) {
358 new (m_data + cursor + count - 1) T(std::move(m_data[cursor - 1]));
359 m_data[cursor - 1].~T();
360 }
361 for (size_type cursor = 0; cursor < count; ++cursor)
362 new (m_data + index + cursor) T(value);
363 m_size += count;
364 return m_data + index;
365 }
366
367 template<Type::SafeValue T>
368 template<std::input_iterator InputIt>
369 Vector<T>::iterator Vector<T>::insert(const_iterator position, InputIt first, InputIt last) {
370 const size_type index = static_cast<size_type>(position - cbegin());
371 Vector copied;
372 for (; first != last; ++first)
373 copied.push_back(static_cast<T>(*first));
374 if (copied.empty())
375 return begin() + static_cast<difference_type>(index);
376 if (m_size + copied.size() > m_capacity)
377 reserve(m_capacity * 2 > m_size + copied.size() ? m_capacity * 2 : m_size + copied.size());
378 const size_type count = copied.size();
379 for (size_type cursor = m_size; cursor > index; --cursor) {
380 new (m_data + cursor + count - 1) T(std::move(m_data[cursor - 1]));
381 m_data[cursor - 1].~T();
382 }
383 for (size_type cursor = 0; cursor < count; ++cursor)
384 new (m_data + index + cursor) T(std::move(copied[cursor]));
385 m_size += count;
386 return m_data + index;
387 }
388
389 template<Type::SafeValue T>
390 Vector<T>::iterator Vector<T>::insert(const_iterator position, std::initializer_list<T> values) {
391 return insert(position, values.begin(), values.end());
392 }
393
394 template<Type::SafeValue T>
395 template<std::ranges::input_range R>
396 Vector<T>::iterator Vector<T>::insert_range(const_iterator position, R&& range) {
397 return insert(position, std::ranges::begin(range), std::ranges::end(range));
398 }
399
400 template<Type::SafeValue T>
401 template<class... Args>
402 Vector<T>::iterator Vector<T>::emplace(const_iterator position, Args&&... args) {
403 const size_type index = static_cast<size_type>(position - m_data);
404 if (m_size == m_capacity)
405 Grow();
406 for (size_type cursor = m_size; cursor > index; --cursor) {
407 new (m_data + cursor) T(std::move(m_data[cursor - 1]));
408 m_data[cursor - 1].~T();
409 }
410 new (m_data + index) T(std::forward<Args>(args)...);
411 ++m_size;
412 return m_data + index;
413 }
414
415 template<Type::SafeValue T>
416 Vector<T>::iterator Vector<T>::erase(const_iterator position) {
417 return erase(position, position + 1);
418 }
419
420 template<Type::SafeValue T>
421 Vector<T>::iterator Vector<T>::erase(const_iterator first, const_iterator last) {
422 const size_type index = static_cast<size_type>(first - m_data);
423 const size_type count = static_cast<size_type>(last - first);
424 for (size_type cursor = 0; cursor < count; ++cursor)
425 m_data[index + cursor].~T();
426 for (size_type cursor = index + count; cursor < m_size; ++cursor) {
427 new (m_data + cursor - count) T(std::move(m_data[cursor]));
428 m_data[cursor].~T();
429 }
430 m_size -= count;
431 return m_data + index;
432 }
433
434 template<Type::SafeValue T>
435 void Vector<T>::assign(size_type count, const T& value) {
436 if (count == 0) {
437 clear();
438 return;
439 }
440 const T copied(value);
441 clear();
442 reserve(count);
443 if constexpr (Type::TriviallyCopyable<T> && Type::TriviallyCopyConstructible<T>) {
444 std::uninitialized_fill_n(m_data, static_cast<std::size_t>(count), copied);
445 m_size = count;
446 }
447 else {
448 for (size_type index = 0; index < count; ++index)
449 push_back(copied);
450 }
451 }
452
453 template<Type::SafeValue T>
454 template<std::input_iterator InputIt>
455 void Vector<T>::assign(InputIt first, InputIt last) {
456 Vector copied;
457 if constexpr (Type::ContiguousIterator<InputIt>
458 && Type::SameAs<std::iter_value_t<InputIt>, T>
459 && Type::ConvertibleTo<std::iter_reference_t<InputIt>, const T&>
460 && Type::TriviallyCopyable<T> && Type::TriviallyCopyConstructible<T>) {
461 if (first != last) {
462 const auto count = static_cast<std::size_t>(last - first);
463 copied.reserve(size_type{count});
464 std::memcpy(copied.m_data, std::to_address(first), count * sizeof(T));
465 copied.m_size = size_type{count};
466 }
467 }
468 else {
469 for (; first != last; ++first)
470 copied.push_back(static_cast<T>(*first));
471 }
472 swap(copied);
473 }
474
475 template<Type::SafeValue T>
476 void Vector<T>::assign(std::initializer_list<T> values) {
477 clear();
478 reserve(values.size());
479 for (const T& value : values)
480 push_back(value);
481 }
482
483 template<Type::SafeValue T>
484 template<std::ranges::input_range R>
485 void Vector<T>::assign_range(R&& range) {
486 assign(std::ranges::begin(range), std::ranges::end(range));
487 }
488
489 template<Type::SafeValue T>
490 void Vector<T>::resize(size_type count) {
491 if (count == m_size)
492 return;
493 if (count < m_size) {
494 erase(m_data + count, end());
495 return;
496 }
497 reserve(count);
498 if constexpr (Type::TriviallyCopyable<T> && Type::TriviallyDefaultConstructible<T>) {
499 std::uninitialized_value_construct_n(m_data + m_size, static_cast<std::size_t>(count - m_size));
500 m_size = count;
501 }
502 else {
503 while (m_size < count)
504 emplace_back();
505 }
506 }
507
508 template<Type::SafeValue T>
509 void Vector<T>::resize(size_type count, const T& value) {
510 if (count == m_size)
511 return;
512 if (count < m_size) {
513 erase(m_data + count, end());
514 return;
515 }
516 const T copied(value);
517 reserve(count);
518 if constexpr (Type::TriviallyCopyable<T> && Type::TriviallyCopyConstructible<T>) {
519 std::uninitialized_fill_n(m_data + m_size, static_cast<std::size_t>(count - m_size), copied);
520 m_size = count;
521 }
522 else {
523 while (m_size < count)
524 push_back(copied);
525 }
526 }
527
528 template<Type::SafeValue T>
529 bool Vector<T>::operator==(const Vector& other) const requires Type::EqualityComparable<T> {
530 if (m_size != other.m_size)
531 return false;
532 for (size_type index = 0; index < m_size; ++index) {
533 if (!(m_data[index] == other.m_data[index]))
534 return false;
535 }
536 return true;
537 }
538
539 template<Type::SafeValue T>
540 STORMBYTE_FORCE_INLINE std::strong_ordering Vector<T>::operator<=>(const Vector& other) const requires requires(const T& left, const T& right) { left < right; } {
541 if (*this < other)
542 return std::strong_ordering::less;
543 if (other < *this)
544 return std::strong_ordering::greater;
545 return std::strong_ordering::equal;
546 }
547
548 template<Type::SafeValue T>
549 bool Vector<T>::operator<(const Vector& other) const requires requires(const T& left, const T& right) { left < right; } {
550 const size_type count = m_size < other.m_size ? m_size : other.m_size;
551 for (size_type index = 0; index < count; ++index) {
552 if (m_data[index] < other.m_data[index])
553 return true;
554 if (other.m_data[index] < m_data[index])
555 return false;
556 }
557 return m_size < other.m_size;
558 }
559
560 template<Type::SafeValue T>
561 bool Vector<T>::operator<=(const Vector& other) const requires requires(const T& left, const T& right) { left < right; } {
562 return !(other < *this);
563 }
564
565 template<Type::SafeValue T>
566 bool Vector<T>::operator>(const Vector& other) const requires requires(const T& left, const T& right) { left < right; } {
567 return other < *this;
568 }
569
570 template<Type::SafeValue T>
571 bool Vector<T>::operator>=(const Vector& other) const requires requires(const T& left, const T& right) { left < right; } {
572 return !(*this < other);
573 }
574
575 template<Type::SafeValue T>
576 T* Vector<T>::Allocate(size_type capacity) {
577 return capacity == 0 ? nullptr : static_cast<T*>(Heap::Allocate(capacity * sizeof(T)));
578 }
579
580 template<Type::SafeValue T>
581 void Vector<T>::Release(T* data, size_type count) noexcept {
582 if (data == nullptr)
583 return;
584 for (size_type index = 0; index < count; ++index)
585 data[index].~T();
586 Heap::Free(data);
587 }
588
589 template<Type::SafeValue T>
590 void Vector<T>::Grow() {
591 reserve(m_capacity == 0 ? Size{1} : m_capacity * 2);
592 }
593 }
594}