C++ 在抛出一个 'std::bad_alloc' what() 实例后调用终止：std::bad_alloc Aborted
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/8677238/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc Aborted
提问by Avinash
I am getting a bad_allocexception in my program.
bad_alloc我的程序出现异常。
These are the constraints:
这些是约束：
- 1 <= T <= 10
- The length of each string is at most 100000 and contains only lower case characters.
- 1 <= T <= 10
- 每个字符串的长度最多为 100000，并且只包含小写字符。
With those constraints, I am unable to figure out why my program is getting bad_alloc.
有了这些限制，我无法弄清楚为什么我的程序会得到bad_alloc.
#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
class SuffixArray {
std::vector<std::string> suffixes;
size_t N;
public:
SuffixArray(std::string& s) {
N = s.length();
suffixes.resize(N);
for (size_t i = 0; i < N; i++)
suffixes[i] = s.substr(i);
std::sort(suffixes.begin() , suffixes.end());
}
~SuffixArray() {
}
size_t lcp(std::string& s, std::string& t) {
size_t N = std::min(s.length(), t.length());
for (size_t i = 0; i < N; i++)
if (s[i] != t[i])
return i;
return N;
}
};
int main ( int argc, char **argv) {
int T;
std::cin >> T;
std::vector<size_t> results;
for ( int i = 0; i < T; i++) {
std::string str;
std::cin >> str;
SuffixArray sa(str);
size_t sol = 0;
for ( std::string::iterator it = str.begin(); it != str.end(); ++it) {
std::string target = std::string(it, str.end());
sol += sa.lcp(str, target);
}
results.push_back(sol);
}
for ( std::vector<size_t>::iterator it = results.begin(); it != results.end(); ++it)
std::cout << *it << std::endl;
results.clear();
return 0;
}
回答by ChrisWue
Because what you do here:
因为你在这里做什么：
for (size_t i = 0; i < N; i++)
suffixes[i] = s.substr(i);
is: Create Nsub strings of lengths 0, 1, 2, ..., N
The total amount of memory these are going to consume is: 1 + 2 + 3 + ... + Nbytes. Having good old Gauss at your hand you will find that the sum of the first Nnumbers is: N * (N + 1) / 2
是：创建N长度为 0、1、2、...、N 的子字符串这些将要消耗的内存总量是：1 + 2 + 3 + ... + N字节。手头上有好的老高斯，你会发现第一个N数字的总和是：N * (N + 1) / 2
Now if you set N = 100,000 this results in about 5GB of memory consumption - which is larger than the max. 2GB address space your program usually has unless you run it on a 64bit system.
现在，如果您设置 N = 100,000，这将导致大约 5GB 的内存消耗 - 这大于最大值。除非您在 64 位系统上运行它，否则您的程序通常具有 2GB 的地址空间。
Edit: I don't know what the problem is you are trying to solve however your implementation seems strange:
编辑：我不知道您要解决的问题是什么，但是您的实现似乎很奇怪：
You never ever use the computed suffixes: The only function of SuffixArrayyou are using is lcpwhich makes no reference to the stored suffixesvector. So what you need them for in the first place?
您永远不会使用计算后的后缀：SuffixArray您使用的唯一功能是lcp不引用存储的suffixes向量。那么你首先需要它们做什么？
