Is std::vector::size() allowed to require non-trivial computations? When would it make sense?

Question

I'm reviewing a piece of code and see a class where an std::vector is stored as a member variable and the size of that std::vector is stored as a separate member variable. Both std::vector and its "stored copy" of size are never change during the containing object lifetime and the comments say size is stored separately "for convenience and for cases when an implementation computes the size each time".

My first reaction was "WT*? Should't it be always trivial to extract std::vectors size?"

Now I've carefully read 23.2.4 of C++ Standard and can't see anything saying whether such implementations are allowed in the first place and I can't imagine why it would be necessary to implement std::vector in such way that its current size needs non-trivial computations.

Is such implementation that std::vector::size() requires some non-trivial actions allowed? When would having such implementation make sense?

Answer 1

C++03 says in Table 65, found in §23.1, that size() should have a constant complexity. (In C++0x, this is required for all containers.) You'd be hard-pressed to find a std::vector<> where it's not.

Typically, as Steve says, this is just the difference between two pointers, a simple operation.