I’m new to cpp, please help me out with the queries below
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.
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.
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
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
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.
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
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.
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.
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
nor I hav guts to tag him
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
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
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.
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