Если «A» имеет переменную-член «x» типа «A *», а «B» наследуется от «A», как переопределить «x» как «B *» внутри «B»?

Question

Редактировать: более простая версия вопроса:

class ForwardNode // A
{
public:

    char val;
    ForwardNode* next; // x

    ForwardNode(char val, ForwardNode* next = nullptr) : val(val), next(next) {}
};

class BidirectionalNode : public ForwardNode // B
{
public:

    BidirectionalNode* prev;

    BidirectionalNode(char val, BidirectionalNode* next = nullptr, BidirectionalNode* prev = nullptr)
        : ForwardNode(val, next), prev(prev) {}
};

Здесь я определяю передний узел и двунаправленный узел. Прямой узел имеет ссылку только на следующий узел. Двунаправленный узел имеет ссылку как на предыдущий, так и на следующий узел.

Похоже, BidirectionalNode точно так же, как ForwardNode, но с дополнительной ссылкой на предыдущий узел. Поэтому я позволил BidirectionalNode унаследовать от ForwardNode. Но теперь каждый раз, когда мне нужно обработать next или current как BidirectionalNode, мне придется сначала разыграть его, так как он определен как ForwardNode.

Вот пример:

class ForwardList
{
public:

    ForwardNode* head;
    ForwardNode* tail;
    ForwardNode* current = nullptr;

    ForwardList(ForwardNode* head, ForwardNode* tail) :
        head(head), tail(tail) {}

    void PrintListForwards()
    {
        current = head;
        do
        {
            std::cout << current->val;
            current = current->next;
        } 
        while (current != nullptr);

        std::cout << std::endl;
    }
};

// BidirectionalList is a ForwardList for the same reason 
// BidirectionalNode is a ForwardNode.
class BidirectionalList : public ForwardList
{
public:

    BidirectionalList(BidirectionalNode* head, BidirectionalNode* tail) :
        ForwardList(head, tail) {}

    void PrintListBackwards()
    {
        current = tail;
        do
        {
            std::cout << current->val;

            // here I wanna redefine current as BidirectionalNode*
            // instead of casting every time they are used.
            current = ((BidirectionalNode*)current)->prev;
        } 
        while (current != nullptr);

        std::cout << std::endl;
    }
};

Здесь я должен привести current к BidirectionalNode*, чтобы иметь возможность использовать prev.

Есть ли способ переопределить next и current как BidirectionalNode* вместо того, чтобы разыгрывать это каждый раз?

Другой пример:

std::pair<BidirectionalNode*, BidirectionalNode*> CreateBidirectionalList(std::string string)
{
    if (string.empty())
    {
        BidirectionalNode* node = new BidirectionalNode{ 0 };
        return { node, node };
    }

    BidirectionalNode* head = new BidirectionalNode{ string[0] };
    BidirectionalNode* tail = head;
    for (int i = 1; i < string.size(); i++)
    {
        tail->next = new BidirectionalNode{ string[i] };

        // have to cast.
        ((BidirectionalNode*)(tail->next))->prev = tail;
        // have to cast again.
        tail = ((BidirectionalNode*)tail->next);

        tail->val = string[i];
    }

    return { head, tail };
}

---

Оригинальный вопрос:

#include <iostream>

class Node
{
public:

    int value;
    Node* next;

    Node(Node* next, int value) : next(next), value(value) {}
};

class DoublyLinkedNode
{
public:

    int value;
    DoublyLinkedNode* prev;
    DoublyLinkedNode* next;

    DoublyLinkedNode(DoublyLinkedNode* prev, DoublyLinkedNode* next, int value)
        : prev(prev), next(next), value(value) {}
};

class ILinkedList
{
public:

    virtual void PushBack(int value) = 0;
    virtual void SetCurrentToBegin() = 0;
    virtual int GetCurrent() = 0;
    virtual bool HasNext() = 0;
    virtual void SetToNextNode() = 0;
};

class IDoublyLinkedList : public ILinkedList
{
public:

