爲對象不同領域優化的搜索

struct Pack 
{ 
    unsigned int id; 
    string name; 
    string surname; 
    string username; 
    string address; 
};

如果我想這種類型的對象，我可以存儲集合中搜索給定的「用戶名」它們是，它們以「用戶名」作爲鍵和正確的包對象作爲值的std :: map。

但是如果我還想搜索給定的ID呢？

我遇到這個問題的一個解決方案是將數據放在另一個數據結構（如鏈接列表）和std :: maps中。第一張地圖將具有「用戶名」鍵，第二張地圖將具有「ID」鍵。作爲值，它們都會有一個指向適當的Pack對象的指針。

此外，我忘了提及一件重要的事情。如果我還想刪除一個對象，我還需要刪除2 std :: maps中的條目。如果我想增加std :: maps的數量（搜索給定的名字，姓氏等），那麼刪除過程會變得更加「重要」。

這個問題有更好的解決方案嗎？

謝謝。

2014-03-19 Daniel

如果性能比不使用鏈表更重要..其結構複雜。你應該使用數組結構。看看[盒裝結構]（http://www.geeksforgeeks.org/structure-member-alignment-padding-and-data-packing/） – DOOM

@Mike你的解決方案是一個很好的解決方案。每個'map'類似於數據庫索引，'list'類似於數據庫表。他們只是在記憶中。 – Alex

@DOOM鏈接列表在這裏適用。如果可以在創建'map'後添加新元素，則數組會使'map'中的舊指針失效。鏈接列表中的指針將保持有效。 – Alex

如果你想在不同的鍵上進行高效查找，那麼真的沒有辦法繞過每個地圖 - 可能有庫爲你抽象，但類似的東西仍然會在幕後發生。

但是你根本不需要鏈接列表。您可以讓兩個（或全部）地圖都有直接指向Pack對象的指針。沒有必要讓這些Pack對象駐留在二級結構中。

此外，您可以使用unordered_map而不是map來獲得預期的O（1）操作性能，而不是O（log n）。

2014-03-19 11:00:11 Dukeling

回答