Take the 2-minute tour ×

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

share|improve this question
"pointers... ha ha ha" -> xkcd.com/138 –  Billy ONeal Nov 11 '09 at 20:32
add comment

4 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
+1, very clever –  Chris Thompson Nov 11 '09 at 18:58
+1 (+2 for giving multiple pointers, but -1 for uninitialized pointers :) –  Oren S Nov 11 '09 at 19:18
add comment

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.

share|improve this answer
add comment

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?

share|improve this answer
While you want to increase the size by a constant factor, you normally want to use a factor smaller than two. As Andrew Koenig demonstrated quite some time ago, you normally want a factor smaller than 1+sqrt(5)/2 -- this leads to better memory reuse over time. –  Jerry Coffin Nov 11 '09 at 20:08
note that 1+sqrt(5)/2 is larger than 2... –  Greg Rogers Nov 11 '09 at 20:38
Although (1+sqrt(5))/2 isn't. So I'm prepared to believe that the claim is not complete rubbish, merely contains a typo... –  Steve Jessop Nov 12 '09 at 3:52
That's the golden ratio btw –  Steven Dec 9 '09 at 23:51
add comment

Your Answer


