C++ STL SET

general
, ,
1

When we insert an element in set, it is logarithmic in complexity. So if I insert a pair< string,string > or pair < string,int > or some other pair, SET sorts according to the key first and then according to the value.So while sorting according to two parameters that is key and value, does the insertion is still logarithmic? In other words does the pair also get inserted in SET in O(logn)? Also tell me about insertion of pair< int,pair< string,string>>.

2

According to this:

http://www.cplusplus.com/reference/set/set/insert/

It is logarithmic time in general… but it depends on how the insertion is done… and indirectly, I believe, on the type of elements that are being inserted…

Maybe someone with more expertise can help you better with this matter,

Bruno

1 Like
3

“SET sorts according to the key first and then according to the value”.
Actually, set is always sorted according to some comparator other than in the way you think.
For pair<string, int> it looks like

bool operator<(pair<string, int> a, pair<string, int> b) {
    return a.first < b.first || (a.first == b.first && a.second < b.second);
}

So insertion to set requires O(log N) comparison operations and O(log N) operations with pointers to the key-type.

You could even have set<vector<pair<string,vector<vector<int> > > > > and still insertion will be in O(log N) comparison operations.

Another question is that comparison could require more than O(1) operation. Then of course the final complexity could be more than O(log N).

In the example above with pair<string, int> the final complexity is O(log N * maxL) where maxL is the maximal length of the inserted string since comparison of two strings of length L1 and L2 requires O(min(L1, L2)) operations.

That is why we have the complexity O((N + M) * log N * maxL) in the problem CVOTE.

5 Likes
4

A Set achieve faster execution for insertion and deletion because it is implemented as a red black tree ( The idea is to strengthen the rep invariants of the binary search tree so that trees are always approximately balanced. To help enforce the invariants, we color each node of the tree either red or black ). Ordered set keeps its elements in some sorted order. They generally provide operations for finding the minimum and maximum elements of the set, for iterating over all the elements between two elements, and for extracting ordered subsets of the elements between a range.
A tree with n nodes is kept balanced, its height is O(lg n), which leads to a lookup operation running in time O(lg n).

5

Thank you sir, it was really a nice explanation. So in general I can say that set inserts in O(logn * C) where C is the time taken to compare the element inserted.

6

Thanks karuma for the response, I understood now

7

Sometimes when I submit the answers using pair in set, it gives TLE but when I push the pair in the vector and then sort that vector and print it gets AC. The difference between the two is sometimes more than 1 sec. Can you explain me the reason?

8

Set is much slower then vector. Always try to avoid it.

I mean inserting all in set and doing traversal could be several times slower than sorting the vector.

1 Like