On 10/8/10 5:24 CDT, Torarin wrote:
2010/10/7 Andrei Alexandrescu<seewebsiteforem...@erdani.org>:
In the end I figured there was only _one_
quadratic operation - appending to a vector<size_t> that held document
lengths. That wasn't even the bulk of the data and it was the last thing I
looked at! Yet it made the run time impossible to endure.
From sgi's stl vector:
void push_back(const _Tp& __x) {
if (_M_finish != _M_end_of_storage) {
construct(_M_finish, __x);
++_M_finish;
}
else
_M_insert_aux(end(), __x);
}
How is this quadratic, let alone linear?
My code wasn't using push_back.
Andrei
