18#include <initializer_list>
24#include "pw_allocator/allocator.h"
25#include "pw_assert/assert.h"
26#include "pw_containers/internal/count_and_capacity.h"
27#include "pw_containers/internal/generic_deque.h"
28#include "pw_numeric/saturating_arithmetic.h"
51template <
typename ValueType,
typename SizeType = u
int16_t>
53 DynamicDeque<ValueType, SizeType>,
55 containers::internal::CountAndCapacity<SizeType>> {
60 containers::internal::CountAndCapacity<SizeType>>;
63 using typename Base::const_iterator;
64 using typename Base::const_pointer;
65 using typename Base::const_reference;
66 using typename Base::difference_type;
67 using typename Base::iterator;
68 using typename Base::pointer;
69 using typename Base::reference;
70 using typename Base::size_type;
71 using typename Base::value_type;
80 :
Base(0), allocator_(&allocator), buffer_(
nullptr) {}
89 : allocator_(other.allocator_), buffer_(other.buffer_) {
90 other.buffer_ =
nullptr;
91 Base::MoveAssignIndices(other);
101 using Base::try_emplace_back;
102 using Base::try_emplace_front;
104 using Base::try_push_back;
105 using Base::try_push_front;
106 using Base::try_resize;
111 template <
typename InputIt,
112 typename = containers::internal::EnableIfInputIterator<InputIt>>
113 iterator insert(const_iterator pos, InputIt first, InputIt last);
115 iterator insert(const_iterator pos,
const value_type& value) {
119 iterator insert(const_iterator pos, value_type&& value) {
123 iterator insert(const_iterator pos,
125 const value_type& value) {
129 iterator insert(const_iterator pos, std::initializer_list<value_type> ilist) {
158 return new_capacity <=
Base::capacity() || IncreaseCapacity(new_capacity);
169 constexpr size_type max_size() const noexcept {
170 return std::numeric_limits<size_type>::max();
178 Base::SwapIndices(other);
179 std::swap(allocator_, other.allocator_);
180 std::swap(buffer_, other.buffer_);
186 template <
typename,
typename>
189 static constexpr bool kFixedCapacity =
false;
191 pointer data() {
return std::launder(
reinterpret_cast<pointer
>(buffer_)); }
192 const_pointer data()
const {
193 return std::launder(
reinterpret_cast<const_pointer
>(buffer_));
196 [[nodiscard]]
bool IncreaseCapacity(size_type new_capacity);
198 size_type GetNewCapacity(
const size_type new_size) {
201 return std::max(size_type{4 *
sizeof(
void*) /
sizeof(value_type)},
208 bool ReallocateBuffer(size_type new_capacity);
210 Allocator* allocator_;
214template <
typename ValueType,
typename SizeType>
215DynamicDeque<ValueType, SizeType>& DynamicDeque<ValueType, SizeType>::operator=(
216 DynamicDeque&& other)
noexcept {
218 allocator_->Deallocate(buffer_);
220 allocator_ = other.allocator_;
221 buffer_ = other.buffer_;
222 other.buffer_ =
nullptr;
224 Base::MoveAssignIndices(other);
228template <
typename ValueType,
typename SizeType>
229DynamicDeque<ValueType, SizeType>::~DynamicDeque() {
231 allocator_->Deallocate(buffer_);
234template <
typename ValueType,
typename SizeType>
236 return new_capacity <= Base::capacity() ||
237 IncreaseCapacity(GetNewCapacity(new_capacity)) ||
238 IncreaseCapacity(new_capacity);
241template <
typename ValueType,
typename SizeType>
243 size_type new_capacity) {
245 if (buffer_ !=
nullptr && Base::CanExtendBuffer() &&
246 allocator_->Resize(buffer_, new_capacity *
sizeof(value_type))) {
247 Base::HandleExtendedBuffer(new_capacity);
252 return ReallocateBuffer(new_capacity);
255template <
typename ValueType,
typename SizeType>
257 if (Base::size() == Base::capacity()) {
262 allocator_->Deallocate(buffer_);
264 Base::HandleShrunkBuffer(0);
272 if (Base::CanShrinkBuffer() &&
273 allocator_->Resize(buffer_, Base::size() *
sizeof(value_type))) {
274 Base::HandleShrunkBuffer(Base::size());
276 ReallocateBuffer(Base::size());
280template <
typename ValueType,
typename SizeType>
282 size_type new_capacity) {
283 std::byte* new_buffer =
static_cast<std::byte*
>(
284 allocator_->Allocate(allocator::Layout::Of<value_type[]>(new_capacity)));
285 if (new_buffer ==
nullptr) {
289 pointer dest = std::launder(
reinterpret_cast<pointer
>(new_buffer));
290 auto [data_1, data_2] = Base::contiguous_data();
292 if constexpr (std::is_move_constructible_v<value_type>) {
293 dest = std::uninitialized_move(data_1.begin(), data_1.end(), dest);
294 std::uninitialized_move(data_2.begin(), data_2.end(), dest);
296 dest = std::uninitialized_copy(data_1.begin(), data_1.end(), dest);
297 std::uninitialized_copy(data_2.begin(), data_2.end(), dest);
300 std::destroy(data_1.begin(), data_1.end());
301 std::destroy(data_2.begin(), data_2.end());
303 allocator_->Deallocate(buffer_);
304 buffer_ = new_buffer;
306 Base::HandleNewBuffer(new_capacity);
310template <
typename ValueType,
typename SizeType>
311template <
typename InputIt,
typename>
312typename DynamicDeque<ValueType, SizeType>::iterator
313DynamicDeque<ValueType, SizeType>::insert(const_iterator pos,
317 if constexpr (std::is_same_v<std::input_iterator_tag,
318 typename std::iterator_traits<
319 InputIt>::iterator_category>) {
323 DynamicDeque temp(*allocator_);
324 temp.assign(first, last);
325 return Base::insert(pos,
326 std::make_move_iterator(temp.data()),
327 std::make_move_iterator(temp.data() + temp.size()));
329 return Base::insert(pos, first, last);
Definition: allocator.h:34
Definition: dynamic_deque.h:55
void reserve(size_type new_capacity)
Increases capacity() to at least new_capacity. Crashes on failure.
Definition: dynamic_deque.h:146
void reserve_exact(size_type new_capacity)
Increases capacity() to exactly new_capacity. Crashes on failure.
Definition: dynamic_deque.h:162
constexpr DynamicDeque(DynamicDeque &&other) noexcept
Definition: dynamic_deque.h:88
void swap(DynamicDeque &other) noexcept
Swaps the contents of two deques. No allocations occur.
Definition: dynamic_deque.h:177
bool try_reserve(size_type new_capacity)
Definition: dynamic_deque.h:235
void shrink_to_fit()
Attempts to reduce capacity() to size(). Not guaranteed to succeed.
Definition: dynamic_deque.h:256
constexpr allocator_type & get_allocator() const
Returns the deque's allocator.
Definition: dynamic_deque.h:174
bool try_reserve_exact(size_type new_capacity)
Definition: dynamic_deque.h:157
constexpr DynamicDeque(Allocator &allocator) noexcept
Definition: dynamic_deque.h:79
Definition: dynamic_vector.h:48
Definition: generic_deque.h:189
bool try_assign(size_type count, const value_type &value)
Definition: generic_deque.h:612
iterator insert(const_iterator pos, const value_type &value)
Definition: generic_deque.h:364
std::optional< iterator > try_emplace(const_iterator pos, Args &&... args)
constexpr size_type capacity() const noexcept
Returns the maximum number of elements in the deque.
Definition: generic_deque.h:63
std::optional< iterator > try_insert(const_iterator pos, const value_type &value)
Definition: generic_deque.h:474
Provides basic helpers for reading and writing UTF-8 encoded strings.
Definition: alignment.h:27
constexpr T mul_sat(T lhs, T rhs) noexcept
Definition: saturating_arithmetic.h:71