Printable View
Are vectors (the dynamic array, not the mathematical kind :) ) similar to linked lists, in the aspect that they hold the next node in the list, and that they have an internal node class, or how else do they work? Anyway, thanks for any explanation :D .
vector is not node based. It is array based. a vector is a dynamic array.
No, they are not similar to linked lists in that aspect. I assume you are referring to the vector class in the STL, which is basically an array (as Stoned_Coder said). If you already know how an array works, then the rest of the answer won't matter much.Quote:
Originally posted by Lurker
Are vectors similar to linked lists, in the aspect that they hold the next node in the list, and that they have an internal node class
An array does not have an internal node, instead, it has space allocated for as many objects (or maybe more) as it currently contains. This memory is in one contiguous block (at least logically). Therefore, there is no need to have a next pointer, since you know the size of each "node" and you can just move that distance from the current object to find the next one.Quote:
Originally posted by Lurker
or how else do they work?
That is why arrays (and consequently vectors) provide fast access to any random index. If you have an array of 243 objects which are 16 bytes each, and you want to access the one at index 156, then simply go to the memory location 2496 bytes (156*16) after the first object in the array. With a list, the objects could be anywhere in memory, so you have to traverse each node looking at the next pointer to see where the next node is. You'd have to do that 156 times.
One negative for arrays (and of course vectors) compared to lists is that it is ineffiicent to insert into the middle. If you insert an object into spot 156 in the middle of your array of 243 objects, then you have to copy the data for each object after spot 156 and move it over 16 bytes in memory. This is because arrays must always have contiguous memory, so object 157 must be immediately after 156 in memory. In a list, you just put the object wherever you want and then set the next pointer for object 155 to it, then put the next pointer for the new object to the one that used to be at spot 156 - much more efficient.
Those are just a couple examples of how the differences in the way the two container types work affect their use. Of course there are many other container types that have other positives and negatives.