On Wed, 26 Nov 2003 21:01:24 +0000 (UTC), do-not-spam-benh@bwsint.com
(Ben Hutchings) wrote:

> John Potter wrote:
> > On Mon, 17 Nov 2003 20:13:08 +0000 (UTC), jpearapplebanana@freeshell.org
> > (Jim Apple) wrote:
> >
> >> Everywhere I see implementations of std::deque, it uses a map/block
> >> structure.  Is there any reason why it can't be implemented as two
> >> vectors, one for the front, and one for the back?
> >
> > Insert(begin(), x) and insert(end(), x) are required to be constant time
> > making exactly one call to the copy ctor.
>
> Where the standard refers to time complexity, it really means the
> complexity of the number of operations performed on elements (23.1/2).

That is the point.  Exactly one call to the copy ctor is allowed.  No
reallocation of space containing T's is allowed.  Impossible to
implement deque with two vectors.

> > It is not allowed to reallocate and copy as vector does.

> However, it may do that with the map or some other hidden information, so
> the time complexity as normally understood is likely to be "amortised
> constant", with the worst case being linear.

Sure and when the T is large enough to produce a map of pointers to
arrays of one T, it could even be quadradic.  So what?  You still can't
implement it with two vectors.

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

do-not-spam-benh@bwsint.com (Ben Hutchings) wrote in message news:<slrnbs96o2.1r4.do-not-spam-benh@tin.bwsint.com>...
> John Potter wrote:
...
> > Insert(begin(), x) and insert(end(), x) are required to be constant time
> > making exactly one call to the copy ctor.
>
> Where the standard refers to time complexity, it really means the
> complexity of the number of operations performed on elements (23.1/2).

What he said is almost an exact quote of 23.2.1.3p3. To be exact, it
says "Inserting a single element at the beginning or end of a deque
always takes constant time and causes a single call to the copy
constructor of T".

> > It is not allowed to reallocate and copy as vector does.
>
> However, it may do that with the map or some other hidden information, so
> the time complexity as normally understood is likely to be "amortised
> constant", with the worst case being linear.

In general yes, but not when it makes more specific statements, such
as "a single call to the copy construct of T". Note also that "An
insert at either end of the deque ... has no effect on the validity of
references to elements of the deque." That's can't be done if there's
any reallocation triggered by inserting those elements. That's a hard
thing to ensure in conjunction with the other complexity requirements,
if the underlying implementation were that of using two vectors.

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

John Potter wrote:
> On Mon, 17 Nov 2003 20:13:08 +0000 (UTC), jpearapplebanana@freeshell.org
> (Jim Apple) wrote:
>
>> Everywhere I see implementations of std::deque, it uses a map/block
>> structure.  Is there any reason why it can't be implemented as two
>> vectors, one for the front, and one for the back?
>
> Insert(begin(), x) and insert(end(), x) are required to be constant time
> making exactly one call to the copy ctor.

Where the standard refers to time complexity, it really means the
complexity of the number of operations performed on elements (23.1/2).

> It is not allowed to reallocate and copy as vector does.

However, it may do that with the map or some other hidden information, so
the time complexity as normally understood is likely to be "amortised
constant", with the worst case being linear.

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

Everywhere I see implementations of std::deque, it uses a map/block
structure.  Is there any reason why it can't be implemented as two
vectors, one for the front, and one for the back?

Jim
--
to email me, use only the 'j' followed by the red fruit

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Jim Apple" <jpearapplebanana@freeshell.org> wrote in message
news:bpb9on$1s0$1@news.wplus.net...

> Everywhere I see implementations of std::deque, it uses a map/block
> structure.  Is there any reason why it can't be implemented as two
> vectors, one for the front, and one for the back?

I'm guessing that you intend the front vector to store elements in
reverse order, so that push_front has amortized constant time.
If so, that approach meets deque requirements in many cases, but
not all. What happens, for example, if you do enough pop_front
calls to empty the front vector (or enough pop_back calls to
empty the back vector)? Subsequent pops then get just as expensive
as for a vector.

Maybe there's a strategy for handling or avoiding this case, but I
suspect that it starts looking as expensive in complexity as
maintaining the traditional map of blocks.

P.J. Plauger
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://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Jim Apple" <jpearapplebanana@freeshell.org> wrote in message
news:bpb9on$1s0$1@news.wplus.net...
> Everywhere I see implementations of std::deque, it uses a map/block
> structure.  Is there any reason why it can't be implemented as two
> vectors, one for the front, and one for the back?

Because deques don't just grow out from and shrink to a center location.  You
can constantly push on the end and pop off the beginning.  Unless I'm missing
something, your two vector solution wouldn't handle that situation
efficiently.

Ken


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Mon, 17 Nov 2003 20:13:08 +0000 (UTC), jpearapplebanana@freeshell.org
(Jim Apple) wrote:

> Everywhere I see implementations of std::deque, it uses a map/block
> structure.  Is there any reason why it can't be implemented as two
> vectors, one for the front, and one for the back?

Insert(begin(), x) and insert(end(), x) are required to be constant time
making exactly one call to the copy ctor.  It is not allowed to
reallocate and copy as vector does.

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://www.jamesd.demon.co.uk/csc/faq.html                       ]