更有效的方法來查找矢量中的連續數字？

Question

我需要編寫一個程序來打印文件中特定單詞的行號（升序）。該方案的實施例輸出將是：

Hello 1, 3, 5-6, 8, 10-15. 
// 5-6 represents 5, 6 (consecutive numbers) 

的行號存儲在排序vector<int>，沒有重複。我創造了一個解決方案，但我的直覺告訴我我可以做得更好。我希望得到一些反饋。此外，以下代碼僅處理行號。這個詞在另一種方法中找到。

void IndexPager::createLines(vector<int>& vec, string& line) 
{ 
    int start = *vec.begin(), end = -1, offset = 0; // initial offset to start 

    for (vector<int>::const_iterator itr = vec.begin(); 
     itr != vec.end() + 1; itr++) 
    { 
    if (*itr == start + offset && itr != vec.end()) 
    { 
     end = *itr; 
     ++offset; 
    } // check if line numbers are consecutive and not reading at end of vector 
    else // not consecutive 
    { 
     if ((end != -1) && (end != start)) 
     { 
     line.append(intToString(start) + "-"); 
     line.append(intToString(end)); 
     } // if there existed consecutive numbers, display with dash 
     // must be difference of at least 1 
     else // else, there were no consecutive numbers 
     line.append(intToString(start)); 

     if (itr != vec.end()) // check if not at end of vector 
     line.append(", "); 
     else // reached end of vector 
     line.append("."); 

     start = *itr; // set start to next line number. Soft reset. 
     offset = 1; // change default offset to 1. 0 for first case. 
     end = -1; 
    } // not consecutive 
    } // Get all line numbers and format for proper output 
} // createLines() 

Answer 1

幾個意見。

你假設向量長度
1. > 0
2. vec.end（）+ 1可能不會給你希望，這取決於載體實現的結果。

在循環體的開始處增加itr而不是在最後使用來解決這兩個問題。

效率，你可以嘗試更換「啓動+偏移」和「下一個」

void IndexPager::createLines(vector<int>& vec, string& line) 
{ 
    int start,end,next; 
    vector<int>::const_iterator itr = vec.begin(); 
    next=end=start=*itr; 
    while(itr!=vec.end()) 
    { 
     ++itr; 
     end=next++; 
     if(itr==vec.end()||next!=*itr) 
     { 
      // break in consecutive sequence 
      line.append(intToString(start)); 
      if(end!=start){ 
       line.append("-"); 
       line.append(intToString(end)); 
      } 
      if(itr!=vec.end()) 
      { 
       line.append(", "); 
      } 
      next=end=start=*itr; 
     } 
    } // Get all line numbers and format for proper output 
    line.append("."); 
} // createLines() 

ITR仍在覈對vec.end（）每次迭代三次，所以你可能要重複的突破-in-sequence部分，並且使用正常的（auto i：vec）代替，但是所述編譯器優化可以消除重複