c++ - 如何在 C++ 中实现减少内存使用的 Trie？

Question

我需要实现一个 trie 结构，以存储大约 30k 个字符串。现在，trie 结构看起来像这样

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

对于每个节点，由于固定大小的数组，我分配了太多空间，所以我的程序由于大量内存使用而崩溃。对于这个问题，我不能使用地图，这是迄今为止我找到的唯一解决方案。有人有其他提示吗？

谢谢。

Answer 1

使用std::unordered_map<char, TrieNode>而不是TrieNode *数组。

如果您需要对孩子进行排序，请使用std::map<char, TrieNode>.

如果不允许使用 STL，请自行实现 hashmap 或平衡二叉树类。