How does the vector::size() returns size of the vector in constant time?

  • A+
Category:Languages

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 push_back or 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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: