Is it allowed by the standard for a deque to allocate is memory in a sparse way?
My understanding is that most implementations of deque allocate memory internally in blocks of some size. I believe, although I don't know this for a fact, that implementations allocate at least enough blocks to store all the items for there current size. So if a block is 100 items and you do
std::deque<int> foo;
foo.resize( 1010 );
You will get at least 11 blocks allocated. However given that in the above all 1010 int are default constructed do you really need to allocate the blocks at the time of the resize call? Could you instead allocate a given block only when someone actually inserts an item in some way. For instance the implementation could mark a block as "all default constructed" and not allocate it until someone uses it.
I ask as I have a situation where I potentially want a deque with a very large size that might be quite sparse in terms of which elements I end up using. Obviously I could use other data structures like a map but I'm interested in what the rules are for deque.
A related question given the signature of resize void resize ( size_type sz, T c = T() ); is whether the standard requires that the default constructor is called exactly sz times? If the answer is yes then I guess you can't do a sparse allocation at least for types that have a non trivial default constructor, although presumably it may still be possible for built in types like int or double.