Re: check if a variable is inside a set of values
Sounds like it's just syntactic sugar wrapping the vector/algorithm approach. Still, keeping the interface consistent is a nice touch since it would make timing the speed difference between the approaches similar.
I'd imagine that inserting everything via the set interface would be O(n^2 lg n). However, as stated in the link, you can use the "low level interface" (read: underlying vector push_back) to insert everything in O(n lg n) by only doing the sort once at the end rather than on every insertion.
Re: check if a variable is inside a set of values
Quote:
Originally Posted by
Lindley
Sounds like it's just syntactic sugar wrapping the vector/algorithm approach.
Well it's kinda like a priorty_queue. All it does is wrap another container, and provide a modified interface for a specific use.
So yeah, syntactic sugar, but that's what we're asking for.
Quote:
Originally Posted by
Lindley
I'd imagine that inserting everything via the set interface would be O(n^2 lg n). However, as stated in the link, you can use the "low level interface" (read: underlying vector push_back) to insert everything in O(n lg n) by only doing the sort once at the end rather than on every insertion.
You are probably right, I didn't do a full study of that container. but as said previously, the goal of such a container is really to be filled only once, and then never touched again. So being able to optimize that phase is just the cherry on the cake :).
PS. If you know what you are doing, you could fill it in o(n) by using insertion with hint. That would require the input being pre-sorted, but not an impossible assumption. But again, who cares?
