The 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 proport

The 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.