Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What does .size() for a vector in C++ actually do?

Tags:

c++

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()?

like image 540
DJM123 Avatar asked May 20 '17 14:05

DJM123


2 Answers

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.

like image 175
Angew is no longer proud of SO Avatar answered Sep 29 '22 08:09

Angew is no longer proud of SO


The implementation of std::vector::size is implementation dependant even if it's required to have a complexity in O(1).

like image 37
nefas Avatar answered Sep 29 '22 07:09

nefas