How operations invalidate iterators - couple of doubts...

[JUAN DENT]

Hi,
Lippman's C++ Primer 5th edition states:

"After an operation that adds elements to a container:

1) iterators, pointers and references (including the off-the-end and before-the-beginning iterators) to a list or forward_list remain valid
"

QUESTION: what if the element was added at the end or at the beginning, how can the corresponding iterators remain valid?


"After we remove an element:
2) iterators, pointers and references (including the off-the-end and before-the-beginning iterators) to a list or forward_list remain valid"

QUESTION: what if the element was removed from the end or the beginning, how can the corresponding iterators remain valid?

"After we remove an element:
3) all other iterators, pointers and references to a deque are invalidated if the removed elements are anywhere but the front or the back. If we removed elements from the back of the deque, the off-the-end iterator is invalidated but others are unaffected; they are also unaffected if we remove from the front"

QUESTION: why are all invalidated if we remove an element from a deque anywhere but the front or the back? If we remove from the end, why does off-the-end iterator becomes invalidated (whereas from other containers that iterator remains valid?)?

"After removing an element:
4) all other iterators, pointers and references to a vector or string remain valid for elements before the removal point. The off-the-end iterator is always invalidated when we remove items."


QUESTION: why is off-the-end iterator become invalid?

Thanks for the help!!

Juan Dent

[helios]

what if the element was added at the end or at the beginning, how can the corresponding iterators remain valid?

what if the element was removed from the end or the beginning, how can the corresponding iterators remain valid?

Because insertion and removal on a linked list does not require nodes to be reallocated. Instead, pointers are simply redirected.

why are all invalidated if we remove an element from a deque anywhere but the front or the back?

Because removing from the middle of a deque may require shifting all elements around.

If we remove from the end, why does off-the-end iterator becomes invalidated (whereas from other containers that iterator remains valid?)?

Because a deque behaves partly as a vector. The end() iterator is (conceptually) adressof(deque.back()) + 1. Since popping from the back moves adressof(deque.back()) a previously obtained end() iterator might point to adressof(deque.back()) + 2, which would be invalid.

why is off-the-end iterator become invalid?

Same idea as for deque. vector.back() becomes a different element.

[JUAN DENT]

Ok, got the last 2 thanks!.

However still not clear for the first 2 cases:

for a list, the end() iterator is NOT (conceptually) addressof(list.back()) + 1, because lists are not contiguous. So how are end() iterators represented in a list?

How about before beginning iterators for forward_lists? what do they point to? I bet these 2 questions will contain the answers to my original 2 questions...


Thanks helios. ... will wait for your answers

Juan

[helios]

So how are end() iterators represented in a list?

A list iterator is probably a pointer to the node, so the end() might be represented as a null pointer.

How about before beginning iterators for forward_lists? what do they point to?

Suppose that the forward_list is implemented like this:

struct list_node;

template <typename T>
class half_list_node{
    list_node<T> *next;
};

template <typename T>
class list_node : public half_list_node<T>{
    T data;
};

class forward_list_iterator;

template <typename T>
class forward_list{
    half_list_node<T> before_first;
    forward_list_iterator<T> before_begin() const{
        return forward_list_iterator<T>(&this->before_first);
    }
};

template <typename T>
class forward_list_iterator{
    half_list_node<T> *current;
public:
    const T &operator*() const{
        return static_cast<list_node  *>(this->current)->data;
    }
    void operator++(){
        this->current = this->current->next;
    }
};

[JUAN DENT]

Thanks a lot!! Great answers helios!!

Juan Dent