Skip to content
TheChatArchiveThe Chat Archive
gpt-4o-mini-2024-07-18· OpenAIAi2 WildChat-4.8M (AI2)

Я хочу создать класс для работы с двусвязным списком в persistent-варианте. Но я не хочу…

  1. 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"

  2. 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-подхода.

  3. User

    Что-то не так: version[0]: 100 200 300 version[0]: 100 200 300 version[1]: -250 -150 version[2]: -250 -150

  4. 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;
    }
    

    В этом коде:

    1. При создании версии списка мы сохраняем ссылку на последний узел и правильно обновляем указатели prev и next для каждого узла.
    2. При добавлении нового узла в начале мы создаем новый узел и задаем указатель next для него, чтобы он указывал на голову последней версии.
    3. При добавлении нового узла в конце мы используем последний узел последней версии, и обновляем указатели, чтобы связать новый узел с предыдущим.

    Попробуйте выполнить этот код, и он должен правильно выводить все версии списка.