"James Kuyper Jr." wrote:

> See section 23.2.4.3p2: "... If [first and last] are input iterators,
> the complexity is proportional to the number of elements in the range
> [first, last) times the distance to the end of the vector."
>
> I have to admit that I don't understand where the multiplication comes
> from. To insert N items at a point which is M positions from the end of
> the vector would seem to require 2N+M copies and a comparable amortized
> cost in reallocations by use of the following algorithm:
>
It looks like the standard allows you to implement insert via iterators
using successive single inserts.  Not the most efficient behavior imaginable.

---
[ 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.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." wrote:
>
> See section 23.2.4.3p2: "... If [first and last] are input iterators,
> the complexity is proportional to the number of elements in the range
> [first, last) times the distance to the end of the vector."
>
> I have to admit that I don't understand where the multiplication comes
> from. To insert N items at a point which is M positions from the end of
> the vector would seem to require 2N+M copies and a comparable amortized
> cost in reallocations by use of the following algorithm:
>

With input iterators you don't know what N is. Unless you're willing to
allocate separate storage to hold a copy of the input range, you're
stuck with element by element insertion.

--
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://www.research.att.com/~austern/csc/faq.html                ]

Pete Becker wrote:
>
> "James Kuyper Jr." wrote:
> >
> > See section 23.2.4.3p2: "... If [first and last] are input iterators,
> > the complexity is proportional to the number of elements in the range
> > [first, last) times the distance to the end of the vector."
> >
> > I have to admit that I don't understand where the multiplication comes
> > from. To insert N items at a point which is M positions from the end of
> > the vector would seem to require 2N+M copies and a comparable amortized
> > cost in reallocations by use of the following algorithm:
> >
>
> With input iterators you don't know what N is. Unless you're willing to
> allocate separate storage to hold a copy of the input range, you're
> stuck with element by element insertion.

The algorithm I gave neither required knowledge of what N is, nor did it
require element by element insertion. It may be an incorrect
implementation, but if so, could you explain what was wrong with it?

---
[ 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.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." wrote:
>
> Pete Becker wrote:
> >
> > "James Kuyper Jr." wrote:
> > >
> > > See section 23.2.4.3p2: "... If [first and last] are input iterators,
> > > the complexity is proportional to the number of elements in the range
> > > [first, last) times the distance to the end of the vector."
> > >
> > > I have to admit that I don't understand where the multiplication comes
> > > from. To insert N items at a point which is M positions from the end of
> > > the vector would seem to require 2N+M copies and a comparable amortized
> > > cost in reallocations by use of the following algorithm:
> > >
> >
> > With input iterators you don't know what N is. Unless you're willing to
> > allocate separate storage to hold a copy of the input range, you're
> > stuck with element by element insertion.
>
> The algorithm I gave neither required knowledge of what N is, nor did it
> require element by element insertion. It may be an incorrect
> implementation, but if so, could you explain what was wrong with it?
>

It allocates separate storage to hold a copy of the input range. That's
not necessarily wrong or incorrect, but it's a different resource
tradeoff.

--
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://www.research.att.com/~austern/csc/faq.html                ]

James Dennett wrote:
>
> Peter Schmitteckert wrote:
...
> > Therefore I'd like to suggest a new container _seque<>_,
> > a _single_ende_queue_ that behaves like vector<>, with the
> > difference that the elements of vector<> are garanteed to be consecutive
> > in memory, while the elements of seque could have a more advanced
> > memory management.
>
> Why not use std::deque?  It seems to have the semantics that you
> want for seque.

Please note that std::deque<> and std::vector<> have different
requirements on the complexity of some operations, and have different
rules governing the invalidation of iterators, pointers and references.
Those differences are not all in std::deque<>'s favor - for some
applications std::vector<> is preferable to std::deque<>. A
non-contiguous vector<> can be implemented to meet all of those
requirements.

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Francis Glassborow wrote:

>[...]

> What is wrong with using a deque?
>

James Dennett wrote:
[...]
>
> Why not use std::deque?  It seems to have the semantics that you
> want for seque.

Sorry, I even don't know myself.
deque<> is fine. I had a knot in my brain thinking that deque should have
more overhead.
I apologize for disturbing you,
best whishes
Peter

_________________________________________
Beware of the day
if your snark be a boojum
(Lewis Carrol)

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Salut,

concerning the implementation of vector<> I have mixed feelings.

On one hand I would like to be sure that member are stored in a single
memory block, which allows me to take advantage of that if I need,
or it simplifies inter-language operability.

On the other hand I'd like vector<> to hande really large vectors
without reallocating a single big memory block just for enlarging
the vector. So a list of memory blocks would be more appropriate.

Therefore I'd like to suggest a new container _seque<>_,
a _single_ende_queue_ that behaves like vector<>, with the
difference that the elements of vector<> are garanteed to be consecutive
in memory, while the elements of seque could have a more advanced
memory management.

Best wishes,
Peter
_________________________________________
Beware of the day
if your snark be a boojum
(Lewis Carrol)

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <987ua4$pin$06$1@news.t-online.com>, Peter Schmitteckert
<peter-NOSPAM@schmitteckert.org> writes
>Therefore I'd like to suggest a new container _seque<>_,
>a _single_ende_queue_ that behaves like vector<>, with the
>difference that the elements of vector<> are garanteed to be consecutive
>in memory, while the elements of seque could have a more advanced
>memory management.

What is wrong with using a deque?

--
Francis Glassborow
See http://www.accu.org for details of The ACCU Spring Conference, 2001
(includes many regular participants to C & C++ newsgroups)

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Peter Schmitteckert wrote:
>
> Salut,
>
> concerning the implementation of vector<> I have mixed feelings.
>
> On one hand I would like to be sure that member are stored in a single
> memory block, which allows me to take advantage of that if I need,
> or it simplifies inter-language operability.
>
> On the other hand I'd like vector<> to hande really large vectors
> without reallocating a single big memory block just for enlarging
> the vector. So a list of memory blocks would be more appropriate.
>
> Therefore I'd like to suggest a new container _seque<>_,
> a _single_ende_queue_ that behaves like vector<>, with the
> difference that the elements of vector<> are garanteed to be consecutive
> in memory, while the elements of seque could have a more advanced
> memory management.

Why not use std::deque?  It seems to have the semantics that you
want for seque.

-- James Dennett

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Dear James Kuyper,

James Kuyper Jr. wrote:

[...]
> Please note that std::deque<> and std::vector<> have different
> requirements on the complexity of some operations, and have different
> rules governing the invalidation of iterators, pointers and references.
> Those differences are not all in std::deque<>'s favor - for some
> applications std::vector<> is preferable to std::deque<>. A
> non-contiguous vector<> can be implemented to meet all of those
> requirements.
Uups, I just looked up in my Stroustrup 4th edition, and found that the
complexity of operation at the end of an container is
constant+ for vector<>
constant for deque<>

(chapter  17.1.2, p494 german edition)
is this right ? vector<> could be more expensive the deque<>

Best wishes,
Peter

_________________________________________
Beware of the day
if your snark be a boojum
(Lewis Carrol)

---
[ 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.research.att.com/~austern/csc/faq.html                ]

Peter Schmitteckert wrote:
>
> Dear James Kuyper,
>
> James Kuyper Jr. wrote:
>
> [...]
> > Please note that std::deque<> and std::vector<> have different
> > requirements on the complexity of some operations, and have different
> > rules governing the invalidation of iterators, pointers and references.
> > Those differences are not all in std::deque<>'s favor - for some
> > applications std::vector<> is preferable to std::deque<>. A
> > non-contiguous vector<> can be implemented to meet all of those
> > requirements.
> Uups, I just looked up in my Stroustrup 4th edition, and found that the
> complexity of operation at the end of an container is
> constant+ for vector<>
> constant for deque<>
>
> (chapter  17.1.2, p494 german edition)
> is this right ? vector<> could be more expensive the deque<>

Inserts into a vector from a pure input_iterator can be a LOT more
expensive than for deque<>. The complexity is proportion to the number
of items inserted TIMES the number of items originally in the vector<>
after the insertion point. This implies an algorithm that moves all of
the items after each insert.

---
[ 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.research.att.com/~austern/csc/faq.html                ]

Tue, 13 Mar 2001 15:20:25 GMT, James Kuyper Jr. <kuyper@wizard.net> pisze=
:

> Inserts into a vector from a pure input_iterator can be a LOT more
> expensive than for deque<>. The complexity is proportion to the number
> of items inserted TIMES the number of items originally in the vector<>
> after the insertion point.

This is false. Insertion into a vector should physically resize it
on overflow by a constant factor instead of by a constant amount.
This gives amortized O(1) insertion time.

--=20
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZAST=CAPCZA
QRCZAK

---
[ 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.research.att.com/~austern/csc/faq.html                ]

Marcin 'Qrczak' Kowalczyk wrote:
>
> Tue, 13 Mar 2001 15:20:25 GMT, James Kuyper Jr. <kuyper@wizard.net> pisze:
>
> > Inserts into a vector from a pure input_iterator can be a LOT more
> > expensive than for deque<>. The complexity is proportion to the number
> > of items inserted TIMES the number of items originally in the vector<>
> > after the insertion point.
>
> This is false. Insertion into a vector should physically resize it
> on overflow by a constant factor instead of by a constant amount.
> This gives amortized O(1) insertion time.
>
No.  It's only constant time at the end.  If you insert or delete
eleswhere, it is linear time (i.e., in proportion to the number
of elements as Mr. Kuyper stated).  If you're not adding/erasing
from the end, you need to shuffle all the elements after the one
you're operating on.

---
[ 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.research.att.com/~austern/csc/faq.html                ]

Marcin 'Qrczak' Kowalczyk wrote:
>
> Tue, 13 Mar 2001 15:20:25 GMT, James Kuyper Jr. <kuyper@wizard.net> pisze:
>
> > Inserts into a vector from a pure input_iterator can be a LOT more
> > expensive than for deque<>. The complexity is proportion to the number
> > of items inserted TIMES the number of items originally in the vector<>
> > after the insertion point.
>
> This is false. Insertion into a vector should physically resize it
> on overflow by a constant factor instead of by a constant amount.
> This gives amortized O(1) insertion time.

See section 23.2.4.3p2: "... If [first and last] are input iterators,
the complexity is proportional to the number of elements in the range
[first, last) times the distance to the end of the vector."

I have to admit that I don't understand where the multiplication comes
from. To insert N items at a point which is M positions from the end of
the vector would seem to require 2N+M copies and a comparable amortized
cost in reallocations by use of the following algorithm:

// Reserved names used, since this would be part of <vector>
template <class _iterator_category, class _Iterator>
void _insert
(iterator _position, _Iterator _first, _Iterator _last)
{
 // normal algorithm.
}

template <class _InputIterator>
void _insert<input_iterator_tag, _InputIterator>
(iterator position, _InputIterator _first, _InputIterator _last)
{
 Vector _a(_first, _last);
 insert(_position, _a.begin(), _a.end());
}

template <class _Iterator>
void insert
(iterator _position, _Iterator _first, _Iterator _last)
{
 _insert<iterator_traits<_Iterator>::iterator_category>
  (_position, _first, _last);
}

So I must be missing something.

---
[ 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.research.att.com/~austern/csc/faq.html                ]

qrczak@knm.org.pl (Marcin 'Qrczak' Kowalczyk) wrote in comp.std.c++:

>Tue, 13 Mar 2001 15:20:25 GMT, James Kuyper Jr. <kuyper@wizard.net> pisze:
>
>> Inserts into a vector from a pure input_iterator can be a LOT more
>> expensive than for deque<>. The complexity is proportion to the number
>> of items inserted TIMES the number of items originally in the vector<>
>> after the insertion point.
>
>This is false. Insertion into a vector should physically resize it
>on overflow by a constant factor instead of by a constant amount.
>This gives amortized O(1) insertion time.

I think James is referring to the contiguity of a vector.

--
Chris Kuan, CSC (Australia)
Concatenate for email: mr gazpacho @ hotmail . com

"Law is a repository for the aimlessly clever" - Tim Freedman

---
[ 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.research.att.com/~austern/csc/faq.html                ]