链表end()迭代器实现困惑及operator--实现疑问

1. 实现end()迭代器 #

end()代表尾后迭代器，它不需要指向真实内存位置，只需要一个能标识“超出最后一个元素”的状态即可。在链表中，这个状态可以直接用nullptr来表示：

实现代码 #

在List类中补充end()函数：

Iterator end()
{
    return Iterator(nullptr);
}

注意：尾后迭代器不允许被解引用，所以要给operator*加安全判断，避免空指针访问：

T& operator*()
{
    if (!m_node)
        throw std::runtime_error("Cannot dereference end iterator");
    return m_node->value;
}

另外，你的insert_back实际是头插逻辑（新节点放在链表头部），导致begin()返回的是链表尾节点，和标准容器begin()指向第一个元素的行为不符。建议修正为真正的尾插逻辑，同时给List类添加尾节点指针，避免每次找尾遍历：

// 修改List的成员变量
private:
    std::shared_ptr<Node<T>> m_head = nullptr;
    std::shared_ptr<Node<T>> m_tail = nullptr;

// 修正insert_back为尾插
void insert_back(const T value)
{
    auto node = std::make_shared<Node<T>>(value);
    if (!m_head)
    {
        m_head = node;
        m_tail = node;
    }
    else
    {
        m_tail->next = node;
        m_tail = node;
    }
}

// 此时begin()直接返回头节点
Iterator begin()
{
    return Iterator(m_head);
}

2. 实现operator--（反向迭代） #

单链表节点只有next指针，没有前驱指针，实现反向迭代有两种方案：

方案一：改成双向链表（推荐） #

给Node类添加前驱指针，这样迭代器可以直接通过前驱指针定位上一个节点，时间复杂度O(1)：

template<typename T>
class Node
{
public:
    Node(const T _value) : value(_value) {}

    T value;
    std::shared_ptr<Node<T>> next = nullptr;
    std::weak_ptr<Node<T>> prev; // 用weak_ptr避免循环引用
};

// 修正insert_back，设置前驱指针
void insert_back(const T value)
{
    auto node = std::make_shared<Node<T>>(value);
    if (!m_head)
    {
        m_head = node;
        m_tail = node;
    }
    else
    {
        node->prev = m_tail;
        m_tail->next = node;
        m_tail = node;
    }
}

// 在Iterator中实现operator--
Iterator& operator--()
{
    if (m_node)
        m_node = m_node->prev.lock(); // 从weak_ptr转为shared_ptr
    return *this;
}

// 后置--运算符
Iterator operator--(int)
{
    Iterator temp = *this;
    --(*this);
    return temp;
}

方案二：单链表下的低效实现（不推荐） #

如果坚持用单链表，只能通过遍历链表找到当前节点的前驱，时间复杂度O(n)，仅适合小链表场景：

// 修改Iterator，持有链表头指针
class Iterator
{
public:
    Iterator(std::shared_ptr<Node<T>> node, std::shared_ptr<Node<T>> head) 
        : m_node(node), m_head(head) {}

    Iterator& operator--()
    {
        if (!m_node)
        {
            // end()迭代器--后指向尾节点
            m_node = m_head;
            while (m_node && m_node->next)
                m_node = m_node->next;
            return *this;
        }
        if (m_node == m_head)
        {
            // 头节点的前一个是end()
            m_node = nullptr;
            return *this;
        }
        // 遍历找前驱节点
        auto prev = m_head;
        while (prev && prev->next != m_node)
            prev = prev->next;
        m_node = prev;
        return *this;
    }

private:
    std::shared_ptr<Node<T>> m_node;
    std::shared_ptr<Node<T>> m_head; // 保存链表头指针
};

// 修改List的begin()和end()，传入头指针
Iterator begin()
{
    return Iterator(m_head, m_head);
}

Iterator end()
{
    return Iterator(nullptr, m_head);
}

内容的提问来源于stack exchange，提问作者KcFnMi