使用迭代器将数组划分为大小不等的部分 [英] Using an iterator to Divide an Array into Parts with Unequal Size

问题描述

我有一个数组，我需要将它分成 3 个元素的子数组.我想用迭代器来做到这一点，但我最终迭代到数组的末尾并出现段错误即使我没有取消引用迭代器.给定:auto foo = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 我在做:

auto bar = cbegin(foo);for (auto it = next(bar, 3); it 

现在我可以通过定义一个 finish 迭代器来解决这个问题:

auto bar = cbegin(foo);自动完成 = next(cend(foo), -(size(foo) % 3));for (auto it = next(bar, 3); it != finish; bar = it, it = next(bar, 3)) {for_each(bar, it, [](const auto& i) { cout << i << endl; });}for_each(bar, finish, [](const auto& i) { cout << i << endl; });for_each(finish, cend(foo), [](const auto& i) { cout << i << endl; });

但是当我不取消引用迭代器时，这似乎是不必要的.为什么我不能做第一个版本?

解决方案

禁止这样做的原因在您的其他问题中很好地介绍了 是过去的one past-the-end"迭代器吗?迭代器未定义的行为? 所以我只介绍改进的解决方案.

对于随机访问迭代器(如果您使用 <，则必须拥有它)，不需要昂贵的模运算.

重点是:

• it + stride 在 it 接近尾声时失败
• end() - stride 如果容器包含的元素太少，则会失败
• end() - 它总是合法的

从那里，它是简单的代数操作来改变 it + stride <end() 转化为合法形式(两边都减去it).

最后的结果，我用过很多次了:

for( auto it = c.cbegin(), end = c.cend(); end - it >= stride; it += stride )

如果内存模型是平坦的，编译器可以自由地优化它以与预先计算的 end - stride * sizeof(*it) 进行比较——C++ 行为的限制不适用于编译器将 C++ 翻译成的原始操作.

如果您更喜欢使用命名函数而不是运算符，您当然可以使用 std::distance(it, end)，但这只会对随机访问迭代器有效.p>

要与前向迭代器一起使用，您应该使用结合了增量和终止条件的东西，例如

struct less_preferred { size_t value;less_preferred(size_t v) : value(v){} };模板<类型名迭代器>bool try_advance(Iterator&it, less_preferred step, Iterator end){而(step.value--){如果(它 == 结束)返回 false；++它;}返回真；}

通过这个额外的重载，您将获得随机访问迭代器的高效行为:

templateauto try_advance( RandomIterator& it, size_t stride, RandomIterator end )->decltype(end - it < stride)//SFINAE{if (end - it < stride) 返回 false；它+=步幅；返回真；}

I have an array which I need to divide up into 3-element sub-arrays. I wanted to do this with iterators, but I end up iterating past the end of the array and segfaulting even though I don't dereference the iterator. given: auto foo = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; I'm doing:

auto bar = cbegin(foo);

for (auto it = next(bar, 3); it < foo.end(); bar = it, it = next(bar, 3)) {
    for_each(bar, it, [](const auto& i) { cout << i << endl; });
}

for_each(bar, cend(foo), [](const auto& i) { cout << i << endl; });

Now I can solve this by defining a finish iterator:

auto bar = cbegin(foo);
auto finish = next(cend(foo), -(size(foo) % 3));

for (auto it = next(bar, 3); it != finish; bar = it, it = next(bar, 3)) {
    for_each(bar, it, [](const auto& i) { cout << i << endl; });
}

for_each(bar, finish, [](const auto& i) { cout << i << endl; });
for_each(finish, cend(foo), [](const auto& i) { cout << i << endl; });

But this seems unnecessary when I don't dereference the iterator. Why can't I do the first version?

解决方案

The reason this is prohibited is covered well at your other question Are iterators past the "one past-the-end" iterator undefined behavior? so I'll just address improved solutions.

For random-access iterators (which you must have if you are using <), there's no need whatsoever for the expensive modulo operation.

The salient points are that:

• it + stride fails when it nears the end
• end() - stride fails if the container contains too few elements
• end() - it is always legal

From there, it's simple algebraic manipulation to change it + stride < end() into a legal form (subtract it from both sides).

The final result, which I have used many times:

for( auto it = c.cbegin(), end = c.cend(); end - it >= stride; it += stride )

The compiler is free to optimize that back to comparison to a precomputed end - stride * sizeof(*it) if the memory model is flat -- the limitations of C++ behavior don't apply to the primitive operations which the compiler translates C++ into.

You may of course use std::distance(it, end) if you prefer to use the named functions instead of operators, but that will only be efficient for random-access iterators.

For use with forward iterators, you should use something that combines the increment and termination conditions like

struct less_preferred { size_t value; less_preferred(size_t v) : value(v){} };

template<typename Iterator>
bool try_advance( Iterator& it, less_preferred step, Iterator end )
{
     while (step.value--) {
         if (it == end) return false;
         ++it;
     }
     return true;
}

With this additional overload, you'll get efficient behavior for random-access iterators:

template<typename RandomIterator>
auto try_advance( RandomIterator& it, size_t stride, RandomIterator end )
     -> decltype(end - it < stride) // SFINAE
{
     if (end - it < stride) return false;
     it += stride;
     return true;
}

这篇关于使用迭代器将数组划分为大小不等的部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！