Need help to understand trie implementation using maps - c++

help
#1

Implementation Code

I’m new to cpp, please help me out with the queries below

  1. In above code what Trie* is doing in maps and while creating an object? I have heard about pointers but ‘*’ thing comes before the variable name, Any cpp resources regarding this will be helpful.
  2. which implementation is better, maps or using char array

If there is any video where implementation of trie using cpp is done please share it with me.
Thanks.

#2
  1. what trie* is doing :- each char is mapped to pointer to struct. Here trie is not var name. You put data type name while creating maps. So Trie* is like data type of whatever(struct) is used as value in map
  2. which is better:- ideally array shld be faster than unordered_map but they both hav same theoretical time complexity
    what shld u use?
    ans is none
    i hav tried many implementations and believe me this one is too slow and will give tle for most probs
    I know one implementation. Will find it and tell you

Edit:- here it is. Its cheng2014’s code
refer it
https://www.codechef.com/viewsolution/13476683

2 Likes
#3

Yes, pointer comes before the variable name and after the data type. ‘Trie’ here is a derived data type (structure) like int, char, float, etc.

I think you’re talking about this: "unordered_map<char, Trie*> map; "
Here Trie* is a pointer of type ‘Trie’, which means it can only store the addresses of Trie type data types.

I hope it is clear to you.

#4

Why cant we write *Trie instead.

#5

https://www.techiedelight.com/memory-efficient-trie-implementation-using-map-insert-search-delete/

#6

For int we write it as (int *)
for float (float *)
Similarly for Trie it is (Trie *)

#7

what about this implementation of trie

#8

see at line 16
I hate that new
its what slows everything
calling new or malloc for every insertion will do ur job but as i said may give tle for some probs
eg I tried a lot for this prob but could not do it
https://www.codechef.com/JUNE18B/status/SHKSTR,ganesh92

However this guy’s similar solution passed(with new op) with 0.73 sec
https://www.codechef.com/viewsolution/18725964

But the implementation I told you earlier took 0.17 sec
https://www.codechef.com/viewsolution/18749725

My pt is why to struggle when a simpler way is there

#9

hi, which code’s line 16 ?? Moreover, would you suggest to use a memory heavy implementation of trie (using 2d array ) than using so called memory efficient one ( using new + pointers) ?
Also, can you provide some tested results to show how much time is affected using the new implementation ? I faced some similar issue here. Can’t understand why so.

#10

The implemetation you provided, is it better than using the gp_hash instead of unordered_map described here. ???

#11

i was talking abt the one ayush asked
see his comment jst b4 mine
in that at line 16 they used new op which is slow

where is 2D array ?

and i did provide numbers to support my claim
see submissions i provided

#12

which code u r seeing
see my 1st comment on this topic
thats what i provided
it has arrays not maps
what can be faster that direct array access

#13

2d array implemetation of trie. There are more such implementations. I think the the efficient implementation (cheng2014’s code) that you gave, also has similar memory complexity. please let me know if I am wrong.

#14

I got that implementation while I was researching but couldn’t properly understand it
then I started stalking red coders and found cheng’s implementation
yup AFIK cheng wins
He doesn’t even knows that we are using his code :smile:
nor I hav guts to tag him

1 Like
#15

Lol…Why ??
If he comes to know, is there any problem ???
Though his implemetation seems time efficient, I am sure it is memory heavy, and that’s why map implementation is quite popular…But unfortunately, sometimes it gives strange results :sleepy::sleepy::sleepy:

#16

u can modify his solution to hav maps
but it will be comparatively slow
i said not to use new op
for that what cheng did is declared a global array at once

1 Like
#17

hey, since I switched to CPP, I was thinking of just using the code without understanding it completely at the moment, is it fine? I mean for solving the questions including trie.

#18

are u asking for permission?
its upto you

#19

No would it be helpful, I mean if I will be able to solve question without understanding implementation

#20

sometimes I do that too
we all doing CP for fun right?
so do whatever feels right
but you will hav more control over ur code if you know whats going in it
use it for now, get those green ACs and take ur time to understand it
many people will not like this way but I find its okk

1 Like