c++ - boost unordered_set 的意外行为

Question

当我使用 boost::unordered_set 时，我遇到了一种我没有预料到的行为。我提取了一个最小的例子(虽然不太确定“最小”，但 :-) )来证明我的意思。该程序执行以下操作:

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

这个尺寸不是我所期望的。我认为不会插入第二个实例，因为它与第一个实例等效。文档说:

Pred: A binary predicate that takes two arguments of the same type as the elements and returns a bool. The expression pred(a,b), where pred is an object of this type and a and b are key values, shall return true if a is to be considered equivalent to b. This can either be a class implementing a function call operator or a pointer to a function (see constructor for an example). This defaults to equal_to, which returns the same as applying the equal-to operator (a==b). The unordered_set object uses this expression to determine whether two element keys are equivalent. No two elements in an unordered_set container can have keys that yield true using this predicate. Aliased as member type unordered_set::key_equal.

和:

Insert: Inserts new elements in the unordered_set. Each element is inserted only if it is not equivalent to any other element already in the container (elements in an unordered_set have unique values).

所以我没有正确阅读规范，但我无法弄清楚哪里出了问题。 (该规范来自 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

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

http://www.boost.org/doc/libs/1_56_0/doc/html/unordered/hash_equality.html

If you wish to use a different equality function, you will also need to use a matching hash function. For example, to implement a case insensitive dictionary you need to define a case insensitive equality predicate and hash function: