bradds@concentric.net (Bradd W. Szonye) writes:

|>  Actually, the requirement that adding characters to the end of a string or
|>  vector takes "constant amortized time" [...]

Where does it say this in the draft.  There is a complexity requirement
on vector, but the only one I could find for string was for swap.

--
James Kanze         home:     kanze@gabi-soft.fr        +33 (0)3 88 14 49 00
                    office:   kanze@vx.cit.alcatel.fr   +33 (0)1 69 63 14 54
GABI Software, Sarl., 8 rue des Francs Bourgeois, F-67000 Strasbourg, France
       -- Conseils en informatique industrielle --


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Philip Gruebele <philipg@bayarea.net> wrote in article
<01bbd4c0$0d8bdda0$7f40dbcd@philipg>...
> I think that the following function is very important to add to the
string
> class: A size_by() function which allows the user to set the amount that
> the internal array is grown each time the string needs to expand beyond
the
> currently allocated internal array.  This can be very important to make
> incremental string creation of large strings much faster.   Currently
there
> appears to be no way of settings this.  One implementation could grow the
> array a single character at a time while another grows the array
> exponentially.  The 2 implementations would have completely different
> performance characteristics which would be outside of the control of the
> user.

Actually, the requirement that adding characters to the end of a string or
vector takes "constant amortized time" implies that the allocation
increases are exponential. Increasing the allocated size by a constant
amount each time leads to N-squared time complexity. The trouble with a
size_by() function is that it would be difficult to define it so that it
takes an integral argument yet still allocates in constant amortized time.
One way around it would be to increase the size-by amount on each
allocation, but then it would be out of the hands of the users again
anyway. Whether the resize factor is x1.5, x2, or more is
implementation-defined, but what matters it that it is an exponential
increase. If the final size is known, then reserve() is the correct
function to call. Also keep in mind that if all allocation occurs during
explicit reserve() calls, the behavior is the same as having a size_by()
function.
--
Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~bradds


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Philip Gruebele <philipg@bayarea.net> wrote in article
<01bbd4c0$0d8bdda0$7f40dbcd@philipg>...
> I think that the following function is very important to add to the string
> class: A size_by() function which allows the user to set the amount that
> the internal array is grown each time the string needs to expand beyond the
> currently allocated internal array.  This can be very important to make
> incremental string creation of large strings much faster.   Currently there
> appears to be no way of settings this.  One implementation could grow the
> array a single character at a time while another grows the array
> exponentially.  The 2 implementations would have completely different
> performance characteristics which would be outside of the control of the
> user.

Actually, the requirement that adding characters to the end of a string or
vector takes "constant amortized time" implies that the allocation
increases are exponential. Increasing the allocated size by a constant
amount each time leads to N-squared time complexity. The trouble with a
size_by() function is that it would be difficult to define it so that it
takes an integral argument yet still allocates in constant amortized time.
One way around it would be to increase the size-by amount on each
allocation, but then it would be out of the hands of the users again
anyway. Whether the resize factor is x1.5, x2, or more is
implementation-defined, but what matters it that it is an exponential
increase. If the final size is known, then reserve() is the correct
function to call. Also keep in mind that if all allocation occurs during
explicit reserve() calls, the behavior is the same as having a size_by()
function.
--
Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~bradds
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

I think that the following function is very important to add to the string
class: A size_by() function which allows the user to set the amount that
the internal array is grown each time the string needs to expand beyond the
currently allocated internal array.  This can be very important to make
incremental string creation of large strings much faster.   Currently there
appears to be no way of settings this.  One implementation could grow the
array a single character at a time while another grows the array
exponentially.  The 2 implementations would have completely different
performance characteristics which would be outside of the control of the
user.

Regards

Philip Gruebele
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]