我正在用C++編寫一個基本的圖形API(我知道庫已經存在,但我正在爲練習/體驗做)。該結構基本上是鄰接列表表示的結構。因此,有頂點對象和邊緣對象和圖表類包含:在C++中實現列表位置定位器?
list<Vertex *> vertexList
list<Edge *> edgeList
每個邊緣對象有兩個頂點*代表其端點的成員,每個Vertex對象具有代表的邊緣射入邊緣*成員名單頂點。
這一切都很標準,但這是我的問題。我希望能夠在常量時間內實現邊和頂點的刪除,因此,例如,每個頂點對象都應該有一個指向頂點列表中其頂點*的位置的定位器成員。我第一次實施這樣的方式是通過保存目錄::迭代器,如下所示:
vertexList.push_back(v);
v->locator = --vertexList.end();
然後,如果我需要稍後刪除這個頂點,然後而不是搜索整個VertexList時,它的指針,我可以打電話:
vertexList.erase(v->locator);
這工作得很好,在第一,但似乎,如果有足夠的變化(刪除)都在列表中進行,迭代器將成爲外的日期,我得到的各種迭代器的錯誤在運行時。這對於鏈表來說似乎很奇怪,因爲它似乎並不需要在刪除後重新分配列表的其餘成員,但是STL可以通過保持內存的連續性來做到這一點?
無論如何,如果有人對此有何洞見,我將不勝感激。在C++中是否有一個標準的方法來實現一個定位器,該定位器可以追蹤元素在列表中的位置而不會過時?
許多感謝, 傑夫
看看boost圖庫如何解決這個問題。它比簡單的'std :: list'複雜得多幾個數量級(它基本上允許你以任何你可能想要的方式來定義圖形),但是因爲你正在學習C++,所以值得一看。 – 2012-04-01 23:21:46