How stl vector gives random access

Question

Hello Gurus,

Yesterday evening I was using std::vector for my work, and this question popped into my mind: how does vector gives random access?

I tried to look into code but was unsuccessful. Can anyone give some pointers?

Thanks, Arun

Answer 1

Sure, here are some pointers:

int *x, *y;

But seriously, a vector is internally just implemented as an array. It provides an overloaded indexing operator ([]) to allow you to access it like an array.

Answer 2

Vector uses contiguous memory underneath, so it gives random access the same way as an array essentially: it knows the starting address and the size of elements and does some pointer math.

Answer 3

Vector generally uses a dynamic array implementation[*]...at all times the data is stored in a continuous block of memory, so that pointer arithmetic can be used for O(1) access to any (already existing) element.

The trick to efficient dynamic arrays (assuming that you don't already know it), is to always increase the size of the reserved store by at least a constant factor (see Jerry Coffin comment). The result of this is that as we add an indefinite number of new elements, taking the factor as 2 for simplicity the first element is copied on the nth add, and the (2*n) add and the (4*n)th add and the ...

This series converges, so we can guarantee that adding N new elements requires O(N) time. However, any given add may require a reallocation and a copy of all the existing elements, so there is no latency guarantee what-so-ever.

[*] I don't know of another mechanism that will achieve the required performance. Anyone?

Answer 4

at least a factor of two

Actually, many implementations use a factor of 1.5 The important thing is that it's a factor, so you get exponential vector growth.