作者ric2k1 (Ric)
看板EE_DSnP
标题Re: [问题] hw5关於_trace问题
时间Sun Nov 27 00:53:12 2011
※ 引述《shryuhuai ()》之铭言：
: 刚刚想了一下发现bst用_trace写似乎会有bug
: 如果有以下程式码
: int main(){
: BSTree mytree;
: mytree.insert("A");
: mytree.insert("B");
: mytree.insert("C");
: mytree.insert("D"); // 排序为 A B C D
: BSTree::iteraotr it1 = mytree.begin(); // it1内为_root
: BSTree::iterator it2 = ++mytree.begin(); // it2内为_root,R
: BSTree::iterator it3 = ++(++mytree.begin()); // it3内为_root,R,R
: BSTree::iterator it4 = ++(++(++mytree.begin())); // it4内为_root,R,R,R
: cout << *it1 << *it3 << endl; // 输出AC
: mytree.erase(it2);
: cout << *it1 << *it3 << endl; // 应该要输出AC,但是会变成AD,因为B被拔掉了
你举的例子在我用 _trace 实现的 BST iterator 不会有问题，
我的输出会是 AC, 而不会是 AD.
这个跟 STL 的 set/list behavior 是一样的。
: cout << *it4 << endl; // 记忆体区段错误?
这个应该不会有 seg fault.
: }
: 目前想不到修正bug的方法
: 因为iterator又不能知道其他iterator的存在
: 还是_trace的操作和我想像的不一样?
: ※ 编辑: shryuhuai 来自: 175.182.109.245 (11/26 22:35)
不过用 _trace 来 implement 的确会有一个问题，
就是如果 container class 中途 erase 掉 _trace 中间的 node,
虽然这时呼叫 operator *() 不会有问题，
但是如果呼叫 operator ++() 可能就会 get lost 了...
解决的办法可以用 dirty bit, 但是目前 ref program 也没有做，
所以大家也可以不用管他，
可以假设
在 iterator 存活的期间 container class 不会被改变 !!
等我明年来 improve 这点之後再来改 spec 好了!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.248.111.4