last day (15 days later) » 

8:18 PM
1
A: Validity of list begin iterator after insertion

KlausI 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 ...

 
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.
 
@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.
 
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?
 
@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.
 
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.
 
8:18 PM
@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!
BTW: We discussing the c++ standard now. You are absolutly free to implement your own container class for your needs. But you still stay on the problem to give the the "iterator" a new meaning and you must tell them how to behave on ay kind of container content modification. This is like: Stay before last inserted element, go behind the next inserted element, stay at the begin and so on. For my feeling it makes the scenario to complex.
Are you here? :-)
 
Yes, just a moment :)
I'm not quite understanding why you think that pinning the iterator to the end of the collection is the right thing to do when you call begin()on an empty list. If I think implemenation-wise, the case where the list is non-empty and the iterator is pointing to a single element should be quite clear. But the empty case is ambigous. End is equal to begin, and so where the iterator points to is ambigous if you think about values.
If I would choose to have the iterator stay at the begin, it would make sense. Same if I chose to pin it to the end.
So if anything I would argue that the standard in that case allows an implementation to choose to pin the iterator to either begin or end. But I'm also not convinced that they have done either intentionally...
Maybe it's just an oversight?
 
The problem is: The "end" iterator points BEHIND the end, but the begin iterator points to the FIRST element, if not existing, it can not point to it, because it is not present. Simply that. If we would like to have something like that, we must define it in a way to say: Begin() points BEFORE the first element. For a use case, where you say: Please point me always to the begin(), than simply do not use the "constant" iterator but the "begin()" function.
I see your needs and I absolutely agree that it feels not very handy on a first view. But all this is done by definition of the c++ standard. Regarding your question and your observed behaviour, I am in hope to give you the correct answer. My wish is also that you accept my answer, even if you dislike the standard :-)
 
8:35 PM
I don't particularly dislike it, but I would like to see which part of if defines this. Especially since I think doing this caused a crash in Visual Studio :)
Trying to grok what you are saying about end points behind the end and so forth. What you are basically saying is that the begin iterator cannot really exist in its "proper form" before there is at least one element in the collection, right? Well, begin() is defined for empty collections, so doesn't that counter your argumentation?
I do see that it's mentioned on cppreference that the begin iterator for an empty collection shouldn't be dereferenced, but nothing about it not pointing to the beginning of the collection once elements are added.
I guess you are basically saying that iterators works by pointing to elements in collections?
 
" but nothing about it not pointing to the beginning of the collection once elements are added."
That is simply by defintion of the begin() function as already given in my post: If empty, ret val is same as `end()`. That means, it points to the end if "generated" from empty list. As this, it still points to the end, even if you `push_back` something in. If insert is used, it always inserts BEFORE the current element which the iterator points to. So there is no gap in the docs. The point is simply that the `begin()` function is defined by returning the `end()` if container is empty.
 
> If empty, ret val is same as `end()`

It doesn't say that, though? It simply says that `begin() == end()`, which can be done in a smarter way. If you assume these are simple memory address comparisons, such as addresses into arrays, then yes, I agree that it wouldn't be possible.
And as I said, deque actually keeps the iterator pointing to the begin of the collection: cpp.sh/9ertes
So I cannot be that clear-cut that you need to keep the iterator pointing to the end.
 
8:53 PM
You are right. It would be nicer if they would write "It returns the same value as end()". We can read the current docs here in the opposite direction: This can also mean that end() delivers the begin() iterator...
BTW: That is a simple wiki and you can register and update! They are really like to get updates/comments on there docs. Bit cppreferrence nor cplusplus.com are "official" docs. If you really want to read the standards, take the official ISO-paper. The drafts are for free, the released papers must be paid.
But as said: I want to leave for having a meal ( 10 pm local time now ) :-) Would be nice to see the acceptance from you on my answer... thanks. I am not responsible for the c++ standards nor the docs nor the most popular reference sites... as this, I still believe my answer is correct :-)
 
Thanks for the discussion Klaus. I'm in the same time zone, so I can relate. I will consider accepting you answer if it turns out to be the correct one. But I'd like to keep the question open and see if I can get more attention to the question, because I believe it's an underspecified part of the spec.
 
OK, have a nice evening... let me know, if you find something related to this topic... always important to stay informed :-) Thanks for the discussion! Bye!
 

last day (15 days later) »