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

subramanian100in@yahoo.com, India wrote:

> 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

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

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

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

On 7 ÆÅ×, 08:58, "Alf P. Steinbach" <al...@start.no> wrote:

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

* Pavel Shved:
> On 7 ???, 08:58, "Alf P. Steinbach" <al...@start.no> wrote:
>
>> 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? :-)

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

--
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?

On 7 $B'f'V'S(B, 10:12, "Alf P. Steinbach" <al...@start.no> wrote:
>
> 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.