Why no operator+ for std::list iterators?

Question

I was about to write code like this:

std::list<whatevertype> mylist;

// ...

std::list<whatevertype>::iterator it;

for(it = mylist.begin(); it != mylist.end(); ++it) {
    // ...
    if(some condition)
        mylist.erase(it);
}

But I realized, this code is wrong: mylist.erase(x) will invalidate the iterator it, so the ++it is likely to fail.

So I tried changing it to

std::list<whatevertype>::iterator it;
std::list<whatevertype>::iterator nextit;

for(it = mylist.begin(); it != mylist.end(); it = nextit) {
    // ...
    nextit = it + 1;
    if(some condition)
        mylist.erase(it);
}

But, to my surprise, this failed: evidently operator+ is not defined for std::list iterators.

I've since found this other question and learned that the standard idiom for deleting "out from under" an iterator is more like

for(it = mylist.begin(); it != mylist.end(); ) {
    if(some condition)
          it = mylist.erase(it);
    else  ++it;
}

I believe I could also get away with

for(it = mylist.begin(); it != mylist.end(); ) {
    // ...
    std::list<whatevertype>::iterator previt = it;
    ++it;

    if(some condition)
        mylist.erase(previt);
}

But my question is, is there a reason that operator+ is not defined for these iterators?

You get the equivalent functionality by using [`std::next`](http://en.cppreference.com/w/cpp/iterator/next). — R Sahu, Mar 05 '18 at 18:04
It's probably a better idiom to use [std::remove_if](http://en.cppreference.com/w/cpp/algorithm/remove) than a manual loop. — Galik, Mar 05 '18 at 18:17

score 14 · Accepted Answer · edited Feb 06 '23 at 19:40

One rule they had with the std iterators and collection was to make expensive things verbose.

On a list iterator, it+50 takes O(50) time. On a vector iterator, it+50 takes O(1) time. So they implemented + on vector iterators (and other random access iterators) but not on list iterators (and other weaker iterators).

std::next and std::advance and std::prev can solve your problem easier:

auto previt = std::prev(it);

or

auto nextit = std::next(it);

these also take a count, but because they are an explicit function call it was decided that them being expensive is acceptable.

Among other things, you can search for calls to std::next and std::prev and get iterator manipulation; + is heavily overloaded and finding the expensive calls is hard.

Note that std::basic_string doesn't follow the same conventions as other std containers.

"Make expensive things verbose". Aha. That's the key. Thanks. — Steve Summit, Mar 05 '18 at 18:15

score 4 · Answer 2 · answered Mar 05 '18 at 18:05

4

It isn't that + is missing for all iterators. It is missing for std::list iterators.

That's because a list iterator is incredibly inefficient at random access. Therefore, making random access easy is a bad idea.

You can use std::advance. It makes it more evident that you are moving across the list one element at a time.

answered Mar 05 '18 at 18:05

Zan Lynx

53,022
10
79
131

Question title updated in response to your first sentence, thanks. – Steve Summit Mar 05 '18 at 18:17

score 3 · Answer 3 · answered Mar 05 '18 at 18:05

std::list uses a BidirectionalIterator which only defines increment and decrement. As std::list is a linked list the implementation of the iterator can only move one node at a time.

The interface is designed to make sure you know that moving by more than one element isn't a simple operation like it is with other iterators like a RandomAccessIterator returned from a std::vector.

see http://en.cppreference.com/w/cpp/concept/Iterator for a definition of the different iterator types.

Why no operator+ for std::list iterators?

3 Answers3

Related