在C++中實現列表位置定位器？

我正在用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++中是否有一個標準的方法來實現一個定位器，該定位器可以追蹤元素在列表中的位置而不會過時？

許多感謝，傑夫

來源

2012-04-01 jfrazier

看看boost圖庫如何解決這個問題。它比簡單的'std :: list'複雜得多幾個數量級（它基本上允許你以任何你可能想要的方式來定義圖形），但是因爲你正在學習C++，所以值得一看。 – 2012-04-01 23:21:46

（我假設你是單線程的，顯然列表不是線程安全的）

，但也許是STL這樣做是爲了通過保持內存有所優化連續的？

不正確 - list :: insert，list :: push_front和list :: push_back不影響list :: iterators的有效性。如果您只是在列表中調用這些增變器，則它將保持有效。

無論如何，如果有人對此有何洞見，我將不勝感激。在C++中是否有一個標準的方法來實現一個定位器，該定位器可以跟蹤元素在列表中的位置而不會過時？

你的方法應該工作，請張貼一些代碼證明它不工作。在此期間這裏有兩個備選表示：

爲什麼不使用：

struct Graph 
{ 
    typedef unique_ptr<Vertex> PVertex; 
    typedef unique_ptr<Edge> PEdge; 

    unordered_set<PVertex> verticies; 
    unordered_set<PEdge> edges; 
};

這樣你可以刪除它們在固定時間像你的願望。 unordered_set通常使用散列表實現，因此其分攤的O（1）訪問時間。

而且還的unique_ptr意味着你可以有unordred_sets「擁有」他們

如果verticies是可數，有一個固定的最高要求上限（N），另一個表示是：

struct Graph 
{ 
    typedef unique_ptr<Vertex> PVertex; 
    typedef unique_ptr<Edge> PEdge; 

    array<PVertex, N> verticies; 
    array<array<PEdge, N>, N> edges; 
};

在哪裏如果verticies [x]或edges [x] [y]爲nullptr，意味着對應的頂點或邊不存在，則邊[i] [j]包含verticies [i]和verticies [j]之間的邊。

老C++版本：

unordered_set在TR1介紹。如果你沒有這個，你可以使用boost。如果你不想使用boost，你可以使用一個普通的舊集合，它會給logn訪問時間，或者你可以實現你自己的散列表。
unique_ptr可以替換爲舊版本的auto_ptr。
數組可以用常規數組或矢量來替換。

來源

2012-04-01 22:42:31

請注意，unordered_set <>，unique_ptr <>和array <>是C++ 11的特性。 – stanwise 2012-04-01 22:47:24

如果'std :: unordered_set'和'std :: array'不可用，並且無法進行編譯器升級，並且您沒有招聘人員，則始終可以通過Boost獲取他們。 – 2012-04-01 22:52:55

而2011版本是C++當前批准的標準。默認情況下，我們使用當前版本 - 但好的，我爲舊版本添加一些註釋 – 2012-04-01 22:55:06

在C++中實現列表位置定位器？

回答

相關問題