Я получаю следующую ошибку: завершение вызывается после создания экземпляра 'std::bad_alloc'

Итак, у меня есть строка s, которую я повторяю n раз. Например, у меня есть «аба» и n = 10, и я хочу найти количество букв «а». Итак, в этом случае (абаабаабаа) у нас есть 7 «а». Я написал следующий код, который проходит некоторые тестовые случаи, но когда n велико, я получаю сообщение об ошибке: завершение вызывается после создания экземпляра 'std::bad_alloc. Есть ли способ это исправить? Спасибо.

long repeatedString(string s, long n) {

    long i = 0, j = 0, cnt = 0;
    long sz = s.size();
    vector<char> ar;

    while (i < n)
    {
        ar.push_back(s[j]);
        j++;

        if (j >= sz)
        {
            j = 0;
        }

        i++;
    }

    i = 0;
    while (i < n)
    {
        if (ar[i] == 'a')
        {
            cnt++;
        }
        i++;
    }

    return cnt;

}

c++ string vector long-integer bad-alloc
person C96    schedule 24.02.2020    source источник
comment
Пожалуйста, отредактируйте свой вопрос с помощью минимальный воспроизводимый пример или SSCCE (короткий, автономный, правильный пример)   -  person NathanOliver    schedule 24.02.2020
comment
Оффтопик: Вам следует зарезервировать ar заранее. ar.reserve(n)   -  person ChrisMM    schedule 24.02.2020
comment
Насколько большим будет n, прежде чем он выйдет из строя? Если вы повторите s много миллиардов раз, у вас может просто не хватить памяти для представления результирующей строки.   -  person François Andrieux    schedule 24.02.2020
comment
@ François Andrieux Если я сделаю это, я не получу нужное количество а. Количество а в аба равно 2. Но если я сделаю 2*10, я получу 20, когда должен получить 7 (абаабаабаа)   -  person C96    schedule 24.02.2020
comment
Единственная причина std::bad_alloc — Нехватка памяти. например В системе недостаточно свободной памяти для выделения запрошенного объема, или память фрагментирована для выделения этого блока.   -  person Victor Gubin    schedule 24.02.2020
comment
Вы уверены, что n ‹ s.length()? Если нет, то будут происходить всякие странности.   -  person El Stepherino    schedule 24.02.2020
comment
@ El Stepherino n не меньше s.length. Например, s = a и n может быть 1 миллиард.   -  person C96    schedule 24.02.2020
comment
@VictorGubin Понятно. Я неправильно понял значение n. Вы все еще можете сделать это, не генерируя всю строку. Либо подсчитайте 'a's вместо генерации ar. Вы также можете подсчитать 'a' в s, умножить это на n / s.size(), а затем перебрать только s для n % s.size() символов, чтобы увидеть, сколько завершающих 'a' нужно добавить к счету.   -  person François Andrieux    schedule 24.02.2020

Ответы (1)


arrow_upward
3
arrow_downward

По сути, причина в том, что у вас заканчивается память. Когда вы делаете push_back, вектор может перераспределяться, что потребует capacity + capacity * 2 (множитель может варьироваться) места в непрерывном распределении. Если вы зарезервируете память заранее, это решит эту проблему, но вам все равно потребуется n непрерывных байта памяти.

Лучшее решение — просто прочитать строку и выполнить умножение, например:

size_t repeatedString( const std::string &s, size_t n ) {
    size_t sz = s.size();
    size_t cnt = 0;

    for ( const char &c : s ) {
        if ( c == 'a' ) {
            ++cnt;
        }
    }

    size_t mult = n / sz;
    cnt *= mult;
    size_t rem = n % sz;

    for ( size_t idx = 0; idx < rem; ++idx ) {
        if ( s[idx] == 'a' ) {
            ++cnt;
        }
    }

    return cnt;
}

Это делает так, что вам не нужно выделять дополнительные n байт, поэтому память уменьшается.

person ChrisMM    schedule 24.02.2020
comment
Это сделало это. Спасибо!! - person C96; 24.02.2020