问题与++归并用C

Question

vector<int>& mergesort(vector<int> &a) { 
    if (a.size() == 1) return a; 
    int middle = a.size()/2; 
    vector<int>::const_iterator first = a.begin(); 
    vector<int>::const_iterator mid = a.begin() + (middle - 1); 
    vector<int>::const_iterator last = a.end(); 
    vector<int> ll(first, mid); 
    vector<int> rr(mid, last); 

    vector<int> l = mergesort(ll); 
    vector<int> r = mergesort(rr); 
    vector<int> result; 
    result.reserve(a.size()); 
    int dp = 0, lp = 0, rp = 0; 

    while (dp < a.size()) { 
     if (lp == l.size()) { 
      result[dp] = (r[rp]); 
      rp++; 
     } else if (rp == r.size()) { 
      result[dp] = (l[lp]); 
      lp++; 
     } else if (l[lp] < r[rp]) { 
      result[dp] = (l[lp]); 
      lp++; 
     } else { 
      result[dp] = (r[rp]); 
      rp++; 
     } 
     dp++; 
    } 
    a = result; 
    return a; 
} 

它正确编译但在执行中，我得到：

This application has requested the runtime to end it in an unusual way.

这是一个奇怪的错误。

是否有什么是根本上错误的代码？

Answer 1

一个问题是使用reserve()（使用resize()或附加项目push_back()而不是访问索引）。

---

if (a.size() == 1) return a; 
int middle = a.size()/2; 
vector<int>::const_iterator first = a.begin(); 
vector<int>::const_iterator mid = a.begin() + (middle - 1); 
vector<int>::const_iterator last = a.end(); 
vector<int> ll(first, mid); 
vector<int> rr(mid, last); 

这可能是另一个问题。如果大小为2，那么ll将最终成为空向量，并且此函数似乎不处理这个问题。无论如何，从中间减去1似乎没有多少理由。

---

也可能要复制周围的事物，远远超过需要的：你不应该需要l和r向量（因为它们只会成为ll和rr副本），同样地，我不认为你需要result矢量，因为你可以将合并结果写回a。

Answer 2

这result.reserve(a.size())只是影响了向量的能力，而不是它的大小。 （矢量的容量为告诉哪个大小该矢量可以增长，而不需要重新分配和复制所有成员。基本上它仅用于优化目的。）在保留之后，您不能访问result中的任何成员，因为那里没有。使用result.push_back(...)而不是result[dp] = ...或result.resize(a.size())而不是result.reserve(a.size())。

我想前者可能更有效。

Answer 3

reserve（）不会更改向量中的内容量。你已经创建了一个空矢量，为它保留了一定的大小，然后使用v [i] = x;这不是矢量的有效使用，因为矢量中还没有任何第i个元素。

改为使用resize（）。

Answer 4

错误信息是非常不清楚的，因为它是VC++的标准消息，当一个异常未处理时。你可以添加一个try-catch-clock到你的main来获得异常和一个更有意义的错误：

int main() { 
    try { 
     // do main stuff here 
    } 
    catch (std::exception & e) { 
     std::cout << e.what() << std::endl; 
    } 
} 

这是用于命令行的。如果您的应用程序没有，请使用消息框或将错误写入日志文件。

关于代码中的问题，所有其他答案似乎是正确的。