我想为一组浮点值指定一个唯一对象。这样做，我正在探索两种不同的选择：在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