Блог пользователя daihan

How can i implement std::map C++ by myself without using stl ?
Автор daihan, 5 лет назад, По-английски

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 .

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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 ?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, just take a look at the Operations section.

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится -21 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          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.

          → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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>
→ Ответить