[Bug libstdc++/24693] Deque improvements

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=24693

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Created attachment 33542
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=33542&action=edit
Patch to cache a free node.

(In reply to Paolo Carlini from comment #2)
> More interesting work to do:
> 
>   http://gcc.gnu.org/ml/libstdc++/2005-11/msg00241.html

Here's a proof of concept to prevent repeated reallocations for this case:

while (a long time)
{
     dq.push_front(t);
     ...
     dq.pop_back();
}

A single free node is cached in _M_map[-1], so there's no change to the layout
of the class.