If we declare trie,

struct trie{
    int count;
    trie* next[26];
};

We use like that, but this approach takes much memory every time we put words, so new trie established. If we make one new trie, we must make 26 spaces due to that array.

Why we don't use unordered_map for "next", so we make space as needed every time we put the words in trie?

So i use

struct trie{
    int count;
    unordered_map <char,trie*> next;
};

and it works.

Is there any disadvantage for unordered_map than arr[26]?

If we declare trie,

struct trie{
    int count;
    trie* next[26];
};

We use like that, but this approach takes much memory every time we put words, so new trie established. If we make one new trie, we must make 26 spaces due to that array.

Why we don't use unordered_map for "next", so we make space as needed every time we put the words in trie?

So i use

struct trie{
    int count;
    unordered_map <char,trie*> next;
};

and it works.

Is there any disadvantage for unordered_map than arr[26]?

• c++
• trie

• 1 Very little overhead with a plain array compared to a hash-table (which is what std::unordered_map is)? Simplicity? – Some programmer dude Commented Jan 20 at 11:42
• check out this question, can have all answers you want, if not duplicated stackoverflow.com/questions/2196995/… – quintumnia Commented Jan 20 at 11:44
• thanks. so maps are lot lot more inefficient than simple array in itself. and that's why people use array than map. although it makes 26 new spaces every time new trie formed. – 유정현 Commented Jan 20 at 11:52
• 1 @Caleth Note "it alone is about the same size". I'm saying that the fixed memory overhead even before allocations could be more or less equal to the size of the array. – HolyBlackCat Commented Jan 20 at 12:19
• 1 You will have to aske the designer of that piece of code. While map might be more readable to you it might lack in other areas (like performance). – Pepijn Kramer Commented Jan 20 at 13:40

1 Answer 1

Not sure why this is downvoted, because it's a valid question, and there seems to be no duplicate question yet.

A std::unordered_map<char, trie*> will take sizeof(std::unordered_map<char, trie*>) bytes of memory in the trie object itself, independent of std::unordered_map<char, trie*>::size(). In addition, it will take a several extra bytes per trie* in that std::unordered_map. 16 or 32 bytes per entry would be perfectly normal.

So it's very well possible that it takes more bytes in memory than that trie*[26]. Even if it did save memory, the trie*[26] has an additional advantage of being contiguous in memory, quite possible on a single cache line. It's also a bit simpler and uses less instructions in the compiler executable.