Я получаю следующую ошибку: завершение вызова после выброса экземпляра 'std :: bad_allo c' - PullRequest
Новая
       61

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

0 голосов
/ 24 февраля 2020

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

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;

}

1 Ответ

3 голосов
/ 24 февраля 2020

По сути, причина в том, что вам не хватает памяти. Когда вы делаете 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 байтов, что сокращает объем памяти.

...