multiset的erase()操作中出现跳过元素的问题
要写成 it=s.erase(it);
或 s.erase(it++);
list,set,multiset的erase会返回删除这个元素后的下一个地址
昨天,我写了一个multiset去重,让tt指向it的后面第一个元素,若重复则删除这2个元素,并令it=tt,it++;来使it指向tt的下一个元素(我想指向原it的后面第2个元素,并认为tt的下一个元素就是原it的后面第2个元素)
1 #include<iostream> 2 #include<cstdio> 3 #include<set> 4 using namespace std; 5 6 typedef long long ll; 7 multiset<ll> s; 8 multiset<ll>::iterator it; 9 multiset<ll>::iterator tt; 10 11 int main() 12 { 13 ll t,n,in; 14 cin >> t; 15 while (t--) 16 { 17 s.clear(); 18 cin >> n; 19 for(int i = 1; i<=n; i++) 20 { 21 cin >> in; 22 s.insert(in); 23 } 24 25 for(it = s.begin(); it != s.end() && tt != s.end();) 26 { 27 tt=it; 28 tt++; 29 if(it == s.end() || tt == s.end())break; 30 if(*it == *tt) 31 { 32 s.erase(it); 33 s.erase(tt); 34 it = tt; 35 it++; 36 } 37 else 38 { 39 it=tt; 40 } 41 } 42 it = s.begin(); 43 tt = it; 44 tt++; 45 printf("%lld %lld\n",*tt,*it); 46 47 } 48 }
然而去重失败了
接着我尝试输出每次检测到的元素,发现当检测到2 2后,下一次检测到的是3 4,也就是说程序跳过了3 3.
于是我尝试查看迭代器的地址,发现出现了下面这种情况
(我给ii迭代器模拟it迭代器的情况)
tt指向it后面的一个元素,也就是tt=it;tt++;然后删除元素时,我将ii=tt;ii++;
这时每当ii++时,它的地址从48->88->a8(168),但如果写成it++;it++;的话,it的地址是从28->08->68的,第一个3在68那,但如果是我原来写的方法,这时就访问的到了88,也就是第2个3的位置,也就是跳过了一个元素。
当ii=tt;ii++;后ii指向的不是第一个3,但2次i++后的却是第一个3,
如果是2次i++后结果是正确的
1 #include<iostream> 2 #include<cstdio> 3 #include<set> 4 using namespace std; 5 const int amn=1000005; 6 typedef long long ll; 7 multiset<ll> s; 8 multiset<ll>::iterator it; 9 multiset<ll>::iterator tt; 10 multiset<ll>::iterator ii; 11 int main() 12 { 13 ll t,n,in; 14 cin >> t; 15 while (t--) 16 { 17 s.clear(); 18 cin >> n; 19 for(int i = 1; i<=n; i++) 20 { 21 cin >> in; 22 s.insert(in); 23 } 24 25 for(it = s.begin(); it != s.end() && tt != s.end();) 26 { 27 tt=it; 28 tt++; 29 if(it == s.end() || tt == s.end())break; 30 if(*it == *tt) 31 { 32 s.erase(it); 33 s.erase(tt); 34
35 it++; 36 it++; 37 } 38 else 39 { 40 it=tt; 41 } 42 } 43 it = s.begin(); 44 tt = it; 45 tt++; 46 printf("%lld %lld\n",*tt,*it); 47 } 48 }