4 ms·
Ah, yes that's true, good point. If that is the goal, BST sort might be a good idea as well (put elements into a balanced binary search tree as you receive the
by kadoban 7y ago
Ah, yes that's true, good point.
If that is the goal, BST sort might be a good idea as well (put elements into a balanced binary search tree as you receive them). Not _quite_ the same semantics (you don't have an array exactly at each step), but much faster asymptotics and should be able to answer any queries you'd be doing anyway.
- nwallin 7y agoYes, exactly. One thing to keep in mind is that it's surprisingly common for a sorted array to outperform a binary search tree because of cache locality and pointer indirection being slow, even though random inserts into arrays are slow. Especially for small sets or when reads greatly outnumber writes. Boost has flat_map and flat_set for this.