deque push_(back/front) complexity
Dhruv
push_(whatever) functions should be constant time (as opposed to
amortized time). Now, how would one do that keeping in mind that you
have to provide elemental access (random access).
-Dhruv.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std...@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Maciej Sobczak
Dhruv wrote:
> It is mentioned (in the standard) that for deque and vector the
> push_(whatever) functions should be constant time (as opposed to
> amortized time).
I think that the word "amortized" is missing in few places.
Note, that:
23.2.4/1:
"A vector [...] supports (amortized) constant time insert [...] at the end."
The above description for vector is correct and expresses the fact that
the implementation is expected to meet the "constant time" for
sufficiently large number of operations - this is what "amortized" is
all about.
Having this in mind, the wording in 23.2.1/1:
"A deque [...] supports constant time insert [...] at the beginning and
the end."
seems to miss the obvious wording "(amortized)" before "constant", which
would make this wording analogous to that from 23.2.4/1.
Also, the 23.1.1/12:
"The operations in Table 68 are provided only for the containers for
which they take constant time:"
should contain the wording "(amortized)" for consistency with all the above.
Is this what you mean?
--
Maciej Sobczak
http://www.maciejsobczak.com/
Distributed programming lib for C, C++, Python & Tcl:
http://www.maciejsobczak.com/prog/yami/
Bo Persson
"Maciej Sobczak" <mac...@maciejsobczak.com> skrev i meddelandet
news:bcpv0b$711$1...@SunSITE.icm.edu.pl...
Probably. :-)
This text is revised for the next edition of the standard document:
"Table 68 lists sequence operations that are provided for some types
of sequential containers but not others. An implementation shall
provide these operations for all container types shown in the
``container'' column, and shall implement them so as to take amortized
constant time"
See
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1481.html#139
Bo Persson
bo...@telia.com
Chris Jefferson
> It is mentioned (in the standard) that for deque and vector the
> push_(whatever) functions should be constant time (as opposed to
> amortized time). Now, how would one do that keeping in mind that you
> have to provide elemental access (random access).
>
I believe the true results are (looking in book).
Vector has constant time on push_back as long as you have allocated
enough space previously. If you haven't it's amorised (as it may have to
copy the vector). push_front is O(n)
deque is amorised time on both push_back and push_front, mainly because
you can't allocate space at "both ends". If you could it would be
constant time.
Ben Hutchings
Dhruv wrote:
> It is mentioned (in the standard) that for deque and vector the
> push_(whatever) functions should be constant time (as opposed to
> amortized time). Now, how would one do that keeping in mind that you
> have to provide elemental access (random access).
I see no such wording. Please cite chapter and verse.
John Madsen
> It is mentioned (in the standard) that for deque and vector the
> push_(whatever) functions should be constant time (as opposed to
> amortized time). Now, how would one do that keeping in mind that you
> have to provide elemental access (random access).
>
> -Dhruv.
The standard explicitly says that vector's push_back takes amortized
constant time:
"A vector is a kind of sequence that supports random access iterators.
In addition, it supports (amortized) constant time insert and erase
operations at the end;" (23.2.4/1)
Deque's push methods are simply constant time because it is never
necessary to reallocate the entire sequence (as is the case with
vector).
I'm not sure what you're worried about with random access, but I'm
guessing it has to do with reallocation after insertion.
John
Andy Sawyer
on Thu, 19 Jun 2003 02:24:59 +0000 (UTC),
mac...@maciejsobczak.com (Maciej Sobczak) wrote:
> Hi,
>
> Dhruv wrote:
> > It is mentioned (in the standard) that for deque and vector the
> > push_(whatever) functions should be constant time (as opposed to
> > amortized time).
>
> I think that the word "amortized" is missing in few places.
>
> Note, that:
>
> 23.2.4/1:
> "A vector [...] supports (amortized) constant time insert [...] at the end."
>
> The above description for vector is correct and expresses the fact
> that the implementation is expected to meet the "constant time" for
> sufficiently large number of operations - this is what "amortized" is
> all about.
>
>
> Having this in mind, the wording in 23.2.1/1:
> "A deque [...] supports constant time insert [...] at the beginning
> and the end."
>
>
> seems to miss the obvious wording "(amortized)" before "constant",
> which would make this wording analogous to that from 23.2.4/1.
The reason that (amortized) is missing is because it is not
needed. For deque, insert at the beginning and end
(i.e. push_back/_front) really are constant time, whilst with vector
push_back is amortized constant time (a deque never needs to copy it's
contents as a result of a push_back, whilst a vector may do).
--
"Light thinks it travels faster than anything but it is wrong. No matter
how fast light travels it finds the darkness has always got there first,
and is waiting for it." -- Terry Pratchett, Reaper Man
Francis Glassborow
<an...@despammed.com> writes
>The reason that (amortized) is missing is because it is not
>needed. For deque, insert at the beginning and end
>(i.e. push_back/_front) really are constant time, whilst with vector
>push_back is amortized constant time (a deque never needs to copy it's
>contents as a result of a push_back, whilst a vector may do).
Nonetheless it does need to acquire extra memory periodically which is
not a zero cost operation. And it also needs to do something about the
intermediate indirection layer.
--
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
Francis Glassborow
Madsen <johnmads...@hotmail.com> writes
>Deque's push methods are simply constant time because it is never
>necessary to reallocate the entire sequence (as is the case with
>vector).
Constant time in my book means the same time for every use of an
operation. This is not the case for a deque. However it is amortised
constant time because the cost of allocating an extra block of memory is
shared between all the potential elements that will be stored in that
block.
--
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
---
John Potter
Sawyer) wrote:
> The reason that (amortized) is missing is because it is not
> needed. For deque, insert at the beginning and end
> (i.e. push_back/_front) really are constant time, whilst with vector
> push_back is amortized constant time (a deque never needs to copy it's
> contents as a result of a push_back, whilst a vector may do).
You hit the play on words exactly. Deque push_back/front is NOT
constant TIME. It does use a constant number of calls to the copy
ctor of T. Nothing is measured in terms of time. Everything is
measured in terms of operations on T.
When sizeof(T) is large enough, deque becomes an array of pointers
to T. It has amortized constant time growth of the array of
pointers, but claims to have constant growth because it makes no
copies of T. Nice tap-dance.
John
Dhruv
Ok, thanks for the link. Ok, so it's been resolved (or will be in the
near future)......
Regards,
Dhruv.
Hans Bos
""Bo Persson"" <bo...@telia.com> wrote in message
news:FfmIa.16481$dP1....@newsc.telia.net...
>
>
> This text is revised for the next edition of the standard document:
>
> "Table 68 lists sequence operations that are provided for some types
> of sequential containers but not others. An implementation shall
> provide these operations for all container types shown in the
> ``container'' column, and shall implement them so as to take amortized
> constant time"
>
> See
> http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1481.html#139
>
I don't think this is enough.
Table 68 doesn't describe the insert function
According to 23.2.1.3/3 inserts at either end of the deque must take
constant time.
And also 23.2.4.3/2 says that the complexity of insert is proportional to
the distantant to the end.
So even with the change in defect report 139, deque.insert(begin(), ...),
deque.insert(end(), ..) and vector.insert(end(), ...) must take (non
amortized) constant time.
Greetings,
Hans.
Andy Sawyer
on Fri, 20 Jun 2003 21:48:39 +0000 (UTC),
fra...@robinton.demon.co.uk (Francis Glassborow) wrote:
> In article <vfv2he...@ender.evo6.com>, Andy Sawyer
> <an...@despammed.com> writes
>
> >The reason that (amortized) is missing is because it is not
> >needed. For deque, insert at the beginning and end
> >(i.e. push_back/_front) really are constant time, whilst with vector
> >push_back is amortized constant time (a deque never needs to copy it's
> >contents as a result of a push_back, whilst a vector may do).
>
> Nonetheless it does need to acquire extra memory periodically which is
> not a zero cost operation. And it also needs to do something about the
> intermediate indirection layer.
Complexity requirements of the standard library containers are written
in terms of operations on the contained type. Thus, deque's push_front
and push_back are considered "constant time" (O(1)).
--
"Light thinks it travels faster than anything but it is wrong. No matter
how fast light travels it finds the darkness has always got there first,
and is waiting for it." -- Terry Pratchett, Reaper Man
---
Andy Sawyer
on Fri, 20 Jun 2003 22:12:54 +0000 (UTC),
jpo...@falcon.lhup.edu (John Potter) wrote:
> On Fri, 20 Jun 2003 19:38:34 +0000 (UTC), an...@despammed.com (Andy
> Sawyer) wrote:
>
> > The reason that (amortized) is missing is because it is not
> > needed. For deque, insert at the beginning and end
> > (i.e. push_back/_front) really are constant time, whilst with vector
> > push_back is amortized constant time (a deque never needs to copy it's
> > contents as a result of a push_back, whilst a vector may do).
>
> You hit the play on words exactly. Deque push_back/front is NOT
> constant TIME.
Indeed, but it IS "O(1)". In fact, there's no way ANY standard library
component can claim to do anything in constant TIME, because there may
be many timing issues outside the control of the library (and even the
calling program).
> It does use a constant number of calls to the copy ctor of T.
> Nothing is measured in terms of time. Everything is measured in
> terms of operations on T.
Exactly.
> When sizeof(T) is large enough, deque becomes an array of pointers
> to T.
Actually, sizeof(T) doesn't need to be large - although every
implementation of std::deque I've studied has based their "page size"
on sizeof(T). It seems legitimate (if perhaps not terribly efficient)
to implement deque in this way for any T. Of course, if the "page
size" of the deque were user configurable...
> It has amortized constant time growth of the array of pointers, but
> claims to have constant growth because it makes no copies of T.
> Nice tap-dance.
Ah, but can it do the hustle? ;)
Regards,
Andy S.
--
"Light thinks it travels faster than anything but it is wrong. No matter
how fast light travels it finds the darkness has always got there first,
and is waiting for it." -- Terry Pratchett, Reaper Man
---
John Potter
(Francis Glassborow) wrote:
> In article <vfv2he...@ender.evo6.com>, Andy Sawyer
> <an...@despammed.com> writes
> >The reason that (amortized) is missing is because it is not
> >needed. For deque, insert at the beginning and end
> >(i.e. push_back/_front) really are constant time, whilst with vector
> >push_back is amortized constant time (a deque never needs to copy it's
> >contents as a result of a push_back, whilst a vector may do).
> Nonetheless it does need to acquire extra memory periodically which is
> not a zero cost operation. And it also needs to do something about the
> intermediate indirection layer.
The standard ignores all of these things. 23.1/2.
John
Dhruv
[snip]......
> I think that the word "amortized" is missing in few places.
>
> Note, that:
>
> 23.2.4/1:
> "A vector [...] supports (amortized) constant time insert [...] at the end."
>
> The above description for vector is correct and expresses the fact that
> the implementation is expected to meet the "constant time" for
> sufficiently large number of operations - this is what "amortized" is
> all about.
>
> Having this in mind, the wording in 23.2.1/1:
> "A deque [...] supports constant time insert [...] at the beginning and
> the end."
>
> seems to miss the obvious wording "(amortized)" before "constant", which
> would make this wording analogous to that from 23.2.4/1.
>
> Also, the 23.1.1/12:
> "The operations in Table 68 are provided only for the containers for
> which they take constant time:"
>
> should contain the wording "(amortized)" for consistency with all the above.
>
> Is this what you mean?
>
Yes.
-Dhruv.
Dhruv
> dhru...@gmx.net (Dhruv) wrote in message news:<cf18e89.03061...@posting.google.com>...
> > It is mentioned (in the standard) that for deque and vector the
> > push_(whatever) functions should be constant time (as opposed to
> > amortized time). Now, how would one do that keeping in mind that you
> > have to provide elemental access (random access).
> >
> > -Dhruv.
>
> The standard explicitly says that vector's push_back takes amortized
> constant time:
>
> "A vector is a kind of sequence that supports random access iterators.
> In addition, it supports (amortized) constant time insert and erase
> operations at the end;" (23.2.4/1)
>
> Deque's push methods are simply constant time because it is never
> necessary to reallocate the entire sequence (as is the case with
> vector).
>
> I'm not sure what you're worried about with random access, but I'm
> guessing it has to do with reallocation after insertion.
>
> John
As Francis Glassborow said.
For elemental access to be possible, the pointers to the data (even)
need to be stored in a contiguous manner, and for that to be
reallocated, the operation will be to the order of O(N), however,
since O(N) == k*N, the 'k' for reallocating a pointer, and the 'k' for
reallocating the actual type around which deque is parameterized would
vary depending upon the sizeof(the type). Generally for types with
non-trivial ctor(s), this can be quite expensive, so their 'k' can be
substantially large. However, the operation is essential of O(N)
complexity, if the array of pointers runs out of free space.
Regards,
Dhruv.
Hans Bos
"John Potter" <jpo...@falcon.lhup.edu> wrote in message >
> You hit the play on words exactly. Deque push_back/front is NOT
> constant TIME. It does use a constant number of calls to the copy
> ctor of T. Nothing is measured in terms of time. Everything is
> measured in terms of operations on T.
>
> When sizeof(T) is large enough, deque becomes an array of pointers
> to T. It has amortized constant time growth of the array of
> pointers, but claims to have constant growth because it makes no
> copies of T. Nice tap-dance.
>
This cannot be the intention.
If this is true, then a reasonable implementation of a deque would be to
have an vector of pointers to element.
Push_front can insert a new pointer (takes O(size) time) in the vector and
call the constructor for the element (is one operation on the object).
Note that using a vector to pages of N elements instead of one element
doesn't help.
Then push_front will take size / N time every N calls,
so push_front will take O(size/N*N) = O(size) amortized time.
I checked the standard and 23/2 says:
All of the complexity requirements in this clause are stated solely in terms
of the number of operations on the contained objects. [Example: the copy
constructor of type vector <vector<int> > has linear complexity, even though
the complexity of copying each contained vector<int> is itself linear. ]
I think that what was meant here is that it is assumed that operation on
objects take constant time.
Is this another defect?
Greetings,
Hans.
Francis Glassborow
<hans...@xelion.nl> writes
>So even with the change in defect report 139, deque.insert(begin(), ...),
>deque.insert(end(), ..) and vector.insert(end(), ...) must take (non
>amortized) constant time.
And that can only be true in the sense of measuring time in terms of the
number of ctor calls. It is clearly not possible if extra memory has to
be allocated.
If the Standard asserts something that cannot be achieved it is
defective.
--
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
---
John Madsen
> In article <fbec00f5.03061...@posting.google.com>, John
> Madsen <johnmads...@hotmail.com> writes
> >Deque's push methods are simply constant time because it is never
> >necessary to reallocate the entire sequence (as is the case with
> >vector).
>
>
> Constant time in my book means the same time for every use of an
> operation. This is not the case for a deque. However it is amortised
> constant time because the cost of allocating an extra block of memory is
> shared between all the potential elements that will be stored in that
> block.
By your reasoning a constant operation could not have a conditional in
it. Deque's push_back is constant time (not amortized) because the
time it takes to perform the operation is not dependent on the number
of elements in the deque in a way that affects the asymptotic
complexity. Just because every N mod elements_per_block operations
take longer does not mean that they do not take constant time.
Vector's push_back is amortized constant time since it will need, at
times, to copy all the elements in the container. This copying is a
linear time operation. Neither vector nor deque's time requirements
have to do with the time it takes to perform memory allocation.
John
John Madsen
>
> By your reasoning a constant operation could not have a conditional in
> it. Deque's push_back is constant time (not amortized) because the
> time it takes to perform the operation is not dependent on the number
> of elements in the deque in a way that affects the asymptotic
> complexity. Just because every N mod elements_per_block operations
> take longer does not mean that they do not take constant time.
Hmm. Scratch "N mod" from the above. Not sure what I was thinking
there. The point, however, is the same. There's no need to amortize
something that's already a constant time operation.
Andy Sawyer
seen twice]
In article <t5ouaQA0...@robinton.demon.co.uk>,
on Tue, 24 Jun 2003 03:42:52 +0000 (UTC),
fra...@robinton.demon.co.uk (Francis Glassborow) wrote:
> In article <3ef4bbe2$0$49100$e4fe...@news.xs4all.nl>, Hans Bos
> <hans...@xelion.nl> writes
>
> >So even with the change in defect report 139, deque.insert(begin(), ...),
> >deque.insert(end(), ..) and vector.insert(end(), ...) must take (non
> >amortized) constant time.
>
> And that can only be true in the sense of measuring time in terms of
> the number of ctor calls.
Which is precisely what is happening:
,----[ 23.1 (lib.container.requirements), paragraph 2 ]
| 2 All of the complexity requirements in this clause are stated solely
| in terms of the number of operations on the contained objects.
`----
I think it's clear what that means.
> It is clearly not possible if extra memory has to be allocated.
Allocating memory does not, in itself, affect the complexity of the
operation. It might affect the number of clock cycles or the number or
microseconds required to complexe the operation, but it does not
affect the complexity as far as the standard is concerned.
> If the Standard asserts something that cannot be achieved it is
> defective.
I that were the case, then yes, the standard would be
defective. Perhaps you should raise a DR so that LWG can mark it NAD?
Regards,
Andy S
--
"Light thinks it travels faster than anything but it is wrong. No matter
how fast light travels it finds the darkness has always got there first,
and is waiting for it." -- Terry Pratchett, Reaper Man
---
Andy Sawyer
on Tue, 24 Jun 2003 03:42:52 +0000 (UTC),
fra...@robinton.demon.co.uk (Francis Glassborow) wrote:
> In article <3ef4bbe2$0$49100$e4fe...@news.xs4all.nl>, Hans Bos
> <hans...@xelion.nl> writes
>
> >So even with the change in defect report 139, deque.insert(begin(), ...),
> >deque.insert(end(), ..) and vector.insert(end(), ...) must take (non
> >amortized) constant time.
>
> And that can only be true in the sense of measuring time in terms of
> the number of ctor calls.
Which is precisely what is happening:
,----[ 23.1 (lib.container.requirements), paragraph 2 ]
| 2 All of the complexity requirements in this clause are stated solely
| in terms of the number of operations on the contained objects.
`----
I think it's clear what that means.
> It is clearly not possible if extra memory has to be allocated.
Allocating memory does not, in itself, affect the complexity of the
operation. It might affect the number of clock cycles or the number or
microseconds required to complexe the operation, but it does not
affect the complexity as far as the standard is concerned.
> If the Standard asserts something that cannot be achieved it is
> defective.
I that were the case, then yes, the standard would be
defective. Perhaps you should raise a DR so that LWG can mark it NAD?
Regards,
Andy S
--
"Light thinks it travels faster than anything but it is wrong. No matter
how fast light travels it finds the darkness has always got there first,
and is waiting for it." -- Terry Pratchett, Reaper Man
---
John Potter
(John Madsen) wrote:
> johnmads...@hotmail.com (John Madsen) wrote in message news:<fbec00f5.03062...@posting.google.com>...
> > By your reasoning a constant operation could not have a conditional in
> > it. Deque's push_back is constant time (not amortized) because the
> > time it takes to perform the operation is not dependent on the number
> > of elements in the deque in a way that affects the asymptotic
> > complexity. Just because every N mod elements_per_block operations
> > take longer does not mean that they do not take constant time.
> Hmm. Scratch "N mod" from the above. Not sure what I was thinking
> there. The point, however, is the same. There's no need to amortize
> something that's already a constant time operation.
Did you miss some of the other posts? Consider that an array of T* is a
valid implimentation. The only difference from vector is that when the
size of that array is doubled, the unused space is split with half at
each end of the used space. We now have either push_front or push_back
being amortized const time in number of copies of T* objects. However,
the standard does not count operations on T* objects. It only counts
operations on T objects. So we have measurable amortized constant time
and standardized fictional constant time.
Hans Bos
> valid implimentation. The only difference from vector is that when the
> size of that array is doubled, the unused space is split with half at
> each end of the used space. We now have either push_front or push_back
> being amortized const time in number of copies of T* objects. However,
> the standard does not count operations on T* objects. It only counts
> operations on T objects. So we have measurable amortized constant time
> and standardized fictional constant time.
The point is that the standard as written today doesn't require constant
time for push_front
It only requires a (amortized) constant number of calls to the (copy)
constructor.
So a valid implementation can take O(size) time (or worse).
If you require amortized constant time push_front you cannot rely on
std::deque.
Greetings,
Hans.
John Potter
Bos") wrote:
> "John Potter" <jpo...@falcon.lhup.edu> wrote in message >
> > Did you miss some of the other posts? Consider that an array of T* is a
> > valid implimentation. The only difference from vector is that when the
> > size of that array is doubled, the unused space is split with half at
> > each end of the used space. We now have either push_front or push_back
> > being amortized const time in number of copies of T* objects. However,
> > the standard does not count operations on T* objects. It only counts
> > operations on T objects. So we have measurable amortized constant time
> > and standardized fictional constant time.
> The point is that the standard as written today doesn't require constant
> time for push_front
> It only requires a (amortized) constant number of calls to the (copy)
> constructor.
It requires constant (not amortized) number of calls. Push_front or
push_back must do a constant number of copies.
> So a valid implementation can take O(size) time (or worse).
Sure. It could implement an array of pointers and increase by one for
each push producing O(N) each or O(N^2) sequence.
> If you require amortized constant time push_front you cannot rely on
> std::deque.
Right. Did you miss the point that Madsen claimed constant time is
provided? Did I misread his article or did you not read it?
John