Re: implementation of vector, deque
* Barry:
subramanian100in@yahoo.com, India wrote:
vector stores the elements contiguously. Does the deque also store the
elements contiguously in order to provide operations similar to the
vector ?.
No, as Kai-Uwe Bux mentioned else-thread.
vector uses array.
sgi STL uses /_Tp** _M_map/ for this indirect paging/mapping
<std>
23.2.1/1
In addition, it supports constant time insert and erase operations at
the beginning or the end; insert and erase in the middle take linear
time. That is, a deque is especially optimized for pushing and popping
elements at the beginning and end.
</std>
these requirement makes deque can't use the same data structure as vector.
No, on the contrary: they make it easy to implement a dequeue in terms
of e.g. a (single) vector, treating the vector as a circular buffer.
At least if "constant time" is interpreted as "amortized constant time",
as with push_back on a vector (where also the expression "constant time"
is used).
If deque had been restricted to one sequential iterator, and insert and
erase had to be via that iterator, then insert and erase could have been
constant time also in the middle, still with a vector as storage.
However, if dequeue had been designed with contiguous storage in mind,
then it would presumably have had a capacity().
The lack of support for that allows more elaborate implementations.
Cheers, & hth.,
- Alf
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?