On Friday, August 12, 2011 15:29 Ellery Newcomer wrote: > On 08/12/2011 03:54 PM, Jonathan M Davis wrote: > > In the case of container that uses nodes - such as a linked list - > > because you can add and remove elements without affecting other > > elements, iterators and ranges don't tend to get invalidated as easily. > > As long as you don't remove the element (or elements in the case of a > > range - assuming that it keeps track of its two end points, as is > > likely) that it points to, then adding or removing elements from the > > container shouldn't invalidate the iterator/range. > > "shouldn't" isn't a guarantee. Where there is "shouldn't", there can't > be stableRemove*, no?
An implementation can guarantee it as long as your range doesn't directly point to an element being removed (i.e. as long as the element isn't on the ends - or maybe one past the end, depending on the implementation). But _no_ container can guarantee that an iterator or range which directly references an element which is removed is going to stay valid - not without playing some serious games internally which make iterators and ranges too inefficent, and possibly not even then. So, stableRemove is only going to guarantee that a range stays valid on as long as the end points of that range aren't what was being removed. > > So, basically what it comes down to is the short answer. A range which > > has been invalidated doesn't point to what it's supposed to point to > > anymore, and using it results in undefined behavior. It's less likely to > > blow up in D, because it's generally memory-safe, but you're going to > > get incorrect behavior. > > > > - Jonathan M Davis > > suppose your linked list range points to a node X. element in X is > removed by the linked list, and the range automagically moves to X.next > (or X.prev). Is the range invalid by this standard or not? (no way 'san > ifrinn I'm going to implement that, though). If the element that you removed was the end point of a range, then the range won't be valid anymore. > heh heh. most of this business has only convinced me I want immutable > containers. It's only an issue if you keep ranges of a container around and then alter the container. If you're just use ranges to do an operation or two and then throw them away, it's not an issue. C++ has been this way for years, and it's generally not a problem. It _can_ be a problem if you try and keep iterators/ranges around while altering a container, but there's not really a good way around that. And as long as you're aware of that, you'll be fine. It's only when you try and alter a container while retaining ranges to it that you're going to have to start worrying about whether a range has been invalidated or not. - Jonathan M Davis