In other words, does .size() count each element of a vector object whenever it's called and return this value, or does the vector object have a (size_t?) member that holds the number of elements currently in the vector, and the value of this member gets returned by .size()?
What exactly a call to std::vector::size
does depends on the particular implementation of the standard library. However, the standard places several constraints on what it can and cannot do. In particular, it requires a call to size
to execute in constant time, which means it cannot count the elements (that would be linear in the container size, not constant).
A vector's implementation needs one pointer to point to the beginning of the vector, and then other two pieces of information: how large the vector's data currently is (how many elements in the vector), and how large the vector's capacity currently is (how large is the allocated data buffer). The latter two can be implemented either as pointers, or as offsets from the beginning
pointer. Either representation can be used to obtain the size of data in constant time: either return the offset directly, or compute it as end - beginning
.
You can verify the complexity requirement in the standard itself, or in suitable reference documentation.
The implementation of std::vector::size
is implementation dependant even if it's required to have a complexity in O(1)
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With