c++ - C++ 中的合并排序代码实现

Question

我正在尝试使用 vector 和迭代器在 C++ 中实现合并排序。该程序编译正常，但当我尝试运行它时，它崩溃了。我尝试调试它但没有成功。

使用数组的实现很简单，但是当我尝试使用 vector 实现完全相同的算法时，程序无法运行。

#include <iostream>
#include <vector>
#include <algorithm>

void mergesort(std::vector<int>& A, int l, int r);

void merge(std::vector<int>& A, int l, int m, int r);


void mergesort(std::vector<int>& A, int l, int r) {


    if(l < r) {

        int m = l + (r - l) / 2;

        mergesort(A, l, m);

        mergesort(A, m + 1, r);

        merge(A, l, m, r);

    } 
}

void merge(std::vector<int>& A, int l, int m, int r) {

   std::vector<int> L(A.begin() + l, A.begin() + (m - 1));
   std::vector<int> R(A.begin() + m, A.begin() + r);

   std::vector<int>::iterator i = L.begin();
   std::vector<int>::iterator j = R.begin(); 
   std::vector<int>::iterator k = A.begin() + l;

   while(i != L.end() && j != R.end()) {
       if(*i <= *j) {
           *k = *i;
           i++;
       }
       else {
           *k = *j;
           j++;
       }
       k++;
   }

   while(i != L.end()) {
       *k = *i;
       i++;
       k++;
   }

   while(j != R.end()) {
       *k = *j;
       j++;
       k++;
   }
}

void print_vector(std::vector<int> A) {

    std::vector<int>::iterator it;

    for(it = A.begin(); it != A.end(); ++it) {
        std::cout << *it << " "; 
    }
}


int main() {
    std::vector<int> A = {178, 1156, 136, 5, 6, 7};
    mergesort(A, 0, A.size() - 1);

    print_vector(A);
}

Answer 1

在本节中

if(l < r) {
    int m = l + (r - l) / 2;
    mergesort(A, l, m);
    mergesort(A, m + 1, r);
    merge(A, l, m, r);

} 

当 r = l + 1 你得到 m = l 然后你调用 mergesort 要求函数对一个空 vector 进行排序，而 mergesort 的代码假定它不为空。

什么是

 std::vector<int> L(A.begin() + l, A.begin() + (m - 1));

在这种情况下？

这应该是进行调试的良好起点。