C++ STL"set"和"map"支持插入,擦除和查找操作的logarthmic最坏情况时间.因此,底层实现是二进制搜索树.实现set和map的一个重要问题是为迭代器类提供支持.当然,迭代器内部维护一个指向迭代器中"当前"节点的指针.困难在于有效地推进到下一个节点.
我的问题是
如果"set"和"map"实现了二进制搜索树,我们如何使用迭代器类前进到下一个节点,即我们返回++或 - 即,是左子树还是右子树？
一般来说,大多数STL实现BST以及如何实现++或 - 迭代器？
谢谢!
C++规范中没有任何内容需要使用二叉树.因此,++和 - 是根据元素序列定义的.map并set存储有序的元素序列.因此,++将转到下一个元素,并且 - 将转到上一个元素.下一个和前一个元素由元素的顺序定义.
请注意,虽然C++规范不需要使用二叉树,但特定的性能要求几乎强制使用二叉树.
通常,它们使用Red/Black自平衡二叉树中的一些.