Quick A: In C++11 it's required to be constant time.
Recently on SO:
In C++11 it is required that for any standard container the
.size()operation must be complete in "constant" complexity (O(1)). (Table 96 — Container requirements). Previously in C++03
.size()should have constant complexity, but is not required (see Is
std::string size()a O(1) operation?).
The change in standard is introduced by n2923: Specifying the complexity of size() (Revision 1).