Реализация шаблонного типа данных StableVector
Автор: Дима Савостин • Май 29, 2022 • Курсовая работа • 2,517 Слов (11 Страниц) • 178 Просмотры
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Сибирский государственный университет телекоммуникаций и информатики»
(СибГУТИ)
Кафедра вычислительных систем
Расчетно-графическая работа
по дисциплине «Современные технологии программирования»
на тему «Реализация шаблонного типа данных StableVector»
Выполнил:
ст. гр. Ив-923
Савостин Д.E
Проверил:
ст. пр. Пименов Е. С.
Содержание
1. Постановка задачи 3
2. Мотивация 4
3. Реализация 5
3.1 Внутреннее устройство 5
3.2 Интерфейс 5
3.3 Итераторы 5
4. Список источников 6
5. Приложение 7
Постановка задачи
Спроектировать шаблонный тип данных StableVector. Использовать стандарт языка С++17. Реализовать итераторы, совместимые с алгоритмами стандартной библиотеки. Покрыть модульными тестами. При реализации не пользоваться контейнерами стандартной библиотеки, реализовать управление ресурсами в идиоме RAII.
В качестве системы сборки использовать CMake. Структурировать проект в соответствии с соглашениями Canonical Project Structure [1]. Всю разработку вести в системе контроля версий git. Настроить автоматическое форматирование средствами clang-format.
Проверить код анализаторами Valgrind Memcheck, undefined sanitizer, address sanitizer, clang-tidy.
Мотивация
Преимущество StableVector, это наличие стабильных итераторов, которые гарантируют стабильность т.е. ссылки и итераторы к эллементу stable_vector остаются действительными до тех пор, пока элемент не стерт, а итератор, которому было присвоено возвращаемое значение end(), всегда остается действительным до тех пор, пока уничтожение связанного с ним stable_vector .
Реализация
Внутреннее устройство
На следующем изображении показана схема структуры StableVector.
[pic 1][pic 2]
Каждый элемент хранится в своем отдельном узле. На все узлы ссылаются из непрерывного массива указателей, но также каждый узел содержит указатель “вверх”, ссылающийся на соответствующую ячейку массива. Этот указатель вверх является ключевым элементом для реализации стабильности и произвольного доступа:
- Итераторы указывают на узлы, а не на массив указателей. Это обеспечивает стабильность, поскольку при вставке или удалении необходимо сместить или переместить только массив указателей.
- Операции произвольного доступа могут быть реализованы с использованием массива указателей в качестве удобной промежуточной зоны. Например, если итератор it содержит указатель узла it и мы хотим продвигаться it по n позициям, мы просто идем “вверх” к массиву указателей, добавляем n туда и потом идем вниз к получившемуся узлу.
Интерфейс
Void pushback(T value) – асимптотическая сложность О(1).
Void insert(T value, size_t index) – асимптотическая сложность О(1) в лучшем случае, О(n) – в худшем случае.
Void pop_back() – асимптотическая сложность О(1)
Void remove(size_t index) – асимптотическая сложность О(1) в лучшем случае, О(n) – в худшем случае.
Void shrink_to_fit() - – асимптотическая сложность О(1) в лучшем случае, О(n) – в худшем случае.
T &operator[](size_t index) – асимптотическая сложность О(1).
bool isEmpty() const – асимптотическая сложность О(1).
size_t size() const – асимптотическая сложность О(1).
size_t capacity() const – асимптотическая сложность О(1).
Iterator begin() const – асимптотическая сложность О(1).
Iterator end() const – асимптотическая сложность О(1).
Итераторы
В данной структуре данных реализован итератор категории “std::input_iterator_tag” Из особенностей реализации могу выделить лишь оператор “++” внутри итератора. Для того, чтобы про итерироваться по StableVector нужно подняться наверх, перейти на следующий указатель, а затем, спуститься вниз.
Список источников
- Kolpackov B. Canonical Project Structure [Электронный ресурс]. URL: https://open-std.org/JTC1/SC22/WG21/docs/papers/2018/p1204r0.html
- http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
Приложение
StableVector.hpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 | #include <iostream> namespace MyVector { template <typename T> class MyVector { private: class Node { private: T Value; Node **Up = nullptr; public: friend MyVector; Node() = default; Node(T value, Node **up) : Value(value), Up(up) {} Node(const Node &other) = delete; Node(Node &&other) = delete; ~Node() = default; T &operator=(const Node &other) = delete; T &operator=(Node &&other) = delete; }; public: class Iterator { friend MyVector; public: using iterator_category = std::input_iterator_tag; using value_type = T; using difference_type = std::ptrdiff_t; using pointer = value_type *; using reference = value_type &; private: Node *Current = nullptr; explicit Iterator(Node *current) : Current(current) {} public: Iterator() = default; ~Iterator() = default; bool operator==(Iterator other) const { return Current == other.Current; } bool operator!=(Iterator other) const { return Current != other.Current; } T &operator*() const { return Current->Value; } T *operator->() const { return &Current->Value; } Iterator &operator++() { Current = *(&(*(Current->Up)) + 1); return *this; } Iterator operator++(int) { Iterator iter = *this; ++*this; return iter; } }; private: size_t Capacity = 0; size_t Size = 0; Node **Arr = nullptr; public: MyVector() = default; MyVector(const MyVector &other) : Capacity(other.Capacity), Arr(new Node *[Capacity]) { for (size_t i = 0; i < other.Size; ++i) { pushBack(other.Arr[i]->Value); } } MyVector(MyVector &&other) noexcept : Capacity(other.Capacity), Size(other.Size), Arr(other.Arr) { other.Arr = nullptr; other.Size = other.Capacity = 0; } ~MyVector() { for (size_t i = 0; i < Size; i++) { delete Arr[i]; } delete[] Arr; } MyVector &operator=(const MyVector &other) { if (this != &other) { for (size_t i = 0; i < Size; i++) { delete Arr[i]; } delete[] Arr; Capacity = other.Capacity; Size = 0; Arr = new Node *[Capacity]; for (size_t i = 0; i < other.Size; ++i) { pushBack(other.Arr[i]->Value); } } return *this; } MyVector &operator=(MyVector &&other) noexcept { if (this != &other) { for (size_t i = 0; i < Size; i++) { delete Arr[i]; } delete[] Arr; Arr = other.Arr; Size = other.Size; Capacity = other.Capacity; other.Arr = nullptr; other.Size = other.Capacity = 0; } return *this; } void addMemory() { if (Capacity == 0) { Arr = new Node *[1]; Capacity = 1; } else { Capacity *= 2; Node **tmp = Arr; Arr = new Node *[Capacity]; for (size_t i = 0; i < Size; ++i) { Arr[i] = tmp[i]; Arr[i]->Up = &Arr[i]; } delete[] tmp; } } void pushBack(T value) { if (Size >= Capacity) { addMemory(); } Arr[Size] = new Node(value, &(Arr[Size])); Size++; } void insert(T value, size_t index) { if (Size >= Capacity) { addMemory(); } ++Size; Node *temp1; Node *temp2; temp1 = new Node(value, &Arr[index]); for (size_t i = index; i < Size; ++i) { temp2 = Arr[i]; Arr[i] = temp1; Arr[i]->Up = &Arr[i]; temp1 = temp2; } } void pop_back() { if (Size != 0) { delete Arr[Size - 1]; Size--; } } void remove(size_t index) { if (index < Size) { delete Arr[index]; for (size_t i = index + 1; i < Size; ++i) { Arr[i - 1] = Arr[i]; Arr[i - 1]->Up = &Arr[i - 1]; } Arr[Size - 1] = nullptr; --Size; } } void shrink_to_fit() { Capacity = Size; Node **tmp = Arr; Arr = new Node *[Capacity]; for (size_t i = 0; i < Size; ++i) { Arr[i] = tmp[i]; Arr[i]->Up = &Arr[i]; } delete[] tmp; } T &operator[](size_t index) { return Arr[index]->Value; } bool isEmpty() const { return Size == 0; } size_t size() const { return Size; } size_t capacity() const { return Capacity; } Iterator begin() const { return Iterator(Arr[0]); } Iterator end() const { return Iterator(Arr[Size]); } }; template <typename T> inline std::ostream &operator<<(std::ostream &os, const MyVector<T> &vec) { for (const T &val : vec) os << val << ' '; { return os; } } } // namespace MyVector |
...