Add sem03

7 files changed, 1543 insertions, 0 deletions

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 <iostream>
+
+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<E*>(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 <iostream>
+
+// 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<class T>
+void g(T&& x)
+{
+    f(std::forward<T>(x));
+}
+
+struct printer
+{
+    static void print()
+    {
+        std::cout << std::endl;
+    }
+
+    template<class T, class... Args>
+    static void print(const T& first, const Args&... args)
+    {
+        std::cout << first << " ";
+        print(std::forward<const Args&>(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 <stddef.h>
+
+template <class T>
+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<T> operator+(int off) const
+	{
+		return {memPointer + off};
+	}
+
+	const_vector_iterator<T> operator-(int off) const
+	{
+		return {memPointer - off};
+	}
+
+	int operator-(const_vector_iterator<T> 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 T>
+class vector_iterator
+{
+  public:
+	vector_iterator(T* passedVal)
+		: memPointer{passedVal} {};
+	vector_iterator(T* passedVal, size_t _push)
+		: memPointer{passedVal + _push} {};
+
+	vector_iterator<T>& operator++()
+	{
+		memPointer++;
+		return *this;
+	}
+
+	vector_iterator<T> operator++(int) const
+	{
+		vector_iterator it = *this;
+		++(*this);
+		return it;
+	}
+
+	vector_iterator<T>& operator--()
+	{
+		memPointer--;
+		return *this;
+	}
+
+	vector_iterator<T> operator--(int) const
+	{
+		vector_iterator it = *this;
+		--(*this);
+		return it;
+	}
+
+	operator const_vector_iterator<T>() const
+	{
+		return const_vector_iterator(memPointer);
+	}
+
+	vector_iterator<T> operator+(int off) const
+	{
+		return {memPointer + off};
+	}
+
+	vector_iterator<T> 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<T>& it) const
+	{
+		return (memPointer == it.memPointer);
+	}
+
+	bool operator!=(const vector_iterator<T>& it) const
+	{
+		return !(memPointer == it.memPointer);
+	}
+
+  private:
+	T* memPointer;
+};
+
+template <class T>
+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<T>& operator++()
+	{
+		memPointer--;
+		return *this;
+	}
+
+	reverse_vector_iterator<T> operator++(int) const
+	{
+		reverse_vector_iterator it = *this;
+		++(*this);
+		return it;
+	}
+
+	reverse_vector_iterator<T>& operator--()
+	{
+		memPointer++;
+		return *this;
+	}
+
+	reverse_vector_iterator<T> operator--(int) const
+	{
+		reverse_vector_iterator it = *this;
+		--(*this);
+		return it;
+	}
+
+	reverse_vector_iterator<T> operator+(int off) const
+	{
+		return {memPointer - off};
+	}
+
+	reverse_vector_iterator<T> 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<T>& it) const
+	{
+		return (memPointer == it.memPointer);
+	}
+
+	bool operator!=(const reverse_vector_iterator<T>& 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 <algorithm>
+#include <cassert>
+#include <chrono>
+#include <functional>
+#include <iostream>
+#include <thread>
+
+struct Entity
+{
+	int x;
+
+	Entity(int _x)
+		: x(_x)
+	{}
+	Entity()
+		: x()
+	{}
+
+	~Entity()
+	{
+		x = -1;
+	}
+};
+
+void tests_default()
+{
+	vector<Entity> 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<Entity> v;
+	vector<Entity> 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<int> 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<int> 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<int> 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<int> copy(start);
+	for (size_t i = 0; i < length; i++)
+		assert(copy[i] == start[i]);
+
+	// Move constructor tests
+	vector<int> 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<constructor_called> v(10);
+	assert(called == 10);
+	v.reserve(20);
+	assert(called == 10);
+
+	std::vector<Entity> v2(20, 20);
+	for (const auto& e : v2)
+	{
+		assert(e.x == 20);
+	}
+}
+
+void push_back_tests()
+{
+	vector<int> 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<int> 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<int> 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<Entity> 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<std::thread> v;
+	vector<std::function<void()>> 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 <stddef.h>
+#include <utility>
+
+template <class T>
+class allocator
+{
+public:
+    T *allocate(size_t n) const;
+    void deallocate(T *ptr, size_t n) const;
+
+    template <class... Args>
+    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 <class... Args>
+    void construct_range(T *begin, T *end, Args &&...args) const;
+    void destroy_range(T *begin, T *end) const;
+};
+
+// allocates uninitialized storage 
+template <class T>
+T *allocator<T>::allocate(size_t n) const
+{
+    if(n == 0)
+        return nullptr;
+    
+    return static_cast<T *>(::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 <class T>
+void allocator<T>::deallocate(T *ptr, size_t n) const
+{
+    if (!n)
+        return;
+
+    ::operator delete(ptr, n * sizeof(T));
+}
+
+// destructs an object in allocated storage 
+template <class T>
+void allocator<T>::destroy(T *ptr) const
+{
+    ptr->~T();
+}
+
+template <class T>
+template <class... Args>
+void allocator<T>::construct(T *ptr, Args &&...args) const
+{
+    ::new (ptr) T(std::forward<Args>(args)...);
+}
+
+// constructs an object in allocated storage 
+template <class T>
+template <class... Args>
+void allocator<T>::construct_range(T *begin, T *end, Args &&...args) const
+{
+    while (begin != end)
+    {
+        construct(begin, std::forward<Args>(args)...);
+        ++begin;
+    }
+}
+
+// calls destroy on a range.
+template <class T>
+void allocator<T>::destroy_range(T *begin, T *end) const
+{
+    while (begin != end)
+    {
+        destroy(begin);
+        ++begin;
+    }
+}
+
+// calls construct on a range.
+template<class T>
+void allocator<T>::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 <class T>
+void allocator<T>::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 T, class Allocator = allocator<T>>
+class vector
+{
+  public:
+	using iterator = vector_iterator<T>;
+	using const_iterator = const_vector_iterator<T>;
+	using reverse_iterator = reverse_vector_iterator<T>;
+
+	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 <class... Args>
+	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 <class T, class Allocator>
+vector<T, Allocator>::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 <class T, class Allocator>
+vector<T, Allocator>::vector(size_t count, const T& initial)
+	: _data(_allocator.allocate(count))
+	, _size(count)
+	, _capacity(count)
+{
+	_allocator.construct_range(_data, _data + _size, initial);
+}
+
+template <class T, class Allocator>
+vector<T, Allocator>::vector(const vector& other)
+{
+	copy(other);
+}
+
+template <class T, class Allocator>
+vector<T, Allocator>& vector<T, Allocator>::operator=(const vector& other)
+{
+	if (this != &other)
+	{
+		free();
+		copy(other);
+	}
+	return *this;
+}
+
+template <class T, class Allocator>
+vector<T, Allocator>::vector(vector&& other)
+{
+	move(std::move(other));
+}
+
+template <class T, class Allocator>
+vector<T, Allocator>& vector<T, Allocator>::operator=(vector&& other)
+{
+	if (this != &other)
+	{
+		free();
+		move(std::move(other));
+	}
+	return *this;
+}
+
+template <class T, class Allocator>
+vector<T, Allocator>::~vector()
+{
+	free();
+}
+
+template <class T, class Allocator>
+void vector<T, Allocator>::copy(const vector<T, Allocator>& other)
+{
+	_data = _allocator.allocate(other.capacity());
+	_allocator.copy_range(_data, other._data, other._data + other.size());
+
+	_size = other.size();
+	_capacity = other.capacity();
+}
+
+template <class T, class Allocator>
+void vector<T, Allocator>::free()
+{
+	_allocator.destroy_range(_data, _data + size());
+	_allocator.deallocate(_data, capacity());
+}
+
+template <class T, class Allocator>
+void vector<T, Allocator>::move(vector<T, Allocator>&& other)
+{
+	_size = other.size();
+	_capacity = other.capacity();
+	_data = other._data;
+
+	other._data = nullptr;
+	other._size = other._capacity = 0;
+}
+
+template <class T, class Allocator>
+size_t vector<T, Allocator>::size() const
+{
+	return _size;
+}
+
+template <class T, class Allocator>
+size_t vector<T, Allocator>::capacity() const
+{
+	return _capacity;
+}
+
+template <class T, class Allocator>
+size_t vector<T, Allocator>::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 <class T, class Allocator>
+void vector<T, Allocator>::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 <class T, class Allocator>
+void vector<T, Allocator>::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 <class T, class Allocator>
+void vector<T, Allocator>::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 <class T, class Allocator>
+void vector<T, Allocator>::push_back(const T& element)
+{
+	if (size() == capacity())
+		reserve(calculate_capacity());
+
+	_allocator.construct(_data[_size++], element);
+}
+
+template <class T, class Allocator>
+void vector<T, Allocator>::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 <class T, class Allocator>
+void vector<T, Allocator>::erase(const_iterator position)
+{
+	erase(position, position + 1);
+}
+
+// Erases the specified range from the container.
+template <class T, class Allocator>
+void vector<T, Allocator>::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 <class T, class Allocator>
+void vector<T, Allocator>::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 <class T, class Allocator>
+template <class... Args>
+void vector<T, Allocator>::emplace_back(Args&&... args)
+{
+	if (size() == capacity())
+		reserve(calculate_capacity());
+
+	_allocator.construct(&_data[_size++], std::forward<Args>(args)...);
+}
+
+template <class T, class Allocator>
+T& vector<T, Allocator>::operator[](size_t idx)
+{
+	return _data[idx];
+}
+
+template <class T, class Allocator>
+const T& vector<T, Allocator>::operator[](size_t idx) const
+{
+	return _data[idx];
+}
+
+template <class T, class Allocator>
+T* vector<T, Allocator>::data()
+{
+	return _data;
+}
+
+template <class T, class Allocator>
+void vector<T, Allocator>::clear()
+{
+	_allocator.destroy_range(_data, _data + size());
+	_size = 0;
+}
+
+template <class T, class Allocator>
+bool vector<T, Allocator>::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 <utility>
+
+namespace Constants
+{
+constexpr unsigned GROWTH_FACTOR = 2;
+}
+
+template <class T>
+class vector
+{
+  public:
+	using iterator = vector_iterator<T>;
+	using const_iterator = const_vector_iterator<T>;
+	using reverse_iterator = reverse_vector_iterator<T>;
+
+	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 <class... Args>
+	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 <class T>
+vector<T>::vector(size_t count)
+	: _data(static_cast<T*>(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 <class T>
+vector<T>::vector(size_t count, const T& initial)
+	: _data(static_cast<T*>(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 <class T>
+vector<T>::vector(const vector& other)
+{
+	copy(other);
+}
+
+template <class T>
+vector<T>& vector<T>::operator=(const vector& other)
+{
+	if (this != &other)
+	{
+		free();
+		copy(other);
+	}
+	return *this;
+}
+
+template <class T>
+vector<T>::vector(vector&& other)
+{
+	move(std::move(other));
+}
+
+template <class T>
+vector<T>& vector<T>::operator=(vector&& other)
+{
+	if (this != &other)
+	{
+		free();
+		move(std::move(other));
+	}
+	return *this;
+}
+
+template <class T>
+vector<T>::~vector()
+{
+	free();
+}
+
+template <class T>
+void vector<T>::copy(const vector<T>& other)
+{
+	// allocate enough memoty
+	_data = static_cast<T*>(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 <class T>
+void vector<T>::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 <class T>
+void vector<T>::move(vector<T>&& other)
+{
+	_size = other.size();
+	_capacity = other.capacity();
+	_data = other._data;
+
+	other._data = nullptr;
+	other._size = other._capacity = 0;
+}
+
+template <class T>
+size_t vector<T>::size() const
+{
+	return _size;
+}
+
+template <class T>
+size_t vector<T>::capacity() const
+{
+	return _capacity;
+}
+
+template <class T>
+size_t vector<T>::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 <class T>
+void vector<T>::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<T*>(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 <class T>
+void vector<T>::reserve(size_t n)
+{
+	if (n <= capacity())
+		return;
+
+	T* new_data = static_cast<T*>(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 <class T>
+void vector<T>::shrink_to_fit()
+{
+	if (capacity() == size())
+		return;
+
+	T* new_data = static_cast<T*>(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 <class T>
+void vector<T>::push_back(const T& element)
+{
+	if (size() == capacity())
+		reserve(calculate_capacity());
+
+	new (&_data[_size++]) T(element);
+}
+
+template <class T>
+void vector<T>::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 <class T>
+void vector<T>::erase(const_iterator position)
+{
+	erase(position, position + 1);
+}
+
+// Erases the specified range from the container.
+template <class T>
+void vector<T>::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 <class T>
+void vector<T>::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 <class T>
+template <class... Args>
+void vector<T>::emplace_back(Args&&... args)
+{
+	if (size() == capacity())
+		reserve(calculate_capacity());
+
+	new (&_data[_size++]) T(std::forward<Args>(args)...);
+}
+
+template <class T>
+T& vector<T>::operator[](size_t idx)
+{
+	return _data[idx];
+}
+
+template <class T>
+const T& vector<T>::operator[](size_t idx) const
+{
+	return _data[idx];
+}
+
+template <class T>
+T* vector<T>::data()
+{
+	return _data;
+}
+
+template <class T>
+void vector<T>::clear()
+{
+	for (size_t i = 0; i < size(); i++)
+		(_data + i)->~T();
+
+	_size = 0;
+}
+
+template <class T>
+bool vector<T>::empty() const
+{
+	return (size() == 0);
+}
\ No newline at end of file