Привет всем, я пытаюсь использовать boost::unordered_set
для пользовательского типа класса. Класс хранит информацию о координатах и некоторых других значениях, но только координаты используются для создания значения хеш-функции. Теперь, если я хочу вставить точку, и уже есть точка с равными координатами (отсюда набор), мне нужно изменить третье значение от исходного объекта (например, object.isDuplicate = true
очень упрощенный). Пожалуйста, не слишком привязывайтесь к значению bool и обнаружению дубликатов, потому что в исходном коде это немного сложнее, но это должно только показать, что мне нужен неконстантный доступ к хранимому классу. Я могу использовать только Boost 1.53 и C ++ 03 и GCC 4.4.3
Проблема сейчас, когда я пытаюсь вставить точку с boost::unordered_set::insert
я получаю pair<iterator, bool>
из которых первый член является неизменным итератором для вставленной или исходной записи, а второй является bool
указывает, было ли введено значение или нет. Я не могу изменить значение с помощью неизменяемого итератора, к сожалению, поэтому мне пришлось думать о чем-то другом. Поэтому я сейчас пытаюсь сохранить указатель на мой объект в наборе, а затем получить к нему доступ через этот указатель, чтобы изменить значение (что должно быть в порядке, поскольку значение не имеет ничего общего со значением хеш-функции и, следовательно, не изменяет ключ). Поэтому я попытался перегрузить boost::hash_value
функция для принятия указателя на мой класс, например:
size_t hash_value(const A * a) {
size_t seed = 0;
boost::hash_combine(seed, a->a);
boost::hash_combine(seed, a->b);
return seed;
}
Но unordered_set
похоже, не использует мою перегруженную функцию (я попытался напечатать семя в конце, но он не появляется, поэтому я предполагаю, что он использует другую перегрузку), даже если я инициализирую свой набор с unordered_set< A *, boost::hash<A *> >
, Для аспекта хеширования: когда я пытаюсь использовать набор без указателя, он работает нормально, но я не могу изменить значение.
Я немного искал в boost :: ссылка на хеш и нашел эту перегрузку template<typename T> std::size_t hash_value(T* const&);
который, я думаю, используется вместо моего собственного (и просто хэшируется с адресом объектов), но затем я удивляюсь, почему мой компилятор не запрашивает переопределение этой функции (я компилирую с -Wall -Wextra -pedantic
флаги включены.
Так это актуальная проблема? И если это как я могу сказать моему компилятору явно использовать мою пользовательскую хэш-функцию?
Наконец небольшой пример, который я написал, чтобы проверить все
#include <iostream>
#include <string>
#include <boost/functional/hash.hpp>
#include <boost/unordered_set.hpp>
using boost::unordered_set;
struct A {
double a;
double b;
bool isDup;
A(const double a, const double b): a(a), b(b), isDup(false) {}
A(const A & a): a(a.a), b(a.b), isDup(a.isDup) {}
/* Two equal As ought to have a bitwise equal floating point value so this is okay */
bool operator==(const A & a) const {
if (a.a != this->a) return false;
if (a.b != this->b) return false;
return true;
}
};size_t hash_value(const A * a) {
size_t seed = 0;
boost::hash_combine(seed, a->a);
boost::hash_combine(seed, a->b);
std::cout << "Seed: " << seed << std::endl; /* This is not printed so i assume the function is not called */
return seed;
}int main() {
A a1(1.2, 2.3);
A a2(2.3, 3.4);
A a3(3.4, 4.5);
A a4(a1);
unordered_set< A *, boost::hash<A *> > usa; /* This was unintended lol */
if ( ! usa.insert(&a1).second ) std::cout << "Error " << a1.a << ", " << a1.b << " is already in set" << std::endl;
if ( ! usa.insert(&a2).second ) std::cout << "Error " << a2.a << ", " << a2.b << " is already in set" << std::endl;
if ( ! usa.insert(&a3).second ) std::cout << "Error " << a3.a << ", " << a3.b << " is already in set" << std::endl;
if ( ! usa.insert(&a4).second ) {
/* This is not called */
std::cout << "Error " << a4.a << ", " << a4.b << " is already in set" << std::endl;
(*(usa.insert(&a4).first))->isDup = true;
}
}
Есть несколько проблем с вашей первоначальной функцией hash_value
:
boost
пространство имен, потому что boost::hash<T*>
Запускает boost::hash_value
который отключает зависимый от аргумента поиск имени.boost::hash
(перед включением boost/hash.hpp
).Например.:
#include <cstddef> // std::size_t
struct A;
namespace boost { inline std::size_t hash_value(A* a); }
#include <iostream>
#include <string>
#include <boost/functional/hash.hpp>
#include <boost/unordered_set.hpp>
struct A { /*... */};
size_t boost::hash_value(A* a) {
size_t seed = 0;
boost::hash_combine(seed, a->a);
boost::hash_combine(seed, a->b);
std::cout << "Seed: " << seed << std::endl; /* This is not printed so i assume the function is not called */
return seed;
}
Кроме того, вам нужно указать свой собственный класс сравнения элементов, по умолчанию в boost::unordered_set
сравнивает указатели
Как примечание стороны дизайн boost::hash
а также std::hash
является менее чем идеальным в отношении объединения хэшей из нескольких элементов. Я не могу рекомендовать достаточно, используя новый хэш фреймворк из N3980 Типы Не знаю #.
Хорошо, я нашел решение (или скорее обходной путь?) Сам сейчас. Вторая проблема была equal_to
класс, который используется по умолчанию boost::unordered_set
, equal_to<A *>
никогда не вернется false
потому что у нас всегда есть разные точки и, следовательно, &a1 == &a2
всегда будет иметь значение false, поэтому я должен был написать свой собственный компаратор, который разыменовывает объекты перед их сравнением, а затем вызывает их operator==
,
Тогда я просто заключил в капсулу hash
Функция и компаратор в отдельном классе и затем передают их как аргументы шаблона при создании набора следующим образом:
class compA {
public:
size_t operator()(const A * a) const {
size_t seed = 0;
boost::hash_combine(seed, a->a);
boost::hash_combine(seed, a->b);
return seed;
}
bool operator()(const A * a1, const A * a2) const {
if (*a1 == *a2) return true;
return false;
}
};
unordered_set<A *, compA, compA> usa;
Но я все еще хотел бы знать, почему моя первоначальная попытка не сработала.