Хэш-карта векторов, проверка ключа диапазона
Учитывая unordered_map<vector<T*>,V> с соответствующей хеш-функцией, можно ли проверить существование значения ключа в форме span<T*> без предварительного преобразования его в вектор (и выделения кучи памяти)? Мы можем предположить, что размеры всех ключей (как векторов, так и диапазонов) равны, но неизвестны во время компиляции.
Лучшее, что я могу придумать, — это создать хэш-набор set<int64_t> хэш-значений на карте, вычислить хэш диапазона и преобразовать его в вектор только в том случае, если его хэш существует. Но все это кажется довольно громоздким, учитывая, что span содержит всю информацию, необходимую в этом случае.
Я тоже был бы рад, если бы мы нашли какой-нибудь альтернативный тип ключа для карты, который работает с интервалами. Черт возьми, может быть, unordered_map<span<T*>,pair<vector<T*>,V>> работает, где ключ диапазона фактически хранит указатель данных и размер соответствующего ему вектора значений?
можно ли проверить существование значения ключа в виде span<T*> без предварительного преобразования его в вектор (и выделения кучи памяти)? Я бы поискал прозрачный хеш-ключ.
Прозрачный хеш-ключ — это именно то, что я искал, спасибо!
Ответы 2
Вам нужен прозрачный хеш (и равенство) для вашей карты. Поскольку вы можете создать std::span из std::vector, вам нужно реализовать его только для std::span<T*>. Вам придется использовать find вместо operator[] или at до C++26.
struct hash_span {
using is_transparent = void;
std::size_t operator()(std::span<T*> data) { /* existing code here */ }
};
struct equal_span {
using is_transparent = void;
bool operator()(std::span<T*> lhs, std::span<T*> rhs) { /* existing code here */ }
};
Который затем используется как unordered_map<vector<T*>, V, hash_span, equal_span>.
возможно, вы можете использовать std::reference_wrapperstd::span<T*> в качестве ключа в unordered_map.
std::unordered_map<std::reference_wrapper<std::span<T*>>, int> map;
- Плюсы: исключает необходимость использования специального компаратора равенства и пользовательского хеш-функция для std::span<T*>
- Минусы: Представляет std::reference_wrapper, который может быть менее интуитивным и потенциально менее эффективен из-за косвенности.
В моем случае карта должна владеть своими ключами. Поэтому понадобится vector<T*> или какой-то специальный ключ. Тем не менее, спасибо за предложение.
это не имеет особого смысла, поскольку ключи карт являются константами, и их порядок\хеш или содержимое не могут быть изменены. Обычно это момент, когда вводится суррогатный ключ.