Представить список целых чисел как одно целое число в C++

Question

Я хочу сконденсировать список из 100 неотрицательных 32-битных целых чисел в одно целое число. В идеале результирующее целое всегда уникально, но допустимо несколько относительно редких столкновений. Как это сделать?

Я пишу головоломку. Часть моего алгоритма поиска позволяет избежать повторного изучения состояний головоломки, которые уже видели. Я буду использовать целое число, сгенерированное из списка, в качестве ключа в таблицу statesAlreadySeen. В настоящее время я использую строки в качестве ключей. Однако я видел заметные улучшения производительности при переходе от строковых ключей к целым ключам в map<,>, поэтому я хотел бы переключиться.

Редактировать: Спасибо за неупорядоченные предложения карты! Однако мне все еще интересно узнать о фактической хэш-функции. IIRC - простая функция, включающая базовую манипуляцию бит и xoring. Было бы замечательно видеть это и иметь общее понимание вероятностей столкновений.

Answer 1

Как указано в комментариях, вам необходимо использовать хеш-функцию. Наиболее легко осуществляется с boost::hash_range:

#include <boost/functional/hash.hpp> 
std::size_t vectorhash(std::vector<int> f){ 
    size_t hash = std::size_t hash = boost::hash_range(f.begin(), f.end()); 
} 

Сказав, что, если у вас нет реальной необходимости держать государства упорядоченные (и я не могу понять, почему вы бы), я бы с решением о us2012 сохраняя ключи string и переключаясь на unordered_map - таким образом, чтобы контейнер позаботился о хешировании.