c – 为双向链表实现begin()和end()

发布时间：2020-12-16 09:50:37 所属栏目：百科来源：网络整理

导读：我编写了自己的容器类,其原始内部数据结构是std :: list.然后我需要创建自己的双向链表.我现在已经实现了我自己的双链表以及我自己的链表列表迭代器,但是我遇到问题让它表现得像std :: list,特别是使用begin()和end(). 根据我的理解,begin()应该指向第一个节

我编写了自己的容器类,其原始内部数据结构是std :: list.然后我需要创建自己的双向链表.我现在已经实现了我自己的双链表以及我自己的链表列表迭代器,但是我遇到问题让它表现得像std :: list,特别是使用begin()和end().

根据我的理解,begin()应该指向第一个节点,而end()应该指向一个元素超过最后一个元素.我需要确保当我调用end()时我可以减少回到有效的最后一个元素.我还需要确保我可以做正常的遍历,比如……

while (beg != end ) { do something; beg++; }

本质上,我的链表只使用包含数据元素的节点,指向前一节点的指针和指向下一个节点的指针.

当我第一次尝试实现我的end()时,我的最后一个节点的下一个指针是nullptr.它可以单独工作,但不会像stl一样工作.

关于如何以与标准库相同的方式实现begin()和end()的任何建议？

解决方法

您可以引入一个标记节点并具有循环链表.

草图：

class List
{
    private:
    struct Node {
        Node* previous;
        Node* next;

        Node() : previous(this),next(this) {}
    };

    struct DataNode : Node {
        int data;
    };

    public:
    class iterator
    {
        friend class List;

        private:
        iterator(Node* node) : m_node(node) {}

        public:
        iterator() : m_node(0) {}

        iterator& operator ++() {
            m_node = m_node->next;
            return *this;
        }

        int& operator * () {
            // Note: Dereferncing the end (sentinal node) is undefined behavior.
            return reinterpret_cast<DataNode*>(m_node)->data;
        }

        // More iterator functions.

        private:
        Node* m_node;
    };

    public:
    List() : m_sentinal(new Node) {}

    iterator begin() { return iterator(m_sentinal->next); }
    iterator end() { return iterator(m_sentinal); }

    iterator insert(iterator position,int data) {
        DataNode* data_node = new DataNode; // pass data
        Node* current = position.m_node;
        data_node->next = current;
        data_node->previous = current->previous;
        current->previous->next = data_node;
        current->previous = data_node;
        return iterator(current);
    }

    void append(int data) {
        insert(end(),data);
    }

    private:
    Node* m_sentinal;
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!