Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
563 views
in Technique[技术] by (71.8m points)

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

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?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...