O(n^2) is bad - can it be fixed?

[E. Mark Ping]

In article <7ik839g8tb.fsf at enark.csis.hku.hk>,
Isaac To Kar Keung  <kkto at csis.hku.hk> wrote:
>>>>>> "E" == E Mark Ping <emarkp at CSUA.Berkeley.EDU> writes:
>
>    E> Doubtful.  It most likely does what std::list<> does--it allocates
>    E> space each time a new entry is added.  That's linear, not n^2 time.
>    E> std::vector<> uses geometric allocation to get amortized constant
>    E> allocation time.
>
>That's impossible.  If allocation is done everytime, just the copying that
>would be needed will cost quadratic time.  Do read the manual.  There is
>something called the "capacity" of a vector, which can be larger than the
>"size" of a vector.  The capacity is the minimum size of the vector to which
>the vector need to grow to, before the next time new space is allocated.

Note please that I was writing about list, not vector when an entry is
added.  I clearly stated that vector uses a geometric algorithm (like
doubling capacity when existing capacity is exhausted).
-- 
Mark Ping                     
emarkp at soda.CSUA.Berkeley.EDU