Неупорядоченная карта работает необычно медленно по сравнению с картой C ++ - PullRequest
Новая
       9

Неупорядоченная карта работает необычно медленно по сравнению с картой C ++

0 голосов
/ 24 июня 2018

Я пытаюсь использовать неупорядоченную карту, чтобы хэшировать массив размера 2 и искать карту позже. К сожалению, это значительно медленнее, чем когда я использую обычную карту c ++, что я не считаю правильным, потому что вставка и поиск - это O (log (n)) на карте и O (1) на неупорядоченной карте. Следует отметить, что вместо массива я использовал объединенное строковое значение значений в массиве на карте. Я не думаю, что это должно иметь значение, потому что конкатенация строк стоит дороже, чем создание массива размера 2. Я приложил соответствующий код.

Спасибо всем:) 

struct arraySizeTwoEqualityStruct 
{

    bool operator()( const array< double, 2 >& leftArraySizeTwo, 
                     const array< double, 2 >& rightArraySizeTwo ) const 
    {

        return 
                abs( leftArraySizeTwo[ 0 ] - rightArraySizeTwo[ 0 ] ) < 0.0001 &&
                abs( leftArraySizeTwo[ 1 ] - rightArraySizeTwo[ 1 ] ) < 0.0001;

    }

};


struct arraySizeTwoHashStruct 
{

    size_t operator( )( const array< double, 2 >& arrayToHash ) const
    {

        return ( hash< double > ( ) ( arrayToHash[ 0 ] ) ^ hash< double > ( ) ( arrayToHash[ 1 ] ) ); 

    }

};

1 Ответ

0 голосов
/ 24 июня 2018

[unord.req] / 5 Два значения k1 и k2 типа Key считаются эквивалентными, если предикат равенства ключей контейнера возвращает true при передаче этих значений,Если k1 и k2 эквивалентны, хэш-функция контейнера должна возвращать одно и то же значение для обоих.

Ваши arraySizeTwoEqualityStruct и arraySizeTwoHashStruct нарушают это требование.Первый объявляет два элемента, которые «достаточно близки», чтобы быть эквивалентными, но последний по-прежнему дает им другой хэш.Поэтому ваша программа демонстрирует неопределенное поведение.

[unord.req] / 3 Каждый неупорядоченный ассоциативный контейнер параметризуется с помощью ... двоичного предиката Pred, который вызывает отношение эквивалентности для значений типа Key.

Акцент мой.arraySizeTwoEqualityStruct дополнительно недопустимо в том смысле, что оно не вызывает отношения эквивалентности.В частности, он не транзитивен: существуют значения A, B и C, такие что A "достаточно близко" к B и B к C, но Aне "достаточно близко" к C.

...