Loop end condition with iterators and custom step size

Question

I am adding some functionality to a previously built code. I have to loop over a list is steps of 2 and process the elements elements differently.

Here's my attempt.

for(auto list_it = std::next(list.begin()); list_it != list.end() ; std::advance(list_it,2)){

   // Do something

}

I am initializing list_it to point to the second element using next(list.begin()) Each iteration it moves forward by 2 advance(list_it,2)).

[Q]

I am unsure how to test the loop exit condition.

list_it != list.end() might not work if we skip over list.end() when advancing forward by 2.

Is there any standard way to deal with this issue? I might check skipped iterators for being list.end(), but I don't see this as a nice, scalable way with larger step sizes. (unless it turns out to be the only way).

You **can't** skip over `list.end()`, it will be undefined behaviour. — Evg, Jan 02 '20 at 16:01
How about checking whether : iter != list.end() && (iter+1) != list.end() ? That should work. — H S, Jan 02 '20 at 16:09
@E.N.D, `std::next(iter)` instead of `iter + 1`. List iterators are not random access. — Evg, Jan 02 '20 at 16:14

H S · Accepted Answer · 2020-01-02T17:03:08.877

1

Update : Modifying for generic size.

For step size of k, You can get size of List in O(n) or O(1) - depending upon C++ compiler. After that compute steps you're allowed to take by:

  size_t steps_allowed = list.size()/k; 
   // list.size() is O(n) for C++98 and O(1) for standard C++ 11.

Then loop over another variable i and inside loop termination condition check for i against steps_allowed.

edited Jan 02 '20 at 17:03

answered Jan 02 '20 at 16:24

H S

1,211
6
11

`std::next(list_it) != list.end()` isn't going to help since you are increasing by `std::advance(list_it,2)` – NathanOliver Jan 02 '20 at 16:25
Loop will terminate because upon advancing by 2, `list_it` will fall on `list.end()`, wouldn't it? – H S Jan 02 '20 at 16:28
It could, or it could be one past the end. Remember, the OP is looking for a generic solution, not for just if the step is `2`. – NathanOliver Jan 02 '20 at 16:29
Oops, Let me modify it for generic one. – H S Jan 02 '20 at 16:33
In standard C++11, `std::list::size()` [is](https://stackoverflow.com/questions/228908/is-listsize-really-on) `O(1)`. – Evg Jan 02 '20 at 16:52
Wow, I didn't know that. Thanks a lot. – H S Jan 02 '20 at 17:01

score 1 · Answer 2 · answered Jan 02 '20 at 16:40

You can't advance past the .end() iterator. You have to use either a counter, or check all intermediate iterators. For example:

template<class It>
void checked_advance(It& it, It last, std::size_t n) {
    while (n-- > 0 && it != last)
        ++it;
}

assert(!list.empty());
for (auto it = std::next(list.begin()); it != list.end(); 
     checked_advance(it, list.end(), step)) {
    // ...
}

NathanOliver · Answer 3 · 2020-01-02T16:14:25.637

0

You can change you condition to check and make sure the difference between the current iterator and the end iterator is more then the step amount. That would look like

for(auto list_it = std::next(list.begin()); 
    std::distance(list_it, list.end()) > step; 
    std::advance(list_it, step))
{

// Do something
}

edited Jan 02 '20 at 16:14

answered Jan 02 '20 at 16:04

NathanOliver

171,901
28
288
402

1

It looks like `O(N)` traversal is now `O(N^2)`. – Evg Jan 02 '20 at 16:19
@Evg `O(2N)` no? I'm advancing the current iterator twice, not the from the beginning every time. – NathanOliver Jan 02 '20 at 16:21
But `std::distance` has to traverse the list, too. At each step it makes `O(N)` iterations. – Evg Jan 02 '20 at 16:23
@Evg Yeah, but it's traversing from `list_it` so you only do `step` traversals. – NathanOliver Jan 02 '20 at 16:24
1

@Evg Oops, nevermind, I get it. I'll still leave it as an option – NathanOliver Jan 02 '20 at 16:26

score 0 · Answer 4 · answered Jan 02 '20 at 16:13

0

With range-v3, you might do:

for (auto& e : list | ranges::view::drop(1) | ranges::views::stride(2)) {
    // e
}

answered Jan 02 '20 at 16:13

Jarod42

203,559
14
181
302

Interesting. I will stick to the standard library for now though – User 10482 Jan 02 '20 at 21:01

Loop end condition with iterators and custom step size

4 Answers4