代码之家 › 专栏 › 技术社区 › bremen_matt

C++:一个迭代器“for循环”的成语,它在步长>1中移动,允许非随机访问反向迭代器。

c++

bremen_matt · 技术社区 · 6 年前

对不起,问题的措辞。如果你能想出更好的表达问题的方法,请编辑。

绕过一个 std::vector v 一步一步,我们有很多选择。以下是一些立即想到的问题:

1. for ( auto & elem : v )
2. for ( int i = 0 ; i < v.size() ; ++i )
3. for ( auto begin = v.begin() ; begin < v.end() ; begin++ )

现在我想把讨论限制在基于迭代器的方法上,因为我最终会对其他容器感兴趣。例如,假设我有一个方法juts接受 begin 和 end 迭代器:

template <typename Iterator>
void foo( Iterator begin, Iterator end ){
    for ( ; begin < end ; begin++ ){
       ...
    }
}

这方面的问题是,由于我们不能简单地为所有容器增加迭代器,所以这将无法用于更一般的容器。好吧,我们来解决这个问题:

template <typename Iterator>
void foo( Iterator begin, Iterator end ){
    for ( ; begin < end ; std::advance( begin, 1 ) ){
       ...
    }
}

啊哈,但还有另一个问题,特别是,如果有人给我们一个反向迭代器会发生什么…好啊。如果我们担心的话,我们可以简单地把这个改成

template <typename Iterator>
void foo( Iterator begin, Iterator end ){
    for ( ; begin != end ; std::advance( begin, 1 ) ){
       ...
    }
}

这是我的问题…现在如何适应大于1的步长,同时确认可以有一个反向的非随机访问迭代器?

具体来说,最轻的是什么 test 我可以插入以下代码:

template <typename Iterator>
void foo( Iterator begin, Iterator end, const size_t step ){
    for ( ; test(begin, end) ; std::advance( begin, step ) ){
       ...
    }
}

编辑:

指出了当我跨过容器端部时,提前函数可能是未定义的。那个bug也需要修复。

3 回复 | 直到 6 年前

lubgr 6 年前

这是一个模板,它使用给定的步骤大小执行迭代,并在每次增量之后检查终止条件。它还调用带有未引用迭代器的函数。

template <typename Iterator, typename Fct>
void foo(Iterator begin, Iterator end, std::size_t step, const Fct& f) {
   if (begin == end)
      return;

   while (true) {
      f(*begin);

      for (std::size_t i = 0; i < step; ++i)
         if (++begin == end)
            return;
   }
}

这应该适用于任何非随机访问迭代器,例如

const auto print = [](const auto& arg){ std::cout << arg << "\n";  };

std::list<int> l{42, 43, 44, 45, 46};

foo(l.crbegin(), l.crend(), 3, print);

或者,例如,使用输入迭代器。

foo(std::istream_iterator<char>(std::cin), std::istream_iterator<char>(), 2, print);

Ohnemichel 6 年前

微不足道的回答: 代替

std::advance( begin, step )

通过

for (int i=0;i<step;i++) {if (begin!=end) std::advance(begin,1);}

. 在for循环增量中。因为唯一的检查方法 如果你已经过去 无序流形中的一个元素是在每个步骤中检查的。这就是模加密的密码学优势所在。如果你接到一个订单,但不知道它是正向的还是反向的,你可以在开始时检查

bool bigger_at_beginning=begin > end;

让比较依赖于那个bool,比如

bigger_at_beginning ? (begin<end) : (begin>end)

但这并不是直接的,也不会在完全无序的迭代器上工作,所以我更喜欢以前的方式。

Aconcagua 6 年前

跳跃多个元素的真正大问题是不您正在寻找的测试——它避免了迭代器的增量超过容器的末尾(这是未定义的行为)!

以下情况:

std::vector<int> v({7});
for(auto i = v.begin(); i < v.end(); i += 2);

是的,我甚至跳过了 std::advance 故意比较…

将迭代器增加到向量末尾以外!尽管那可能似乎要运行良好,它仍然是未定义的行为。

如果您想要一个基于迭代器的通用解决方案,那么您需要知道还有多少元素:

template <typename Iterator>
void foo(Iterator begin, Iterator end, typename Iterator::difference_type step)
{
    if(begin != end)
    {
        for(;;)
        {
            // use *begin
            if(end - begin <= step)
                break;
            begin += step;
        }
    }
}

当然,这只适用于随机访问迭代器。但是如果我们用 if(std::distance(begin, end) <= step) 和 std::advance(begin, step) 在上面的RA变体中,我们得到了一个适用于 全部的 迭代器的类型。

为了简单性/可维护性,您可能希望继续使用。

单独:对于非RA迭代器,您需要这样做 step 单步单脚跳两次一次用于计算距离,一次用于实际前进。因此,您可能更喜欢在一次执行中手动执行这两项操作。在一般的解决方案中,首先检查类型:

for(;;)
{
    // use *begin;

    if constexpr
    (
        std::is_same_v<typename Iterator::iterator_category, std::random_access_iterator_tag>
    )
    {
        if(std::distance(begin, end) <= step)
            goto LOOP_EXIT; // alternatively (here only): break;
                            // (wanted to be consistent with else branch...)
        std::advance(begin, step);
    }
    else
    {
        for(size_t i = 0; i < step; ++i)
        {
            if(std::advance(begin, 1) == end)
                goto LOOP_EXIT;
        }
    }
}
LOOP_EXIT:
// if no further instructions follow:
(void) 0;

如果你需要更多的时间,你可以把这个搬到你自己的地方。

template <typename Iterator>
Iterator advance_not_beyond(Iterator begin, Iterator end, size_t step)
{ /* ... */ }

只要我们没有 std::advance_not_beyond 按照标准…