std::map and binary search tree

Question

I have read that std map is implemented using binary search tree data structure.

BST is a sequential data structure (like elements in an array) which stores elements in a BST node and maintains elements in their order. For e.g. if element is less than node, store it in left of node and if it is larger than node, store it in right of node. With this approach, we achieve O(log n) complexity for various operations like search, insert etc.

However, std map is an associate container. We have a key and a value pair to insert. Is it really implemented using BST and, if yes, how? In BST, we don't have any key or value. It is a kind of standard container.

I am little confused. Please help me in providing clarification. Its not affecting my work but I want to understand them better. Thanks for your help.

Answer 1

A node in a map will generally looks something like this:

struct node
{
    node* left;
    node* right;

    Key_type key;
    Value_type value;
};

You have a general understanding of how a BST works, as you stated:

if element is less than node, store it in left of node and if it is larger than node, store it in right of node.

In the case of my node struct, the "element" is the key member. So keys are compared to determine the organization of the tree. Nodes who's keys compare less than that of a parent node are placed on the left, and nodes who's keys compare greater being placed on the right. The value does not take part in the organization of the tree, it is just supplementary data. It is associated with the key simply by being part of the same struct.

Answer 2

There's nothing in the C++ standard that dictates how a std::map should be implemented. Consequently, the underlying data structure of a std::map is a decision that has to be taken by the implementer.

Most implementations however, implement std::map as a red-black tree.