3 ms·
Is there any reason why you can't use a sorted vector (possibly of pointers into pooled memory actually storing the strings)? Would this be necessarily worse p
by daemin 11y ago
Is there any reason why you can't use a sorted vector (possibly of pointers into pooled memory actually storing the strings)?
Would this be necessarily worse performance than a Trie or Hash ?
- gdwatson 11y agoThe sorted vector has O(n) insertion cost. A hashtable has O(1) insertion, possibly amortized; a trie, if I understand correctly, has an insertion cost proportionate to the length of the string, assuming a fixed alphabet. So as the vector gets larger the amount of time it takes to insert an item will grow at the same rate as the vector does, but the cost to insert the item into a hashtable or trie will remain about the same.