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
]