Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why aren't C++ maps implemented as tries?

Tries are very fast data structures. Looking up a word takes O(sizeofword) time, while std::maps are self-balacing trees. Why aren't the standard C++ map templates implemented with tries. Is there any specific reason? Are there any tradeoffs of using a trie instead of a self-balancing tree?

like image 931
Global Warrior Avatar asked Jan 20 '12 09:01

Global Warrior


People also ask

How is map implemented C++?

The container map is an associative container included in the standard library of C++. The definition of this class is in the header file “map” of the namespace std. STL Map Internal Implementation: It's implemented as a self-balancing red-black tree.

Does map use bst?

I have read that std map is implemented using binary search tree data structure. BST is a sequential data structure (like elements in an array) which stores elements in a BST node and maintains elements in their order.

How does STD map work?

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare . Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.


1 Answers

Tries can only be used when the keys to be stored can be processed digit by digit or character by character. The C++ std::map and std::set are designed to work with any comparable elements as keys, and thus can't be implemented in a way that processes the keys character by character. They instead (typically) use balanced binary search trees, which don't need to introspect on the keys and can instead just use a comparator to do fast lookups.

If you know for sure that certain properties hold for your keys, you can in some cases do even better than tries (see the van Emde Boas tree for an example). However, library designers have to design for a lot of use cases and thus may need to pick options that are slower than the absolutely best option because they need to handle the largest possible number of options.

Additionally, it's actually perfectly possible that a conforming C++ implementation contain a specialization of std::map or std::set that uses a trie when the keys are strings. I don't believe that any do, but it is in theory possible.

Hope this helps!

like image 133
templatetypedef Avatar answered Sep 22 '22 11:09

templatetypedef