Mergeort - std :: bad_alloc бросил при попытке назначить вектор
Вопрос
Доброе дневные дамы и гонщики. Итак, это не мой день для ошибок. Реализация Mergeort (не на месте) в C ++, и у меня есть реальные проблемы с кодом, не имея, почему. Вторая строка mergeSort()
Функция назначает результат merge()
в вектор ints, result
. Отказ Эта линия (фактическое распределение, а не функция) бросает bad_alloc
Ошибка, и я понятия не имею, почему.
Интернет говорит о том, что bad_alloc
В основном брошен из-за ошибок вне памяти, но это не может быть так, как впервые его вызывается на векторе 500 ints, который должен быть в глубине не слишком много памяти (как это, как 2 КБ на 32-битный int?). Я предполагаю, что я делаю что-то глупо и неверное для C ++, но я не знаю, что. Я пытался позвонить what()
За исключением, но это просто возвращает его имя. Код:
vector<int> Sorting::mergeSort(vector<int> A) {
// If the length of A is 0 or 1, it is sorted.
if(A.size() < 2) return A;
// Find the mid-point of the list.
int midpoint = A.size() / 2;
// Declare the left/right vectors.
vector<int> left, right;
// Declare the return vector.
vector<int> result (A.size());
for(int i = 0; i < midpoint; ++i) {
left.push_back(A.at(i));
}
for(int i = midpoint; i < A.size(); ++i) {
right.push_back(A.at(i));
}
left = mergeSort(left);
right = mergeSort(right);
result = merge(left, right);
return result;
}
vector<int> merge(vector<int> left, vector<int> right) {
vector<int> result;
while(left.size() > 0 && right.size() > 0) {
if(left.front() <= right.front()) {
result.push_back(left.front());
left.erase(left.begin());
} else {
result.push_back(right.front());
right.erase(right.begin());
}
}
if(left.size() > 0) {
for(int i = 0; i < left.size(); ++i) {
result.push_back(left.at(i));
}
} else {
for(int i = 0; i < right.size(); ++i) {
result.push_back(right.at(i));
}
}
}
Если я переписал merge
функция просто принять ссылку на result
И редактируйте его во время функции, он работает нормально, но я хотел держать код как можно ближе к «стандартному» PSEDO-коду, приведенному для слияния.
Я ценю любую помощь, спасибо.
Решение
в Merge
функция, vector<int> result
не возвращается.