check if a variable is inside a set of values

[Lindley]

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.

[monarch_dodra]

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.

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?