Re: implementation of vector, deque

From:

Barry <dhb2000@gmail.com>

Newsgroups:

comp.lang.c++

Date:

Thu, 07 Feb 2008 12:44:31 +0800

Message-ID:

<foe7cl$2c1$1@news.cn99.com>

subramanian100in@yahoo.com, India wrote:

vector and deque provide similar operations like operator[]. vector

the /operator[]/ and /at/ member functions are only provided by
containers whose iterators are random access iterators.

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.

Does the standard say anything regarding how the elements

should be stored in vector and deque ?

the standard says nothing about the underlying data structure.

Kindly clarify.

Well, the timing requirement somehow decides how the library components
are designed using certain data structure.

--
Best Regards
Barry