I am getting the following error: terminate called after throwing an instance of 'std::bad_alloc'

Question

好的，我有一个重复 n 次的字符串 s。例如，我有 "aba" 和 n = 10，我想找到 a的数量。所以在这种情况下 (abaabaabaa) 我们有 7 个 a。我写了下面的代码，通过了一些测试用例，但是当 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;

}

Answer 1

基本上，原因是您运行内存不足。当您执行 push_back 时，向量可能会重新分配，这将需要 capacity + capacity * 2（乘数可能会有所不同）的连续分配量 space。如果您提前保留，这将解决该问题，但您仍然需要 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 字节，因此减少了内存。

I am getting the following error: terminate called after throwing an instance of 'std::bad_alloc'

I am getting the following error: terminate called after throwing an instance of 'std::bad_alloc'

c++

string

vector

long-integer

bad-alloc