boost unordered_set的意外行为

Question

当我使用boost::unordered_set时，我遇到了一种我没有预料到的行为。我提取了一个极小的例子(但对“极小”不太确定:-)来说明我的意思。该方案做了以下工作：

• 类'edge_type‘定义为字段'index’以及其他字段
• 定义了一个比较运算符，如果两个实例的所有字段相等，则返回true。
• 使用自己的散列函数和谓词为那些边缘_类型定义了一个unordered_set，以检查等效的元素
• 哈希函数使用所有字段来计算哈希值。
• 谓词仅使用字段“index”检查等价性。
• 创建“edge_type”的两个实例具有相同的索引，但具有不同的其他字段。
• 将这两个实例与operator=()进行比较，结果如下：“不等于”
• 将这两个实例与boost::unordered_set<...>::key_eq()进行比较，结果如下所示：“实例等效”
• 在插入第一个实例后将第二个实例插入到unordered_set中将导致unordered_set大小为2。

这个尺寸和我预期的不一样。我认为第二个实例不会被插入，因为它与第一个实例是等价的。文件上说：

Pred:一个二进制谓词，它接受两个相同类型的参数作为元素，并返回bool。表达式pred(a，b)，其中pred是这种类型的对象，a和b是键值，如果a被认为等同于b，则返回true。这可以是实现函数调用操作符的类，也可以是指向函数的指针(示例见构造函数)。这默认为equal_to，它的返回与应用相等的操作符(a==b)相同。unordered_set对象使用此表达式确定两个元素键是否等效。unordered_set容器中的任何两个元素都不能有使用此谓词生成true的键。别名为成员类型unordered_set::key_equal。

和：

插入:在unordered_set中插入新元素。只有当每个元素不等同于容器中的任何其他元素( unordered_set中的元素具有唯一值)时，才会插入该元素。

因此，我没有正确地阅读规范，但我不知道我哪里出错了。(规范来自www.cplusplus.com。我和tr1::unordered_set有同样的经历，gcc 4.8.1，boost 1.54。我们还没有在工作中使用C++11 )。我很感激任何关于我去哪的暗示。

示例：

/* File: test_set.cpp
   Compile: g++ -I ${BOOST_INCLUDE} -L ${BOOST_LIB) -lboost_unit_test_framework test_set.cpp -o test_set
   Output:
   Running 1 test case...
   test_set.cpp(110): error in "types_construction_and_operators": check ec.size() == 1 failed [2 != 1]
 *** 1 failure detected in test suite "Master Test Suite" 
*/


#define BOOST_TEST_DYN_LINK
#define BOOST_TEST_MAIN

#include <boost/functional.hpp>
#include <boost/unordered_set.hpp>
#include <boost/functional/hash.hpp>
#include <boost/operators.hpp>
#include <boost/test/unit_test.hpp>
#include <boost/test/unit_test.hpp>
#include <boost/test/results_reporter.hpp>
#include <boost/test/output_test_stream.hpp>
#include <boost/test/unit_test_log.hpp>
#include <boost/test/unit_test_suite.hpp>
#include <boost/test/framework.hpp>
#include <boost/test/detail/unit_test_parameters.hpp>
#include <boost/test/utils/nullstream.hpp>
typedef boost::onullstream onullstream_type;

using boost::test_tools::output_test_stream;
using namespace boost::unit_test;

#define BOOST_TEST_MODULE test_unordered_set


struct edge_type;
struct edge_equal_to;
typedef  boost::unordered_set<edge_type, boost::hash<edge_type>, edge_equal_to > edge_collection_type;
std::size_t hash_value( edge_type const& edge );

struct edge_type : public boost::equality_comparable<edge_type> {
   edge_type( std::size_t index, std::size_t f, std::size_t t );
   edge_type( edge_type const& );
   std::size_t index;
   std::size_t from_node_index;
   std::size_t to_node_index;
   edge_type& operator=( edge_type const& that );
   bool operator==( edge_type const& that ) const;
};

struct edge_equal_to : std::binary_function< edge_type, edge_type, bool > {
   bool operator()( edge_type const& edge1, edge_type const& edge2 ) const;
};



bool edge_equal_to::operator()( edge_type const& edge1,
                                edge_type const& edge2 ) const {
   return edge1.index == edge2.index ;
}

std::size_t hash_value( edge_type const& edge ) {
   std::size_t  seed = 0;
   boost::hash_combine(seed, edge.index );
   boost::hash_combine(seed, edge.from_node_index );
   boost::hash_combine(seed, edge.to_node_index );
   return seed;
}

edge_type::edge_type( std::size_t idx,
                      std::size_t f,
                      std::size_t t ) :
   index(idx), from_node_index(f), to_node_index(t) {
}

edge_type::edge_type( edge_type const& that ) {
   from_node_index = that.from_node_index;
   to_node_index   = that.to_node_index;
   index = that.index;
}

edge_type& edge_type::operator=( edge_type const& that ) {
   if( this != &that ) {
      from_node_index = that.from_node_index;
      to_node_index   = that.to_node_index;
      index = that.index;
   }
   return *this;
}

bool edge_type::operator==( edge_type const& that ) const {
   return index == that.index &&
          from_node_index == that.from_node_index &&
          to_node_index == that.to_node_index;
}


BOOST_AUTO_TEST_SUITE( test_suite_unordered_set )

BOOST_AUTO_TEST_CASE( types_construction_and_operators )
{
   edge_type edge1( 1, 100, 101 );
   BOOST_CHECK_EQUAL( edge1.index, 1 );
   BOOST_CHECK_EQUAL( edge1.to_node_index, 101 );
   BOOST_CHECK_EQUAL( edge1.from_node_index, 100 );

   edge_type edge2( 1, 102, 103 );
   BOOST_CHECK_EQUAL( edge2.index, 1 );
   BOOST_CHECK_EQUAL( edge2.to_node_index, 103 );
   BOOST_CHECK_EQUAL( edge2.from_node_index, 102 );

   BOOST_CHECK( edge1 != edge2 );

   edge_collection_type ec;

   ec.insert( edge1 );
   BOOST_CHECK_EQUAL( ec.size(), 1 );

   BOOST_CHECK_EQUAL( ec.key_eq()( edge1, edge2 ), true );
   ec.insert( edge2 );
   BOOST_CHECK_EQUAL( ec.size(), 1 );  // <---- This test fails !
}

BOOST_AUTO_TEST_SUITE_END()

Answer 1

如果两个实例应该被认为是相等的，那么它们也应该具有相同的散列值。只有当两个实体的散列相同时才使用相等谓词来确定它们是否真正相等，或者这是偶然的哈希冲突情况。

equality.html

如果希望使用不同的相等函数，还需要使用匹配的散列函数。例如，要实现不区分大小写的字典，需要定义不区分大小写的等式谓词和哈希函数：

Answer 2

测试失败，因为您在集合中插入了两个不相等的对象。因此，ec.size()应该返回2。

这是因为edge_equal的实现只测试索引的相等性，而哈希函数依赖于所有成员。