Как можно использовать union в качестве ключа unordered_map?

Question

[quad69]

Есть такой union:

union ObjectPos {
    unsigned short x;
    unsigned short y;
}

И мне нужно использовать его в качестве ключа для unordered_map:
std::unordered_map<ObjectPos , Object*> objects;

Задача стоит в том, что есть N штук экземпляров класса Object и мне нужно по x и y находить их.
Конкретное количество неизвестно и по ходу работы программы одни объекты удаляются, и могут появиться другие (всё происходит в разных координатах).

Можно конечно ObjectPos заменить на обычный int и написать функцию которая будет из двух short'ов делать один int (и наоборот), но это крайне не удобно...

Comments

[Евгений Шатунов]

quad69 ,

и мне нужно по x и y находить их

Можно конечно ObjectPos заменить на обычный int и написать функцию которая будет из двух short'ов делать один int

Какие свойства отличают union от struct?
Ты точно выбрал правильный формат памяти для записи позиций объектов?

[Василий Дёмин]

quad69, подсказка - union имеет размер наибольшего поля (в данном случае 2 байта), при этом в каждый момент времени валидным считается только одно из всех полей - последнее установленное. Вам нужна структура из двух значений типа short

[quad69]

Евгений Шатунов, Если честно, не знаю. Я только в процессе изучения, до этого кодил на PHP и подобных языках, а это сам понимаешь, детский сад по сравнению с C++. Я не мало гуглил по этому поводу и там везде рассказывается про способ хранения, что мне особо ничего не говорит, ведь в конечном итоге они работают не отличимо

[Евгений Шатунов]

quad69, union и struct работают еще как отличимо.
Твой ObjectPos имеет размер 2 байта и выравнивание на 2 байта. Оба его поля размещаются в этих двух байтах, адреса этих полей одинаковы и размеры тоже одинаковы - 2 байта.
Т.к. поля у тебя имеют один тип, для объектов ObjectPos допускается задать значение одного поля и прочитать его же из другого поля. Документация дает исчерпывающее понимание этого формата.

В структуре - struct - все поля имеют свой собственный адрес, упакованы согласно своему выравниванию и занимают свою уникальную память согласно своему собственному размеру.
Если бы ты написал так:

struct ObjectPos {
    unsigned short x;
    unsigned short y;
};

то размер ObjectPos был бы уже 4 байта, т.к. оба поля имели бы в структуре свою собственную память.

Т.к. ты еще только учишься, тебе стоит больше внимания уделять документации и общим источникам информации.

Answer 1

[Василий Дёмин]

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

struct MyStruct {
    unsigned short x;
    unsigned short y;
};

template<>
struct std::hash<MyStruct> {
    std::size_t operator()(MyStruct const& s) const noexcept {
        return ((size_t)s.x << 16) | s.y;
    }
};

Comments

[Евгений Шатунов]

Василий Дёмин , в коде подсчета хэша сейчас есть UB. Давай приглядимся к документации побитовых сдвигов.

In any case, if the value of the right operand is negative or is greater or equal to the number of bits in the promoted left operand, the behavior is undefined.

16-тибитное целое на шестнадцать бит сдвигать неправильно.
Лично я бы написал здесь такое приведение: ( size_t( s.x ) << 16 ).

[Василий Дёмин]

Евгений Шатунов, Забыл, что типы автоматом не приводятся. Исправил

[quad69]

Спасибо, теперь работает! Пришлось немного подправить, у меня почему то оно не хочет работать без operator== в структуре (весь вывод в ошибках, решение нашёл благодаря гуглу).

struct ObjectPos {
	unsigned short x;
	unsigned short y;

	bool operator==(const ObjectPos &pos) const {
		return x == pos.x && y == pos.y;
	}
};

P.s Не понимаю зачем это нужно, ведь оно же ищет по хеш-функции определенной выше?

[Евгений Шатунов]

quad69, все верно. Условиями установки пользовательского типа в качестве ключа std::unordered_map[?] являются по умолчанию: наличие достижимого инстанцирования шаблона std::hash и оператора эквивалентности.
Но если ты внимательно посмотришь документацию, то увидишь что тебе достаточно было всего лишь указать правильные аргументы шаблона std::unordered_map, использовав свои типы вместо типов по умолчанию.

Не понимаю зачем это нужно, ведь оно же ищет по хеш-функции определенной выше

Это нужно для случаев коллизии по хэшу. В этом случае std::unordered_map будет искать среди ключей с одинаковым хэшем эквивалентный искомому.