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.

Why is std::map implemented as red-black tree?

user3920237
– user3920237

2014-08-24 02:32:42 +00:00
Commented Aug 24, 2014 at 2:32 — user3920237
– user3920237, Commented Aug 24, 2014 at 2:32

Benjamin Lindley · Accepted Answer · 2014-08-24 02:56:49Z

18

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.

edited Aug 24, 2014 at 2:56

answered Aug 24, 2014 at 2:51

Benjamin Lindley

104k11 gold badges210 silver badges285 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Dimitrios Bouzas · Accepted Answer · 2014-08-24 02:33:31Z

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.

answered Aug 24, 2014 at 2:33

Dimitrios Bouzas

43.1k11 gold badges103 silver badges177 bronze badges

3 Comments

user982740 Over a year ago

cplusplus.com/reference/map/map "Maps are typically implemented as binary search trees." Okay, lets say if it is implemented using BST, my question is how it is implemented. How the BST node look like? Where do the keys go?

Dimitrios Bouzas Over a year ago

@user982740 A red–black tree is a data structure which is a type of self-balancing binary search tree. How is implemented is up to the implementer. To which implementation are you referring (e.g., GCC, Clang, VS)?

WhozCraig Over a year ago

@user982740.... "Maps are typically implemented as binary search trees" appears nowhere in the C++ standard. Implementation of a std::map<> is left to the implementation, so long as it compiles with the rules dictated by the standard for (a) Associative containers (C++11 §23.2.4) and (b) the specific additional requirements and exceptions for std::map<> (C++11 §23.4.4).

Collectives™ on Stack Overflow

std::map and binary search tree

2 Answers 2

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related