我有200套約50,000唯一整數0至500,000我需要映射到另一個小的值的範圍的高效且緊湊的地圖（整數的一對，的值是不相關的，從而沒有點播計算）。C++與整數密鑰
我試過使用std :: unordered_maps，並使用了大約50MB（在VS2015堆診斷工具中測量），而性能很好Id想要得到這種內存使用下來（打算成爲一些小的後臺服務500MB雲服務器）。
切實我最初的版本是200獨立std::unordered_map<int, std::pair<int, int>>。
一個選項似乎是一個排序數組，並使用二分搜索，但還有什麼？
我認爲排序的向量應該工作，如果你不會改變它的排序向量。它非常節省空間，即無指針開銷。
如果您需要更好的性能，並且不介意一些第三方庫。你可以嘗試sparse_hash_map，它實現了非常小的空間開銷哈希映射。
我想這是最有效的記憶將是一個std::vector<std::pair<int, std::set<Something>>>，就像你已經建議。
在這種情況下，你只會有內存開銷的結果：
你還挺表明，後集結你不再延長載體，所以要麼你可以reserve或shrink_to_fit擺脫未使用的空間。 （請注意，儲備還修復了增長期間內存使用率的上漲）
如果您的密碼使用率更高，則可以考慮將存儲更改爲std::vector<std::set<Something>>或std::vector<std::unique_ptr<std::set<Something>>>。在這種結構中，索引是隱含的，但只有在每個索引都有值時纔會顯示內存增益。
使用矢量的缺點是你必須編寫一些自定義代碼。在這種情況下，std::unordered_map和std::map並不壞，如果你不介意少的標準實現處理器緩存（L1 ...）更多高速緩存未命中，一個可以檢查出Googles sparsehash，Googles cpp-btree或Facebooks AtomicHashMap from Folly，雖然我不沒有任何經驗。
最後，我們可以知道爲什麼你都在存儲器中的數據，但我沒有看到一個方法來防止這種情況，如果你需要的最佳性能。
我不明白'set :: set'是如何工作的。 「Something」看起來像什麼？至於具有排序數組的自定義代碼，計劃只使用'std :: sort'（創建後）和'std :: lower_bound'（查找）。 –
除非你的意思是什麼是值和數組索引是關鍵？就像我說的那樣，數據是從0到500,000的50,000個數字，所以使用這樣的數組只有大約10％的效率。在64位平臺上，sizeof（unique_ptr）的大小也只有2個整數，儘管我認爲我可以爲它們設置一個「無效值」（可能是INT_MAX）。 –
的確，它代表着一些存儲空間，因爲我不確定你的表示。 （或者這個線程的下一個讀者） – JVApen
高效的存儲，這取決於精確值範圍內，您可能需要使用位操作的鍵/值對存儲在一個單一的值：例如，如果值是非常小的，你甚至可以使用24位的鍵和8位的值，導致一個單一的32位條目。我相信現在大多數編譯器現在都使用32位或64位對齊方式，因此存儲例如32位密鑰和16位值可能仍然需要每個條目64位。如果瓶頸是內存總線和高速緩存未命中，使用簡單壓縮對性能也有好處，而不是CPU本身。
然後它取決於您想要執行的操作類型。存儲密鑰的最簡單的方法將是一個有序結構數組或者我上面提出的組合的ley/value條目。這是快速且非常節省空間的，但需要O（log n）查找。
如果你想變得更有趣，你可以使用perfect hashing，這個想法是找到一個散列函數，它爲每個鍵產生唯一的散列值。這允許hashmap是一個簡單的數組，它只需要比我上面提出的排序後的數組稍微大一些。找到一個好的散列函數應該是相對較快的，你可以通過將數組放大一點，並允許數組中的一些未使用的字段來使它更容易。 Here是一個完美哈希的實現，但我沒有使用它自己。
在這兩種情況下，內存消耗將爲：（對數）*（每個條目的位數）位，以及在使用第二種方法時存儲散列函數。
**編輯**
從@FireLancer評論後更新。另外，增加了一些關於壓縮數組性能的文字。
我沒看到你的第一個例子中的一點操作在這裏會有幫助。我期望一個'struct Value {int x; int y; }'無論如何都要存儲爲8個連續字節。也許key + value_1 + value_2可以說是8個字節而不是12個，但是需要看看是否可以限制足夠的值範圍。在運行時構建一個更好的散列函數的可能性看起來很有趣，但是會試驗看看它與我的數據集有多密集。 –
@FireLancer你說得對，在C/C++中，如果你不想使用每個鍵/值的非標準位寬（我在Java中考慮），那麼位操作只會有所幫助。我會更新答案。 – TilmannZ
200個「套」中的每一套都有自己獨特的地圖嗎？ – WhozCraig
你嘗試過'std :: map'嗎？ – Galik
@Galik對於這種情況既不佔用空間，也不像性能，特別是'std :: unordered_map'。我更加好奇是否有任何調整桶的大小。 – WhozCraig