Is std :: vector :: size () allowed to require nontrivial calculations? When will it make sense?

Question

I look at a code snippet and see a class where std::vector is stored as a member variable, and the size of this std::vector stored as a separate member variable. Both std::vector and its "saved copy" of the size never change during the life of the object, and comments say that the size is stored separately "for convenience and for the" strong "cases where the implementation calculates the size each time.

My first reaction was "WT *? Should it always be trivial to retrieve the size of std::vector ?"

Now I carefully read 23.2.4 of the C ++ standard and don’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 so that its current size requires nontrivial calculations.

Is such an implementation such that std::vector::size() requires some nontrivial actions? When does such an implementation make sense?

Answer 1

I would suggest that your definition of "trivial" does not match your definition of the author of the code.

If size not saved, I would expect begin and end be saved, and size as the difference between the two, and this code will be embedded. Thus, we mainly talk with two (nearby) images of memory access and subtraction instead of a single memory access.

For most practical purposes, both of these are trivial, and if the author of the standard library believes that the result of this calculation should not be cached, then personally I gladly accept their opinion. But the author of this code comment might think differently.

The IIRC standard says somewhere that size "must be" O (1), not sure if it is in the text for sequences or for containers. I do not think that he does not indicate anywhere that this should be for vector . But even if we read that as an integral requirement, a fundamental QOI problem arises here - what do I do when I optimize my code for such a poor implementation through regular implementations?

If someone uses such an implementation, apparently because they want their code to run slowly. Who am I to judge otherwise ?; -)

It is also possible that the author of the code has profiled using a number of end-begin implementations and measured significant improvement by caching size. But I think it is less likely that the author is too pessimistic in the worst case scenario that their code should handle.

Answer 2

C ++ 03 says in table 65, found in §23.1, that size() must be of constant complexity. (In C ++ 0x, this is necessary for all containers.) It would be difficult for you to find std::vector<> where it is not.

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