Scott Meyers wrote:

> Table 68 says that the operational semantics of a call to push_front on a
> sequence is the same as inserting at the beginning of the sequence.  This
> makes sense.  However, 23.2.1.3 says this about the complexity of insert
> into a deque:
>
>   Inserting a single element either at the beginning or end of a deque
>   always takes constant time and causes a single call to the copy
>   constructor of T.
>
> >From my understanding of how deques are implemented, I don't see how this
> can be.  In the worst case, inserting a new element at the beginning of a
> deque may require moving n pointers, where n is linear in the size of the
> deque.
>
> Austern's book says that the complexity guarantee for push_front in a
> sequence is amortized constant time.  That seems more reasonable to me.  Is
> this a defect in the standard (failure to say *amortized* constant time) or
> a defect in my understanding?  (My money's on the latter, but you never
> know -- sometimes you get lucky.)

Insertions and deletions at either the front or back of a deque are in O( 1 )
(constant) time.

Consider a deque implemented as a doubly linked list with a head sentinel node
and a tail sentinel node.

To insert at front of the list,  will only have to change where the current
first in list Node is pointing to the new node to be inserted (instead of the
head) and make the head point to the new Node,  as well as pointing the new
Node to the head and previous first in list.

Insert_last is similar.

These operation is in in constant time as it does not matter how many elements
in deque/list

Mark

--
_____________________________________________

Mark Cowan
Newcastle Australia
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 27 Dec 99 09:48:32 GMT, Mark Cowan
<mark.cowan@studentmail.newcastle.edu.au> wrote:

: Scott Meyers wrote:
:
: > Table 68 says that the operational semantics of a call to push_front on a
: > sequence is the same as inserting at the beginning of the sequence.  This
: > makes sense.  However, 23.2.1.3 says this about the complexity of insert
: > into a deque:
: >
: >   Inserting a single element either at the beginning or end of a deque
: >   always takes constant time and causes a single call to the copy
: >   constructor of T.
: >
: > >From my understanding of how deques are implemented, I don't see how this
: > can be.  In the worst case, inserting a new element at the beginning of a
: > deque may require moving n pointers, where n is linear in the size of the
: > deque.
: >
: > Austern's book says that the complexity guarantee for push_front in a
: > sequence is amortized constant time.  That seems more reasonable to me.  Is
: > this a defect in the standard (failure to say *amortized* constant time) or
: > a defect in my understanding?  (My money's on the latter, but you never
: > know -- sometimes you get lucky.)
:
: Insertions and deletions at either the front or back of a deque are in O( 1 )
: (constant) time.
:
: Consider a deque implemented as a doubly linked list with a head sentinel node
: and a tail sentinel node.

You are confusing the adt deque with std::deque.  Std::deque can not be
implemented as a doubly linked list.  It is a random access container.

Scott's point is that if the left most array is full, the push_front
will involve either shifting the array pointers right to make room
for another array or allocating another array of pointers and copying
to it.  In either case, the amount of copying of pointers is linear
in the size of the deque.  Only one T copy ctor is needed, but that
is not all that is happening.

John


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

John Potter wrote:
....
> : Scott Meyers wrote:
> :
> : > Table 68 says that the operational semantics of a call to push_front on a
> : > sequence is the same as inserting at the beginning of the sequence.  This
> : > makes sense.  However, 23.2.1.3 says this about the complexity of insert
> : > into a deque:
> : >
> : >   Inserting a single element either at the beginning or end of a deque
> : >   always takes constant time and causes a single call to the copy
                     ^^^^^^^^^^^^^
> : >   constructor of T.
....
> You are confusing the adt deque with std::deque.  Std::deque can not be
> implemented as a doubly linked list.  It is a random access container.
>
> Scott's point is that if the left most array is full, the push_front
> will involve either shifting the array pointers right to make room
> for another array or allocating another array of pointers and copying
> to it.  In either case, the amount of copying of pointers is linear
> in the size of the deque.  Only one T copy ctor is needed, but that
> is not all that is happening.

That's not a conforming implementation of std:deque<>. There are two
guarantees: not just a single copy constructor call, but also constant
time. That implementation would violate the second guarantee.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote in message <386804BF.B3811D46@wizard.net>...
>That's not a conforming implementation of std:deque<>. There are two
>guarantees: not just a single copy constructor call, but also constant
>time. That implementation would violate the second guarantee.

Given the addional requirement of constant time random access, is a
conforming implementation possible at all?

- Anders

PS: The Rogue Wave implementation with BCB4 seems to work like Scott
assumed.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <386804BF.B3811D46@wizard.net>, James Kuyper
<kuyper@wizard.net> wrote:

