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

[E. Mark Ping]

In article <3B09FBF9.8691EBFE at accessone.com>,
Helen Dawson  <helend at accessone.com> wrote:
>List does much better. Why? It probably does the same thing that the
>STL vector typically does - the allocabe space doubles whenever it
>runs out of room, and then the newly allocated space is filled in
>as needed.

Doubtful.  It most likely does what std::list<> does--it allocates
space each time a new entry is added.  That's linear, not n^2 time.
std::vector<> uses geometric allocation to get amortized constant
allocation time.

If you need to add on character at a time, choose the data structure
that does what you want.  Perhaps a list of char?
-- 
Mark Ping                     
emarkp at soda.CSUA.Berkeley.EDU