Перенос предложения: голоса +4, -0
Aвтор идеи: alexander.y.k
В высококонкурентном коде порой требуется знать займет ли вставка следующего элемента в unordered контейнер около-константное время или линейное (а то и квадратичное) время. Стандарт описывает, что unordered контейнеры увеличивают число bucket'ов когда нужно сохранить load_factor() ниже чем max_load_factor(). Было бы удобно получить целочисленный ответ на этот вопрос без float армифметики.
Сейчас для определения такой ситуации либо нужно делать сравнение целого числа с float:
if( unord.size() + new_items_count >= unord.max_load_factor() * unord.bucket_count() ) {
// slow insertion
}
else {
// fast insertion
}А так же здесь для меня до сих пор не очевидно, что нужно использовать знак сравнения ">=" (в gcc реализации в этом примере корректен именно он), по тому, что пересказ стандарта своими словами легко может сделать сравнение строгим. Так например cppreference.com, наводит именно на эти мысли:
The container automatically increases the number of buckets if the load factor exceeds this [max_load_factor()] threshold.
Так же можно добиться результата эмулируя происходящее внутри контейнера, что должно быть снова затрагивает float'ы, и вообще говоря implementation specific, и так же не очевидна корректность происходящего для всех возможных комбинаций размера коллекции, количества вставляемых элементов и актуальных значений max_load_factor() и bucket_count().
Помимо этого, сама формулировка из стандарта: "The container automatically increases the number of buckets as necessary to keep the load factor below this [max_load_factor()] number", — не ограничивает реализации делать переаллокации в "удобное" для них время.
Далее, учитывая доминирующее положении реализации float чисел по стандарту IEEE 754, мы получаем, что если число элементов вышло за пределы 2^24 (=16'777'216), то требуется точная эмуляция поведения реализации для недежных выводов.
Я могу ошибаться, но кажется есть еще один нюанс того как x86 процессоры производят floating арифметику — они ведут флаг округления говорящий в какую сторону был округлен резултат последней операции, и в следующий раз применяют округление в другую сторону, чтобы накопление ошибок округления более-менее нивелировали друг друга в последовательных вычислениях. Если такие механизмы имеются на платформе, то собственноручно написанная техника проверки запаса может дать иной результат относительно того какой получила реализация в текущий момент.
Таким образом хотелось бы иметь гарантированно работающий механизм получения запаса на количество вставляемых элементов которое не преведет к переаллокации, что-то вроде такого:
if( unord.size() + new_items_count > unord.capacity() ) {
// slow insert
}
else {
// fast insert
}
Перенос предложения: голоса +4, -0
Aвтор идеи: alexander.y.k
В высококонкурентном коде порой требуется знать займет ли вставка следующего элемента в unordered контейнер около-константное время или линейное (а то и квадратичное) время. Стандарт описывает, что unordered контейнеры увеличивают число bucket'ов когда нужно сохранить load_factor() ниже чем max_load_factor(). Было бы удобно получить целочисленный ответ на этот вопрос без float армифметики.
Сейчас для определения такой ситуации либо нужно делать сравнение целого числа с float:
А так же здесь для меня до сих пор не очевидно, что нужно использовать знак сравнения ">=" (в gcc реализации в этом примере корректен именно он), по тому, что пересказ стандарта своими словами легко может сделать сравнение строгим. Так например cppreference.com, наводит именно на эти мысли:
Так же можно добиться результата эмулируя происходящее внутри контейнера, что должно быть снова затрагивает float'ы, и вообще говоря implementation specific, и так же не очевидна корректность происходящего для всех возможных комбинаций размера коллекции, количества вставляемых элементов и актуальных значений max_load_factor() и bucket_count().
Помимо этого, сама формулировка из стандарта: "The container automatically increases the number of buckets as necessary to keep the load factor below this [max_load_factor()] number", — не ограничивает реализации делать переаллокации в "удобное" для них время.
Далее, учитывая доминирующее положении реализации float чисел по стандарту IEEE 754, мы получаем, что если число элементов вышло за пределы 2^24 (=16'777'216), то требуется точная эмуляция поведения реализации для недежных выводов.
Я могу ошибаться, но кажется есть еще один нюанс того как x86 процессоры производят floating арифметику — они ведут флаг округления говорящий в какую сторону был округлен резултат последней операции, и в следующий раз применяют округление в другую сторону, чтобы накопление ошибок округления более-менее нивелировали друг друга в последовательных вычислениях. Если такие механизмы имеются на платформе, то собственноручно написанная техника проверки запаса может дать иной результат относительно того какой получила реализация в текущий момент.
Таким образом хотелось бы иметь гарантированно работающий механизм получения запаса на количество вставляемых элементов которое не преведет к переаллокации, что-то вроде такого: