關於什麼樣的數據結構用於快速搜索時間的建議C++

我目前正在思考我可能用於當前項目的數據結構的過程。我不需要刪除項目，因爲我正在加載數據庫，使用它，然後退出程序。唯一的約束與搜索時間有關（內存在第二次，但主要是時間）。關於什麼樣的數據結構用於快速搜索時間的建議C++

關於我打算做什麼的概述。我正在解析文件並提取用於創建各種對象的信息。閱讀文件並創建對象之後，我有一組多個對象作爲字符串引用另一個對象。

這裏的目標是要找到其中的淨從一個域轉到另一個

如：文本輸入文件：

module Blabla 
netTomodule Foo 
domain 1 
..../*Other parameters of the module*/ 
end module 

module Foo 
netTomodule Blabla 
netTomodule Foo2 
domain 2 
..../*Other parameters of the module*/ 
end module 

module Foo2 
netTomodule Foo 
domain 2 
..../*Other parameters of the module*/ 
end module

我得到3模塊對象foo foo2的和BLABLA和閱讀之後其屬性如下：

class Module{ 
private : 
string name; 
int domain; 
netlist * mynetlist; 
... 
}

我的意見，我想對他諮詢的事情：

思考之後，我認爲我最好的拍攝是：

當讀取文件並提取信息，我應該創建模塊的鏈接列表。
然後用我讀過的模塊的數量，我創建一個數組，它的大小是它的兩倍。
對於每個模塊，我使用散列函數來散列模塊名稱，並將指針放在數組中的給定索引處
現在，當我想要找到一個模塊時，我只需要計算散列值，並得到指針在給定的指數（或增量，如果它不是好的模塊，因爲之前在製作陣列時發生衝突）

這基本上是散列表或至少我知道的一個實現的一個哈希表從我的clasess。

我的問題是這是一個好主意嗎？是否有一個我可以使用的哈希表庫？（我聽說過尋找unordered_map和地圖，但我不知道它是否適合我的需求）

這是一個巨大的文字，所以我希望它足夠詳細，所以謝謝你，如果你有勇氣閱讀一切！

來源

2011-05-06 djfoxmccloud

很難理解你的問題，因爲它有很多不相關的信息和重複。嘗試專注於基本要求並避免空洞的短語（「你應該知道的事情就是......」）。 – 2011-05-06 09:19:49

如果不知道你想要用你的模塊執行什麼操作，很難回答。你試圖解決的總體問題是什麼？ – 2011-05-06 09:23:41

我已編輯，使其更清晰，這裏的目標是要找到哪個網絡從一個域到另一個域（即有一個淨網絡Foo和Blabla跨域從2到1） – djfoxmccloud 2011-05-06 09:24:17

只需使用標準庫或boost附帶的散列表即可。大多數將具有unordered_map（由TR1指定並且針對C++ 0x），但是一些將具有std::hash_map或stdext::hash_map，其中各種實現略微不同，例如，原SGI與微軟。

您不需要構建列表，只需將對象直接放置在散列表中;它允許順序迭代，儘管它將以某種固定的隨機順序。

來源

2011-05-06 09:55:07

嗨，我想這就是我要做的。我誤以爲我們在C班做了什麼，老師告訴我們知道散列表初始化元素的數量。謝謝：） – djfoxmccloud 2011-05-06 11:38:58

你可以維護一個散列表（string =>指向Module類型的對象的指針）而不是鏈接列表。

再次類模塊的內部，再維持一個HashMap或地圖的字符串=>指針

來源

2011-05-06 09:37:31 mukeshkumar

我在課堂上告訴，要使一個散列表我不得不知道其中的元素數量（有一個散列表是兩倍的大小）。這就是爲什麼我在OP中說過，我創建了一個鏈表來計算元素的數量，然後通過它來計算一個哈希值。 //這是不是真的？我可以直接使用散列表來放入東西嗎？ – djfoxmccloud 2011-05-06 09:49:27

@djfoxmccloud：每個合理的哈希表都會自動調整大小。 'unordered_map'和所有其他的'hash_map'實現都與我迄今見過的標準庫一起使用。 – 2011-05-06 09:56:23

@djfoxmccloud：我剛剛提出了一個解決方案。就計算對象的數量而言，即使這樣做，您也不必創建鏈接列表。在讀取文件以創建模塊對象時，您可以隨時對它們進行計數。所以一旦你創建了所有的對象，你就會知道它的大小。與網絡（或模塊對象內的鏈接）一樣，在獲得結束標記「結束模塊」時，您會注意到它的大小。 – mukeshkumar 2011-05-06 09:56:52

如果有興趣在間接關係爲好（Foo2 - >Foo - >BlaBla）你基本上具有的曲線圖。在這種情況下，您可以使用Boost.Graph。

來源

2011-05-06 09:42:05

謝謝，但我只對非傳遞關係感興趣！ – djfoxmccloud 2011-05-06 09:46:31

關於什麼樣的數據結構用於快速搜索時間的建議C++

回答

相關問題