4

Consider the following program:

#include <list>
#include <cstdio>

int main() {
    std::list<int> l;
    std::list<int>::iterator it = l.begin();
    l.push_back(0);
    l.insert(it, 1);
    for(const int &i: l) {
        printf("%d", i);
    }
}

(http://cpp.sh/66giy)

This prints 01. Very surprising. If I change the list to a deque, it prints the expected 10.

Is this a bug?

EDIT: The deque behavior is irrelevant, iterators to deques are invalidated by push_back.

Alexander Torstling
  • 18,552
  • 7
  • 62
  • 74
  • list does not invalidate iterators on insert so `it` will point to what it pointed to. (begin in your example) – NathanOliver Jan 29 '20 at 20:11
  • @NathanOliver That is not true, at least in clang it will print the opposite. I know about iterator invalidation, but I think this is an edge case. Can you unlock this question please? Example: http://cpp.sh/66giy – Alexander Torstling Jan 30 '20 at 07:19
  • [std::list::insert](https://en.cppreference.com/w/cpp/container/list/insert) - `iterator insert( iterator pos, const T& value );` *"inserts value before pos"* -- so your output is expected. – David C. Rankin Feb 11 '20 at 19:51
  • @DavidC.Rankin that would become "inserts value before beginning", so I would expect "1" to be inserted at the start of the collection. – Alexander Torstling Feb 11 '20 at 19:57
  • Recall you have pushed, `l.push_back(0);`, and that initially when the list is empty `it.begin() == it.end()`. I don't see any inconsistency in the `.push_back()` which adds to the beginning of the list and `it` initialized when the list was empty now being one after the `.push_back()` as it was equal to `.end()` to begin with. (I'd have to look further, but the behavior here is likely left to compiler -- I just don't know) – David C. Rankin Feb 11 '20 at 20:41
  • @DavidC.Rankin That's exactly what I'm wondering. If the standard allows for simply returning end when calling `begin()` on an empty collection, or if it has to do something smarter. Or more generally, what is exactly expected from these empty collection iterators. If iterators aren't supposed to be invalidated, I'm surprised that my begin iterator starts pointing to end when I add an element. Maybe empty collection iterators just aren't well defined, i don't know, but it's unhandy for me if that's the case. – Alexander Torstling Feb 11 '20 at 20:55

1 Answers1

2

I can't catch your problem... ok, lets try to reproduce:

std::list<int> l;
std::list<int>::iterator it = l.begin();

What is your iterator pointing to? To the end of the list as the list is empty!

§23.2.1 [container.requirements.general] p6

begin() returns an iterator referring to the first element in the container. end() returns an iterator which is the past-the-end value for the container. If the container is empty, then begin() == end();

l.push_back(0);

Now the list contains a single element. Your iterator is valid as a list did not invalidate the iterator and points still to the end of the list.

l.insert(it, 1);

Now you insert 1 before the iterator which points still to the end. So your first element is a 0 and the last one is a 1.

So your output is 01 as expected.

Maybe your expectation that the begin() delivers a fixed virtual start of container iterator is simply wrong?

Community
  • 1
  • 1
Klaus
  • 24,205
  • 7
  • 58
  • 113
  • Yes, this is where it gets interesting. Your quote states that `begin() == end()` when the container is empty, but says nothing about what should happen when the container grows. If list iterators are to remain valid after insertion, I would argue that the iterator have to track whether it's a begin or end iterator. – Alexander Torstling Feb 11 '20 at 19:53
  • @AlexanderTorstling: There is nothing in c++ which tracks something automatically. The container did simply not know that there is a iterator still present in your prog which should be "updated" in any case. And the `begin()` method is simply defined to deliver the "end" if the container is empty. No chance for tracking and especially it would simply do the wrong thing! In addition: If we could do it, to what element should `begin()` point if the container is empty? Simply impossible by definition of container classes from the standards. – Klaus Feb 11 '20 at 20:00
  • It would be perfectly reasonable in my mind that the iterator object has state. It can still equate to another iterator despite having differing internal state. You state that not adding to the end is wrong. How do you then explain that deque has the opposite behavior? – Alexander Torstling Feb 11 '20 at 20:04
  • 1
    @AlexanderTorstling: If the iterator has a internal state which tells us that it points to the beginning, than it must be registered to the container to get updated automatically. There is no interface for that in all the container classes. I see your wishes but it is simply not defined as this. BTW: Iterators are defined to iterate! If it has a state which says "Please point to begin()", what is the sense of it? If you do not need a iterator but the *current* begin() value, than don't use the previous generated iterator but the `begin()` function. – Klaus Feb 11 '20 at 20:07
  • Does the iterator really have to register for updates? If it has a reference to the container, it should be golden, right? I hear your argumentation, but to me this sounds like "in a naive/straight-forward implementation, this would happen". I'm not convinced you couldn't make it different. My usecase is that I wanted to track an insertion point in a list by means of storing an iterator, and I get a lot of special cases in my code if the container cannot handle the empty container case properly. But mostly, I was curious what the standards says about this, since it felt unclear to me. – Alexander Torstling Feb 11 '20 at 20:12
  • @AlexanderTorstling: If you call any member function of your container class, how would it be possible that the container class knows to inform some iterators? OK, it might be possible that they can be "tracked" from creation, so begin(9 will not only deliver the iterator but register already for tracking, fine. But still the same problem: You must provide the intent of the use of the iterator. And empty container is not a special case! Inserting before the current iterator position moves logically the iterator "behind" the inserted element. It is never at the begin anymore! – Klaus Feb 11 '20 at 20:18
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/207612/discussion-between-klaus-and-alexander-torstling). – Klaus Feb 11 '20 at 20:18