c++ - 集合中的迭代器如何工作

Question

我想知道在 C++ 的 STL 中设置的迭代器是如何工作的。我猜该集合是使用二叉搜索树实现的，这意味着迭代器会按顺序遍历这棵树。但我的问题是，他们什么时候进行这种遍历，在一开始当我们喜欢 它= s.begin() 并将遍历的指针存储在内部堆栈中，并在迭代器中的每个增量上仅引用此数据结构或者迭代器中的增量对树进行新的中序遍历。

我的意思是当我们初始化时

     set<int>  s;
     set<int>::iterator it;

 //and then use it like:

      for(it = s.begin(); it!=s.end(); )
      {
           dosth();
           ++it;     // does this do a inorder traversal of the tree again to find the next 
                     // node or it gets the next node in the tree by reading the internal
                    // data structure(of inorder traversal) which is created when we do   s.begin().
      } 

Answer 1

这是一个有趣的问题。正如 Nicol 指出的那样，它依赖于实现，在实现自己的集合时，您必须决定是喜欢更小的迭代器还是更快速的遍历(您可以将更多数据放入迭代器以加快速度)。

在我的平台上(64 位)std::set<T>::iterator是 8 字节大小，这表明它只保留指向实际节点的指针。如果集合是使用某种树实现的，那么迭代器的递增绝对不是 O(1) 操作，需要遍历最多 log(N) 个附加节点(如果谈论平衡树)。我还检查了 ++it 的速度针对不同节点的操作，并且它不是恒定的，这表明额外的遍历。对于通用集容器来说完全没问题，因为它满足了树遍历复杂性的期望，并且人们通常认为迭代器越小越好。如果你实现标准的递归树遍历，它是完全一样的，你只是在堆栈上隐藏了额外的节点访问。

看看Implementing an iterator over a binary search tree获取有关实现您自己的树迭代器的更多详细信息。