Hi, I'm just polishing up a few notes for an exam, and I have it written that the library needed for a bst is <map>, but none of my google hits indicated this is so. Mostly, it was people creating their own bst using studio bits, vector, etc.
I'm just trying to verify if the standard c++ library is map.
There is no "binary search tree" component in the C++ standard library, by any name.
It is true that std::map (and std::set) are typically implemented using a red-black tree, however, the types are written to act like maps and sets, not a BST. Their implementation is incidental; If a tree is required, use a type that behaves like one.
There is no binary search tree in the standard library.
Some standard library components are typically implemented using a self-balancing BST called a red-black tree. If such a tree exists at all in a standard library implementation, it is an internal detail not available to the library user.
In particular, while mapmay use a binary search tree on the inside, it is not a binary search tree.
Re-reading jjordan33’s initial post, it would appear that his/her professor has stated in class that some object in the Standard Library is a BST.
For purposes of the exam, yes, any associative container may be considered (equivalent to) a BST.
std::map <key, value> is an associative array using key to lookup value.
std::set <key_value> is an associative array using key_value to look up that same key_value.
As mbozzi indicated, implementations of the Standard Library typically use a red-black tree, which is a more advanced form of a BST.
So... close enough. Answer ‘yes’ on your exam and get an ‘A’, but know better for yourself.