丨迭代器模式下如何設(shè)計(jì)實(shí)現(xiàn)一個(gè)支持快照功能的iterator

話不多說(shuō)，讓我們正式開始今天的學(xué)習(xí)我們先來(lái)介紹一下問(wèn)題的背景：如何實(shí)現(xiàn)一個(gè)支持“快照”功能的迭代器模理解這個(gè)問(wèn)題最關(guān)鍵的是理解“快照”兩個(gè)字。所謂“快照”，指我們?yōu)槿萜鲃?chuàng)建迭代器的時(shí)候，相當(dāng)于給容器拍了一張快照（Snashot）。之后即便我們?cè)鰟h容器中的元素，快照中的元素并不會(huì)做相應(yīng)的改動(dòng)。而迭代器遍歷的對(duì)象是快照而非容器，這樣就避免了在使用迭代器遍歷的過(guò)程中，增刪容器中的元素，導(dǎo)致的不可預(yù)期的結(jié)果或者報(bào)錯(cuò)。接下來(lái)，我舉一個(gè)例子來(lái)解釋一下上面這段話。具體的代碼如下所示。容器list中初始了3、8、2三個(gè)元素。盡管在創(chuàng)建迭代器iter1之后，容器list刪除了元素3，只剩下8、2兩個(gè)元素，但是，通過(guò)iter1遍歷的對(duì)象是快照，而非容器list本身。所以，遍歷的結(jié)果仍然是3、8、2。同理，iter2、iter3也是在各自的快照上遍歷，輸出的結(jié)果如代碼中注釋List<Integer>list=new tor<Integer>iter1=list.ilist.remove(newInteger(2));//list：3, tor<Integer>iter2=list.ilist.remove(new

3,8,3, tor<Integer>iter3=list.itor();//snapshot://輸出結(jié)果：38while(iter1.hasNext())System.out.print(iter1.next()+"1516//輸出結(jié)果：3while(iter2.hasNext())System.out.print(iter1.next()+"2122//while(iter3.hasNext())}System.out.print(iter1.next()+"如果由你來(lái)實(shí)現(xiàn)上面的功能，你會(huì)如何來(lái)做呢？下面是針對(duì)這個(gè)功能需求的骨架代碼，其中包含ArrayList、SnapshotArrayI }System.out.print(iter1.next()+"代1publicArrayList<E>implementsList<E>2//TODO:成員變量、私有函數(shù)等345publicvoidadd(Eobj)6//TODO:由你來(lái)完7}89publicvoidremove(Eobj)//TODO:}public tor<E> tor()returnnewSnapshotArrayI}}publicclassSnapshotArrayItor<E>Itor<E>//TODO:成員變量、私有函數(shù)等publicbooleanhasNext()//TODO:}publicEnext(){//返回當(dāng)前元素，并//TODO:}}我們先來(lái)看最簡(jiǎn)單的一種解決辦法。在迭代器類中定義一個(gè)成員變量snapshot來(lái)快代代123456789publicclass{privateinttor<E>implementsprivateArrayList<E>public{this.cursor=tor(ArrayList<E>this.snapshot=new}publicbooleanhasNext()returncursor<}publicEnext()EcurrentItem=snapshot.get(cursor);return}}存中重復(fù)多份。不過(guò)，慶幸的是，Java中的拷貝屬于淺拷貝，也就是說(shuō)，容器中的對(duì)象并非真的拷貝了多份，而只是拷貝了對(duì)象的而已。關(guān)于深拷貝、淺拷貝，我們?cè)诘?7講中有詳細(xì)的講解，你可以回過(guò)頭去再看一下。那有沒(méi)有什么方法，既可以支持快照，又不需要拷貝容器我們?cè)賮?lái)看第二種解決方案我們可以在容器中，為每個(gè)元素保存兩個(gè)時(shí)間戳，一個(gè)是添加時(shí)間戳adTimestamp，一個(gè)是刪除時(shí)間戳elTimesamp。當(dāng)元素被加入到集合中的時(shí)候，adTimestamp設(shè)置為當(dāng)前時(shí)間，將elTimesamp設(shè)置成最大長(zhǎng)整型值（Lon.MAX_ALUE）。當(dāng)元素被刪除時(shí)，elTimesamp更新為當(dāng)前時(shí)間，表示已經(jīng)被刪除。注意，這里只是標(biāo)記刪除，而非真正將它從容器中刪同時(shí)，每個(gè)迭代器也保存一個(gè)迭代器創(chuàng)建時(shí)間戳snapshotTimestamp，也就是迭代器對(duì)應(yīng)addTimestamp<snapshotTimestamp<delTimestamp的元素，才是屬于這個(gè)迭代器的如果元素的addTimestamp>snapshotTimestamp，說(shuō)明元素在創(chuàng)建了迭代器之后才加入的，不屬于這個(gè)迭代器的快照；如果元素的delTimestamp<snapshotTimestamp，說(shuō)明如下所示。注意，我們沒(méi)有考慮ArrayList的擴(kuò)容問(wèn)題，感的話，你可以自己完善一代代123456789publicclassArrayList<E>implementsList<E>privatestaticfinalintDEFAULT_CAPACITY=privateintactualSize//不包含標(biāo)記刪除元素privateinttotalSize;//包含標(biāo)記刪除元素privateObject[]elements;privatelong[]addTimestamps;privatelong[]publicArrayList()this.elements=newObject[DEFAULT_CAPACITY];this.addTimestamps=newlong[DEFAULT_CAPACITY];this.delTimestamps=newlong[DEFAULT_CAPACITY];this.totalSize=0;this.actualSize=}publicvoidadd(Eobj)elements[totalSize]=addTimestamps[totalSize]=delTimestamps[totalSize]=}publicvoidremove(Eobj)for(inti=0;i<totalSize;{if(elements[i].equals(obj))delTimestamps[i]=}}}publicint{return}publicint{return}publicEget(int{if(i>={thrownewIndexOutOfBound}return}publiclonggetAddTimestamp(int{if(i>=totalSize)thrownewIndexOutOfBound}return}publiclonggetDelTimestamp(int{if(i>=totalSize)thrownewIndexOutOfBound}return}}publicclassSnapshotArrayItor<E>I{privatelongprivateintcursorInAll;//在整個(gè)容器中的下標(biāo)，而非快照中privateintleftCount;//快照中還有幾個(gè)元素未被privateArrayList<E>

