#c #unordered-map
#c #неупорядоченная карта
Вопрос:
Я создал unordered_map, используя тип ключа rot3d, который определен ниже:
#ifndef EPS6
#define EPS6 1.0e-6
#endif
struct rot3d
{
double agl[3]; // alpha, beta, gamma in ascending order
bool operator==(const rot3d amp;other) const
{
// printf("== usedn");
return abs(agl[0]-other.agl[0]) <= EPS6 amp;amp; abs(agl[1]-other.agl[1]) <= EPS6 amp;amp; abs(agl[2]-other.agl[2]) <= EPS6;
}
};
Равенство rot3d определяется условием, что каждый компонент находится в пределах небольшого расстояния от того же компонента от другого объекта rot3d.
Затем я определил тип значения RotMat:
struct RotMat // rotation matrix described by a pointer to matrix and trunction number
{
cuDoubleComplex *mat = NULL;
int p = 0;
};
В конце концов, я определил хэш-таблицу из rot3d в RotMat, используя самостоятельно определенную хэш-функцию:
struct rot3dHasher
{
std::size_t operator()(const rot3damp; key) const
{
using std::hash;
return (hash<double>()(key.agl[0]) ^ (hash<double>()(key.agl[1]) << 1) >> 1) ^ (hash<double>()(key.agl[2]) << 1);
}
};
typedef std::unordered_map<rot3d,RotMat,rot3dHasher> HashRot2Mat;
Проблема, с которой я столкнулся, заключалась в том, что ключ был напечатан, чтобы быть в хэш-таблице, но функция «find» его не нашла. Например, я напечатал ключ, используя итератор хэш-таблицы:
Key: (3.1415926535897931,2.8198420991931510,0.0000000000000000)
Но затем я также получил эту информацию, указывающую на то, что ключ не был найден:
(3.1415926535897931,2.8198420991931505,0.0000000000000000) not found in the hash table.
Хотя два ключа не совпадают на 100%, определение «==» должно гарантировать, что они будут равны. Итак, почему я вижу этот ключ в хэш-таблице, но он не был найден с помощью «find»?
Комментарии:
1. Я подозреваю, что проблема может заключаться в том, что вам не разрешено предоставлять хешер, который выдает разные значения хэша для элементов, которые сравниваются равными. Значения, которые отличаются, но в
EPS6
пределах друг от друга, будут сравниваться равными при создании разных хэшей.2. У вас есть допуск, определенный в вашем операторе равенства. В хэш-функции нет такой вседозволенности. Для значений с плавающей запятой требуются другие структуры данных, такие как восьмидеревья, хэш-таблица просто не будет вести себя так, как вы надеетесь.
3. Ваше определение равенства также имеет основную проблему в том, что оно не является транзитивным. С вашим определением возможно, что a == b и b == c, но a != c . Это не работает.
Ответ №1:
Сравнения эквивалентности на основе хэша могут иметь ложные срабатывания, которые разрешаются вызовом operator==
.
Сравнения эквивалентности на основе хэша не должны иметь ложноотрицательных результатов, но ваши имеют. Ваши два «не на 100% одинаковых» ключа имеют разные значения хэша, поэтому элемент даже не найден в качестве кандидата для тестирования с использованием operator==
.
Необходимо, чтобы (a == b) подразумевало (хэш(a) == хэш(b)) , и ваши определения нарушают это предварительное условие. Хэш-таблица со сломанным предварительным условием может вести себя неправильно многими способами, в том числе не находить элемент, который вы ищете.
Используйте другую структуру данных, которая не зависит от хеширования, но соответствует ближайшему соседу. Octtree было бы разумным выбором.
Комментарии:
1. Я выяснил проблему с помощью механизма хэш-таблицы. Когда хэш-таблица выполняет поиск ключа, она сначала использует хэш-функцию для хэширования индекса в сегменты. Если индекс указывает на сплошную ячейку, то он извлекает ключ из корзины и сравнивает его с искомым ключом. Если два ключа равны (здесь происходит сравнение ключей), ключ найден. Причиной моей ошибки должно быть то, что искомый ключ фактически не был сохраненным ключом из-за числовых ошибок, и хэш-таблица так и не достигла корзины, в которой был сохранен истинный ключ, и проверка равенства «==» не была инициирована.
Ответ №2:
Равенство rot3d определяется условием, что каждый компонент находится в небольшом диапазоне от того же компонента от другого объекта rot3d.
Это не эквивалентность. Это должно быть у вас, a==b
и b==c
подразумевает a==c
. Ваш не соответствует этому требованию.
Использование несоответствия в алгоритме std или контейнере нарушает предварительные условия std, что означает, что ваша программа неправильно сформирована, диагностика не требуется.
Также ваш хэш хэширует эквивалентные значения по-разному. Также незаконно.
Один из способов исправить это — создать сегменты. Каждый сегмент имеет размер вашего epsilon.
Чтобы определить, находится ли значение в ваших сегментах, проверьте сегмент, в который вы поместили значение проверки, плюс все соседние сегменты (3 ^ 3 или 27 из них).
Для каждого элемента дважды проверьте расстояние.
struct bucket; // array of 3 doubles, each a multiple of EPS6. Has == and hash. Also construct-from-rod3d that rounds.
bucket get_bucket(rot3d);
Теперь, скорее всего, вы просто кэшируете. И в формате EPS достаточно хорош.
template<class T, class B>
struct adapt:T{
template<class...Args>
auto operator()(Argsamp;amp;...args)const{
return T::operator()( static_cast<B>(std::forward<Args>(args))... );
}
using is_transparent=void;
};
std::unordered_map<bucket, RotMat, adapt<std::hash<rot3d>, bucket>, adapt<std::equal_to<>, bucket>> map;
здесь мы преобразуем rod3ds в сегменты «на лету».