作者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