when i wrote the code using small to larger techinque,
if i write code like
if((int)s.size()<(int)s1.size()){
for(set<pair<lld,int> >::iterator it = s.begin();it!=s.end();it++) s1.insert(*it);
s = s1;
}else{
for(set<pair<lld,int> >::iterator it = s1.begin();it!=s1.end();it++) s.insert(*it);
}
it gets TLE ( problem accept 4 second )
but if i write code like
if((int)s.size()<(int)s1.size()){
for(set<pair<lld,int> >::iterator it = s.begin();it!=s.end();it++) s1.insert(*it);
swap(s,s1);
}else{
for(set<pair<lld,int> >::iterator it = s1.begin();it!=s1.end();it++) s.insert(*it);
}
it gets AC and run so fast ( runnging time is 200ms )
but i don't know why difference of time is so big.. help..
Auto comment: topic has been updated by TaeHo0o00o0N (previous revision, new revision, compare).
swap for set is O(1): http://www.cplusplus.com/reference/set/set/swap-free/
internal pointers are exchanged, that's why.
Also, your snippets do different things.
and s = s1 is O(N) ??
yes because this operation copies s1 into s
Thank you!!!
Does this work for any stl container? Like vector, map, etc.
Assume swap has the complexity of one construction and two assignments.
For containers, assignments are usually linear. However, swap is specialized in STL containers to make it constant:
http://www.cplusplus.com/reference/vector/vector/swap-free/ http://www.cplusplus.com/reference/map/map/swap-free/ http://www.cplusplus.com/reference/queue/queue/swap-free/ http://www.cplusplus.com/reference/queue/priority_queue/swap-free/
etc..
I assumed that swap works in linear time as they contain objects. I Didn't knew it takes constant time. Thank you very much!
Hold up... If I swap a set to empty set, is it O(1) ?
The correct way to do it is
The reason swap and move work in O(1) for all STL containers is because the content doesn't have to be duplicated unlike in s=s1.
While original question is already answered, why don't you write this snippet as
I tried to read your code from my phone and it took me more than one minute to understand what it means. Use c++17 whenever you can, it really increases readability. (But this one trick is even since c++11)
Thank you for advising for me!! I agree what you are saying... but i'm too lazy to correct my disadvantage.. Try to use macro and increase my readability