Is there a sorted container in the STL?

Question

Is there a sorted container in the STL?

What I mean is following: I have an std::vector<Foo>, where Foo is a custom made class. I also have a comparator of some sort which will compare the fields of the class Foo.

Now, somewhere in my code I am doing:

std::sort( myvec.begin(), myvec.end(), comparator ); 

which will sort the vector according to the rules I defined in the comparator.

Now I want to insert an element of class Foo into that vector. If I could, I would like to just write:

 mysortedvector.push_back( Foo() ); 

and what would happen is that the vector will put this new element according to the comparator to its place.

Instead, right now I have to write:

myvec.push_back( Foo() ); std::sort( myvec.begin(), myvec.end(), comparator ); 

which is just a waste of time, since the vector is already sorted and all I need is to place the new element appropriately.

Now, because of the nature of my program, I can't use std::map<> as I don't have a key/value pairs, just a simple vector.

If I use stl::list, I again need to call sort after every insertion.

Answer 1

Yes, std::set, std::multiset, std::map, and std::multimap are all sorted using std::less as the default comparison operation. The underlying data-structure used is typically a balanced binary search tree such as a red-black tree. So if you add an element to these data-structures and then iterate over the contained elements, the output will be in sorted order. The complexity of adding N elements to the data-structure will be O(N log N), or the same as sorting a vector of N elements using any common O(log N) complexity sort.

In your specific scenario, since you don't have key/value pairs, std::set or std::multiset is probably your best bet.