4 ms·
Do you mean using an array instead of map for storing pointer to the next node? Conceptually, an array is just a map that uses an integer and identity function
by panda88888 7y ago
Do you mean using an array instead of map for storing pointer to the next node? Conceptually, an array is just a map that uses an integer and identity function and the hashing function.
In practice, the map implementation trades speed for space efficiency.
For an array implementation, the entire array of pointers has to be allocated for all possible character set for each node. This leads to wasted space since trie nodes usually only have child pointers for a subset of character sets. Map implementation don’t have to allocate space to store pointers for the entire character set, so it can be more space efficient. However, the hash function is probably an order of magnitude more cycle than that for array (usually just the ascii code with offset and some bound checking).
- stabbles 7y agoWell, an unordered_map / hash map is in the end backed by a dynamically sized array, so "Map implementation don’t have to allocate space to store pointers for the entire character set" might not be true for two reasons: (1) there _is_ an additional allocation* that is not present in the std::array case for the dynamic array and (2) there is a default size of this unordered_map when nothing has been inserted yet, are you sure it's smaller than 256 elements? * Well, maybe there is something like small vector optimization going on for small unordered_maps, though.
- panda88888 7y agoAgreed. For the standard implementation, the dynamically allocated array may be bigger than 256. I would imagine, since it’s C++, it’s probably possible to set the initial array size.