結合查找和有序數據的C++數據結構

我有一個排序圖，當我加載邊時，我使用散列表來查找頂點。邊緣按照源排序，因此我只需要查看「更深」的頂點。如果給定的邊具有水平上的源頂點n，則接收器頂點必須在水平上m，其中m> n。我需要利用這種行爲來提高性能。結合查找和有序數據的C++數據結構

「理想」天真解決方案將是每個級別的散列表，我可以使用該級別查找正確的表格，然後在表格中查找元素。這也使我能夠在n，源等級大於等級時能夠回收內存的額外好處。不幸的是，該圖對於這種方法來說太大了，10^6級和10^9個頂點。

有沒有人有什麼建議我應該看什麼數據結構？ Gracias

來源

2010-11-28 akintayo

爲什麼你需要在每個級別的哈希表？只有一個普通的圖形結構（爲每個節點分配內存，並從每個節點到每個接收器都有一個指針）有什麼問題？這仍然讓你查找任何頂點，給定它的地址，並且從每個頂點可以找到它指向的所有頂點。也許我不瞭解你需要執行什麼操作。 – mgiuca 2010-11-29 01:25:02

給定你對問題的大小估計，我會建議一個向量向量：外部向量包含每個級別的一個內部向量，因此它包含大約100萬個條目;內部向量（每個包含大約1000個條目？）應該按排序順序保存，並使用lower_bound()等的分類插入。

您可以通過複製/交換技巧回收內存以將空的舊內部向量替換。

typedef std::vector<Node> level_nodes; 
typedef std::vector<level_nodes> graph_nodes; 

graph_nodes g; 
r.reserve(1000000); // OK, just a few MB 

// ... 

g[12].insert(std::lower_bound(g[12].begin(), g[12].end(), x), x); 

level_nodes().swap(g[11]); // kill level 11 and reclaim memory

來源

2011-08-15 15:41:44

結合查找和有序數據的C++數據結構

回答

相關問題