| > > It turns out that vector could really profit from being
| > > implemented as a circular buffer stored in an array.
| >
| > In what way?
|
| A circular array is just an array where the position
| just before element 0 is element (size()-1) and
| symmetrically the element just after the last one (at
| size()-1) is the first one.
|
| In a circular array, front and back are symmetric and
| equivalent. Thus a circular array provides O(1)
| push_front/pop_front/push_back/pop_back.

Of course, all of these are "O(1) amortized cost" assuming a
multiplicative growth strategy.

This, not STL deque, is the natural underlying data structure for
building stacks and queues.  (STL deque's cheaper random-insert-or-
delete isn't needed and just adds overhead.)

You also get O(1) random access.  A less obvious - but often useful -
operation is O(1) random-delete *which doesn't preserve ordering*:
Swap the element to be deleted with either the first or last element,
then pop the appropriate end.  Handy for small sets (e.g., the buckets
in a hash table).
       -- Jerry
---
[ 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:

> : Thus a circular array provides O(1)
> : push_front/pop_front/push_back/pop_back.
>
> Maybe.  When the array is full push is not O(1), but it could be
> amortized by the growth strategy.

<VID MODE="Big O notation bashing">
But then non const string::begin is not O(1) either
when the string is shared, a string is a Container,
and Container requirements in 23.1/5, table
number ?? says :

a.begin();  constant

(no mention of amortized here)
</DIV>

> : When you mean deque say deque !
>
> That seems impossible.
>
> Deque: A cronologically ordered ...
> Deque: An ADT sequence which supports ...
> Deque: An implementation of the std::deque<> with all of its
> requirements.
>
> Deque is a meaningless term to me without qualification.

I hope that you understoud deque = the standard deque,
ie std::deque.

--

Valentin Bonnard


[ 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              ]

Jim Barry wrote:

> P.J. Plauger <pjp@plauger.com> wrote...

> > It turns out that vector could really profit from being
> > implemented as a circular buffer stored in an array.
>
> In what way?

A circular array is just an array where the position
just before element 0 is element (size()-1) and
symmetrically the element just after the last one (at
size()-1) is the first one.

In a circular array, front and back are symmetric and
equivalent. Thus a circular array provides O(1)
push_front/pop_front/push_back/pop_back.

When you mean deque say deque !

--

Valentin Bonnard
---
[ 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 02 Aug 99 20:55:45 GMT, Valentin Bonnard <Bonnard.V@wanadoo.fr>
wrote:

: A circular array is just an array where the position
: just before element 0 is element (size()-1) and
: symmetrically the element just after the last one (at
: size()-1) is the first one.

yes

: In a circular array, front and back are symmetric and
: equivalent.

Equivalent in complexity but not in effect with regards to front/back.

: Thus a circular array provides O(1)
: push_front/pop_front/push_back/pop_back.

Maybe.  When the array is full push is not O(1), but it could be
amortized by the growth strategy.

: When you mean deque say deque !

That seems impossible.

Deque: A cronologically ordered collection with interface add_youngest,
remove_youngest, and remove_oldest.  Note the absence of add_oldest
which is absurd.  It may be implemented by adding each item with a
time stamp and performing a random shuffle and using exhaustive
search for both remove operations.  There may exist more efficient
methods. :)  As abstractions, stack and queue are cronological and
a double ended queue seems to fit in that abstraction.

Deque: An ADT sequence which supports the above four operations.  As
you note, front and back are interchangable which is not the case in
the cronological deque.

Deque: An implementation of the std::deque<> with all of its
requirements.

Deque is a meaningless term to me without qualification.

Yes, a circular array is a nice implementation for either of the
first two, but I do not see it as an improvement to std::vector<>
which does not require push/pop_front.  std::deque<> is also an
overkill for these two because random access is not a requirement.

We can't have everything in the standard library.  I like knowing
what the requirements are for those things which are included.  If
they do not meet my needs, I can produce something which does.
There are no std::algorithms which work on std::stack, but it is
still useful.

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              ]