Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Binary search tree should support std::bidirectional_iterator_tag #146

Open
domfarolino opened this issue Feb 1, 2020 · 0 comments
Open

Comments

@domfarolino
Copy link
Owner

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant