I fully agree, and yet I have so rarely had direct need for then that it is kind of scary when I see folks reach for them.
Worse, they are stupid common in interviews.
Worse, they are stupid common in interviews.
- Barring very degenerate inputs, prefix tries are usually faster than `std::set<std::string>`. And for longer strings, prefix tries are definitely faster than `std::unordered_set<std::string>`.
- The same ideas that apply to strings apply to bitvectors too, so we can handle arbitrary binary data the same way. (This gives us things like Patricia trees.)
- They're great for implementing immutable sets. In fact most functional languages use some variant of prefix tries for their set/map data structures.
And some real-world use cases:
- Symbol lookup in mach-O (macOS) binaries use prefix tries
- One of the fastest string sorting algorithms (burstsort) uses prefix tries
- Program analysis / abstract interpretation really benefits from immutable sets of bitvectors with fast union operations
- Pretty sure every typeahead / autocomplete implementation uses some kind of trie
- And for something a bit more esoteric: scrabble/boggle AIs use them too
I suspect you are right on most uses, though for many first iterations a simple ordered set works wonderfully well, and is much easier to think of.