System.currentTimeMillis();this.cursorInAll=0;this.leftCount=arrayList.actualSize();;this.arrayList=arrayList;justNext();//先跳到這個(gè)迭代器快照的第一}publicbooleanhasNext()returnthis.leftCount>=0;//注意是>=,而非}publicEnext()EcurrentItem=arrayList.get(cursorInAll);return}privatevoidjustNext()while(cursorInAll<arrayList.totalSize())longaddTimestamp=arrayList.getAddTimestamp(cursorInAll);longdelTimestamp=if(snapshotTimestamp>addTimestamp&&snapshotTimestamp<delTimestamp}}}}實(shí)際上，上面的解決方案相當(dāng)于解決了一個(gè)問(wèn)題，又引入了另外一個(gè)問(wèn)題。ArrayList底層依賴數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，原本可以支持快速的隨機(jī)，在O(1)時(shí)間復(fù)雜度內(nèi)獲取下標(biāo)為i的元素，但現(xiàn)在，刪除數(shù)據(jù)并非真正的刪除，只是通過(guò)時(shí)間戳來(lái)標(biāo)記刪除，這就導(dǎo)致無(wú)法《數(shù)據(jù)結(jié)構(gòu)與算法之美》專欄，這里我就不展開講解現(xiàn)在，我們來(lái)看怎么解決這個(gè)問(wèn)題：讓容器既支持快照遍歷，又支持隨機(jī)解決的方法也不難，我稍微提示一下。我們可以在ArrayList中兩個(gè)數(shù)組。一個(gè)支持記刪除的，用來(lái)實(shí)現(xiàn)快照遍歷功能；一個(gè)不支持標(biāo)記刪除的（也就是將要?jiǎng)h除的數(shù)據(jù)直接數(shù)組中移除），用來(lái)支持隨機(jī)。對(duì)應(yīng)的代碼我這里就不給出了，感的話你可以自己好了，今天的內(nèi)容到此就講完了。我們一塊來(lái)總結(jié)回顧一下，你需要重點(diǎn)掌握的內(nèi)今天我們講了如何實(shí)現(xiàn)一個(gè)支持“快照”功能的迭代器。其實(shí)這個(gè)問(wèn)題本身并不是學(xué)習(xí)的重點(diǎn)，因?yàn)樵谡鎸?shí)的項(xiàng)目開發(fā)中，我們幾乎不會(huì)遇到這樣的需求。所以，基于今天的內(nèi)容我不想做過(guò)多的總結(jié)。和你說(shuō)一說(shuō)，為什么我要來(lái)講今天的內(nèi)容呢？實(shí)際上，學(xué)習(xí)本節(jié)課的內(nèi)容，如果你只是從前往后看一遍，看懂就覺(jué)得ok了，那收獲幾乎是零。一個(gè)好學(xué)習(xí)方法是，把它當(dāng)作一個(gè)思考題或者面試題，在看我的講解之前，自己主動(dòng)思考如何解決，并且把解決方案用代碼實(shí)現(xiàn)一遍，然后再來(lái)看跟我的講解有哪些區(qū)別。這個(gè)過(guò)程對(duì)你分析問(wèn)題、解決問(wèn)題的能力的鍛煉，代碼設(shè)計(jì)能力、編碼能力的鍛煉，才是最有價(jià)值的，才是我們這篇文章的意義所在。所謂“知識(shí)是死的，能力才是活的”就是這個(gè)道理。其實(shí)，不僅僅是這一節(jié)的內(nèi)容，整個(gè)專欄的學(xué)習(xí)都是這樣在《數(shù)據(jù)結(jié)構(gòu)與算法之美》專欄中，有同學(xué)曾經(jīng)對(duì)我說(shuō)，他看了很多遍我的專欄，幾乎看懂了所有的內(nèi)容，他覺(jué)得都掌握了，但是，在最近第一次面試中，面試官給他出了一個(gè)結(jié)合實(shí)際開發(fā)的算法題，他還是沒(méi)有思路，當(dāng)時(shí)腦子一片放空，問(wèn)我學(xué)完這個(gè)專欄之后，要想應(yīng)付算法面試，還要學(xué)哪些東西，有沒(méi)有推薦的書籍。我看了他的面試題之后發(fā)現(xiàn)，用我專欄里講的知識(shí)是完全可以解決的，而且，專欄里已經(jīng)講過(guò)類似的問(wèn)題，只是換了個(gè)業(yè)務(wù)背景而已。之所以他沒(méi)法回答上來(lái)，還是沒(méi)有將知識(shí)轉(zhuǎn)化成解決問(wèn)題的能力，因?yàn)樗皇堑亍翱础?，從?lái)沒(méi)有主動(dòng)地“思考”。只掌握了知識(shí)，沒(méi)鍛煉能力，遇到實(shí)際的問(wèn)題還是沒(méi)法自己去分析、思考、解決。我給他的建議是，把專欄里的每個(gè)開篇問(wèn)題都當(dāng)做面試題，自己去思考一下，然后再看解答。這樣整個(gè)專欄學(xué)下來(lái)，對(duì)能力的鍛煉就多了，再遇到算法面試也就不會(huì)一點(diǎn)思路都沒(méi)有了。同理，學(xué)習(xí)《設(shè)計(jì)模式之美》這個(gè)專欄也應(yīng)該如此。在今天講的解決方案二中，刪除元素只是被標(biāo)記刪除。被刪除的元素即便在沒(méi)有迭代器使用的情況下，也不會(huì)從數(shù)組中真正移除，這就會(huì)導(dǎo)致不必要的內(nèi)存占用。針對(duì)這個(gè)問(wèn)題，你有進(jìn)一步優(yōu)化的方法嗎？歡迎留言和我你的思考。如果有收獲，歡迎你把這篇文章給你的朋友?歸科技所有 不得售賣。頁(yè)面已增加防盜追蹤，將依法其上一 66|迭代器模式（中）：遍歷集合的同時(shí)，為什么不能增刪集合元素下一 68|者模式（上）：手把手帶你還原者模式誕生的思維過(guò)言精選留言言除元素總數(shù)<總數(shù)的1/2時(shí)，進(jìn)行resize數(shù)組，清空被刪除的元素，回收空間。1 5思考題感覺(jué)像是數(shù)據(jù)庫(kù)的展3 5展3展3@Override展1在調(diào)用 tor()之