"in" everywhere

[Torarin]

2010/10/7 Andrei Alexandrescu <SeeWebsiteForEmail at 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?