c++ - Using an iterator to Divide an Array into Parts with Unequal Size

Question

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?

Answer 1

The segfault you are seeing is coming from next checking the range for you is an assertion in your Debug implementation to check against undefined behavior. The behavior of iterators and pointers is not defined beyond the their allocated range, and the "one past-the-end" element: Are iterators past the "one past-the-end" iterator undefined behavior?

This means that incrementing past the "one past-the-end" element is undefined behavior independent of the iterator's subsequent use. In order to have defined behavior you must use a solution like your Integer Modulo algorithm or similar, but you will have to change auto it = next(bar, 3) to something that conditionalizes based on the availability of at least the size of your sub-array, so something like: auto it = size(foo) <= 3 ? finish : next(bar, 3).

Where available the best solution here is going to cause the least redundant iteration is to track the size remaining in the container as an integer which does not suffer from undefined behavior when it falls outside the range and "one past-the-end". This can be accomplished by:

auto bar = cbegin(foo);

for (auto i = size(foo); i > STEP; i -= STEP) {
    for(auto j = 0; j < STEP; ++j, ++bar) cout << *bar << '';
    cout << endl;
}

for(auto i = 0; j < STEP; ++j, ++bar) cout << *bar << '';
cout << endl;

EDIT: I had previously suggested using pointers which are not Debug conditioned, this is undefined behavior.

The problem is that next is checking the range for you. We use pointers outside of allocated memory all the time, for example nullptr and end, and that's all it here is. If you just use C-style pointer arithmetic here you'll be fine:

auto bar = cbegin(foo);

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

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

Live Example

Alternatively, if you run in Release configuration the range checks should be removed, so you will be able to use the first version of your code.