Topic: Why can't a deque be more like a vector?


Author: Miles Sabin <miles@mistral.co.uk>
Date: 1997/08/07
Raw View
Has there been any discussion by the committee of the semantics of
deque<T>::insert() (23.2.1.3)? The requirement that,

  An insert at either end of the deque invalidates all iterators to
  the deque, but has no effect on the validity of references to
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  elements of the deque.
  ^^^^^^^^^^^^^^^^^^^^^

combined with the fact that deques are required to support random
access iterators (ie. O(1) for operator[] and for operator+/- on
iterators) forces an overly heavyweight implementation (as found in
the HP and SGI STL's).

Clearly this requirement is much more demanding than the corresponding
clause for vector, and is quite likely to be unnecessary for many (if
not most) applications. If it were dropped (ie. insert at either end
allowed to invalidate references to elements), and a reserve()
function added,

  reserve(size_type at_end, size_type at_begin = 0);

we could have a considerably lighter implementation, which would
probably be more practical in the typical case.

What's the justification for this requirement?


Miles

--
Miles Sabin                               mailto:miles@mistral.co.uk
Cathexis                                  voice  01273 732338
                                          letter 10 Pembroke Gardens
                                                 Brighton, BN3 5DY
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]