Is map the library for Binary Search Trees?

[jjordan33]

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.

Thanks!!

[mbozzi]

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.

[jjordan33]

I didn't word it correctly.

What library is the #include < > out of the standard template libraries for a BST?

Thanks!

[Duthomhas]

There isn’t. The library is written to accomplish tasks, not to support a specific data structure.

If you want a BST, write one. (It is fun and easy!)

[mbozzi]

Read my previous post again. Trying again:

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 map may use a binary search tree on the inside, it is not a binary search tree.

[Duthomhas]

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.

[jonnin]

and, if you need a bin search (not the question, but for your own knowledge), http://www.cplusplus.com/reference/algorithm/binary_search/
in case you overlooked it (I often forget what is and what isnt in there).

[jjordan33]

Mbozzi, my mistake. I didn't realize that your answer was answering what I really needed.

It's as Duthomas said, my professor said to know the stl libraries for each data structure.

Y'all got me straightened out though. Thanks!

[mbozzi]

No worries! Good luck on your exam.