vector.cpp(檔案已創建)
| @@ -0,0 +1,145 @@ | |||
| 1 | + | #include <cstddef> | |
| 2 | + | #include <new> | |
| 3 | + | #include <utility> | |
| 4 | + | #include <algorithm> | |
| 5 | + | #include <stdexcept> | |
| 6 | + | #include <memory> | |
| 7 | + | #include <iostream> | |
| 8 | + | #include <string> | |
| 9 | + | ||
| 10 | + | namespace getcracked { | |
| 11 | + | ||
| 12 | + | template <typename T> | |
| 13 | + | class vector { | |
| 14 | + | private: | |
| 15 | + | std::size_t m_size{0}; | |
| 16 | + | std::size_t m_cap{0}; | |
| 17 | + | T* p_arr{nullptr}; | |
| 18 | + | ||
| 19 | + | // allocate raw memory (uninitialized) | |
| 20 | + | static T* allocate(std::size_t n) { | |
| 21 | + | if (n == 0) return nullptr; | |
| 22 | + | return static_cast<T*>(::operator new(sizeof(T) * n)); | |
| 23 | + | } | |
| 24 | + | ||
| 25 | + | // destroy all elements and free memory | |
| 26 | + | void destroy_and_free() noexcept { | |
| 27 | + | if (p_arr) { | |
| 28 | + | std::destroy_n(p_arr, m_size); | |
| 29 | + | ::operator delete(p_arr); | |
| 30 | + | } | |
| 31 | + | p_arr = nullptr; | |
| 32 | + | m_size = 0; | |
| 33 | + | m_cap = 0; | |
| 34 | + | } | |
| 35 | + | ||
| 36 | + | // reallocate with move semantics | |
| 37 | + | void grow(std::size_t new_cap) { | |
| 38 | + | T* new_arr = allocate(new_cap); | |
| 39 | + | std::size_t i = 0; | |
| 40 | + | try { | |
| 41 | + | for (; i < m_size; ++i) | |
| 42 | + | std::construct_at(new_arr + i, std::move_if_noexcept(p_arr[i])); | |
| 43 | + | } catch (...) { | |
| 44 | + | // rollback on exception | |
| 45 | + | std::destroy_n(new_arr, i); | |
| 46 | + | ::operator delete(new_arr); | |
| 47 | + | throw; | |
| 48 | + | } | |
| 49 | + | ||
| 50 | + | std::destroy_n(p_arr, m_size); | |
| 51 | + | ::operator delete(p_arr); | |
| 52 | + | p_arr = new_arr; | |
| 53 | + | m_cap = new_cap; | |
| 54 | + | } | |
| 55 | + | ||
| 56 | + | public: | |
| 57 | + | vector() = default; | |
| 58 | + | ||
| 59 | + | explicit vector(std::size_t count, const T& value = T()) | |
| 60 | + | : m_size(count), m_cap(count), p_arr(allocate(count)) | |
| 61 | + | { | |
| 62 | + | std::uninitialized_fill_n(p_arr, count, value); | |
| 63 | + | } | |
| 64 | + | ||
| 65 | + | // copy constructor | |
| 66 | + | vector(const vector& other) | |
| 67 | + | : m_size(other.m_size), m_cap(other.m_size), p_arr(allocate(other.m_size)) | |
| 68 | + | { | |
| 69 | + | std::uninitialized_copy_n(other.p_arr, other.m_size, p_arr); | |
| 70 | + | } | |
| 71 | + | ||
| 72 | + | // move constructor | |
| 73 | + | vector(vector&& other) noexcept | |
| 74 | + | : m_size(other.m_size), m_cap(other.m_cap), p_arr(other.p_arr) | |
| 75 | + | { | |
| 76 | + | other.p_arr = nullptr; | |
| 77 | + | other.m_size = other.m_cap = 0; | |
| 78 | + | } | |
| 79 | + | ||
| 80 | + | // destructor | |
| 81 | + | ~vector() { destroy_and_free(); } | |
| 82 | + | ||
| 83 | + | // copy assignment | |
| 84 | + | vector& operator=(const vector& other) { | |
| 85 | + | if (this == &other) return *this; | |
| 86 | + | destroy_and_free(); | |
| 87 | + | m_size = other.m_size; | |
| 88 | + | m_cap = other.m_size; | |
| 89 | + | p_arr = allocate(m_cap); | |
| 90 | + | std::uninitialized_copy_n(other.p_arr, other.m_size, p_arr); | |
| 91 | + | return *this; | |
| 92 | + | } | |
| 93 | + | ||
| 94 | + | // move assignment | |
| 95 | + | vector& operator=(vector&& other) noexcept { | |
| 96 | + | if (this == &other) return *this; | |
| 97 | + | destroy_and_free(); | |
| 98 | + | m_size = other.m_size; | |
| 99 | + | m_cap = other.m_cap; | |
| 100 | + | p_arr = other.p_arr; | |
| 101 | + | other.p_arr = nullptr; | |
| 102 | + | other.m_size = other.m_cap = 0; | |
| 103 | + | return *this; | |
| 104 | + | } | |
| 105 | + | ||
| 106 | + | template <typename U> | |
| 107 | + | void push_back(U&& value) { | |
| 108 | + | if (m_size == m_cap) | |
| 109 | + | grow(m_cap == 0 ? 1 : m_cap * 2); | |
| 110 | + | ||
| 111 | + | std::construct_at(p_arr + m_size, std::forward<U>(value)); | |
| 112 | + | ++m_size; | |
| 113 | + | } | |
| 114 | + | ||
| 115 | + | void pop_back() { | |
| 116 | + | if (m_size == 0) return; | |
| 117 | + | --m_size; | |
| 118 | + | std::destroy_at(p_arr + m_size); | |
| 119 | + | } | |
| 120 | + | ||
| 121 | + | const T& at(std::size_t index) const { | |
| 122 | + | if (index >= m_size) throw std::out_of_range("index out of range"); | |
| 123 | + | return p_arr[index]; | |
| 124 | + | } | |
| 125 | + | ||
| 126 | + | T& at(std::size_t index) { | |
| 127 | + | if (index >= m_size) throw std::out_of_range("index out of range"); | |
| 128 | + | return p_arr[index]; | |
| 129 | + | } | |
| 130 | + | ||
| 131 | + | std::size_t size() const noexcept { return m_size; } | |
| 132 | + | std::size_t capacity() const noexcept { return m_cap; } | |
| 133 | + | ||
| 134 | + | void reserve(std::size_t new_cap) { | |
| 135 | + | if (new_cap > m_cap) | |
| 136 | + | grow(new_cap); | |
| 137 | + | } | |
| 138 | + | ||
| 139 | + | void shrink_to_fit() { | |
| 140 | + | if (m_cap > m_size) | |
| 141 | + | grow(m_size); | |
| 142 | + | } | |
| 143 | + | }; | |
| 144 | + | ||
| 145 | + | } // namespace getcracked | |
上一頁
下一頁