如何使用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); 
   }