c++ - 在 C++ 中缓存浮点值

Question

我想将一个唯一对象分配给一组浮点值。为此，我正在探索两种不同的选择:

第一个选项是在类中维护一个静态 HashMap (std::unordered_map<double,Foo*>) 并避免首先创建重复项。这意味着我不会调用构造函数，而是检查该值是否已经在哈希中，如果是，则重用它。我还需要在析构函数中从 HashMap 中删除值。

第二个选项是在创建过程中允许重复值，只是尝试一次对它们进行排序并在创建所有值后检测重复项。我想我也需要 HashMap 来进行排序。还是有序映射 ('std::map) 也能正常工作？

是否有理由认为第一个选项(我更喜欢它)在任何情况下都会慢得多？也就是说，如果我一次执行所有条目而不是一次执行一个条目，查找重复条目会快得多吗？

我知道兑现 float 时的陷阱，并会防止将非数字和无穷大添加到 map 中。相同常量的一些重复条目也不是问题，如果少数条目发生这种情况 - 它只会导致非常小的速度损失。

Answer 1

取决于 float 的来源和可能的值数字，一个更大的问题可能是定义一个散列函数，它尊重平等。 (0、Inf 和 NaN 是问题值——大多数浮点格式有两种表示形式，分别为 0、+0.0 和-0.0，比较相等；我认为同样的事情也适用于 Inf。和两个 NaN 总是比较不相等，即使它们具有完全相同的位模式。)

除此之外，在所有性能问题中，您都必须进行衡量。您没有指出该集合可能有多大。除非是巨大，如果所有值都预先插入，最快的解决方案是通常在 std::vector 上使用 push_back，然后是 std::sort，如果所需的，std::unique 在 vector 被填充之后。在许多在某些情况下，使用 std::vector 并保持排序会更快，即使插入和删除很频繁。 (当你收到一个新请求时，使用std::lower_bound 寻找入口点；如果该位置的值发现不相等，则在该点插入一个新条目。)改进后的std::vector 的位置在很大程度上抵消了由于在插入和删除过程中移动对象，甚至经常事实上，访问是 O(lg n) 而不是 O(1)。 (在一种特殊情况下，我发现哈希表和排序之间的收支平衡点std::vector 大约有 100,000 个条目。)