c++ - 如何迭代以获取自定义 map ？

Question

我希望构建自己的 map 类。 (其行为与 C++ STL 完全相同)我希望能够按键值顺序遍历所有元素。

我将我的 map 实现为一个不平衡的二叉搜索树。

所以我的问题是如何有效地执行迭代器增量。一种低效的方法是遍历树中的每个元素以找到下一个最低的键。有更快的方法吗？

谢谢。

Answer 1

这在一定程度上取决于实现细节。如果你的不平衡二叉搜索树的节点有一个“父”指针，你可以用它来遍历它。++iterator 的实现可能看起来像这样:

if (current_node.has_right_child()) {
  // We go to the right subtree of the current node and
  // take the smallest element of that subtree.
  current_node = current_node.right_child();
  while (current_node.has_left_child()) {
    current_node = current_node.left_child();
  }
} else {
  // We have to go up. If the current element is the left child of the parent,
  // we can just go to the right child of the parent.
  // If it is the right child, we have to go further up
  while (true) {
    if (!current_node.has_parent()) {
      // We got up to the root and never found a right child.
      // So we are at the end of the iteration.
      current_node = NULL;
      break;
    }
    Node* parent = current_node.parent();
    bool is_left_child = parent.left_child() == current_node;
    current_node = parent;
    if (is_left_child) {
      // if this was the left child, then the parent is the correct next element.
      break;
    }
    // if this was the right child, we have to go further up
    // until we leave this subtree, so we continue iterating.
  }
}

如果您的二叉树没有父节点，您可以将父节点存储在迭代器中。 IE。你可以维护一个 vector parent ；您将当前节点的父节点存储到根目录中。如果仍然需要这个，我可以提供一个实现，但是因为你用父指针编辑了我的“非父指针”版本，所以看起来你有父指针。所以我把它留下了。