Я хочу создать класс для работы с двусвязным списком в persistent-варианте. Но я не хочу…
- User
Я хочу создать класс для работы с двусвязным списком в persistent-варианте. Но я не хочу хранить все версии одновременно в векторе. Я хочу сделать вот так: у меня в классе будет один вектор со всеми значениями, а версии списков будут просто указывать на элементы моего вектора; если добавляется новая версия с одним отличием, то в этот вектор просто в конец добавляется новое значение, а старые неизменённые значения остаются указывать на те же адреса в памяти template struct DL_node {
}; template class PersistentDoublyLinkedList {};
Работать я хочу с ним примерно вот так: int arr[] = {100, 200, 300}; int size = sizeof(arr) / sizeof(arr[0]); PersistentDoublyLinkedList list(arr, size); // creates a version[0] = 100, 200, 300 list.printAllVersions(); // prints "version[0]: 100, 200, 300"
list.push_front(-250); // creates version[1] = -250, 100, 200, 300
list.push_back(-150); // creates version[2] = -250, 100, 200, 300, -150
list.printAllVersions(); // prints "version[0]: 100, 200, 300\t version[1] = -250, 100, 200, 300\t version[1] = -250, 100, 200, 300, -150\t"
- Assistant
Чтобы реализовать класс для работы с двусвязным списком в persistent-версии, мы можем создать структуру
DL_node, представляющую узел списка, и классPersistentDoublyLinkedList, который будет хранить все значения в одном векторе. Каждая версия будет ссылаться на узлы, которые не изменились, и при добавлении новых узлов мы будем просто добавлять их в конец вектора.Вот пример реализации такого подхода:
#include <iostream> #include <vector> #include <memory> template <typename T> struct DL_node { T value; std::shared_ptr<DL_node<T>> prev; std::shared_ptr<DL_node<T>> next; DL_node(T val) : value(val), prev(nullptr), next(nullptr) {} }; template <typename T> class PersistentDoublyLinkedList { private: std::vector<std::shared_ptr<DL_node<T>>> nodes; // Вектор с узлами std::vector<std::shared_ptr<DL_node<T>>> head; // Указатели на голову каждой версии public: // Конструктор, инициализирующий список из массива PersistentDoublyLinkedList(T arr[], int size) { for (int i = 0; i < size; ++i) { auto newNode = std::make_shared<DL_node<T>>(arr[i]); nodes.push_back(newNode); if (i > 0) { nodes[i-1]->next = newNode; newNode->prev = nodes[i-1]; } } // Поддерживаем указатель на голову первой версии head.push_back(nodes[0]); } // Метод для печати всех версий void printAllVersions() { for (size_t i = 0; i < head.size(); ++i) { std::cout << "version[" << i << "]: "; auto current = head[i]; while (current) { std::cout << current->value << " "; current = current->next; } std::cout << std::endl; } } // Метод для добавления элемента в начало void push_front(T value) { auto newNode = std::make_shared<DL_node<T>>(value); newNode->next = head[head.size() - 1]; // Указатель на первую версию if (head.size() > 0) { head[head.size() - 1]->prev = newNode; } head.push_back(newNode); // Новая голова для новой версии nodes.push_back(newNode); // Добавление нового узла в вектор узлов } // Метод для добавления элемента в конец void push_back(T value) { auto newNode = std::make_shared<DL_node<T>>(value); auto lastHead = head[head.size() - 1]; newNode->prev = lastHead; // Указатель на предыдущий узел if (lastHead) { lastHead->next = newNode; // Указатель на новый узел } head.push_back(lastHead); // Сохранить последний узел для новой версии nodes.push_back(newNode); // Добавление нового узла в вектор узлов } }; int main() { int arr[] = {100, 200, 300}; int size = sizeof(arr) / sizeof(arr[0]); PersistentDoublyLinkedList<int> list(arr, size); // Создаем версию[0] = 100, 200, 300 list.printAllVersions(); // Печатает "version[0]: 100, 200, 300" list.push_front(-250); // Создает версию[1] = -250, 100, 200, 300 list.push_back(-150); // Создает версию[2] = -250, 100, 200, 300, -150 list.printAllVersions(); // Печатает все версии return 0; }В этом коде мы используем
shared_ptr, чтобы управлять памятью и избежать утечек. Основные операцииpush_frontиpush_backпозволяют изменять лишь указатели на узлы в предыдущих версиях, а новые узлы добавляются к вектору.Обратите внимание, что при добавлении элементов в начало или конец списка мы создаем новый узел, который будет содержать указанное значение, при этом задействуя уже существующие узлы для остальной части списка, что соответствует концепции persistent-подхода.
- User
Что-то не так: version[0]: 100 200 300 version[0]: 100 200 300 version[1]: -250 -150 version[2]: -250 -150
- Assistant
Извините за путаницу в реализации. Давайте исправим наш класс, чтобы он корректно поддерживал версии списков.
При добавлении нового узла, нужно в каждой новой версии корректно хранить указатели на предыдущие узлы. Это важный аспект работы с двусвязными списками, чтобы у нас были правильные ссылки на узлы между версиями.
Вот исправленный код:
#include <iostream> #include <vector> #include <memory> template <typename T> struct DL_node { T value; std::shared_ptr<DL_node<T>> prev; std::shared_ptr<DL_node<T>> next; DL_node(T val) : value(val), prev(nullptr), next(nullptr) {} }; template <typename T> class PersistentDoublyLinkedList { private: std::vector<std::shared_ptr<DL_node<T>>> nodes; // Вектор с узлами std::vector<std::shared_ptr<DL_node<T>>> head; // Указатели на голову каждой версии public: // Конструктор, инициализирующий список из массива PersistentDoublyLinkedList(T arr[], int size) { std::shared_ptr<DL_node<T>> tail = nullptr; for (int i = 0; i < size; ++i) { auto newNode = std::make_shared<DL_node<T>>(arr[i]); nodes.push_back(newNode); if (tail) { tail->next = newNode; newNode->prev = tail; } tail = newNode; } // Поддерживаем указатель на голову первой версии head.push_back(nodes[0]); } // Метод для печати всех версий void printAllVersions() { for (size_t i = 0; i < head.size(); ++i) { std::cout << "version[" << i << "]: "; auto current = head[i]; while (current) { std::cout << current->value << " "; current = current->next; } std::cout << std::endl; } } // Метод для добавления элемента в начало void push_front(T value) { auto newNode = std::make_shared<DL_node<T>>(value); newNode->next = head.back(); // Указатель на первую версию if (head.back()) { head.back()->prev = newNode; } head.push_back(newNode); // Новая голова для новой версии nodes.push_back(newNode); // Добавление нового узла в вектор узлов } // Метод для добавления элемента в конец void push_back(T value) { auto newNode = std::make_shared<DL_node<T>>(value); if (head.empty()) { // Если нет ни одной версии, просто добавьте новый узел head.push_back(newNode); } else { auto lastHead = head.back(); // Последняя версия списка newNode->prev = lastHead; // Указатель на последний узел последней версии lastHead->next = newNode; // Обновляем ранее последнюю версию head.push_back(lastHead); // Создаем новую версию на основе последней } nodes.push_back(newNode); // Добавление нового узла в вектор узлов } }; int main() { int arr[] = {100, 200, 300}; int size = sizeof(arr) / sizeof(arr[0]); PersistentDoublyLinkedList<int> list(arr, size); // Создаем версию[0] = 100, 200, 300 list.printAllVersions(); // Печатает "version[0]: 100, 200, 300" list.push_front(-250); // Создает версию[1] = -250, 100, 200, 300 list.push_back(-150); // Создает версию[2] = -250, 100, 200, 300, -150 list.printAllVersions(); // Печатает все версии return 0; }В этом коде:
- При создании версии списка мы сохраняем ссылку на последний узел и правильно обновляем указатели
prevиnextдля каждого узла. - При добавлении нового узла в начале мы создаем новый узел и задаем указатель
nextдля него, чтобы он указывал на голову последней версии. - При добавлении нового узла в конце мы используем последний узел последней версии, и обновляем указатели, чтобы связать новый узел с предыдущим.
Попробуйте выполнить этот код, и он должен правильно выводить все версии списка.
- При создании версии списка мы сохраняем ссылку на последний узел и правильно обновляем указатели