implementation of vector, deque

[subramanian100in]

vector and deque provide similar operations like operator[]. vector
stores the elements contiguously. Does the deque also store the
elements contiguously in order to provide operations similar to the
vector ?. Does the standard say anything regarding how the elements
should be stored in vector and deque ?

Kindly clarify.

Thanks
V.Subramanian

 

[Kai-Uwe Bux]

vector and deque provide similar operations like operator[]. vector
stores the elements contiguously. Does the deque also store the
elements contiguously in order to provide operations similar to the
vector ?. Does the standard say anything regarding how the elements
should be stored in vector and deque ?

The standard specifies that elements in a vector are stored contiguously in
memory. It does not specify any storage layout for deque. However, the
complexity specifications for deque make are somewhat incompatible with
contiguous storage layout and, to my knowledge, std::deque is usually
implemented as a collection of contiguous pages using one more level of
indirection to provide operator[].


Best

Kai-Uwe Bux

 

[Barry]

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.

 

[Alf P. Steinbach]

* Barry:

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

 

[Alf P. Steinbach]

* Alf P. Steinbach:

* Barry:

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

 

[Pavel Shved]

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

How can `always takes constant time' in 23.2.1.3 section refer to
amortied cost?

The standard is to write the worst cases. No amortized cost shall be
involved there.

P.S. For example, vector's push_back has amortized constant cost in
most common implementations, though the standard defines it to be no-
worst than linear.

 

[Alf P. Steinbach]

* Pavel Shved:

How can `always takes constant time' in 23.2.1.3 section refer to
amortied cost?

I don't think "always" can refer to "amortized". Context: I referred to
the quoted section in the article I replied to, not the section you
refer to here, and the question was whether that requirement implied
that storage couldn't be contiguous, as was stated in that article. See
my earlier posting in this thread for another requirement (reference
validity) that also makes contiguous storage impossible.

The standard is to write the worst cases. No amortized cost shall be
involved there.

P.S. For example, vector's push_back has amortized constant cost in
most common implementations, though the standard defines it to be no-
worst than linear.

push_back was originally required to be simply "constant time" by
§23.1.1/12, but with C++03 corrected to "amortized constant time".

Where did you get that "no-worst than linear" from?


Cheers, & hth.,

- Alf

 

[Pavel Shved]

push_back was originally required to be simply "constant time" by
$B!x(B23.1.1/12, but with C++03 corrected to "amortized constant time".

Where did you get that "no-worst than linear" from?

I missed the first paragraph of 23.1.1/12 and was loking at the table
only. So i followed to insert operation and got it there.

Well, then for me the usage of `amortized cost' is the reason to blame
standard. But, thinking more about it, i concluded that i should
blame O(n) usage as well, so i'd better to shut up. Sorry.