Is there a sorted container in the STL?
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
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.