StormByte 3.0.0
C++26 foundation of the StormByte suite
Loading...
Searching...
No Matches
deque.hxx
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 <StormByte/size.hxx>
46
47#include <compare>
48#include <cstddef>
49#include <deque>
50#include <initializer_list>
51#include <iterator>
52#include <limits>
53#include <utility>
54
59namespace StormByte {
64 namespace Safe {
70 [[noreturn]] STORMBYTE_PUBLIC void ThrowDequeOutOfBounds(const Size& index);
71
79 template<Type::SafeValue T>
81 public:
82 using value_type = T;
83 using size_type = Size;
84 using difference_type = std::ptrdiff_t;
85 using reference = T&;
86 using const_reference = const T&;
87 using pointer = T*;
88 using const_pointer = const T*;
89 class iterator;
90 class const_iterator;
91 using reverse_iterator = std::reverse_iterator<iterator>;
92 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
93
97 Deque() noexcept;
98
105 Deque(size_type count, const T& value);
106
112 explicit Deque(size_type count);
113
121 template<std::input_iterator InputIt>
122 Deque(InputIt first, InputIt last);
123
129 Deque(std::initializer_list<T> values);
130
136 explicit Deque(const std::deque<T>& values);
137
143 STORMBYTE_FORCE_INLINE explicit Deque(std::deque<T>&& values): Deque() {
144 for (T& value : values)
145 push_back(std::move(value));
146 values.clear();
147 }
148
154 Deque(const Deque& other);
155
160 Deque(Deque&& other) noexcept;
161
165 ~Deque() noexcept;
166
173 Deque& operator=(const Deque& other);
174
180 Deque& operator=(Deque&& other) noexcept;
181
188 Deque& operator=(std::initializer_list<T> values);
189
196 Deque& operator=(const std::deque<T>& values);
197
204 STORMBYTE_FORCE_INLINE Deque& operator=(std::deque<T>&& values) {
205 Deque replacement(std::move(values));
206 swap(replacement);
207 return *this;
208 }
209
216 void assign(size_type count, const T& value);
217
225 template<std::input_iterator InputIt>
226 void assign(InputIt first, InputIt last);
227
233 void assign(std::initializer_list<T> values);
234
241 template<std::ranges::input_range R>
242 void assign_range(R&& range);
243
251
259
266
272 const_reference operator[](size_type index) const noexcept;
273
280
287
294
301
306 iterator begin() noexcept;
307
312 iterator end() noexcept;
313
318 const_iterator begin() const noexcept;
319
324 const_iterator end() const noexcept;
325
330 const_iterator cbegin() const noexcept;
331
336 const_iterator cend() const noexcept;
337
345
353
361
369
375 return rbegin();
376 }
377
383 return rend();
384 }
385
390 bool empty() const noexcept;
391
396 size_type size() const noexcept;
397
403 return std::numeric_limits<size_type>::max() / sizeof(T);
404 }
405
410
414 void clear() noexcept;
415
423 iterator insert(const_iterator position, const T& value);
424
432 iterator insert(const_iterator position, T&& value);
433
442 iterator insert(const_iterator position, size_type count, const T& value);
443
453 template<std::input_iterator InputIt>
454 iterator insert(const_iterator position, InputIt first, InputIt last);
455
463 iterator insert(const_iterator position, std::initializer_list<T> values);
464
473 template<std::ranges::input_range R>
474 iterator insert_range(const_iterator position, R&& range);
475
484 template<typename... Args>
485 iterator emplace(const_iterator position, Args&&... args);
486
492 iterator erase(const_iterator position);
493
500 iterator erase(const_iterator first, const_iterator last);
501
507 void push_back(const T& value);
508
514 void push_back(T&& value);
515
523 template<typename... Args>
524 reference emplace_back(Args&&... args);
525
529 void pop_back();
530
536 void push_front(const T& value);
537
543 void push_front(T&& value);
544
552 template<typename... Args>
553 reference emplace_front(Args&&... args);
554
558 void pop_front();
559
566 template<std::ranges::input_range R>
567 void append_range(R&& range);
568
575 template<std::ranges::input_range R>
576 void prepend_range(R&& range);
577
583 void resize(size_type count);
584
591 void resize(size_type count, const T& value);
592
597 void swap(Deque& other) noexcept;
598
603 STORMBYTE_FORCE_INLINE explicit operator std::deque<T>() const {
604 std::deque<T> out;
605 for (const T& value : *this)
606 out.push_back(value);
607 return out;
608 }
609
610 private:
611 struct Block;
612
618 reference Slot(size_type index) noexcept;
619
625 const_reference Slot(size_type index) const noexcept;
626
631 void EnsureBack();
632
637 void EnsureFront();
638
639 Block* m_map;
640 size_type m_offset;
641 size_type m_size;
642 size_type m_capacity;
643 };
644
652 template<Type::SafeValue T>
653 bool operator==(const Deque<T>& left, const Deque<T>& right);
654
662 template<Type::SafeValue T>
663 STORMBYTE_FORCE_INLINE std::strong_ordering operator<=>(const Deque<T>& left, const Deque<T>& right);
664
671 template<Type::SafeValue T>
672 void swap(Deque<T>& left, Deque<T>& right) noexcept;
673 }
674}
675
695
Double-ended sequence stored on Base's heap.
Definition deque.hxx:80
reference back()
Return the last element.
std::reverse_iterator< const_iterator > const_reverse_iterator
Read-only reverse iterator.
Definition deque.hxx:92
const_reference back() const
Return the last element.
iterator erase(const_iterator position)
Destroy the element at position.
STORMBYTE_FORCE_INLINE const_reverse_iterator rbegin() const noexcept
Return a read-only reverse iterator to the last element.
Definition deque.hxx:358
std::reverse_iterator< iterator > reverse_iterator
Mutable reverse iterator.
Definition deque.hxx:91
void append_range(R &&range)
Append a range.
STORMBYTE_FORCE_INLINE const_reverse_iterator crend() const noexcept
Return the read-only reverse end iterator.
Definition deque.hxx:382
Deque() noexcept
Construct an empty deque.
void push_back(const T &value)
Append a copy.
void assign(InputIt first, InputIt last)
Replace the contents with the range [first, last).
iterator insert_range(const_iterator position, R &&range)
Insert a range before position.
reference emplace_back(Args &&... args)
Construct an element at the back.
T value_type
Element type.
Definition deque.hxx:82
iterator emplace(const_iterator position, Args &&... args)
Construct an element before position.
void pop_front()
Destroy the first element.
Deque(Deque &&other) noexcept
Take the blocks.
T & reference
Mutable element reference.
Definition deque.hxx:85
void assign_range(R &&range)
Replace the contents with a range.
bool empty() const noexcept
Test whether the deque is empty.
const_iterator cend() const noexcept
Return the read-only end iterator.
STORMBYTE_FORCE_INLINE reverse_iterator rend() noexcept
Return the mutable reverse end iterator.
Definition deque.hxx:350
void prepend_range(R &&range)
Prepend a range.
const_iterator cbegin() const noexcept
Return a read-only iterator to the first element.
STORMBYTE_FORCE_INLINE size_type max_size() const noexcept
Return the largest representable element count.
Definition deque.hxx:402
void resize(size_type count)
Change the element count.
reference at(size_type index)
Access an element.
iterator begin() noexcept
Return a mutable iterator to the first element.
void pop_back()
Destroy the last element.
T * pointer
Mutable element pointer.
Definition deque.hxx:87
~Deque() noexcept
Destroy every element and release the blocks.
void clear() noexcept
Destroy every element.
size_type size() const noexcept
Return the element count.
const_reference at(size_type index) const
Access an element.
reference emplace_front(Args &&... args)
Construct an element at the front.
void swap(Deque &other) noexcept
Exchange blocks.
void push_front(const T &value)
Prepend a copy.
const T & const_reference
Read-only element reference.
Definition deque.hxx:86
STORMBYTE_FORCE_INLINE const_reverse_iterator rend() const noexcept
Return the read-only reverse end iterator.
Definition deque.hxx:366
void shrink_to_fit()
Release unused blocks.
void assign(size_type count, const T &value)
Replace the contents with count copies of value.
std::ptrdiff_t difference_type
Iterator distance type.
Definition deque.hxx:84
const T * const_pointer
Read-only element pointer.
Definition deque.hxx:88
reference operator[](size_type index) noexcept
Access an element.
iterator end() noexcept
Return the mutable end iterator.
Size size_type
Element count. Size, not std::size_t.
Definition deque.hxx:83
void assign(std::initializer_list< T > values)
Replace the contents with an initializer list.
iterator insert(const_iterator position, const T &value)
Insert a copy before position.
const_reference front() const
Return the first element.
Deque(const Deque &other)
Copy every element into new Base blocks.
const_reference operator[](size_type index) const noexcept
Access an element.
STORMBYTE_FORCE_INLINE const_reverse_iterator crbegin() const noexcept
Return a read-only reverse iterator to the last element.
Definition deque.hxx:374
reference front()
Return the first element.
STORMBYTE_FORCE_INLINE reverse_iterator rbegin() noexcept
Return a mutable reverse iterator to the last element.
Definition deque.hxx:342
Count of abstract units (uint64_t storage).
Definition size.hxx:107
Private Base heap used by StormByte::Safe::Shared, StormByte::Safe::Unique and StormByte::Safe::Clona...
Owned values that cross a DLL without the caller's CRT.
bool operator==(std::span< const std::byte > bytes, const Binary &data) noexcept
Equality of a span against a sequence.
Definition binary.hxx:770
void ThrowDequeOutOfBounds()
Throw the deque out-of-bounds error from Base.
void swap(Binary &left, Binary &right) noexcept
Exchange two sequences.
Definition binary.hxx:760
STORMBYTE_FORCE_INLINE std::strong_ordering operator<=>(std::span< const std::byte > bytes, const Binary &data) noexcept
Three-way comparison of a span against a sequence.
Definition binary.hxx:790
Root namespace of the StormByte suite.
STL namespace.
#define STORMBYTE_FORCE_INLINE
Definition platform.h:134
Host-width-stable count (uint64_t), implicit only to std::size_t.
#define STORMBYTE_PUBLIC_TYPE
Definition visibility.h:57
#define STORMBYTE_PUBLIC
Definition visibility.h:52