Quick A: In C++11 it's required to be constant time.

Recently on SO:

Is list::size() really O(n)?

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).