如何使用end（）迭代器擴展範圍

Question

（不確定這是否是正確的任務） 我正在寫一個與經典排序相關的stl風格的算法。 原型爲：

template<typename RAIter> 
    void Algo(RAIter first, RAIter last) { 
    .... 
    size_t size = std::distance(first, last); 
    RAIter midIter =first; 
    std::advance(midIter, size/2 - 1); 

    Algo(first, midIter); 
    Algo(midIter + 1, last); 
    .... 
} 

，但它不正確的我，因爲，最初 它得到的範圍內工作一樣： 矢量V; Algo（v.begin（），v.end（））;然而，在內部，在遞歸調用中，子範圍不包含end（）元素。

這種情況下的典型技術是什麼？

Answer 1

我會提出兩個選擇。

1. （首選）使算法在內部不需要包含last。你的情況是可以做到這樣的：

   template<typename RAIter> 
   void Algo(RAIter first, RAIter last) { 
       .... 
       size_t size = std::distance(first, last); 
       if (size <= 1) { 
        // special processing of single-item or empty range 
        return; 
       } 
   
       RAIter midIter =first; 
   
       std::advance(midIter, size/2); 
   
       Algo(first, midIter); // midIter not included 
       Algo(midIter, last); // it's included here instead 
   } 
   

2. 讓包括一個獨立的功能，期待與last範圍：

   template<typename RAIter> 
   void AlgoImpl(RAIter first, RAIter last) { 
       .... 
       // looks like this is more correct: 
       // size_t size = std::distance(first, last) + 1; 
       size_t size = std::distance(first, last); 
       RAIter midIter =first; 
       std::advance(midIter, size/2 - 1); // and here "- 1" seems wrong 
   
       AlgoImpl(first, midIter); 
       AlgoImpl(midIter + 1, last); 
       .... 
   } 
   
   template<typename RAIter> 
   void Algo(RAIter first, RAIter last) { 
       if (first == last) { 
        return; 
       } 
       AlgoImpl(first, last - 1); 
   }