From df74c873bc11ad90fb26e582c7be0ed092228661 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Fri, 25 Oct 2024 18:04:36 -0400 Subject: Add sem03 --- .../examples/placement-new-memory-strategy.cpp | 27 ++ .../dynamic-array/examples/variadic-templates.cpp | 61 +++ Seminar03/src/dynamic-array/iterator/iterator.hpp | 205 ++++++++++ Seminar03/src/dynamic-array/tests.cpp | 322 +++++++++++++++ .../dynamic-array/vector-allocator/allocator.hpp | 104 +++++ .../src/dynamic-array/vector-allocator/vector.hpp | 392 +++++++++++++++++++ Seminar03/src/dynamic-array/vector/vector.hpp | 432 +++++++++++++++++++++ 7 files changed, 1543 insertions(+) create mode 100644 Seminar03/src/dynamic-array/examples/placement-new-memory-strategy.cpp create mode 100644 Seminar03/src/dynamic-array/examples/variadic-templates.cpp create mode 100644 Seminar03/src/dynamic-array/iterator/iterator.hpp create mode 100644 Seminar03/src/dynamic-array/tests.cpp create mode 100644 Seminar03/src/dynamic-array/vector-allocator/allocator.hpp create mode 100644 Seminar03/src/dynamic-array/vector-allocator/vector.hpp create mode 100644 Seminar03/src/dynamic-array/vector/vector.hpp (limited to 'Seminar03/src/dynamic-array') diff --git a/Seminar03/src/dynamic-array/examples/placement-new-memory-strategy.cpp b/Seminar03/src/dynamic-array/examples/placement-new-memory-strategy.cpp new file mode 100644 index 0000000..693b95c --- /dev/null +++ b/Seminar03/src/dynamic-array/examples/placement-new-memory-strategy.cpp @@ -0,0 +1,27 @@ +#include + +struct E +{ + E() + { + std::cout << "constr" << std::endl; + } + + ~E() + { + std::cout << "destr" << std::endl; + } +}; + +int main() +{ + std::cout << "operator new called" << std::endl; + E* e = static_cast(operator new(sizeof(E))); + std::cout << "placement new called" << std::endl; + new (e) E(); + + std::cout << "destructor manually called" << std::endl; + e->~E(); + std::cout << "operator delete called" << std::endl; + operator delete(e, sizeof(E)); +} \ No newline at end of file diff --git a/Seminar03/src/dynamic-array/examples/variadic-templates.cpp b/Seminar03/src/dynamic-array/examples/variadic-templates.cpp new file mode 100644 index 0000000..291d81a --- /dev/null +++ b/Seminar03/src/dynamic-array/examples/variadic-templates.cpp @@ -0,0 +1,61 @@ +#include + +// std::forward example - preserve the value category (lvalue or rvalue) +void f(const int& x) +{ + std::cout << "lvalue" << std::endl; +} + +void f(const int&& x) +{ + std::cout << "rvalue" << std::endl; +} + +template +void g(T&& x) +{ + f(std::forward(x)); +} + +struct printer +{ + static void print() + { + std::cout << std::endl; + } + + template + static void print(const T& first, const Args&... args) + { + std::cout << first << " "; + print(std::forward(args)...); + } +}; + +struct Entity +{ + int x; + friend std::ostream& operator<<(std::ostream& os, const Entity& e); + + Entity(int x_) : x(x_) {} + + Entity(Entity&) + { + std::cout << "Copied " << x << std::endl; + } +}; + +std::ostream& operator<<(std::ostream& os, const Entity& e) +{ + os << e.x; + return os; +} + +int main() +{ + int x = 10; + g(x); + + g(std::move(x)); + +} \ No newline at end of file diff --git a/Seminar03/src/dynamic-array/iterator/iterator.hpp b/Seminar03/src/dynamic-array/iterator/iterator.hpp new file mode 100644 index 0000000..4086bf7 --- /dev/null +++ b/Seminar03/src/dynamic-array/iterator/iterator.hpp @@ -0,0 +1,205 @@ +#pragma once +#include + +template +class const_vector_iterator +{ + public: + const_vector_iterator(T* passedVal) + : memPointer{passedVal} + {} + const_vector_iterator(T* passedVal, size_t _push) + : memPointer{passedVal + _push} + {} + + const_vector_iterator operator+(int off) const + { + return {memPointer + off}; + } + + const_vector_iterator operator-(int off) const + { + return {memPointer - off}; + } + + int operator-(const_vector_iterator other) const + { + return memPointer - other.memPointer; + } + + const T* operator->() const noexcept + { + return memPointer; + } + + T& operator*() const noexcept + { + return *(memPointer); + } + + bool operator==(const const_vector_iterator& it) const + { + return (memPointer == it.memPointer); + } + + bool operator!=(const const_vector_iterator& it) const + { + return !(memPointer == it.memPointer); + } + + private: + T* memPointer; +}; + +template +class vector_iterator +{ + public: + vector_iterator(T* passedVal) + : memPointer{passedVal} {}; + vector_iterator(T* passedVal, size_t _push) + : memPointer{passedVal + _push} {}; + + vector_iterator& operator++() + { + memPointer++; + return *this; + } + + vector_iterator operator++(int) const + { + vector_iterator it = *this; + ++(*this); + return it; + } + + vector_iterator& operator--() + { + memPointer--; + return *this; + } + + vector_iterator operator--(int) const + { + vector_iterator it = *this; + --(*this); + return it; + } + + operator const_vector_iterator() const + { + return const_vector_iterator(memPointer); + } + + vector_iterator operator+(int off) const + { + return {memPointer + off}; + } + + vector_iterator operator-(int off) const + { + return {memPointer - off}; + } + + T* operator->() + { + return memPointer; + } + + const T* operator->() const + { + return memPointer; + } + + T& operator*() + { + return *(memPointer); + } + + bool operator==(const vector_iterator& it) const + { + return (memPointer == it.memPointer); + } + + bool operator!=(const vector_iterator& it) const + { + return !(memPointer == it.memPointer); + } + + private: + T* memPointer; +}; + +template +class reverse_vector_iterator +{ + public: + reverse_vector_iterator(T* passedVal) + : memPointer{passedVal} {}; + reverse_vector_iterator(T* passedVal, size_t _push) + : memPointer{passedVal + _push} {}; + + reverse_vector_iterator& operator++() + { + memPointer--; + return *this; + } + + reverse_vector_iterator operator++(int) const + { + reverse_vector_iterator it = *this; + ++(*this); + return it; + } + + reverse_vector_iterator& operator--() + { + memPointer++; + return *this; + } + + reverse_vector_iterator operator--(int) const + { + reverse_vector_iterator it = *this; + --(*this); + return it; + } + + reverse_vector_iterator operator+(int off) const + { + return {memPointer - off}; + } + + reverse_vector_iterator operator-(int off) const + { + return {memPointer + off}; + } + + T* operator->() + { + return memPointer; + } + + const T* operator->() const + { + return memPointer; + } + + T& operator*() + { + return *(memPointer); + } + + bool operator==(const reverse_vector_iterator& it) const + { + return (memPointer == it.memPointer); + } + + bool operator!=(const reverse_vector_iterator& it) const + { + return !(memPointer == it.memPointer); + } + + private: + T* memPointer; +}; \ No newline at end of file diff --git a/Seminar03/src/dynamic-array/tests.cpp b/Seminar03/src/dynamic-array/tests.cpp new file mode 100644 index 0000000..0d30813 --- /dev/null +++ b/Seminar03/src/dynamic-array/tests.cpp @@ -0,0 +1,322 @@ +#define TEST_DIR_VECTOR_ALLOC "vector-allocator/vector.hpp" +#define TEST_DIR_VECTOR "vector/vector.hpp" + +#include TEST_DIR_VECTOR +#include +#include +#include +#include +#include +#include + +struct Entity +{ + int x; + + Entity(int _x) + : x(_x) + {} + Entity() + : x() + {} + + ~Entity() + { + x = -1; + } +}; + +void tests_default() +{ + vector v; + + v.push_back(Entity(1)); + assert(v.back().x == 1); + assert(v.size() == 1); + assert(v.capacity() == 1); + + v.emplace_back(2); + assert(v.back().x == 2); + assert(v.size() == 2); + assert(v.capacity() == 2); + + for (int i = 3; i <= 10; i++) + v.emplace_back(i); + + for (int i = 1; i <= 10; i++) + assert(v[i - 1].x == i); + + for (int i = 1; i <= 10; i++) + assert((v.begin() + (i - 1))->x == i); + + assert(v.size() == 10); + assert(v.capacity() == 16); + + int cnt = 1; + for (auto e : v) + assert(e.x == cnt++); +} + +void test_resize_reserve() +{ + std::vector v; + vector v1; + + assert(v1.size() == v.size() && v1.capacity() == v.capacity()); + assert(v.data() == nullptr && v1.data() == nullptr); + + v.reserve(10); + v1.reserve(10); + assert(v1.size() == v.size() && v1.capacity() == v.capacity()); + + v.reserve(20); + v1.reserve(20); + assert(v1.size() == v.size() && v1.capacity() == v.capacity()); + + v.reserve(10); + v1.reserve(10); + assert(v1.size() == v.size() && v1.capacity() == v.capacity()); + + v.shrink_to_fit(); + v1.shrink_to_fit(); + assert(v1.size() == v.size() && v1.capacity() == v.capacity()); + + v.resize(10); + v1.resize(10); + assert(v1.size() == v.size() && v1.capacity() == v.capacity()); + + v.resize(20); + v1.resize(20); + assert(v1.size() == v.size() && v1.capacity() == v.capacity()); + + for (size_t i = 0; i < v1.size(); i++) + v1[i].x = i; + + v.resize(10); + v1.resize(10); + + for (size_t i = 0; i < v1.size(); i++) + assert(v1[i].x == i); + + assert(v1.size() == v.size() && v1.capacity() == v.capacity()); + assert(v1.front().x == 0 && v1.back().x == 9); + + v.push_back(1); + v.push_back(2); + v.emplace_back(3); + + v1.push_back(1); + v1.push_back(2); + v1.emplace_back(3); + + v.shrink_to_fit(); + v1.shrink_to_fit(); + assert(v1.size() == v.size() && v1.capacity() == v.capacity()); +} + +void push_pop_tests() +{ + vector v; + + for (size_t i = 0; i < 100; i++) + v.push_back(i); + + int j = 100; + while (!v.empty()) + { + assert(v.back() == --j); + v.pop_back(); + } +} + +void erase_tests() +{ + vector v; + for (size_t i = 1; i <= 100; i++) + { + v.push_back(i); + } + + v.erase(v.begin(), v.begin() + 49); + + int j = 50; + + for (auto x : v) + { + assert(x == j++); + } + + assert(v.size() == 51); + + v.erase(v.begin()); + assert(v.front() == 51 && v.size() == 50); + + v.erase(v.begin() + 10, v.begin() + 20); + assert(v.size() == 40); + + for (auto x : v) + { + assert(!(x >= 61 && x <= 70)); + } + + v.erase(v.begin(), v.end()); + assert(v.empty()); +} + +int called = 0; + +struct constructor_called +{ + constructor_called() + { + ++called; + } +}; + +void constructor_tests() +{ + // Default construct + vector start; + assert(start.size() == 0 && start.capacity() == 0 && start.data() == nullptr); + start.push_back(0); + assert(start.size() == 1 && start.capacity() == 1 && start.data() != nullptr); + start.pop_back(); + assert(start.size() == 0 && start.capacity() == 1 && start.data() != nullptr); + + size_t length = 200; + + for (size_t i = 0; i < length; i++) + start.push_back(rand() % 1000); + + // Copy constructor tests + vector copy(start); + for (size_t i = 0; i < length; i++) + assert(copy[i] == start[i]); + + // Move constructor tests + vector moved(std::move(copy)); + assert(copy.data() == nullptr && copy.size() == 0 && copy.capacity() == 0); + + for (size_t i = 0; i < length; i++) + assert(moved[i] == start[i]); + + // Parameter constructors + std::vector v(10); + assert(called == 10); + v.reserve(20); + assert(called == 10); + + std::vector v2(20, 20); + for (const auto& e : v2) + { + assert(e.x == 20); + } +} + +void push_back_tests() +{ + vector v; + + for (size_t i = 0; i < 1000; i++) + v.push_back(i); + + assert(v.size() == 1000); + + for (int i = 0; i < 1000; i++) + assert(v[i] == i); +} + +void erase_test() +{ + vector v; + + for (size_t i = 0; i < 1001; i++) + v.push_back(i); + + auto it = v.begin(); + + while (it != v.end()) + { + if ((*it % 2) == 0) + { + v.erase(it); + it = v.begin(); + } + ++it; + } + + for (auto x : v) + assert(x % 2); + + assert(v.size() == 500); +} + +void iterator_tests() +{ + vector v; + for (size_t i = 0; i < 100; i++) + { + v.push_back(i); + } + + for (size_t i = 0; i < 100; i++) + { + assert(*(v.begin() + i) == i); + assert(*(v.end() - i - 1) == 100 - i - 1); + + if (i) + assert(v.begin() != (v.begin() + i) && (v.begin() + i) != v.end()); + } + + auto it = v.begin(); + assert(*it == 0); + vector v1; + v1.emplace_back(1); + v1.emplace_back(2); + + assert((++v1.begin())->x == 2); + assert(++(++v1.begin()) == v1.end()); + assert(--v1.end() == ++v1.begin()); + + int j = 99; + for (auto rit = v.rbegin(); rit != v.rend(); ++rit) + { + assert(*rit == j--); + } + + assert((v1.rbegin())->x == 2); + assert((++v1.rbegin())->x == 1); +} + +// Still a test with more complex objects +void run_all() +{ + vector v; + vector> tests; + + tests.push_back(constructor_tests); + tests.push_back(tests_default); + tests.push_back(test_resize_reserve); + tests.push_back(push_back_tests); + tests.push_back(push_pop_tests); + tests.push_back(erase_tests); + tests.push_back(erase_test); + tests.push_back(iterator_tests); + + for (const auto& func : tests) + { + v.emplace_back(func); + } + + for (auto& c_thread : v) + { + c_thread.join(); + } +} + +int main() +{ + std::cout << "Start tests...\n"; + run_all(); + std::cout << "No assertions failed!"; +} \ No newline at end of file diff --git a/Seminar03/src/dynamic-array/vector-allocator/allocator.hpp b/Seminar03/src/dynamic-array/vector-allocator/allocator.hpp new file mode 100644 index 0000000..d38587e --- /dev/null +++ b/Seminar03/src/dynamic-array/vector-allocator/allocator.hpp @@ -0,0 +1,104 @@ +#pragma once +#include +#include + +template +class allocator +{ +public: + T *allocate(size_t n) const; + void deallocate(T *ptr, size_t n) const; + + template + void construct(T *ptr, Args &&...args) const; + void destroy(T *ptr) const; + + void copy_range(T* begin_destination, T* begin_source, T* end_source) const; + void move_range(T *begin_destination, T *begin_source, T *end_source) const; + + template + void construct_range(T *begin, T *end, Args &&...args) const; + void destroy_range(T *begin, T *end) const; +}; + +// allocates uninitialized storage +template +T *allocator::allocate(size_t n) const +{ + if(n == 0) + return nullptr; + + return static_cast(::operator new(n * sizeof(T))); +} + +// Deallocates the storage referenced by the pointer ptr, +// which must be a pointer obtained by an earlier call to allocate() +template +void allocator::deallocate(T *ptr, size_t n) const +{ + if (!n) + return; + + ::operator delete(ptr, n * sizeof(T)); +} + +// destructs an object in allocated storage +template +void allocator::destroy(T *ptr) const +{ + ptr->~T(); +} + +template +template +void allocator::construct(T *ptr, Args &&...args) const +{ + ::new (ptr) T(std::forward(args)...); +} + +// constructs an object in allocated storage +template +template +void allocator::construct_range(T *begin, T *end, Args &&...args) const +{ + while (begin != end) + { + construct(begin, std::forward(args)...); + ++begin; + } +} + +// calls destroy on a range. +template +void allocator::destroy_range(T *begin, T *end) const +{ + while (begin != end) + { + destroy(begin); + ++begin; + } +} + +// calls construct on a range. +template +void allocator::copy_range(T* begin_destination, T* begin_source, T* end_source) const +{ + while(begin_source != end_source) + { + construct(begin_destination, *begin_source); + ++begin_source; + ++begin_destination; + } +} + +// calls construct using std::move on a range. +template +void allocator::move_range(T *begin_destination, T *begin_source, T *end_source) const +{ + while (begin_source != end_source) + { + construct(begin_destination, std::move(*begin_source)); + ++begin_source; + ++begin_destination; + } +} \ No newline at end of file diff --git a/Seminar03/src/dynamic-array/vector-allocator/vector.hpp b/Seminar03/src/dynamic-array/vector-allocator/vector.hpp new file mode 100644 index 0000000..7d28c35 --- /dev/null +++ b/Seminar03/src/dynamic-array/vector-allocator/vector.hpp @@ -0,0 +1,392 @@ +#pragma once +#include "../iterator/iterator.hpp" +#include "allocator.hpp" + +namespace Constants +{ +constexpr unsigned GROWTH_FACTOR = 2; +} + +template > +class vector +{ + public: + using iterator = vector_iterator; + using const_iterator = const_vector_iterator; + using reverse_iterator = reverse_vector_iterator; + + vector() = default; + explicit vector(size_t count); + vector(size_t count, const T& initial); + + vector(const vector& other); + vector& operator=(const vector& other); + + vector(vector&& oher); + vector& operator=(vector&& other); + + void push_back(const T& element); + void push_back(T&& element); + void pop_back(); + + void erase(const_iterator position); + void erase(const_iterator first, const_iterator last); + + void clear(); + + template + void emplace_back(Args&&... args); + + T& operator[](size_t idx); + const T& operator[](size_t idx) const; + + T* data(); + + void resize(size_t n); + void reserve(size_t n); + void shrink_to_fit(); + + size_t size() const; + size_t capacity() const; + bool empty() const; + + iterator begin() + { + return iterator(_data); + } + iterator end() + { + return iterator(_data + size()); + } + + const_iterator c_begin() const + { + return const_iterator(_data); + } + const_iterator c_end() const + { + return const_iterator(_data + size()); + } + + reverse_iterator rbegin() + { + return {_data + size() - 1}; + } + + reverse_iterator rend() + { + return {_data - 1}; + } + + const T& back() const + { + return _data[size() - 1]; + } + T& back() + { + return _data[size() - 1]; + } + + const T& front() const + { + return _data[0]; + } + T& front() + { + return _data[0]; + } + + ~vector(); + + private: + void copy(const vector& other); + void free(); + 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(_allocator.allocate(count)) + , _size(count) + , _capacity(count) +{ + _allocator.construct_range(_data, _data + _size); +} + +// Constructs the container with count copies of elements with value initial. +template +vector::vector(size_t count, const T& initial) + : _data(_allocator.allocate(count)) + , _size(count) + , _capacity(count) +{ + _allocator.construct_range(_data, _data + _size, initial); +} + +template +vector::vector(const vector& other) +{ + copy(other); +} + +template +vector& vector::operator=(const vector& other) +{ + if (this != &other) + { + free(); + copy(other); + } + return *this; +} + +template +vector::vector(vector&& other) +{ + move(std::move(other)); +} + +template +vector& vector::operator=(vector&& other) +{ + if (this != &other) + { + free(); + move(std::move(other)); + } + return *this; +} + +template +vector::~vector() +{ + free(); +} + +template +void vector::copy(const vector& other) +{ + _data = _allocator.allocate(other.capacity()); + _allocator.copy_range(_data, other._data, other._data + other.size()); + + _size = other.size(); + _capacity = other.capacity(); +} + +template +void vector::free() +{ + _allocator.destroy_range(_data, _data + size()); + _allocator.deallocate(_data, capacity()); +} + +template +void vector::move(vector&& other) +{ + _size = other.size(); + _capacity = other.capacity(); + _data = other._data; + + other._data = nullptr; + other._size = other._capacity = 0; +} + +template +size_t vector::size() const +{ + return _size; +} + +template +size_t vector::capacity() const +{ + return _capacity; +} + +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. +// If the current size is less than `n`, then additional default-inserted elements are appended. +template +void vector::resize(size_t n) +{ + if (n < size()) + { + _allocator.destroy_range(_data + n, _data + size()); + _size = n; + } + else if (n > size()) + { + if (n <= capacity()) + { + _allocator.construct_range(_data + size(), _data + n); + _size = n; + } + else + { + T* new_data = _allocator.allocate(n); + + // TODO: what if range is not movable? + // _allocator.copy_range(new_data, _data, _data + size()); + _allocator.move_range(new_data, _data, _data + size()); + _allocator.construct_range(new_data + size(), new_data + n); + + _allocator.deallocate(_data, capacity()); + + _data = new_data; + _capacity = n; + _size = n; + } + } +} + +// 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) +{ + if (n <= capacity()) + return; + + T* new_data = _allocator.allocate(n); + + // TODO: what if range is not movable? + _allocator.move_range(new_data, _data, _data + size()); + + _allocator.deallocate(_data, capacity()); + + _data = new_data; + _capacity = 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() +{ + if (capacity() == size()) + return; + + T* new_data = _allocator.allocate(size()); + _allocator.move_range(new_data, _data, _data + size()); + _allocator.deallocate(_data, capacity()); + + _capacity = _size; + _data = new_data; +} + +template +void vector::push_back(const T& element) +{ + if (size() == capacity()) + reserve(calculate_capacity()); + + _allocator.construct(_data[_size++], element); +} + +template +void vector::push_back(T&& element) +{ + if (size() == capacity()) + reserve(calculate_capacity()); + + _allocator.construct(&_data[_size++], std::move(element)); +} + +// Erases the specified elements from the container. +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) +{ + int deleted_count = last - first; + + if (deleted_count <= 0) + return; + + int begin_offset = first - begin(); + int end_offset = last - begin(); + + if (last != c_end()) + { + _allocator.move_range(_data + begin_offset, _data + end_offset, _data + size()); + } + _allocator.destroy_range(_data + end_offset, _data + size()); + _size -= deleted_count; +} + +// Removes the last element of the container. +// Exceptions: Throws nothing. +template +void vector::pop_back() +{ + if (empty()) + return; + + erase(--end()); +} + +// Appends a new element to the end of the container. +// The element is constructed through placement-new in-place. +template +template +void vector::emplace_back(Args&&... args) +{ + if (size() == capacity()) + reserve(calculate_capacity()); + + _allocator.construct(&_data[_size++], std::forward(args)...); +} + +template +T& vector::operator[](size_t idx) +{ + return _data[idx]; +} + +template +const T& vector::operator[](size_t idx) const +{ + return _data[idx]; +} + +template +T* vector::data() +{ + return _data; +} + +template +void vector::clear() +{ + _allocator.destroy_range(_data, _data + size()); + _size = 0; +} + +template +bool vector::empty() const +{ + return (size() == 0); +} \ No newline at end of file diff --git a/Seminar03/src/dynamic-array/vector/vector.hpp b/Seminar03/src/dynamic-array/vector/vector.hpp new file mode 100644 index 0000000..5233072 --- /dev/null +++ b/Seminar03/src/dynamic-array/vector/vector.hpp @@ -0,0 +1,432 @@ + +#pragma once +#include "../iterator/iterator.hpp" +#include + +namespace Constants +{ +constexpr unsigned GROWTH_FACTOR = 2; +} + +template +class vector +{ + public: + using iterator = vector_iterator; + using const_iterator = const_vector_iterator; + using reverse_iterator = reverse_vector_iterator; + + vector() = default; + explicit vector(size_t count); + vector(size_t count, const T& initial); + + vector(const vector& other); + vector& operator=(const vector& other); + + vector(vector&& oher); + vector& operator=(vector&& other); + + void push_back(const T& element); + void push_back(T&& element); + void pop_back(); + + void erase(const_iterator position); + void erase(const_iterator first, const_iterator last); + + void clear(); + + template + void emplace_back(Args&&... args); + + T& operator[](size_t idx); + const T& operator[](size_t idx) const; + + T* data(); + + void resize(size_t n); + void reserve(size_t n); + void shrink_to_fit(); + + size_t size() const; + size_t capacity() const; + bool empty() const; + + iterator begin() + { + return iterator(_data); + } + iterator end() + { + return iterator(_data + size()); + } + + const_iterator c_begin() const + { + return const_iterator(_data); + } + + const_iterator c_end() const + { + return const_iterator(_data + size()); + } + + reverse_iterator rbegin() + { + return {_data + size() - 1}; + } + + reverse_iterator rend() + { + return {_data - 1}; + } + + const T& back() const + { + return _data[size() - 1]; + } + T& back() + { + return _data[size() - 1]; + } + + const T& front() const + { + return _data[0]; + } + T& front() + { + return _data[0]; + } + + ~vector(); + + private: + void copy(const vector& other); + void free(); + void move(vector&& other); + size_t calculate_capacity() const; + + 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)))) + , _size(count) + , _capacity(count) +{ + // default construct all elements + for (size_t i = 0; i < count; i++) + new (&_data[i]) T(); +} + +// 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)))) + , _size(count) + , _capacity(count) +{ + // construct all elements copying initial + for (size_t i = 0; i < count; i++) + new (&_data[i]) T(initial); +} + +template +vector::vector(const vector& other) +{ + copy(other); +} + +template +vector& vector::operator=(const vector& other) +{ + if (this != &other) + { + free(); + copy(other); + } + return *this; +} + +template +vector::vector(vector&& other) +{ + move(std::move(other)); +} + +template +vector& vector::operator=(vector&& other) +{ + if (this != &other) + { + free(); + move(std::move(other)); + } + return *this; +} + +template +vector::~vector() +{ + free(); +} + +template +void vector::copy(const vector& other) +{ + // allocate enough memoty + _data = static_cast(operator new(other.capacity() * sizeof(T))); + + // copy construct elements + for (size_t i = 0; i < other.size(); i++) + new (&_data[i]) T(other[i]); + + _size = other.size(); + _capacity = other.capacity(); +} + +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)); +} + +template +void vector::move(vector&& other) +{ + _size = other.size(); + _capacity = other.capacity(); + _data = other._data; + + other._data = nullptr; + other._size = other._capacity = 0; +} + +template +size_t vector::size() const +{ + return _size; +} + +template +size_t vector::capacity() const +{ + return _capacity; +} + +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. +// If the current size is less than `n`, then additional default-inserted elements are appended. +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(); + + _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(); + + _size = n; + } + else + { + T* new_data = static_cast(operator new(n * sizeof(T))); + + for (size_t i = 0; i < size(); i++) + { + new (&new_data[i]) T(std::move(_data[i])); + (_data + i)->~T(); + } + + for (size_t i = size(); i < n; i++) + new (&new_data[i]) T(); + + operator delete(_data, capacity() * sizeof(T)); + + _data = new_data; + _capacity = n; + _size = n; + } + } +} + +// 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) +{ + if (n <= capacity()) + return; + + T* new_data = static_cast(operator new(n * sizeof(T))); + + 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)); + + _data = new_data; + _capacity = 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() +{ + if (capacity() == size()) + return; + + T* new_data = static_cast(operator new(size() * sizeof(T))); + + 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)); + + _capacity = _size; + _data = new_data; +} + +template +void vector::push_back(const T& element) +{ + if (size() == capacity()) + reserve(calculate_capacity()); + + new (&_data[_size++]) T(element); +} + +template +void vector::push_back(T&& element) +{ + if (size() == capacity()) + reserve(calculate_capacity()); + + new (&_data[_size++]) T(std::move(element)); +} + +// Erases the specified elements from the container. +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) +{ + int deleted_count = last - first; + + if (deleted_count <= 0) + return; + + int begin_offset = first - begin(); + int end_offset = last - begin(); + + if (last != c_end()) + { + for (size_t i = end_offset; i < size(); i++) + new (&_data[begin_offset++]) T(std::move(_data[i])); + } + + for (size_t i = end_offset; i < size(); i++) + (_data + i)->~T(); + + _size -= deleted_count; +} + +// Removes the last element of the container. +// Exceptions: Throws nothing. +template +void vector::pop_back() +{ + if (empty()) + return; + + erase(--end()); +} + +// Appends a new element to the end of the container. +// The element is constructed through placement-new in-place. +template +template +void vector::emplace_back(Args&&... args) +{ + if (size() == capacity()) + reserve(calculate_capacity()); + + new (&_data[_size++]) T(std::forward(args)...); +} + +template +T& vector::operator[](size_t idx) +{ + return _data[idx]; +} + +template +const T& vector::operator[](size_t idx) const +{ + return _data[idx]; +} + +template +T* vector::data() +{ + return _data; +} + +template +void vector::clear() +{ + for (size_t i = 0; i < size(); i++) + (_data + i)->~T(); + + _size = 0; +} + +template +bool vector::empty() const +{ + return (size() == 0); +} \ No newline at end of file -- cgit v1.3.1-23-gd82d