[saagarjha]

I had to implement a trie for an Aho-Corasick implementation a while back, and I just used a std::unordered_set<unichar, std::unique_ptr<trie_node>> to store the children (this was Objective-C++, so I was using UTF-16 characters taken from an NSString). Worked well enough for the effort I put into it.

[rcfox]

So you ended up using a tree to hold your tree nodes. I guess that was good enough for your purpose, but the article is discussing an optimized implementation.

[saagarjha]

std::unordered_map is general a hash table, is it not?

[rcfox]

Sorry, I switched set and unordered set in my mind. Still, a generic hash table isn't going to match a tailored data structure.

[saagarjha]

I mean, it might. I only had to construct one trie, and I used it hundreds of millions of times, so O(1) child (hash) lookup ended up being faster than the O(log(n)) binary search lookup, at best, from the data structure described in the article. And since the data structure in the article wastes some space as well, I may have even used a similar amount of storage.