c++ - QVector<T>::operator[] 失败:意外抛出 "index out of range"

Question

我有两种排序方法:插入排序和shell排序。其中两个工作函数我已经从纯 C 适应了 C++。问题是 ins_sort 函数工作得很好，而 shell_sort 失败了。这可能是什么原因？

    bool less(QVector<int> &arr, int a, int b)
    {
        return arr[a] < arr[b];
    }

    // Performs swap on elements at a and b in QVector<int> arr
    void qswap(QVector<int> &arr, int a, int b)
    {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    /* Failure is thrown in this method */
    void shell_sort(GraphicsView &window, SwapManager &manager)
    {
        auto list = window.items();
        QVector<int> arr;
        for (auto item : list)
            arr.push_back(static_cast<QGraphicsRectWidget*>(item)->m_number);
        int N = arr.size();
        int h = 1;
        while (h < N/3) h = 3*h  + 1;
        while (h >= 1)
        {
            for (int i = h; i < N; ++i)
            {
                for (int j = i; less(arr, j, j-h) && j >= h; j -= h)
                {
                    qswap(arr, j, j-h);
                    manager.addPair(j, j - h);
                }
            }
            h /= 3;
        }
    }

那个做得很好。

    /* This method works just fine */
    void ins_sort(GraphicsView &window, SwapManager &manager)
    {
        auto list = window.items();
        int i, j;
        QVector<int> arr;

        for (auto item : list)
        {
            arr.push_back(static_cast<QGraphicsRectWidget*>(item)->m_number);
        }
        int N = arr.size();
        for (i = 1; i < N; ++i)
        {
            for (j = i - 1; j != -1 && less(arr, j + 1, j); --j)
            {
                qswap(arr, j, j + 1);
                manager.addPair(j, j + 1);
            }
        }
    }

调试器指向“qvector.h”中的这段代码

    Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
      return data()[i]; }

Answer 1

在 for 循环条件中，在比较项目之前检查 j 值是有意义的:

for (int j = i; j >= h && less(arr, j, j-h); j -= h)