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.

Koetke

What about std::set ? – Covenantee

If you knew where it would go you could use insert() – Bauxite

@us2012, I looked at std::set. Problem is those object will be presented in a grid, where user can sort them based on all class member and modify them in any way they see fit. As std::set members are const by definition, this container is not for me. – Koetke

How about boost::multimap? – Gayl

See as well advantages of std::set vs vectors or maps as well as Using custom std::set comparator. – Exequies

@Koetke If the user can modify the values, then they can make the container unsorted. That's why std::set's elements are const – Onceover

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.

Holdfast

also priority_queue? – Pea

I agree with @LushaLi: the accepted answer should also point out to std::priority_queue, but also to std::make_heap and std::push_heap, std::pop_heap dependencies. – Margaritamargarite

@LushaLi std::priority_queue isn't a Container, you can only observe the top element – Onceover

interesting, though, is that none of those admit redundant keys in a way that is easy to use. multimap is the only one that allows redundant keys, but it's not easy to use as a list. – Wisnicki

@Wisnicki multiset also admits redundant keys (set's keys are also it's values) – Onceover

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

Stromboli

Hey, can we also use lower_bound() function in this set?? cuz I was trying something similar to this but it says that no matching member function – Pycnometer

@ArshpreetSingh: Yes, because both std::set and std::multiset provide a lower_bound() function. If you can't get that to work, you might consider creating a minimal reproducible example and asking a new question. – Stromboli

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

Astral

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);

Lurie