    virtual void PushFront(int value) = 0;
    virtual void SetCurrentToEnd() = 0;
    virtual bool HasPrev() = 0;
    virtual void SetToPrevNode() = 0;
};

class LinkedList : public ILinkedList
{
protected:

    Node* head;
    Node* tail;
    Node* current;

public:

    LinkedList()
    {
        std::cout << "Linked List Created." << std::endl;

        tail = new Node{ nullptr, 0 };
        head = new Node{ tail, 0 };
        current = head;
    }

    virtual void PushBack(int value) override
    {
        tail->value = value;
        tail->next = new Node{ nullptr, 0 };
        tail = tail->next;
    }

    virtual int GetCurrent() override
    {
        return current->value;
    }

    virtual void SetCurrentToBegin() override
    {
        current = head->next;
    }

    virtual bool HasNext() override
    {
        return current != tail;
    }

    virtual void SetToNextNode() override
    {
        if (current == tail)
            SetCurrentToBegin();
        else
            current = current->next;
    }
};

class DoublyLinkedList : public IDoublyLinkedList
{

    int value;
    DoublyLinkedNode* head;
    DoublyLinkedNode* tail;
    DoublyLinkedNode* current;

public:

    DoublyLinkedList()
    {
        std::cout << "Doubly Linked List Created." << std::endl;

        head = new DoublyLinkedNode{ nullptr, nullptr, 0 };
        tail = new DoublyLinkedNode{ nullptr, nullptr, 0 };
        head->next = tail;
        tail->prev = head;
        current = head;
    }

    virtual void PushBack(int value) override
    {
        tail->value = value;
        tail->next = new DoublyLinkedNode{ tail, nullptr, 0 };
        tail = tail->next;
    }

    virtual void PushFront(int value) override
    {
        head->value = value;
        head->prev = new DoublyLinkedNode{ nullptr, head, 0 };
        head = head->prev;
    }

    virtual void SetCurrentToEnd() override
    {
        current = tail->prev;
    }

    virtual bool HasPrev() override
    {
        return current != head;
    }

    virtual void SetToPrevNode() override
    {
        if (current == head)
            SetCurrentToEnd();
        else
            current = current->prev;
    }

    virtual int GetCurrent() override
    {
        return current->value;
    }

    virtual void SetCurrentToBegin() override
    {
        current = head->next;
    }

    virtual bool HasNext() override
    {
        return current != tail;
    }

    virtual void SetToNextNode() override
    {
        if (current == tail)
            SetCurrentToBegin();
        else
            current = current->next;
    }
};

void PrintForward(ILinkedList& list)
{
    list.SetCurrentToBegin();

    while (list.HasNext())
    {
        std::cout << list.GetCurrent() << ' ';
        list.SetToNextNode();
    }

    std::cout << std::endl;
}

void PrintBackward(DoublyLinkedList& list)
{
    list.SetCurrentToEnd();

    while (list.HasPrev())
    {
        std::cout << list.GetCurrent() << ' ';
        list.SetToPrevNode();
    }

    std::cout << std::endl;
}

int main()
{
    LinkedList ll;

    for (int i = 1; i <= 5; i++)
        ll.PushBack(i);

    PrintForward(ll);

    std::cout << std::endl;

    // -----------------------------------

    DoublyLinkedList dll;

    for (int i = 1; i <= 5; i++)
        dll.PushFront(i), dll.PushBack(i);

    PrintForward(dll);
    PrintBackward(dll);
}

Вывод:

Linked List Created.
1 2 3 4 5

Doubly Linked List Created.
5 4 3 2 1 1 2 3 4 5
5 4 3 2 1 1 2 3 4 5