> John Potter wrote:
> ....
> > : Scott Meyers wrote:
> > :
> > : > Table 68 says that the operational semantics of a call to
push_front on a
> > : > sequence is the same as inserting at the beginning of the
sequence.  This
> > : > makes sense.  However, 23.2.1.3 says this about the complexity of insert
> > : > into a deque:
> > : >
> > : >   Inserting a single element either at the beginning or end of a deque
> > : >   always takes constant time and causes a single call to the copy
>                      ^^^^^^^^^^^^^
> > : >   constructor of T.
> ....
> > You are confusing the adt deque with std::deque.  Std::deque can not be
> > implemented as a doubly linked list.  It is a random access container.
> >
> > Scott's point is that if the left most array is full, the push_front
> > will involve either shifting the array pointers right to make room
> > for another array or allocating another array of pointers and copying
> > to it.  In either case, the amount of copying of pointers is linear
> > in the size of the deque.  Only one T copy ctor is needed, but that
> > is not all that is happening.
>
> That's not a conforming implementation of std:deque<>. There are two
> guarantees: not just a single copy constructor call, but also constant
> time. That implementation would violate the second guarantee.

Perhaps.  But then there are no standard conforming implementations of
std::deque.  I believe that the lack of "amortized" in the complexity
statement is a defect in the standard, not a defect in every
implementation I'm aware of.

-Howard
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote in message <386804BF.B3811D46@wizard.net>...
>That's not a conforming implementation of std:deque<>. There are two
>guarantees: not just a single copy constructor call, but also constant
>time. That implementation would violate the second guarantee.

So is there any known way to implement deque so that it meets its
guarantees?  If so, what is it?

Please ignore solutions where max_size() is treated as a constant.  You can
certainly implement deque as a circular array of max_size() elements, but
that is not a very satisfactory solution.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 28 Dec 1999 05:12:19 GMT, James Kuyper wrote:
>
> John Potter wrote:
> ....
> > : Scott Meyers wrote:
> > :
> > : > Table 68 says that the operational semantics of a call to push_front on a
> > : > sequence is the same as inserting at the beginning of the sequence.  This
> > : > makes sense.  However, 23.2.1.3 says this about the complexity of insert
> > : > into a deque:
> > : >
> > : >   Inserting a single element either at the beginning or end of a deque
> > : >   always takes constant time and causes a single call to the copy
>                      ^^^^^^^^^^^^^
> > : >   constructor of T.
> ....
> > Scott's point is that if the left most array is full, the push_front
> > will involve either shifting the array pointers right to make room
> > for another array or allocating another array of pointers and copying
> > to it.  In either case, the amount of copying of pointers is linear
> > in the size of the deque.  Only one T copy ctor is needed, but that
> > is not all that is happening.
>
> That's not a conforming implementation of std:deque<>. There are two
> guarantees: not just a single copy constructor call, but also constant
> time. That implementation would violate the second guarantee.

Ah, recursion!  That was the point of my original post (above).  I suspect
the guarantee is incorrect.  See above.

Scott

--
Scott Meyers, Ph.D.                  smeyers@aristeia.com
Software Development Consultant      http://www.aristeia.com/
Visit http://meyerscd.awl.com/ to demo the Effective C++ CD
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Bill Wade wrote:
>
> James Kuyper wrote in message <386804BF.B3811D46@wizard.net>...
> >That's not a conforming implementation of std:deque<>. There are two
> >guarantees: not just a single copy constructor call, but also constant
> >time. That implementation would violate the second guarantee.
>
> So is there any known way to implement deque so that it meets its
> guarantees?  If so, what is it?
>
> Please ignore solutions where max_size() is treated as a constant.  You can
> certainly implement deque as a circular array of max_size() elements, but
> that is not a very satisfactory solution.

I want to emphasize that what Scott Meyers was originally asking about
is whether the constant time guarantee was a mistake; I've no strong
opinion about that subject. I'm only talking about what the requirement
actually is; not whether it's desirable to have it.

That said, I do think it's feasible to meet it. Here's my concept:

deque<>::_block objects contain a pointer to a memory block and a
blocksize, which will be non-zero iff the pointer points to a currently
allocated block of that size.

deque<>::iterator objects will contain a _block pointer, and an offset
within the block. The _blocks will be contiguous, and the memory blocks
they contain will represent portions of the deque<> that are in the same
order as the _blocks themselves. Therefore, iterating past the end of a
memory block involves incrementing the _block pointer, and setting the
offset to zero; iterating before the beginning of a block involves
decrementing the _block pointer, and setting the offset to blocksize-1.

deque<> will contain an array of _blocks, and an iterator range
bracketing the current elements of the deque<>.  There are two key
features that make it possible to meet the complexity requirements:
1. The number of elements in the _block array is fixed, so they never
need to be moved. Only the sizes of the memory blocks they manage
changes.
2. For every entry in the _block array, its blocksize will either be
zero, if the entry is not in use, or a value determined uniquely by its
position in the array if it is in use. There are at least two ways to do
this that work:
a) blocksize is constant. This is the simpler form.
b) The _block in the middle of the table has a blocksize of N; as you
move away from the middle by one element in each direction, the
blocksize doubles. This one wastes less space for small size(). For best
results, the deque<> should be re-centered whenever the standard's
complexity and iterator/reference invalidation specifications allow.

