I was going through this C++ Reference and found that using vector::size() returns the size of the vector in constant time. But, I wonder how one could get the size without actually traversing the vector.
It merely keeps track of the number of elements.
If that changes then that number is updated. For example, the number of elements increases by 1 when
emplace_back is called. This is one of a number of reasons why
std::vector is not intrinsically thread-safe.
As you can imagine, this makes the implementation of
std::vector quite fiddly - the same can be said for other C++ standard library containers too - which is a good reason for not attempting to write container classes yourself.