c++ - std::out_of_range:Mergesort 算法中的 vector 异常

Question

我正在尝试用 C++ 实现 Mergesort 算法。你可以在下面看到我的实现。当我运行算法时，出现以下错误: libc++abi.dylib:以 std::out_of_range 类型的未捕获异常终止: vector 中止陷阱:6

虽然这是我第一次使用 C++，但我认为这个错误意味着我传入了某个 vector 边界之外的索引。这是正确的吗？

如果这是正确的，我无法弄清楚我在哪里超出了某个 vector 的边界。但是，我向控制台打印了一些值并注意到程序无法正确打印 vector 中的元素。也许这会提示索引超出范围的位置。

合并排序实现

#include <iostream>
#include <vector>

void merge(std::vector<int> left, std::vector<int> right, std::vector<int> array)
{
    int lengthLeft = left.size();
    int lengthRight = right.size();

    int i = 0; // index of smallest unpicked element in left
    int j = 0; // index of smallest unpicked element in right
    int k = 0; // position to be filled in array
    while (i < lengthLeft && j < lengthRight)
    {
        if (left.at(i) <= right.at(j))
        {
            array.at(k) = left.at(i);
            k++;
            i++;
        }
        else
        {
            array.at(k) = right.at(j);
            k++;
            j++;
        }
    }
    while (i < lengthLeft)
    {
        array.at(k) = left.at(i);
        k++;
        i++;
    }
    while (j < lengthRight)
    {
        array.at(k) = right.at(j);
        k++;
        j++;
    }
}

std::vector<int> mergesort(std::vector<int> array)
{
    int length = array.size();
    std::cout << "Array Size: " << length << '\n';

    if (length < 2)
    {
        return array;
    }

    int mid = length / 2;
    std::cout << "mid = " << mid << '\n';

    // Temporary vectors.
    std::vector<int> left(mid);
    std::vector<int> right(length - mid);
    std::cout << "Left size: " << left.size() << '\n';
    std::cout << "Right size: " << right.size() << '\n';

    // Moving elements into temporary vectors.
    for (int i = 0; i <= mid; i++)
    {
        left.at(i) = array.at(i);
        std::cout << "Left at i: " << left.at(i) << '\n';
    }
    for (int i = mid + 1; i < length; i++)
    {
        right.at(i) = array.at(i);
        std::cout << "Right at i: " << right.at(i) << '\n'; // <-- THIS DOES NOT PRINT
    }

    mergesort(left);
    mergesort(right);
    merge(left, right, array);

    return array;
}

int main()
{
    std::vector<int> vect = {5, 4, 3, 2, 1};

    for (int i : vect)
    {
        std::cout << i << " " << '\n';
    }

    mergesort(vect);

    for (int i : vect)
    {
        std::cout << i << '\n';
    }

    return 0;
}

控制台输出

5
4
3
2
1
Array Size: 5
mid = 2
Left size: 2
Right size: 3
Left at i: 5
Left at i: 4
libc++abi.dylib: terminating with uncaught exception of type std::out_of_range: vector
Abort trap: 6

Answer 1

你的代码有一些问题，但这个循环给出了错误

for (int i = 0; i <= mid; i++)
{
    left.at(i) = array.at(i);
    std::cout << "Left at i: " << left.at(i) << '\n';
}
for (int i = mid + 1; i < length; i++)
{
    right.at(i) = array.at(i);
    std::cout << "Right at i: " << right.at(i) << '\n'; // <-- THIS DOES NOT PRINT
}

要修复您的错误，您必须将第一个更改为 for (int i = 0; i < mid; i++)替换 <=只有 < , 所以它得到前两位数字。
在第二个你应该更改为 for (int i = 0; i < length - mid; i++)也改right.at(i) = array.at(i);至 right.at(i) = array.at(mid + i); ，这将确保您获得剩余的 3 个，这里的问题是您从 mid 开始这是2和 right vector 的大小只有 3 ，因为 vector 的索引为 0，所以你从最后一个索引开始，下一次迭代超出了它的范围。

所以孔部分会是这样的

for (int i = 0; i < mid; i++)
{
    left.at(i) = array.at(i);
    std::cout << "Left at i: " << left.at(i) << '\n';
}
for (int i = 0; i < length - mid; i++)
{
    right.at(i) = array.at(mid + i);
    std::cout << "Right at i: " << right.at(i) << '\n'; // <-- THIS DOES NOT PRINT
}

尽管如此，您的程序仍不会对 vector 进行排序，C++ 按值传递参数，这意味着每次您使用特定输入调用函数时，它都会创建一个新变量相同的数据。
你的mergesort函数应该接收一个 vector 并更改它的值，这里你有两个选项，或者更改函数以返回一个新 vector ，或者你通过引用将 vector 传递给这个函数，使用 & ，这不是在函数内部创建一个具有相同值的新 vector ，而是将变量的内存引用发送到函数，这样函数就可以访问相同的变量。
您的功能应更改为

void merge(std::vector<int> &left, std::vector<int> &right, std::vector<int> &array)
{ ... }

std::vector<int> mergesort(std::vector<int> &array)
{ ... }

有些时候通过引用传递是有用的，但有时不是，你会及时得到它，但通常在性能方面这是一个很好的做法，因为你没有为每个函数创建新变量。

如果不清楚或者您想要更好的解释，请询问。

提示

小心命名你的变量，你不应该使用保留的名称，array是 C++ 保留 的名称，您应该使用其他名称。

它实际上不是保留字，只有在程序员使用using namespace std 时才会发生冲突。 ，如@user4581301所述

Reserved is a loaded term. In C++ Reserved means you can't use this, no matter what. array is not reserved. Using array as an identifier will only cause problems if is included and the std namespace has been short-circuited with using namespace std (something the wise programmer avoids).