c++ - 如何在 map 中实现终点？

Question

我正在为练习实现一个 map ，我正处于必须迭代它(完成和工作)的地步，但问题是我不知道如何实现最后一个元素(大概空链接)。我在想我会附加一些特殊类型的链接(基本链接的后代)，然后将其附加到最后一个元素，这样我就能够检测到我是否在真正的最后一个元素上。我想知道您对这个想法有何看法，并且可能会从您那里听到一些更传统和经常使用的技术来实现这一点。

Answer 1

如果您的迭代器不是双向的，那么您实际上不需要 end 指向任何东西(在这种情况下只需使用 NULL)。 end() 只需要在双向迭代器的情况下具有真实值，因为在这种情况下，您需要能够从 end() 向后移动到列表的开头。

GNU C++ 库(如果你将 std::map 与 GCC/G++ 一起使用，你会得到什么)将 end() 实现为指向根节点的指针树。这样，如果在双向迭代器中使用，您可以访问根节点以找到树中最右边的节点(即 end() 之前的节点)。

编辑解释一棵空树

map 本身总是包含一个树根节点(它不是指针，它是一个普通成员节点)。当树为空时，该节点的两个叶子都指向该节点本身(end() 也是如此)。所以在空树中 begin() 会返回与 end() 相同的东西。

所以我们有这样的东西:

template<class T> struct node_t {
    T data;
    node_t *left;
    node_t *right;
};


template<class T> class map {
    private:
        node_t root;
    public:
        // ...
        iterator begin() { return iterator(root.left); }
        iterator end() { return iterator(&root); }
}