Is it a bad idea to make a copy of an iterator?

Question

I'm thinking of writing some code which will boil down to this. T is a collection type (currently std::map, if it matters).

T coll;

// ...

T::iterator it, prev;

prev = coll.end();

for(it = coll.begin(); it != coll.end(); ++it) {
    if(prev != coll.end())
        { do something involving previous element; }

    do something involving this element;

    prev = it;
}

My question is, is it in any way a bad idea to copy it to prev like this? Bad style? Likely to annoy a pedant somewhere? Possible to break depending on subtle details of type T?

I don't expect coll to be destroyed while this loop is running, or for any elements to be added to or deleted from it.

On the one hand everything I know about iterators says that this should be Perfectly Safe. But on the other hand, there are things I don't know about iterators, and this feels ever-so-slightly sketchy, so I thought I'd ask.

Addendum:

The other reason this comes up is that my actual code isn't going to involve the for loop I wrote above. What I actually have is event-driven code; which would look more like this:

void onStartDoingSomething() {
    it = coll.start();
    prev = coll.end();
    startOperation(it, prev);
    timerStart();
}

void onTimer() {
    if(finished with operation on it) {
        prev = it;
        ++it;
        startOperation(it, prev);
        if(it == coll.end() {
            timerStop();
            call operation finished;
        }
    }
}

void startOperation(T::iterator next, T::iterator prev) {
    if(prev != coll.end()) {
        finish operation on prev;
    }

    if(next != coll.end()) {
        start operation on next;
    }
}

So another way of stating my question might be, "Do you have to use iterators, and a collection class's begin() and end() methods, only in straitlaced conventional for loops, or can you use them arbitrarily? Is there any state kept in the for loop, or is the state all in the iterator?" Now, I know that there's nothing like "state stored in the for loop", and as far as I know, it's paramount for an iterator to contain all the state it needs. So if, in fact, the iterator not only contains all the state it needs, but is also 100% safely copyable, then the answer to my original question is "No, it's not a bad idea". But the lurking possibility that iterators might not be 100% safely copyable -- for example, if there were subtle aliasing problems if you copied an iterator, incremented the original, then tried to use the copy -- is why this code feels ever-so-slightly sketchy to me.

Given that ypur preconditions hold, and the iterator is not invalidated, I see no problem. — Jesper Juhl, May 03 '18 at 16:15
You make a copy of an iterator here too `it = coll.begin()`. — eerorika, May 03 '18 at 16:17
@user2079303 Good point. I guess my caution comes from wondering whether iterators are best used only in the tightly-constrained pattern of the idiomatic `for` loop, or if you can get crazy and use them arbitrarily. I'll update the question with a bit more of my inquiry along those lines. — Steve Summit, May 03 '18 at 16:20
If the container will not be modified, an even better idea is to use [`std::adjacent_find`](http://en.cppreference.com/w/cpp/algorithm/adjacent_find) with a predicate that gets called with each adjacent pair of values in the container. Just make sure that the predicate always returns false. And since `std::adjacent_find` does, pretty much, what you're doing, in terms of iterating, if it's good enough for `std::adjacent_find`, it's good enough for you. — Sam Varshavchik, May 03 '18 at 16:24
derived from `std::map`? [Subclass/inherit standard containers?](https://stackoverflow.com/questions/6806173/subclass-inherit-standard-containers) — Andriy Tylychko, May 03 '18 at 18:25
@AndriyTylychko ISWYM. Thanks for your concern, and I did say "derived from", but I really meant "synonym of", i.e. "`typedef` for". So no problem there. — Steve Summit, May 03 '18 at 19:03

score 11 · Accepted Answer · answered May 03 '18 at 16:36

11

It depends on the type of iterator, but it's fine for std::map::iterator.

Iterators fall into different categories, depending on the operations they support and the guarantees they provide about the value they refer to.

std::map::iterator satisfies the requirements for the BidirectionalIterator concept. That means that, among other things, incrementing a copy of an iterator will not invalidate the original. That means that doing prev = it; ++it will not invalidate prev, so your algorithm is well-defined.

This is not the case for all iterators, however. The InputIterator concept does not provide this guarantee. Note the postcondition for ++i:

Postcondition: Any copies of the previous value of i are no longer required to be either dereferenceable or to be in the domain of ==.

I'm not aware of any iterators in the standard library that will lose their value if you increment a copy of them, but I have personally built just such an iterator type (it iterates over entries in an archive file, and the previous entry is no longer readable when you advance to the next one).

See also the Iterator, ForwardIterator, RandomAccessIterator, and OutputIterator concepts. All of them build on each other.

answered May 03 '18 at 16:36

Miles Budnek

28,216
2
35
52

1

`std::istream_iterator` is one such "self-destructing" iterator. – Quentin May 03 '18 at 16:39
1

"Incrementing a copy of an iterator will not invalidate the original." Perfect. That's just the guarantee I need. I knew about iterator categories, but I didn't realize that this property was called out in them, or that some categories didn't have it. (Which makes sense -- your archive example is a good one -- and makes me feel better, that I wasn't being overcautious.) – Steve Summit May 03 '18 at 16:40
@Quentin I was thinking `std::istream_iterator` remained valid, but didn't provide the rest of `ForwardIterator`'s multipass guarantee. – Miles Budnek May 03 '18 at 16:44
@SteveSummit Be careful about not resizing the container between calls. – rioki May 03 '18 at 16:51
This issue is causing some minor headaches for me right now. I have written a custom output iterator that is intended only for single-pass use. Yet according to the named requirement _LegacyOutputIterator_, I am supposed to support copying, even though it makes no sense for my iterator, and particularly because it causes headaches with flushing output at the end! (my iterator maps bits to bytes, it wraps another output iterator to a byte stream and _flushes_ whenever enough bits are written to it, and flushes any leftover bits on destruction). I've settled for providing only move semantics. – saxbophone Feb 09 '23 at 00:48

score 0 · Answer 2 · edited Jul 28 '23 at 15:14

Although it is not clear cut, but I would generally discourage against storing iterators.

First, the iterator concept is intended to abstract what you are accessing. This can be a stream or a container. Steam iterators are definitely not stable and storing them will not result in valid code. But storing iterators into containers is safe as long as the container does not change.

And that is the second issue, if you are accessing a container and are only reading from it, your code is fine. If your code is altering the container between calls, there is a chance that your iterator will be invalidated. Different containers have different semantics when a iterator is invalidated, but my rule of thumb is once the container is resized all iterators are invalid.

(I don't tend to memorize the exact semantics, since I program with the assumption that I may change container at any time and vector invalidated all iterators on a resize.)

Is it a bad idea to make a copy of an iterator?

2 Answers2