Menu
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
737
All pointer types are also valid random-access iterators. It is to be noted that containers like vector, deque support random-access iterators.
Vector is implemented as a dynamically allocated array. The memory for this array is allocated in the constructor. As more elements are inserted the array is dynamically increased in size. A constructor without parameter creates an array with a default size.
A Random Access Iterator is an iterator that provides both increment and decrement (just like a Bidirectional Iterator), and that also provides constant-time methods for moving forward and backward in arbitrary-sized steps.
std::vector is a collection class in the Standard Template Library. Putting objects into a vector , taking them out, or the vector performing a resize when an item is added to a full vector all require that the class of the object support an assignment operator, a copy constructor, and move semantics.
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.
178
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.
25
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.
29
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
