From d866bd4b9fb6d586d0fbe44af9ece7d105b75a0c Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Tue, 12 Nov 2024 16:22:20 -0500 Subject: Integrate the use of std::allocator in dynamic array --- Seminar03/src/dynamic-array/vector/vector.hpp | 234 ++++++++++++-------------- 1 file changed, 110 insertions(+), 124 deletions(-) (limited to 'Seminar03/src/dynamic-array/vector') diff --git a/Seminar03/src/dynamic-array/vector/vector.hpp b/Seminar03/src/dynamic-array/vector/vector.hpp index 5233072..8db5178 100644 --- a/Seminar03/src/dynamic-array/vector/vector.hpp +++ b/Seminar03/src/dynamic-array/vector/vector.hpp @@ -1,14 +1,14 @@ - #pragma once + #include "../iterator/iterator.hpp" -#include +#include namespace Constants { constexpr unsigned GROWTH_FACTOR = 2; } -template +template > class vector { public: @@ -57,22 +57,21 @@ class vector } iterator end() { - return iterator(_data + size()); + return iterator(&_data[size()]); } const_iterator c_begin() const { return const_iterator(_data); } - const_iterator c_end() const { - return const_iterator(_data + size()); + return const_iterator(&_data[size()]); } reverse_iterator rbegin() { - return {_data + size() - 1}; + return {&_data[size() - 1]}; } reverse_iterator rend() @@ -106,46 +105,44 @@ class vector void move(vector&& other); size_t calculate_capacity() const; + Allocator _allocator; + T* _data = nullptr; size_t _size = 0; size_t _capacity = 0; }; // Constructs the container with count copies of elements with default value. -template -vector::vector(size_t count) - : _data(static_cast(operator new(count * sizeof(T)))) +template +vector::vector(size_t count) + : _data(_allocator.allocate(count)) , _size(count) , _capacity(count) { - // default construct all elements - for (size_t i = 0; i < count; i++) - new (&_data[i]) T(); + // Default construct all elements. + for (size_t i = 0; i < size(); i++) + _allocator.construct(&_data[i]); } // Constructs the container with count copies of elements with value initial. -// Why dont we call `new` here? -// When you choose a memory managment strategy its better -// to stick with it for concistency. -template -vector::vector(size_t count, const T& initial) - : _data(static_cast(operator new(count * sizeof(T)))) +template +vector::vector(size_t count, const T& initial) + : _data(_allocator.allocate(count)) , _size(count) , _capacity(count) { - // construct all elements copying initial - for (size_t i = 0; i < count; i++) - new (&_data[i]) T(initial); + for (size_t i = 0; i < size(); i++) + _allocator.construct(&_data[i], initial); } -template -vector::vector(const vector& other) +template +vector::vector(const vector& other) { copy(other); } -template -vector& vector::operator=(const vector& other) +template +vector& vector::operator=(const vector& other) { if (this != &other) { @@ -155,14 +152,14 @@ vector& vector::operator=(const vector& other) return *this; } -template -vector::vector(vector&& other) +template +vector::vector(vector&& other) { move(std::move(other)); } -template -vector& vector::operator=(vector&& other) +template +vector& vector::operator=(vector&& other) { if (this != &other) { @@ -172,39 +169,36 @@ vector& vector::operator=(vector&& other) return *this; } -template -vector::~vector() +template +vector::~vector() { free(); } -template -void vector::copy(const vector& other) +template +void vector::copy(const vector& other) { - // allocate enough memoty - _data = static_cast(operator new(other.capacity() * sizeof(T))); - - // copy construct elements + _data = _allocator.allocate(other.capacity()); + + // Copy construct the new memory for (size_t i = 0; i < other.size(); i++) - new (&_data[i]) T(other[i]); + _allocator.construct(&_data[i], other[i]); _size = other.size(); _capacity = other.capacity(); } -template -void vector::free() +template +void vector::free() { - // call destructor on constructed elements for (size_t i = 0; i < size(); i++) - (_data + i)->~T(); - - // deallocate memory - operator delete(_data, capacity() * sizeof(T)); + _allocator.destroy(&_data[i]); + + _allocator.deallocate(_data, capacity()); } -template -void vector::move(vector&& other) +template +void vector::move(vector&& other) { _size = other.size(); _capacity = other.capacity(); @@ -214,64 +208,58 @@ void vector::move(vector&& other) other._size = other._capacity = 0; } -template -size_t vector::size() const +template +size_t vector::size() const { return _size; } -template -size_t vector::capacity() const +template +size_t vector::capacity() const { return _capacity; } -template -size_t vector::calculate_capacity() const +template +size_t vector::calculate_capacity() const { if (capacity() == 0) return 1; return capacity() * Constants::GROWTH_FACTOR; } -// Resizes the container to contain `n` elements, does nothing if `n` == size(). -// If the current size is greater than `n`, the container is reduced to its first count elements. +// Resizes the container to contain `n` elements, does nothing if `n` == size(). +// If the current size is greater than `n`, the container is reduced to its first count elements. // If the current size is less than `n`, then additional default-inserted elements are appended. -template -void vector::resize(size_t n) +template +void vector::resize(size_t n) { if (n < size()) { - // call destructor on constructed elements for (size_t i = n; i < size(); i++) - (_data + i)->~T(); - + _allocator.destroy(&_data[i]); _size = n; } else if (n > size()) { if (n <= capacity()) { - // default construct elements in range [size(), n) for (size_t i = size(); i < n; i++) - new (&_data[i]) T(); - + _allocator.construct(&_data[i]); + _size = n; } else { - T* new_data = static_cast(operator new(n * sizeof(T))); + T* new_data = _allocator.allocate(n); for (size_t i = 0; i < size(); i++) - { - new (&new_data[i]) T(std::move(_data[i])); - (_data + i)->~T(); - } - + _allocator.construct(new_data, std::move(_data[i])); + for (size_t i = size(); i < n; i++) - new (&new_data[i]) T(); + _allocator.construct(&new_data[i]); - operator delete(_data, capacity() * sizeof(T)); + _allocator.deallocate(_data, capacity()); _data = new_data; _capacity = n; @@ -280,25 +268,22 @@ void vector::resize(size_t n) } } -// Increase the capacity of the vector (the total number -// of elements that the vector can hold without requiring reallocation) +// Increase the capacity of the vector (the total number +// of elements that the vector can hold without requiring reallocation) // to a value that's greater or equal to `n`. If `n` is greater than -// the current capacity(), new storage is allocated, otherwise the function does nothing. -template -void vector::reserve(size_t n) +// the current capacity(), new storage is allocated, otherwise the function does nothing. +template +void vector::reserve(size_t n) { if (n <= capacity()) return; - T* new_data = static_cast(operator new(n * sizeof(T))); + T* new_data = _allocator.allocate(n); for (size_t i = 0; i < size(); i++) - { - new (&new_data[i]) T(std::move(_data[i])); - (_data + i)->~T(); - } + _allocator.construct(&new_data[i], std::move(_data[i])); - operator delete(_data, capacity() * sizeof(T)); + _allocator.deallocate(_data, capacity()); _data = new_data; _capacity = n; @@ -306,54 +291,49 @@ void vector::reserve(size_t n) // Requests the container to reduce its capacity to fit its size. // This may cause a reallocation, but has no effect on the vector size and cannot alter its elements. -template -void vector::shrink_to_fit() +template +void vector::shrink_to_fit() { if (capacity() == size()) return; - T* new_data = static_cast(operator new(size() * sizeof(T))); - + T* new_data = _allocator.allocate(size()); for (size_t i = 0; i < size(); i++) - { - new (&new_data[i]) T(std::move(_data[i])); - (_data + i)->~T(); - } - - operator delete(_data, capacity() * sizeof(T)); + _allocator.construct(new_data + i, std::move(_data[i])); + _allocator.deallocate(_data, capacity()); _capacity = _size; _data = new_data; } -template -void vector::push_back(const T& element) +template +void vector::push_back(const T& element) { if (size() == capacity()) reserve(calculate_capacity()); - new (&_data[_size++]) T(element); + _allocator.construct(_data[_size++], element); } -template -void vector::push_back(T&& element) +template +void vector::push_back(T&& element) { if (size() == capacity()) reserve(calculate_capacity()); - new (&_data[_size++]) T(std::move(element)); + _allocator.construct(&_data[_size++], std::move(element)); } // Erases the specified elements from the container. -template -void vector::erase(const_iterator position) +template +void vector::erase(const_iterator position) { erase(position, position + 1); } // Erases the specified range from the container. -template -void vector::erase(const_iterator first, const_iterator last) +template +void vector::erase(const_iterator first, const_iterator last) { int deleted_count = last - first; @@ -365,20 +345,24 @@ void vector::erase(const_iterator first, const_iterator last) if (last != c_end()) { + size_t construct_idx = begin_offset; for (size_t i = end_offset; i < size(); i++) - new (&_data[begin_offset++]) T(std::move(_data[i])); + { + _allocator.construct(&_data[construct_idx], std::move(_data[i])); + ++construct_idx; + } } for (size_t i = end_offset; i < size(); i++) - (_data + i)->~T(); - + _allocator.destroy(&_data[i]); + _size -= deleted_count; } // Removes the last element of the container. // Exceptions: Throws nothing. -template -void vector::pop_back() +template +void vector::pop_back() { if (empty()) return; @@ -386,47 +370,49 @@ void vector::pop_back() erase(--end()); } -// Appends a new element to the end of the container. +// Appends a new element to the end of the container. // The element is constructed through placement-new in-place. -template +template template -void vector::emplace_back(Args&&... args) +void vector::emplace_back(Args&&... args) { if (size() == capacity()) reserve(calculate_capacity()); - new (&_data[_size++]) T(std::forward(args)...); + _allocator.construct(&_data[_size++], std::forward(args)...); } -template -T& vector::operator[](size_t idx) +template +T& vector::operator[](size_t idx) { return _data[idx]; } -template -const T& vector::operator[](size_t idx) const +template +const T& vector::operator[](size_t idx) const { return _data[idx]; } -template -T* vector::data() +template +T* vector::data() { return _data; } -template -void vector::clear() +template +void vector::clear() { for (size_t i = 0; i < size(); i++) - (_data + i)->~T(); - + { + _allocator.destroy(&_data[i]); + } + _size = 0; } -template -bool vector::empty() const +template +bool vector::empty() const { return (size() == 0); } \ No newline at end of file -- cgit v1.3.1-23-gd82d