CODEWITHSUNDEEP
c++boost
ThorstenSchmidt
ThorstenSchmidt

Reputation: 13

Unexpected behavior of boost unordered_set

When I was using a boost::unordered_set I was confronted with a behavior that I did not expect. I extracted a minimal example (not so sure about the 'minimal', though :-) ) to demonstrate what I mean. The programm does the following:

This size is not what I expected. I thought that the second instance would not be inserted because of it being equivalent with the first. The documentation says:

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.

And:

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).

So I am not reading the spec correctly but I can't figure out where I go wrong. (The spec is from www.cplusplus.com. I had the same experience with tr1::unordered_set, gcc 4.8.1, boost 1.54. [We don't use C++11 yet at work ...]). I appreciate any hint about where I go here.

Example:

/* 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()

Upvotes: 1

Views: 119

Answers (2)

Richard Hodges
Richard Hodges

Reputation: 69864

The test fails because you have inserted 2 unequal objects into the set. Therefore ec.size() should return 2.

This is because the implementation of edge_equal only tests for equality of indices, while the hash function is dependant on all members.

Upvotes: 1

Revolver_Ocelot
Revolver_Ocelot

Reputation: 8785

If two instances should be considered equal, they should also have the same hash value. Equality predicate is used only when hashes of two entities are same, to determine, if those are truly equal or this is the case of accidental hash collision.

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:

Upvotes: 1

Related Questions