迭代地图

Question

在这个问题中，我不是问如何做，而是问它是如何完成的。
我正在尝试（作为练习）实现简单的地图，尽管我在实现链接和它们的行为（如何找到下一个位置插入新链接等）方面没有问题，但我遇到了如何实现迭代的问题一张地图。当您考虑并查看 std::map 时，该映射能够返回开始和结束迭代器。如何？特别是结尾？
如果地图是一棵树，你怎么能说这个地图的哪一个分支是终点呢？我只是不明白。如何迭代地图？从树顶开始然后呢？去把所有的东西都列在左边吗？但左边的那些节点也有到右边的链接。我真的不知道。如果有人可以向我解释它或给我一个链接以便我可以阅读它，我将非常高兴。

Answer 1

map 使用二叉搜索树实现。为了满足复杂性要求，它必须是自平衡树，因此通常使用红黑树，但这不会影响您迭代树的方式。

要按从最小到最大的顺序从二叉搜索树中读取元素，您需要对树执行中序遍历。递归实现非常简单，但在迭代器中使用并不实际（迭代器必须在内部维护一个堆栈，这将使其复制成本相对较高）。

您可以实现迭代的有序遍历。这是取自我不久前编写的树容器库的实现。 NodePointerT 是一个指向节点的指针，该节点有 left_、right_ 和 parent_ 类型的指针代码>NodePointerT。

// Gets the next node in an in-order traversal of the tree; returns null
// when the in-order traversal has ended
template <typename NodePointerT>
NodePointerT next_inorder_node(NodePointerT n)
{
    if (!n) { return n; }

    // If the node has a right child, we traverse the link to that child
    // then traverse as far to the left as we can:
    if (n->right_)
    {
        n = n->right_;
        while (n->left_) { n = n->left_; }
    }
    // If the node is the left node of its parent, the next node is its
    // parent node:
    else if (n->parent_ && n == n->parent_->left_)
    {
        n = n->parent_;
    }
    // Otherwise, this node is the furthest right in its subtree; we 
    // traverse up through its parents until we find a parent that was a
    // left child of a node.  The next node is that node's parent.  If 
    // we have reached the end, this will set node to null:
    else
    {
        while (n->parent_ && n == n->parent_->right_) { n = n->parent_; }
        n = n->parent_;
    }
    return n;
}

要找到 begin 迭代器的第一个节点，您需要找到树中最左边的节点。从根节点开始，沿着左子节点指针前进，直到遇到没有左子节点的节点：这是第一个节点。

对于 end 迭代器，您可以将节点指针设置为指向根节点或树中的最后一个节点，然后在迭代器中保留一个标志，指示它是一个结束迭代器（>is_end_ 或类似的东西）。

Answer 2

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

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

或者类似的东西。现在，mymap::begin() 可以返回这样的迭代器实例，n 将指向最左边的节点。 mymap::end() 可以返回带有 n 的实例，该实例可能指向根节点或其他一些特殊节点，从中仍然可以返回到最右边的节点，以便它可以满足从结束迭代器开始的双向迭代。

节点之间移动的操作（operators++() 和 operator--() 等）是从较小的值到较大的值遍历树，反之亦然。您可能在执行插入操作期间已经执行过的操作。

Answer 3

出于排序目的，映射的行为类似于排序的键/值容器（也称为字典）；您可以将其视为键/值对的排序集合，这正是查询迭代器时得到的结果。观察：

map<string, int> my_map;
my_map["Hello"] = 1;
my_map["world"] = 2;
for (map<string, int>::const_iterator i = my_map.begin(); i != my_map.end(); ++i)
    cout << i->first << ": " << i->second << endl;

就像任何其他迭代器类型一样，映射迭代器的行为类似于指向集合元素的指针，对于映射，这是一个 std::pair，其中 first 映射到键和 Second 映射到该值。

当您调用其 find() 方法或使用运算符[] 时，std::map 会在内部使用二分搜索，但您不需要直接访问树表示。

Answer 4

您可能会忽略的一个重要技巧是 end() 迭代器不需要指向任何内容。它可以是 NULL 或任何其他特殊值。

当迭代器越过映射末尾时，++ 运算符将迭代器设置为相同的特殊值。然后一切正常。

要实现++，您可能需要在每个节点中保留下一个/上一个指针，或者您可以通过将刚刚离开的节点与父级最右边的节点进行比较，沿着树向上查找下一个节点节点来查看您是否需要走到那个父节点等。

不要忘记，映射的迭代器应该在插入/擦除操作期间保持有效（只要您没有擦除迭代器的当前节点）。