Реализация шаблонного типа данных StableVector

Автор: Дима Савостин • Май 29, 2022 • Курсовая работа • 2,517 Слов (11 Страниц) • 243 Просмотры

Страница 1 из 11

Федеральное государственное бюджетное образовательное учреждение высшего образования
«Сибирский государственный университет телекоммуникаций и информатики»
(СибГУТИ)

Кафедра вычислительных систем

Расчетно-графическая работа

по дисциплине «Современные технологии программирования»

на тему «Реализация шаблонного типа данных 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

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

...

Скачать: txt (12.9 Kb) pdf (191.8 Kb) docx (278.5 Kb)

Продолжить читать еще 10 страниц(ы) »

Читать полный текст Сохранить

Доступно только на Essays.club