algorithms

algorithms copied to clipboard

All binary search tree iterators support the increment and decrement operators (delegating to the tree's inorder_successor and inorder_predecessor methods, except for the iterator returned by end(). The end() iterator is currently naively implemented, simply wrapping a null node.

In order to support decrementing the end iterator (i.e., end()--), this seems to require some sort of dummy-max node to be maintained as a special right-child of the maximum node in the tree. This will probably not be too hard to implement, but it does interact with at least the tree's insert logic. We should consider doing it so that we can make the binary_search_tree<T>::iterator support the std::bidirectional_iterator_tag.