2

我正在计算集合的交集、并集和差异。我有一个我的 set 类型的 typedef：

typedef set<node_type> node_set;

当它被替换为

typedef hash_set<node_type> node_set;

结果是不同的。这是一个复杂的程序，在我开始调试之前 - 我做得对吗？当我使用这样的功能时：

set_intersection(v_higher.begin(), v_higher.end(), neighbors[w].begin(), neighbors[w].end(), 
            insert_iterator<node_set>(tmp1, tmp1.begin()));
  • 他们应该与 set 和 hash_set 无缝工作吗？
4

3 回答 3

5

我不这么认为。

的前提条件之一set_intersection是：

  • [first1, last1)根据升序排列。operator<也就是说，对于每对迭代器i，并且j在[first1, last1)这样的情况下i，j都是*j < *i假的。

( hash_setand unordered_set) 是无序的，因此无法满足有序条件。

请参阅tr1::unordered_set 联合和交集，了解如何与unordered_sets 相交。

于 2010-03-12T20:09:45.090 回答
1

我要不去。请记住，hash_set它不是标准的 C++，也永远不会是，它是一个不再受支持的旧扩展。较新的“哈希映射”被称为unordered_set和unordered_map，在 TR1、Boost 和 C++0x 中可用。

否的原因是set_intersection需要对输入数据进行排序。相反，哈希映射如此之快的原因是它放弃了排序。这在名字下显然更加明显unordered_set。因此，不能可靠地满足前提条件。

于 2010-03-12T20:11:10.033 回答
0

不，您不能使用set_intersection，因为set_intersection需要订购两组（使用相同的顺序）。哈希集没有以任何方式排序。在 C++0x 中，它们实际上被称为unordered_set.

于 2010-03-12T21:08:17.857 回答