daihan's blog

How can i implement std::map C++ by myself without using stl ?
By daihan, 5 years ago, In English

Very often we use map c++ and solve many complex problem easily . But what if i am not allowed to use any stl and i have to implement map::std c++ by myself . Which data structure should i use ? Should i use Red black tree ? Is it really possible to implement map using red black tree ? If there are alternative way then tell me .

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

std::map is basically the same as a std::set of pairs (key, value) where we compare these pairs only by the key.

So to implement std::map, you'd just need to use a balanced binary search tree (BBST) such as red-black trees (with each node storing the key and the value). I think most STL implementations of std::map use red-black trees.

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

If you have to do that yourself during contest, treap is what you need, just cause it's (imho) easier to implement than other BBSTs. Also if you learn how to do that you'll also be able to implement an implicit treap which is a really powerful data structure.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    nmakeenkov Ow i heard the name for the first time . Do you meant that : https://cp-algorithms.com/data_structures/treap.html ?

    Can i implement set::std using treap ?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, just take a look at the Operations section.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -21 Vote: I do not like it

        nmakeenkov can i use treap for implementing std::set c++?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          As I already said take a look at the Operations section.

          Insert(X,Y) in O(logN).

          Adds a new node to the tree. One possible variant is to pass only X > and generate Y randomly inside the operation (while ensuring that it's different from all other priorities in the tree).

          Search (X) in O(logN).

          Looks for a node with the specified key value X. The implementation is the same as for an ordinary binary search tree.

          Erase (X) in O(logN).

          Looks for a node with the specified key value X and removes it from the tree.

          Also for std::set you'll need lower/upper bound, that is also $$$O(logN)$$$ by just trivially going into the tree. Iterators are also easy to implement (if you need that), but probably all you'll need will be the smallest/largest element (i.e left/right-most nodes). But it's the same as with any BBST as mentioned above.

          → Reply
»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

I presume Samsung is gonna visit your campus for hiring and since it does not allow using <bits/stdc++.h> you are asking this question. The tricky part is you can use all the STL in Samsung test for that you should not use .h header files. If you want to use map you must use 

#include <map>
→ Reply