我想爲一組浮點值指定一個唯一對象。這樣做，我正在探索兩種不同的選擇：在C++中緩存浮點值
第一個選項是維持類中的靜態哈希表（std::unordered_map<double,Foo*>），並避免所有重複的在第一時間創建。這意味着，不是調用構造函數，而是檢查值是否已經存在於散列中，如果是，則重新使用它。我還需要從析構函數中的哈希映射中刪除值。
第二種選擇是在創建過程中允許重複值，只嘗試一次對它們進行排序，並在所有值創建後檢測重複項。我想我會需要散列地圖進行排序。或者，一個有序的地圖（'std :: map）是否也能正常工作？
是否有理由期望第一個選項（我更喜歡）在任何情況下都會比較慢？也就是說，如果我一次執行所有條目而不是一次執行一個條目，會發現重複條目要快得多嗎？
我知道當兌現浮點數時的陷阱，並且會阻止將非數字和無窮大添加到地圖中。對於相同的常量，一些重複的條目也不是問題，如果發生少數條目 - 它只會導致非常小的速度損失。
視信號源和浮點的可能值 號碼，一個更大的問題可能會被定義的哈希函數，其 方面的平等上。 （0，Inf和NaN是問題值—大多數 浮點格式有兩個表示0,+0.0和 -0.0，它們比較相等;我認爲Inf同樣適用。而 2的NaN總是比較不等，即使它們擁有完全相同的位 模式。）
除此之外，在性能的所有問題，你自己去衡量。 你並不表明設定有多大可能會成爲。除非是 巨大的，如果所有的值被插入前面，最快的解決方案是 常常到上std::vector使用push_back，然後std::sort和，如果需要的話 ，std::unique載體已填充之後。在許多情況下 ，使用std::vector並保持其排序是更快，即使 插入和刪除頻繁。 （當你得到一個新的請求，使用 std::lower_bound找到切入點;如果發現位置 值不相等，插在這一點上一個新的條目。）改進 局部性std::vector很大程度上抵消了因任何額外費用到 移動插入和刪除，並經常甚至 事實訪問是O（LG n）的過程中的對象，而不是O（1）。 （在一個特定的情況下，我發現哈希表和排序的 std::vector之間的盈虧平衡點約爲100,000條目。）
我明白了。因此，即使使用哈希映射原則上速度更快，除了最大的情況外，所有情況下的正常排序都可能會更快。這回答我的問題，謝謝！關於使用浮點值作爲哈希表中的鍵，我將確保也將0單獨處理，謝謝您指出。 – Joel 2012-02-17 12:33:42
@Joel 0的唯一問題可能是散列時。如果你使用'sort'，那麼就不會有散列，只是比較，而且0在那裏工作得很好。 – 2012-02-17 13:05:46
你是否考慮實際測量它？
我們沒有人可以告訴你如何你正在考慮的代碼將實際上執行。編寫代碼，編譯它，運行它並測量它運行的速度。
試圖預測哪種解決方案更快的花費時間是（1）浪費您的時間，以及（2）可能產生不正確的結果。
但是，如果你想要一個抽象的答案，這是取決於你的用例。
如果您可以收集所有的值並對它們進行一次排序，那麼可以在O(n lg n)時間內完成。
如果插入在一個時間的一個元件與的std::map的性能特徵的數據結構，那麼每個插入將需要O(lg n)時間等，進行n插入也會採取O(n lg n)時間。
插入到哈希映射（std::unordered_map）開恆定的時間，並因此n插入可以在O(n)來完成。因此理論上，對於足夠大的值n，哈希映射將會更快。
實際上，在你的的情況下，沒有人知道。這就是爲什麼你應該測量它，如果你真的關心性能。
我想了解'的std :: unordered_map'類型以及是否有速度典型應用該類超支從一次添加多個條目。你的評估，它將需要'O（n lg n）'時間是基於使用類似快速排序的東西。顯然，使用相同的哈希映射會給你'O（n）'，所以它不能用於檢測映射中的多個條目。 – Joel 2012-02-17 12:05:53
對於浮點數的*大*陷阱呢？他們不是確切的？你如何處理？ – jalf 2012-02-17 11:51:37
@jalf浮點數是確切的。確切的值可能不是您所期望或想要的值，但每個浮點數都具有確切的值。關於將它們用作散列表中的鍵，它取決於數字的來源。 – 2012-02-17 12:01:22
嗯，我的'Foo'對象將包含浮點數的副本，所以我可以簡單地檢查，如果這個數字匹配散列鍵的。再次，一些重複的條目（不會很多）不是一個嚴重的問題。 – Joel 2012-02-17 12:10:18