Given a deque<>::iterator 'p' and an arbitrary valid
deque<>::difference_type 'i', you must be able to calculate the _block
pointer and offset for 'p+i' in constant time. That's possible with both
of the blocksize patterns described above, though it's more complicated
for 2b than 2a. The critical part of 2b requires calculation of the
integral part of the logarithm base 2 of an integer n, which can be done
in time that actually decreases for large n. The inverse operation 'p-q'
is also constant time.

deque<>::operator[difference_type i] then simply returns begin()+i,
thereby also becoming constant time.

insert() of a single element at either end of the range requires a
single copy construction, preceded by at most the allocation of a single
new memory block, with no moving of the pointers for any other memory
blocks.

I've not actually tried to implement this, so it may have serious flaws
that I haven't noticed yet.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote in message <386ADDE3.9AAB43A@wizard.net>...

>That said, I do think it's feasible to meet it. Here's my concept:

> [ Concept (a): Fixed size array of pointers to fixed size blocks]
> [ Concept (b): Fixed size array of pointers to variable size
(N*powerof(2)) blocks]

Either concept can be made workable for any reasonable problem, but they
both rely heavily on the max_size concept.  Strictly speaking, just about
anything is O(1) if you get to throw in max_size (I can bubble-sort any
array in O(max_size*max_size) time, but since max_size is a constant, so is
max_size*max_size and O(constant) is O(1)).

For concept (a), on a system with 64-bit pointers (max_size of 1<<64) a
deque<char> with size(1) occupys at least 1<<32 bytes of space.  Of course
you could add more layers of indirection, bringing the wasted space down
rapidly.  However you are just taking advantage of the fact that
N*pow(big_number, 1./N) gets small very rapidly as N gets larger.

For concept (b), the fixed size array has only O(log(max_size)) elements,
and I do believe you can probably implement it so that the allocated space
is never more than a few times the largest size() the deque ever had (in
some cases you'd probably want to treat a large block as-if it were much
smaller).

In computer science it is conventional to "cheat" in these complexity
arguments.  We say that integers and pointers are fixed size and operations
(such as addition) occur in constant time.  Of course any counter or pointer
needs to have a size of at least O(log(N)).  We justify this cheating by
saying that our hardware can increment a 64 bit number about as fast as it
can do anything, and we know that max_size is always less than 1<<64.
Another argument is that C++ defines things like pointers to have a fixed
size.  Conventionally we don't let you cheat when talking about data
structures.  For all practical purposes I can't tell the difference if you
start using 29 bits in your integers when previously you were using 17.
However if your std::map changes its depth from 17 to 29 I can almost
certainly notice map::find() starting to take longer.

So for any practical purposes you've got the makings of a strategy that
provides O(1) deque::push_back().  But big-O arguments aren't about
practice, they are about theory.  Since your strategy only works for some
fixed max_size, we just say "that's cheating."
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Bill Wade wrote:
>
> James Kuyper wrote in message <386ADDE3.9AAB43A@wizard.net>...
>
> >That said, I do think it's feasible to meet it. Here's my concept:
>
> > [ Concept (a): Fixed size array of pointers to fixed size blocks]
> > [ Concept (b): Fixed size array of pointers to variable size
> (N*powerof(2)) blocks]
>
> Either concept can be made workable for any reasonable problem, but they
> both rely heavily on the max_size concept.  Strictly speaking, just about
> anything is O(1) if you get to throw in max_size (I can bubble-sort any
> array in O(max_size*max_size) time, but since max_size is a constant, so is
> max_size*max_size and O(constant) is O(1)).
>

O(whatever) refers to the number of objects that are being handled by
the algorithm, not to some arbitrary value. If you double the number of
objects that you're bubble sorting you quadruple the number of
operations needed, so bubble sort is O(n^2).

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Table 68 says that the operational semantics of a call to push_front on a
sequence is the same as inserting at the beginning of the sequence.  This
makes sense.  However, 23.2.1.3 says this about the complexity of insert
into a deque:

  Inserting a single element either at the beginning or end of a deque
  always takes constant time and causes a single call to the copy
  constructor of T.

>From my understanding of how deques are implemented, I don't see how this
can be.  In the worst case, inserting a new element at the beginning of a
deque may require moving n pointers, where n is linear in the size of the
deque.

Austern's book says that the complexity guarantee for push_front in a
sequence is amortized constant time.  That seems more reasonable to me.  Is
this a defect in the standard (failure to say *amortized* constant time) or
a defect in my understanding?  (My money's on the latter, but you never
know -- sometimes you get lucky.)

Thanks,

Scott

--
Scott Meyers, Ph.D.                  smeyers@aristeia.com
Software Development Consultant      http://www.aristeia.com/
Visit http://meyerscd.awl.com/ to demo the Effective C++ CD
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]