doclist 阅读(20) 评论(0)

昨天,我写了一个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,这是否和multiset的数据结构有关?

如果是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                 it = tt;
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 }