Вот простая реализация сильно связанного списка и двусвязного списка. Здесь я использую интерфейс с именем ILinkedList и другой интерфейс с именем IDoublyLinkedList, который расширяет ILinkedList. Очевидно, что двусвязный список представляет собой односвязный список плюс некоторую дополнительную функциональность и может использоваться всякий раз, когда требуется односвязный список. Но поскольку тип узлов, используемых внутри каждого из них, различен, я не могу предположить, что двусвязный список является односвязным списком. Другими словами, я должен определить те же самые функции (просто скопировать и вставить без каких-либо изменений), которые находятся внутри односвязного списка только потому, что тип используемых узлов отличается. Если я позволю DoublyLinkedNode наследовать от Node и просто добавлю дополнительный указатель (prev) и определю узлы внутри интерфейса ILinkedList, если я определю тип узлов как Node, внутри DoublyLinkedList , когда я захочу обработать свои узлы как DoublyLinkedNode, мне придется привести свои узлы к DoublyLinkedNode*. Если я определю их как DoublyLinkedNode, то мне придется оставить указатель prev все время пустым внутри LinkedList. Решение (которого я не знаю, как достичь) - позволить DoublyLinkedNode наследовать от Node и DoublyLinkedList наследовать от LinkedList, определить head, tail, current внутри LinkedList иметь тип Node* и переопределить их как DoublyLinkedNode* внутри DoublyLinkedList. Таким образом, мне не нужно повторять один и тот же код внутри LinkedList, поскольку DoublyLinkedNode является дочерним для Node, и все операции, которые могут быть выполнены на Node, также могут быть выполнены на DoublyLinkedNode в любом случае. Также переопределите next внутри DoublyLinkedNode для типа DoublyLinkedNode*.

Answer 1

Связанный список - это набор узлов, так что каждый узел ссылается на следующий узел. Определение связанного списка не обязательно должно определять, что означает «узел»: разные типы узлов по-прежнему допускают структуру связанного списка. Отразите этот факт в своем коде: шаблон LinkedList над типом узла. Обратите внимание, что этот класс шаблона теряет способность создавать узлы: его конструктор не может создать начальный список и не может иметь PushBack. Это означает, что ваш код теперь имеет три класса: базовый LinkedList, содержащий «только для чтения», общие операции, а затем Singly - и Doubly - связанные подклассы.

struct IDoublyLinkedList : virtual ILinkedList // virtual to avoid multiple inheritance diamond problems!
{ /* etc */ };

template<typename N>
class LinkedList : public virtual ILinkedList
{
protected:
    N *head, *tail, *current;
    LinkedList(N *head, N *tail)
        : head(head), tail(tail), current(head)
    {
        std::cout << "Linked List Created.\n"; // std::endl is usually unnecessary; \n is portably handled anyway
        head->next = tail;
    }

public:    
    virtual int GetCurrent() override
    {
        return current->value;
    }

    virtual void SetCurrentToBegin() override
    {
        current = head->next;
    }

    virtual bool HasNext() override
    {
        return current != tail;
    }

    virtual void SetToNextNode() override
    {
        if (current == tail)
            SetCurrentToBegin();
        else
            current = current->next;
    }
};

struct SinglyLinkedList : LinkedList<Node>
{
    SinglyLinkedList() : LinkedList(new Node(nullptr, 0), new Node(nullptr, 0))
    {
        std::cout << "Singly Linked List Created.\n";
    }

    virtual void PushBack(int value) override
    {
        tail->value = value;
        tail->next = new Node{ nullptr, 0 };
        tail = tail->next;
    }
};

struct DoublyLinkedList : LinkedList<DoublyLinkedNode>, virtual IDoublyLinkedList
{
    DoublyLinkedList() : LinkedList(new DoublyLinkedNode(nullptr, nullptr, 0), new DoublyLinkedNode(nullptr, nullptr, 0))
    {
        std::cout << "Doubly Linked List Created." << std::endl;
        tail->prev = head;
    }

    virtual void PushBack(int value) override
    {
        tail->value = value;
        tail->next = new DoublyLinkedNode{ tail, nullptr, 0 };
        tail = tail->next;
    }

    // doubly-linked list specific methods...
};

Это ни в коем случае не идеально. Если вы продолжите пытаться вывести вещи из этих классов в общий класс, я думаю, что вы в основном сходитесь к использованию в STL распределителей и функторов.

Полный пример Godbolt