Я генерирую большое количество экземпляров классов и сохраняю их в std::unordered_set.Я определил хэш-функцию и отношение равенства, и пока все работает как надо - я вставляю 10000 экземпляров с unordered_set::insert, и я могу найти их с unordered_set::find.Все объекты не повреждены, и нет никаких намеков на повреждение памяти или любую другую проблему.
Однако, когда я продолжаю вставлять, 32769-я вставка завершается с ошибкой - она не выдает, ноон возвращает пару, в которой итератор равен == nullptr (0x00000000).insert определяется как:
pair<iterator, bool> insert(const value_type& Val);
и, как правило, *iterator - это ключ, который я вставил, а bool - true.
Если я (после ошибки) пытаюсь найтиобъект, это - это в наборе;если я попытаюсь вставить его снова, он скажет мне, что он уже там;таким образом, вставка, кажется, работала нормально.Просто возвращаемое значение равно pair<nullptr,true> вместо pair<iterator,bool>.
Обратите внимание, что если я вручную заполнил итератор и продолжу в отладчике, то же самое произойдет снова при первой вставке после 65536, а затем в 131072 и т. Д.(так что для 2 ^ 15 + 1, 2 ^ 16 + 1, 2 ^ 17 + 1, ...) - но не в 3 * 32768 + 1 и т. д.
Для меня это выглядит как-тоshort переполнение.Может быть, мои хэши действительно плохие и приводят к неравномерному заполнению ведер, а в 32768 у него заканчиваются ведра?Я не смог найти ничего более подробного о таком пределе при поиске в Google, и я не знаю достаточно о сбалансированных деревьях или что бы это ни было внутри.
Тем не менее, код библиотеки std должен быть в состоянии справиться с плохим хешированием, я понимаю, еслион становится медленным и неэффективным, но он не должен терпеть неудачу .
Вопрос: Почему не работают вставки 2 ^ 15th + 1, 2 ^ 16th + 1 и т. д.,и как я могу избежать этого?
Это в Microsoft Visual Studio 2017 V15.7.1 (последняя версия по состоянию на 2018-05-15).Компилятор настроен на использование правил C ++ 2017, но я сомневаюсь, что это окажет какое-либо влияние.
Я не могу вставить полный код для минимального жизнеспособного решения, так как генерация объектов сложна для нескольких классов и методов и насчитывает несколько сотенСтроки кода, сгенерированные хэши, очевидно, зависят от деталей объектов, и их нелегко воспроизвести в фиктивном коде.
### Обновление через один день ### : (Iне могу поставить это в ответ, потому что q было отложено) После обширной отладки стандартной библиотеки (включая много царапин на голове), ответ @ JamesPoag, оказывается, указывает на правильную вещь.
После n вставки, я получаю:
n load_factor max_load_factor bucket_count max_bucket_count
32766 0.999938965 1.00000000 32768 536870911 (=2^29-1)
32767 0.999969482 1.00000000 32768 536870911
32768 1.000000000 1.00000000 32768 536870911
32769 0.500000000 1.00000000 65536 536870911
неудивительно, после 32768 вставок коэффициент загрузки достиг своего максимума.32769-я вставка запускает перефразирование в большую таблицу, внутри внутреннего метода _Check_Size:
void _Check_size()
{ // grow table as needed
if (max_load_factor() < load_factor())
{ // rehash to bigger table
size_type _Newsize = bucket_count();
if (_Newsize < 512)
_Newsize *= 8; // multiply by 8
else if (_Newsize < _Vec.max_size() / 2)
_Newsize *= 2; // multiply safely by 2
_Init(_Newsize);
_Reinsert();
}
}
в конце вызывается _Reinsert() и заполняет все 32769 ключей в новые сегменты, и _set all _next и _prev указатели соответственно.Это прекрасно работает.
Однако код, который вызывает эти два, выглядит следующим образом (Plist - это имя моего набора, этот код генерируется из шаблона):
_Insert_bucket(_Plist, _Where, _Bucket);
_TRY_BEGIN
_Check_size();
_CATCH_ALL
erase(_Make_iter(_Plist));
_RERAISE;
_CATCH_END
return (_Pairib(_Make_iter(_Plist), true));
}
Критическая точка находится в последней строке - для построения пары используется _Plist, но он содержит теперь мертвый указатель на _next, потому что все адреса сегмента были перестроены в _Check_size(), несколькими строками ранее.Я думаю, что это ошибка в библиотеке std - здесь нужно найти _Plist в новом наборе, где он выглядит так же, но имеет действительный указатель _next.
Простое «исправление»является (проверено, чтобы работать), чтобы расширить набор прямо перед критическим insert:
if (mySet.size() == mySet.bucket_count()) mySet.rehash(mySet.bucket_count() * 2);.
### Дальнейшее обновление: ### Я пыталсяэкстенсивно (16+ часов), чтобы создать минимальный код , который воспроизводит проблему, но я пока не смог.Я попытаюсь зарегистрировать фактические вычисленные хэши для существующего большого кода.
Одна вещь, которую я обнаружил, состоит в том, что одно хеш-значение одного из ключей изменило (непреднамеренно) между вставкой и перефразировкой.Это может быть основной причиной;если переместить перефразировку за пределы вставки, проблема исчезнет.
Я не уверен, есть ли правило, что хэши должны быть постоянными, но, вероятно, имеет смысл, как еще можно найти ключ снова.