TaeHo0o00o0N's blog

I want to know How swap function works
By TaeHo0o00o0N, history, 4 years ago, In English

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..

  • Vote: I like it
  • +30
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by TaeHo0o00o0N (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

The correct way to do it is

s=move(s1);

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

While original question is already answered, why don't you write this snippet as 

if (s.size() < s1.size()) { //I understand why you used cast to int, but here it's useless. And easier to use macros/function SZ, which casts to int
    for (auto& x: s)
        s1.insert(x);
    s = move(s1);
}
else {
    for (auto& x: s1)
        s.insert(x);
}

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)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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

    → Reply