实现双向链表的begin()和end()函数

Question

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

据我所知，begin()应该指向第一个节点，而end()应该指向最后一个元素的下一个元素。我需要确保在调用end()时，我可以回溯到有效的最后一个元素。我还需要确保我可以进行正常的遍历，比如...

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

基本上，我的链表只是使用包含数据元素、指向前一个节点和指向下一个节点的指针的节点。

当我首次尝试实现我的end()时，我只是将最后一个节点的下一个指针设置为nullptr。它可以运行，但不像STL那样工作。

如何实现与标准库相同的begin()和end()的建议？

- user2120910

---

http://www.cplusplus.com/reference/list/list/，http://www.cplusplus.com/reference/forward_list/forward_list/ - IdeaHat

旁注：您是否考虑过为 std::list 使用自定义分配器？ - user2249683

Answer 1

你可以引入一个哨兵节点并创建一个循环链表。

一个简略的示意图：

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

- user2249683

---

谢谢，哨兵的想法正是我所需要的。谢谢！ - user2120910

Answer 2

你的末尾节点不能为null，因为如果你只有null，就无法实现--（向后回溯）。你需要为结束节点创建一个哨兵，至少要知道如何返回列表中的最后一个节点。

- StilesCrisis

Answer 3

您的容器应该创建一个始终可用的结束节点。当容器为空时，这就是您从begin()返回的内容。您的最后一个真实节点应始终将其下一个节点设置为此结束节点。

- NickC