C++數據結構，最好能容納一大堆名字

你能分享一下你的想法：最好的STL數據結構將用於存儲一個大名稱列表並對這些名字執行搜索？C++數據結構，最好能容納一大堆名字

編輯：這些名稱並非唯一，列表可以隨着新名稱的不斷添加而增加。大概我說的是100萬到1000萬個名字。

2014-10-01 SilverBackApe

名稱是唯一的嗎？你創建這個容器一次，然後搜索很多次，或者是否有一定量的添加/刪除項目以及搜索？你是否需要按字母順序遍歷容器？ – 2014-10-01 01:58:33

動態數組或std :: vector（物理上相同）。設置和鏈接列表不適合大量元素，因爲添加時間太長。 – texasbruce 2014-10-01 02:11:31

另外，多大？如果只有幾百萬名字符長度爲10個字符，std :: map在配置合理的筆記本電腦上可能還不錯。如果您需要幾十億個名稱，每個名稱的長度都是100個字符，或者如果您有一個內存受限的系統，則可能需要一個核心外解決方案，這可能會妨礙STL（儘管Google發現http：//stxxl.sourceforge .net /，聲稱處理這種情況）。 – wrdieter 2014-10-01 03:18:48

由於您要搜索名稱，因此您需要支持快速隨機訪問的結構。這意味着vector，deque和list都是不可能的。此外，矢量/數組對於已排序的集合隨機添加/插入緩慢，因爲它們必須移動項目才能爲每個插入的項目騰出空間。雖然增加到結束非常快。

考慮std::map，std::unordered_map或std::unordered_multimap（或他們的兄弟姐妹std::set，std::unordered_set和std::unordered_multiset如果你只存儲密鑰）。

如果你純粹是做獨特的隨機訪問，我會從一個unordered_ *容器開始。

如果你需要存儲的名稱的有序列表，並且需要執行範圍搜索/迭代和分類操作，如std::map或std::set一個基於樹的容器應該做反覆操作優於因爲前者的哈希基於容器將存儲與其邏輯前驅和後繼相鄰的項目。對於隨機訪問，它是O（log N），它仍然很不錯。

在使用std :: unordered_ *之前，我使用了std::map來爲對象緩存保存大量的對象，儘管有更快的隨機存取容器，但它足以滿足我們的使用要求。較新的unordered_map具有O（1）訪問時間，因此它是散列結構，應該爲您提供接近最佳的訪問時間。

來源

2014-10-01 02:23:14 codenheim

如果他所擁有的僅僅是一個字符串列表，並且沒有任何可以將它們映射到各個「集合」 '容器是一個更好的選擇。 – 2014-10-01 02:33:54

但是他打算把名字映射到什麼地方？ – 0x499602D2 2014-10-01 02:35:14

我不確定他是否需要存儲記錄，或者如果名稱是記錄。我相信他可以根據需要替換相應的替代選項。無論如何，如果你覺得通過引用集合兄弟姐妹來改善答案，我會編輯它。 – codenheim 2014-10-01 02:41:46

您可以考慮使用分隔符連接這些名稱的可能性，但搜索可能會受到影響。你需要想出一個調整後的二進制搜索。

但是你應該首先嚐試一下這個明顯的解決方案，它是一個在stl中被稱爲unordered_map的散列表。看看是否符合你的需求。搜索應該足夠快，但需要花費內存。

來源

2014-10-01 05:23:24 dchhetri

C++數據結構，最好能容納一大堆名字

回答

相關問題