Как получить std :: hash_set & lt; pair & lt; T1, T2 & gt; & gt; скомпилировать и запустить
Проблемный домен
У меня есть (потенциально) длинные списки пар данных, которые мне нужно объединить (и выполнить некоторую логику), чтобы не было дубликатов. Спаривания были int типа, но из-за роста количества данных, я преобразую его в пары size_tи, таким образом, мой тип данных теперь объявлен как pair<size_t, size_t>,
Код, ранее проверенный на уникальность, имея hash_set и исследуя это, чтобы видеть, было ли данное соединение уже замечено и обработано. В качестве ключа его удобно использовать INT64 и построил ключ, используя сдвиг битов и упаковку:
INT64 key = ((INT64)pairsListEntry->first) << 32 | pairsListEntry->second;
Это работало хорошо, так как два intотлично вписывается в INT64 и в результате уникальный ключ. Но по понятным причинам это больше не работает.
Немедленная проблема
Чтобы приспособиться к новым размерам, я попытался провести рефакторинг и объявить hash_set как:
std::hash_set<pair<size_t, size_t>> m_seenPairs;
Это, однако, не удается при компиляции кода, который создает экземпляр этого класса со следующим сообщением об ошибке:
C: \ Program Files (x86) \ Microsoft Visual Studio 9.0 \ VC \ include \ xhash (71): ошибка C2440: «приведение типа»: невозможно преобразовать из «const std :: pair»<_Ty1, _Ty2> ‘до’ size_t ‘
Это происходит глубоко внутри реализации STL, в следующей функции (на return линия):
template<class _Kty> inline
size_t hash_value(const _Kty& _Keyval)
{ // hash _Keyval to size_t value one-to-one
return ((size_t)_Keyval ^ _HASH_SEED);
}
Причина довольно ясна: pair<T1, T2> не знает, как бросить size_t для того, чтобы вычислить хэш-код.
На данный момент, я застрял на том, как заставить его работать. Гугл-фу не особо облажается. Я видел пару постов на ТАК с std::map а также pair, но там, кажется, «просто работать».
Среда VS2008, неуправляемая цель платформы x64.
Вещи, которые я пытался
Я пытался предоставить свой собственный компаратор, как я видел пост, который выглядел по крайней мере едва похожим в дальнейшем:
struct pairs_equal_compare
{
bool operator()(const pair<SampleIdIndex_t, SampleIdIndex_t> & p1, const pair<SampleIdIndex_t, SampleIdIndex_t> & p2) const
{
return (p1.first == p2.first) && (p1.second == p2.second);
}
};
// Holds a set of pairs that are known to exist for deduplication purposes.
stdext::hash_set<pair<SampleIdIndex_t, SampleIdIndex_t>,
stdext::hash_compare<pair<SampleIdIndex_t, SampleIdIndex_t>, pairs_equal_compare>> m_seenPairs;
Это (к тому времени, когда я получил объявления и структуру, должным образом объявленные) привело к точно такой же ошибке — понимая теперь, что это действительно не помогает обойти внутренний вызов hash_value вычислить хеш-код.
Я также кратко попытался использовать pairs_equal_compare на месте hash_compare, но это вызвало больше ошибок компиляции и выглядит как неправильное направление …
Кажется, должен быть разумный способ получить hash_set работать на pair (или любые данные нецелого типа), но это ускользает от меня о том, как этого добиться.
Решение
Вы также можете использовать подходящий Traits объект, который ведет себя как hash_compareт.е. он должен определять два operator()s:
size_t operator()(const Key &key) const; // This one returns the hash of key
bool operator()(const Key &first,
const Key &second) const; // This one returns true if first is less than second
и две целочисленные константы, которые вы, вероятно, можете просто взять из реализации по умолчанию:
const size_t bucket_size = 4;
const size_t min_buckets = 8;
Увидеть документация hash_compare.
Код будет выглядеть так
struct pair_comparator{
typedef std::pair<std::size_t, std::size_t> Key;
size_t operator()(const Key &key) const { return /* your hash code here */; }
bool operator()(const Key &first,
const Key &second) const { return first < second; }
const size_t bucket_size = 4;
const size_t min_buckets = 8;
};
stdext::hash_set<
std::pair<std::size_t, std::size_t>,
pair_comparator
> s;
Изменить: документация говорит, что вы также можете получить из специализации hash_compareи переопределяет только те элементы, которые вам не нравятся, поэтому:
struct pair_comparator : public stdext::hash_compare<std::pair<std::size_t, std::size_t> >{
typedef std::pair<std::size_t, std::size_t> Key;
size_t operator()(const Key &key) const { return /* your hash code here */; }
bool operator()(const Key &first,
const Key &second) const { return first < second; }
};
Что должно избежать проблемы определения const int члены.
Другие решения
Из коробки, stdext::hash_set<> работает только с типами, которые неявно преобразуются в size_t, За std::pair<>вам нужно будет предоставить аргумент stdext::hash_compare<> (за stdext::hash_set<>«s Traits параметр), который ведет себя как таковой, так как std::pair<> сам не делает.
Следующее работает для меня с VS2013, и я не понимаю, почему это не будет работать и с VS2008:
#include <cstddef>
#include <utility>
#include <hash_set>
struct pair_hasher
{
typedef std::pair<std::size_t, std::size_t> value_type;
value_type value;
pair_hasher(value_type const& v) : value(v) { }
operator std::size_t() const
{
return (5381 * 33 ^ value.first) * 33 ^ value.second;
}
};
bool operator <(pair_hasher const& a, pair_hasher const& b)
{
return a.value < b.value;
}
Тогда вам нужно будет объявить свой stdext::hash_set<> экземпляр как таковой:
stdext::hash_set<
std::pair<std::size_t, std::size_t>,
stdext::hash_compare<pair_hasher>
> s;
Для типов, отличных от целочисленных типов для std::pair<>, Обновить pair_hasher::operator std::size_t как необходимо (operator < должно быть хорошо, как есть, до тех пор, пока типы в std::pair<> сами уже сопоставимы).