Concerning linear complexity, what would be the references in the standard to back this up? I am unable to find any, which leads me to believe it could be implementation defined (one could imagine scenarios with primitive types where the behaviour need not be linear).

It was defined linear in C++03 (Table 67 Sequence requirements in 23.1.1[lib.sequence.reqmts]/4 defines clear() in terms of erase(), and erase() has a complexity clause for vectors in[lib.vector.modifiers]/2 that states "Complexity: The destructor of T is called the number of times equal to the number of the elements erased"). In C++11, clear() is no longer defined in terms of erase() for sequence containers, we could make a note (this is LWG 2231) --Cubbi 19:05, 19 February 2013 (PST)
That makes sense, as I was using the C++11 standard as reference. I think a note could be quite usefil. --Juanchopanza 09:46, 20 February 2013 (PST)