Блог

Я создал 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»?

Сравнения эквивалентности на основе хэша могут иметь ложные срабатывания, которые разрешаются вызовом operator== .

Сравнения эквивалентности на основе хэша не должны иметь ложноотрицательных результатов, но ваши имеют. Ваши два «не на 100% одинаковых» ключа имеют разные значения хэша, поэтому элемент даже не найден в качестве кандидата для тестирования с использованием operator== .

Необходимо, чтобы (a == b) подразумевало (хэш(a) == хэш(b)) , и ваши определения нарушают это предварительное условие. Хэш-таблица со сломанным предварительным условием может вести себя неправильно многими способами, в том числе не находить элемент, который вы ищете.

Используйте другую структуру данных, которая не зависит от хеширования, но соответствует ближайшему соседу. Octtree было бы разумным выбором.

Равенство 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 в сегменты «на лету».