問題與++歸併用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; 
    } 
} 

這是用於命令行的。如果您的應用程序沒有，請使用消息框或將錯誤寫入日誌文件。

關於代碼中的問題，所有其他答案似乎是正確的。