首页 文章

如何使用end（）迭代器扩展范围

提问于
浏览 次
0

（不确定这是正确的任务）我正在编写一个与经典排序相关的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);
    ....
 }

但它对我来说无法正常工作，因为它最初得到的范围如下：vector v; Algo（v.begin（），v.end（））;但是，在内部，在递归调用中，子范围不包含end（）元素 .

这种情况下的典型技术是什么？

c++ stl iterator stl-algorithm

1 回答

  • 0

    我提出两种选择 .

    • （首选）使算法在内部不需要包含 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
}
    • 创建一个单独的函数，该函数需要包含 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);
}
    回复于

相关问题