在地图上迭代 [英] Iterating over a map

问题描述

在这个问题我不是问怎么做，但它是如何做。

我试图（作为一个excersise）实现简单的地图，虽然我没有问题的实现链接和他们的行为（如何找到下一个地方插入新的链接等）我坚持的问题如何实现迭代在地图上。当你考虑它，看看std :: map这个地图能够返回开始和结束迭代器。怎么样？特别是结束？

如果地图是树，你怎么能说这个地图的哪个分支是结束？我只是不明白。如何迭代地图？从树的顶部开始，然后什么？去和列出左边的一切？但是左边的那些节点也有到右边的链接。我真的不知道。如果有人可以向我解释或给我一个链接，我会很高兴，所以我可以阅读它。

In this question I'm not asking how to do it but HOW IS IT DONE.
I'm trying (as an excersise) implement simple map and although I do not have problems with implementing links and they behavior (how to find next place to insert new link etc.) I'm stuck with the problem how to implement iterating over a map. When you think about it and look at std::map this map is able to return begin and end iterator. How? Especially end?
If map is a tree how can you say which branch of this map is an end? I just do not understand it. An how to iterate over a map? Starting from the top of the tree and then what? Go and list everything on the left? But those nodes on the left have also links to the right. I really don't know. I will be really glad if someone could explain it to me or give me a link so I could read about it.

推荐答案

地图的迭代器的表示完全取决于您。我认为应该足够使用一个单一的包指针到节点。例如：

The representation of your map's iterator is totally up to you. I think it should suffice to use a single wrapped pointer to a node. E.g.:

template <typename T>
struct mymapiterator
{
  typename mymap<T>::node * n;
};

或类似的东西。现在， mymap :: begin（）可以返回这样的迭代器实例， n 将指向最左边的节点。 mymap :: end（）可以返回 n 指向根或者其他特殊节点的实例仍然可以回到最右边的节点，使得它可以满足来自结束迭代器的双向迭代。

Or something similar. Now, mymap::begin() could return such instance of the iterator that n would point to the leftmost node. mymap::end() could return instance with n pointing to root probably or some other special node from which it is still possible to get back to rightmost node so that it could satisfy bidirectional iteration from end iterator.

在节点之间移动的操作（ operator ++ ）和 operator - （）等）是关​​于遍历树从较小值到较大值，反之亦然。您可能已经在插入操作实现期间实现的操作。

The operation of moving between the nodes (operators++() and operator--(), etc.) are about traversing the tree from smaller to bigger values or vice versa. Operation that you probably have already implemented during insertion operation implementation.

这篇关于在地图上迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！