STL + Ordered set + without duplicates

Use std::set. It's ordered, and it does not allow duplicates.

The only downside is that you don't get random access to the elements though this was not specified as a requirement.

There is always Loki::AssocVector

Otherwise you can easily roll your own:

• use a std::vector or std::deque as the base container
• use lower_bound / upper_bound / equal_range and binary_search generic algorithms to look up an object
• also inplace_merge is great when you already know that the value is not present

But really, use a std::set :)

Insert into a set takes log(n). And the sort is free.

Insert into a vector (push_back) takes constant time. Sorting a vector takes n*log(n). But you still need to remove duplicates.

If you insert in one go and then sort, you can consider also vector. If you insert frequently set is the right one.