How does std::deque work currently?

[Dhruv Matani <dhruvbird at gmx dot net>]

After reading the source, it seems that something like this is happening
in the current version if std::deque:

1. The iterators are actually ranges. They store the first and last
element in a block.

2. Each block may contain or more objects. This block is called a node
in the comments that I read.

3. The iterator(Block/Node) is responsible for operator++(), etc... on
an iterator by checking whether the end of the local (block) storage has
been reached. If so, it makes the pointer to the map point to the next
area in memory, else, just increment the current pointer.

4. I want to confirm when EXACTLY are the iterators for the deque
invalidated?, because it seems to me that whenever the internal map is
reallocated, all the iterators will get invalidated, but this
invalidation will occur only when the client does a ++/-- when the
boundary of the current block has been reached, and the iterator needs
to point to the next block using it's internal pointer to the map.

5. Member function erase will copy all the elements before/after the
elements one place to the left/right depending upon whether the element
being erased is closer to the being or end. Same for insert?

I think that my understanding of erase/insert is incorrect, since the
standard says that erase/insert should be constant time (I think)

Please correct me if I'm wrong.


-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/