C ++ std :: bad_alloc ошибка при использовании меньшего объема памяти?

Question

Я сделал функцию, которая может хранить все решения секретного номера, которые затем будут использоваться в алгоритме.

Эта функция отлично работает для определенных входных значений; однако для некоторых это не работает. Проблема в том, что я получаю ошибку, связанную с использованием слишком большого количества памяти, которая не имеет смысла, учитывая:

Предел количества генерируемых чисел:

int possibilities = std::pow(symbols, length);

когда вы делаете:

generate_list( list , 6, 4 ); it generates 4^6 different numbers = 4096

Однако, когда вы делаете:

 generate_list( list , 4, 6 ); it does not generates 6^4 numbers = 1296 due to error

Как это дает недостаточно памяти, когда генерирует меньше чисел?

Ошибка:

    terminate called after throwing an instance of 'std::bad_alloc'
     what():  std::bad_alloc

Answer 1

Он не имеет никакого отношения к выделению памяти как таковой.

Проблема в этих строках

        int zerosneeded = length - tmp.size();

        while (zerosneeded != 0) {
            tmp.push_back(0);
            zerosneeded--;
        }

не зная, почему он делает то, что делает, у меня возникает вопрос при взгляде на код: «Может ли zerosneeded быть меньше нуля?». Тем более что zerosneeded определяется как int вместо unsigned int (применимо к остальной части кода).

Если значение нуля меньше нуля, бесконечный цикл будет распределяться до исчерпания. Быстрая проверка подтверждает это:

int zerosneeded = length - tmp.size();
if(zerosneeded < 0)
{
    std::cout << "fatal, zerosneeded < 0 \n";
    throw std::runtime_exception("fatal, zerosneeded < 0");
}

Надеюсь, это поможет в вашей отладке.

Редактировать

Относительно того, почему нулевые значения отрицательны:

во-первых, рассчитывается количество возможностей, которое составляет символы ^ длина.

int possibilities = std::pow(symbols, length);

при отправке значений в tmp мы в основном находим первый x такой, что длина ^ x> частное. Частное находится в диапазоне [0, символы ^ длина] и используется push-значениями в tmp.

int quotient = i;
while (quotient!=0) {
    tmp.push_back(quotient % length);
    quotient = quotient / length;
}

Если символы ^ длина> длина ^ длина, первый x такой, что длина ^ x> частное, дает x> длину, в результате чего int zerosneeded = length - tmp.size(); становится отрицательным.

Для примера у нас длина = 4, символы = 6, поэтому коэффициенты имеют диапазон [0,6 ^ 4] = [0, 1296]. Но уже для 256 мы имеем 4 ^ 4 = 256 => 4 ^ 5> 256, поэтому наш x = 5 => zerosneeded = 4 - 5 = -1.

Это ничего особенного для длины = 4 и символов = 6, и на самом деле должно происходить до тех пор, пока длина <символов. </p>