Неожиданное поведение boost unordered_set

Question

Когда я использовал boost :: unordered_set, я столкнулся с поведением, которого я не ожидал. Я извлек минимальный пример (не так уверен в «минимальном», хотя :-)), чтобы продемонстрировать, что я имею в виду. Программа выполняет следующие действия:

• Класса «edge_type» определяются с «индексом» поля, среди других полого
• Оператор Comparision определяется, возвращающим верно для двух случаев, если все их поля равны
• unordered_set определяется для тех edge_type с его собственной хэш-функции и предикат для проверки эквивалентных элементов
• хэш-функция использует все поля для вычисленного значения хэш
• предикат использует только «индекс» поле для проверки эквивалентности
• Два экземпляра 'edge_type' создаются с тем же индексом, но отличаются другими полями.
• Сравнивая два случая с оператором =() приводит к: «Не равно», как и ожидалось
• Сравнивая два экземпляра с результатами повышения :: unordered_set < ...> :: key_eq() в: «Инстансы эквивалент» как и следовало ожидать
• Установка второго экземпляра в unordered_set после того, как первая была вставлена, приводит к размеру unordered_set 2

Этот размер не то, что я ожидал. Я думал, что второй экземпляр не будет вставлен из-за того, что он будет эквивалентен первому. В документации сказано:

Pred: Бинарный предикат, который принимает два аргумента одного и того же типа, что и элементы и возвращает логическое значение. Выражение pred (a, b), где pred является объектом этого типа, а a и b являются ключевыми значениями, возвращает true, если a считается эквивалентным b. Это может быть либо класс, реализующий оператор вызова функции, либо указатель на функцию (см. Конструктор для примера). Это значение по умолчанию равно 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

Если два экземпляра следует считать равным, они также должны иметь одинаковое значение хеш-функции.Предикат равенства используется только тогда, когда хэши двух сущностей одинаковы, чтобы определить, действительно ли они равны или это случай случайного столкновения хэша.

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

Если вы хотите использовать другую функцию равенства, вам также потребуется использовать функцию сопоставления хэш. Например, чтобы реализовать случай нечувствительным словарь вам нужно определить регистрозависимости равенство предиката и хэш-функции:

Answer 2

Тест терпит неудачу, потому что вы вставили 2 неравные объекты в наборе. Поэтому ec.size() должен возвращать 2.

Это связано с тем, что реализация edge_equal проверяет только равенство индексов, а хеш-функция зависит от всех членов.