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

[Isaac To Kar Keung]

>>>>> "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.

Regards,
Isaac.