Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commitdf74c873bc11ad90fb26e582c7be0ed092228661 (patch)
Author
 Stoycho Kyosev <skyosev@2a01-5a8-317-bbdc-4f2b-da5-db2e-fb02.v6.vivacom.bg>
2024-10-25 18:04:36 -0400
Committer
 Stoycho Kyosev <skyosev@2a01-5a8-317-bbdc-4f2b-da5-db2e-fb02.v6.vivacom.bg>
2024-10-25 18:04:36 -0400
Files73d2662eeddf5ebddfa6982270edd21fb4588de9
Data-structures-and-algorithms-df74c873bc11ad90fb26e582c7be0ed092228661.tar
Data-structures-and-algorithms-df74c873bc11ad90fb26e582c7be0ed092228661.tar.gz
Data-structures-and-algorithms-df74c873bc11ad90fb26e582c7be0ed092228661.zip
Parentc31c7c53f87104c254aac5ba99e984f9ec373d9a (diff)
Add sem03
diff --git a/Practicum/pract02/CountingSort.cpp b/Practicum/pract02/CountingSort.cpp
index 04e1e81..383e003 100644
--- a/Practicum/pract02/CountingSort.cpp
+++ b/Practicum/pract02/CountingSort.cpp
@@ -1,3 +1,5 @@
+#include <unistd.h> // size_t
+
void counting_sort(int* arr, size_t arrLength) {
constexpr int MAX_SIZE = 1e5;
int arr_copy[MAX_SIZE];
diff --git a/Seminar02/README.md b/Seminar02/README.md
index 9399aea..64f3a96 100644
--- a/Seminar02/README.md
+++ b/Seminar02/README.md
@@ -122,4 +122,19 @@ in-place - Не
Сложност по памет - Θ(n)
-## Алгоритъмът Quick Sort \ No newline at end of file
+## Алгоритъмът Quicksort
+Нека предположим, че избираме произволен елемент от `p` от `n` елементи, които искаме да сортираме. `Quicksort` разделя останалите `n - 1` елемента на две групи - тези, които са по - малки от `p` и тези, които са по - големи. Всеки от по - малките елементи се намира вляво от всеки от по - големите.
+
+Подобно разделяне ни носи две неща:
+
+* Избраният елемент `p` остава на точната позиция на която ще бъде в сортирания масив.
+* След това разбиване никой елемент не се премества от лявата част в дясната. Това означава, че можем да разглеждаме двете части като отделни масиви!
+
+Функцията, която използваме за да направи такова разделение, наричаме `partition`. След като изберем елемент (наричан `pivot`) извикваме `partition` върху масива и след като тя приключи рекурсивно извикваме `Quicksort` върху лявата подмасива на по - малките елементи и този на по - големите.
+
+* Worst case complextiy = O(n^2) - Можем винаги да избираме най - големия или най - малкия. Тогава няма да имаме два подмасива а един с големина `n - 1`.
+* Average case = O(nlog(n)) - Добре е тук да обърнем внимание на средния случай като той ни дава много по - добра представа за реалния потенциал на `Quicksort`. Въпрки, че в най - лошия случай това е квадратичен алгоритъм, очакваме че няма да вземем най - големия, нито най - малкия, а елемент близък до средния по големина.
+* Стабилен - не, `partition` не гарантира, че ще запази първоначалната наредба на елементите.
+* in place - да
+
+## std::partition, std::merge \ No newline at end of file
diff --git a/Seminar02/src/sorting-algorithms/quick-sort.cpp b/Seminar02/src/sorting-algorithms/quick-sort.cpp
index 3069738..f82e8c5 100644
--- a/Seminar02/src/sorting-algorithms/quick-sort.cpp
+++ b/Seminar02/src/sorting-algorithms/quick-sort.cpp
@@ -4,7 +4,6 @@
/// @brief Reorders the elements in such a way that all elements for which are less than pivot
// precede all elements which are greater or equal to pivot. Relative order of the elements is not preserved.
-// TODO: remove copy somehow???
template <class T>
size_t partition(T* pArr, size_t len)
{
@@ -37,12 +36,12 @@ size_t partition(T* pArr, size_t len)
}
template<class T>
-void quickSort(T* arr, unsigned size)
+void quickSort(T* arr, size_t size)
{
if(size < 2)
return;
- unsigned pivotPos = partition(arr, size);
+ size_t pivotPos = partition(arr, size);
quickSort(arr, pivotPos);
quickSort(arr + pivotPos + 1, size - pivotPos - 1);
@@ -51,7 +50,7 @@ void quickSort(T* arr, unsigned size)
int main()
{
std::vector<int> numbers;
- unsigned size = rand() % 10000;
+ size_t size = rand() % 10000;
numbers.resize(size);
for (size_t i = 0; i < size; i++)
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
diff --git a/Seminar03/src/sorting/counting-sort.cpp b/Seminar03/src/sorting/counting-sort.cpp
new file mode 100644
index 0000000..a744b5c
--- /dev/null
+++ b/Seminar03/src/sorting/counting-sort.cpp
@@ -0,0 +1,52 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+void counting_sort(std::vector<int>& data)
+{
+ if (data.empty())
+ return;
+
+ auto min_max_pair = std::minmax_element(data.begin(), data.end());
+ unsigned count_buffer_size = *min_max_pair.second - *min_max_pair.first + 1;
+
+ // All elements are the same.
+ if (count_buffer_size == 1)
+ return;
+
+ int lower = *min_max_pair.first;
+ std::vector<int> count(count_buffer_size, 0);
+ std::vector<int> copy(data);
+
+ for (int number : data)
+ {
+ count[number - lower]++;
+ }
+
+ for (size_t i = 1; i < count.size(); i++)
+ {
+ count[i] += count[i - 1];
+ }
+
+ for (int i = copy.size() - 1; i >= 0; i--)
+ {
+ data[count[copy[i] - lower] - 1] = copy[i];
+ --count[copy[i] - lower];
+ }
+}
+
+int main()
+{
+ std::vector<int> numbers;
+ unsigned size = rand() % 2000;
+ numbers.resize(size);
+
+ for (size_t i = 0; i < size; i++)
+ {
+ numbers[i] = rand() % 100;
+ }
+
+ counting_sort(numbers);
+
+ std::cout << std::is_sorted(numbers.begin(), numbers.end()) << std::endl;
+} \ No newline at end of file