invalidation of iterators on deque<T>:insert()

[subramanian100in]

In ISO/IEC 14882:2003 document, in the section '23.2.1.3 deque
modifiers', the following is mentioned:

iterator insert(iterator position, const T& x);

void insert(iterator position, size_type n, const T& x);

template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator
last);

1 Effects: An insert in the middle of the deque invalidates all the
iterators and references to elements of the deque. An insert at either
end of the deque invalidates all the iterators to the deque, but has
no effect on the validity of references to elements of the deque.

My questions:
--------------------
what is meant by invalidation of iterators to elements of the deque
and what is meant by invalidation of references to elements of deque ?
(Are they different ?) Kindly give an example so that I can
understand. The second statement in the above, says that 'but has no
effect on the validity of references to elements of the deque'. Here
what is meant by 'but has no effect on the validity of references to
elements' ?.

2 Notes: If an exception is thrown other than by the copy constructor
or assignment operator of T there are no effects.

My questions:
--------------------
Here what exceptions are thrown by copy ctor and assignment operator?
(Is it bad_alloc exception ?). What operations other than copy ctor
and assignment of T can throw exception ? What are those exceptions ?
What is meant by saying 'there are no effects' ?

Kindly explain.

Thanks
V.Subramanian

 

[James Kanze]

In ISO/IEC 14882:2003 document, in the section '23.2.1.3 deque
modifiers', the following is mentioned:

iterator insert(iterator position, const T& x);

void insert(iterator position, size_type n, const T& x);

template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator
last);

1 Effects: An insert in the middle of the deque invalidates
all the iterators and references to elements of the deque. An
insert at either end of the deque invalidates all the
iterators to the deque, but has no effect on the validity of
references to elements of the deque.

My questions:

The standard isn't too clear concerning the first. Clearly, any
attempt to access through the iterator or increment or decrement
it is undefined behavior; I don't think you're even allowed to
copy it, however.

In the case of references, any use of the reference once it
becomes invalid is undefined behavior. For pointers (not
mentionned above, but they are invalidated under the same
conditions as references), any rvalue to lvalue conversion of
the pointer is undefined behavior.

(Are they different ?)

Well, one affects iterators, and the other pointers and
references. The effects of invalidation, however, are pretty
much the same.

Kindly give an example so that I can understand.

std::deque< int > d ;
for ( int i = 1 ; i <= 5 ; ++ i ) {
d.push_back( i ) ;
}
std::deque< int >::iterator
iter = d.begin() + 1 ;
int& r = *iter ;
int* p = &r ;
d.push_back( 100 ) ; // invalidates iter, but not r and p.
d.insert( d.begin() + 2, 42 ) ;
// invalidates iter, r and p.

The second statement in the above, says that 'but has no
effect on the validity of references to elements of the
deque'. Here what is meant by 'but has no effect on the
validity of references to elements' ?.

That it has no effect on the validity of references to elements.
Or pointers to elements, for that matter.

2 Notes: If an exception is thrown other than by the copy
constructor or assignment operator of T there are no effects.

My questions:

Whatever you decide to throw from them.

(Is it bad_alloc exception ?).

It could be, if the copy constructor or the assignment operator
allocate memory dynamically.

What operations other than copy ctor and assignment of T can
throw exception ?

Anything. You, as the programmer of the class, decide what
exceptions will be thrown.

Formally, std::deque can throw just about anything.
Practically, from a QoI point of view, it will throw
std::bad_alloc if an allocation fails, and will be exception
neutral for any exceptions coming from the instantiation class.

What are those exceptions ?
What is meant by saying 'there are no effects' ?

That the function will have no effects if an exception is
thrown. This is the strong exception guarantee. Also known as
transactional integrity: either the function works, returning
normally, or it does nothing.

 

[Barry]

In ISO/IEC 14882:2003 document, in the section '23.2.1.3 deque
modifiers', the following is mentioned:

iterator insert(iterator position, const T& x);

void insert(iterator position, size_type n, const T& x);

template <class InputIterator>
In ISO/IEC 14882:2003 document, in the section '23.2.1.3 deque
modifiers', the following is mentioned:

iterator insert(iterator position, const T& x);

void insert(iterator position, size_type n, const T& x);

template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator
last);

1 Effects: An insert in the middle of the deque invalidates all the
iterators and references to elements of the deque. An insert at either
end of the deque invalidates all the iterators to the deque, but has
no effect on the validity of references to elements of the deque.

My questions:
--------------------
what is meant by invalidation of iterators to elements of the deque
and what is meant by invalidation of references to elements of deque ?
(Are they different ?) Kindly give an example so that I can
understand. The second statement in the above, says that 'but has no
effect on the validity of references to elements of the deque'. Here
what is meant by 'but has no effect on the validity of references to
elements' ?.

Though the standard does not restrict the data structure for
implementing
the containers in the STL.
But taking the usual implemtions of the deque in to account for
answering these question
makes is easier.

The usual data structure of std::deque<T> can be simplified as
array of pointer to array of T, that is

[ ][ ][ ][ ]
| |
| |
* *
* *
* *

[] is a slot, aka pointer to array of T
* is a T

obviously insertion in the middle invalidates both iterators and
reference
while insertion on both ends, array of T maybe allocated if the first/
last array of T
is full, so references are not invalidate. remind that increment/
decrement is invalid for the original interators which is part of
invildation of iterator, while validation of reference only requires
the reference refer to the right original element.

2 Notes: If an exception is thrown other than by the copy constructor
or assignment operator of T there are no effects.

My questions:

All exceptions that may occur, I think.

What operations other than copy ctor

and assignment of T can throw exception ? What are those exceptions ?
What is meant by saying 'there are no effects' ?

It means that the original data remainds.
Check out http://www.boost.org/community/exception_safety.html