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.

Answer 2

I'd like to expand on Jason's answer. I agree to Jason, that either std::set or std::multiset is the best choice for your specific scenario. I'd like to provide an example in order to help you to further narrow down the choice.

Let's assume that you have the following class Foo:

class Foo {
public:
    Foo(int v1, int v2) : val1(v1), val2(v2) {};
    bool operator<(const Foo &foo) const { return val2 < foo.val2; }
    int val1;
    int val2;
};

Here, Foo overloads the < operator. This way, you don't need to specify an explicit comparator function. As a result, you can simply use a std::multiset instead of a std::vector in the following way. You just have to replace push_back() by insert():

int main()
{
    std::multiset<Foo> ms;
    ms.insert(Foo(1, 6));
    ms.insert(Foo(1, 5));
    ms.insert(Foo(3, 4));
    ms.insert(Foo(2, 4));

    for (auto const &foo : ms)
        std::cout << foo.val1 << " " << foo.val2 << std::endl;

    return 0;
}

Output:

3 4
2 4
1 5
1 6

As you can see, the container is sorted by the member val2 of the class Foo, based on the < operator. However, if you use std::set instead of a std::multiset, then you will get a different output:

int main()
{
    std::set<Foo> s;
    s.insert(Foo(1, 6));
    s.insert(Foo(1, 5));
    s.insert(Foo(3, 4));
    s.insert(Foo(2, 4));

    for (auto const &foo : s)
        std::cout << foo.val1 << " " << foo.val2 << std::endl;

    return 0;
}

Output:

3 4
1 5
1 6

Here, the second Foo object where val2 is 4 is missing, because a std::set only allows for unique entries. Whether entries are unique is decided based on the provided < operator. In this example, the < operator compares the val2 members to each other. Therefore, two Foo objects are equal, if their val2 members have the same value.

So, your choice depends on whether or not you want to store Foo objects that may be equal based on the < operator.

Code on Ideone

Answer 3

C++ do have sorted container e.g std::set and std::map

int main() 
{ 
    //ordered set
    set<int> s; 
    s.insert(5); 
    s.insert(1); 
    s.insert(6); 
    s.insert(3); 
    s.insert(7); 
    s.insert(2); 

    cout << "Elements of set in sorted order: "; 
    for (auto it : s) 
        cout << it << " "; 

    return 0; 
} 

Output: Elements of set in sorted order: 1 2 3 5 6 7

int main() 
{ 
    // Ordered map 
    std::map<int, int> order; 

    // Mapping values to keys 
    order[5] = 10; 
    order[3] = 5; 
    order[20] = 100; 
    order[1] = 1; 

   // Iterating the map and printing ordered values 
   for (auto i = order.begin(); i != order.end(); i++) { 
       std::cout << i->first << " : " << i->second << '\n'; 
} 

Output:
1 : 1

3 : 5

5 : 10

20 : 100

Answer 4

In your case, you should use std::lower_bound: it returns an iterator pointing to the first element in the range which does not compare less than the value. And then insert at this place.

std::sort(myvec.begin(), myvec.end(), comparator);
// Now, your vector is sorted, your mission: keep it sorted.
// ... 
// Insert new element:
assert(std::is_sorted(myvec.begin(), myvec.end(), comparator));
Foo new_value;
auto const new_pos = std::lower_bound(myvec.begin(), myvec.end(), new_value, comparator);
myvec.insert(new_pos, new_value);