c++memory-managementtrielow-memory

How to implement Trie with reduced memory usage in C++?

I need to implement a trie structure, to store approximately 30k strings. Right now, the trie structure looks like this

struct TrieNode {
        bool isWord=false;
        struct TrieNode* children[256];
};

For every node, i allocate too much space due to the array of fixed size, so my program is crashing because of huge memory usage. For this problem, i can't use maps, which was the only solution i've found so far. Does anybody have any other tips?

thanks.

Solution

  • Use std::unordered_map<char, TrieNode> instead of TrieNode * array.

    If you need children sorted, use std::map<char, TrieNode>.

    If you're not allowed to use STL, implement a hashmap or balanced binary tree class yourself.